Arrays in Cairo

Arrays in Cairo store their elements in Memory Segments. The array are stored in continuous memory cells.

There are two ways in which arrays can be defined:

1. For arbitrary length array (alloc)

A dynamic array is created using alloc . alloc returns the first element’s address. As an array is filled, the elements take up contiguous memory cells. The alloc() function creates a memory segment that expands as each new element is added to the array.

Arrays are iterated over using recursion.

%builtins output
from starkware.cairo.common.serialize import serialize_word
from starkware.cairo.common.alloc import alloc
func main{output_ptr : felt*}():
    let (x : felt*) = alloc()
    return ()
end

In the above program alloc() function allocate a block of memory to store the value. It gives you address that is free to store a value.

%builtins output
from starkware.cairo.common.serialize import serialize_word
from starkware.cairo.common.alloc import alloc
func main{output_ptr : felt*}():
    let (x : felt*) = alloc()
    assert[x]=4
    serialize_word(x[0])
    assert[x+1]=9
    assert[x+2]=2
    assert[x+3]=7
    return ()
end
    assert[x+1]=9
    assert[x+2]=2
    assert[x+3]=7
    return ()
end

alloc() returns the address of the first element, and then keep adding plus one to that address(x) to get the rest of the elements.

2. For Fixed-length array (new)

When the size of the array is known to us then we can instantiate using tuples. In the below example variable x is defined with the type of pointer. The variable x stores the address of the tuple.

new operator is used to allocate a fixed-size array using tuples.

%builtins output
from starkware.cairo.common.serialize import serialize_word
from starkware.cairo.common.alloc import alloc
func main():
    tempvar x : felt* = new (1, 2, 3, 4, 5)
    serialize_word(x[0]) #define the index number to fetch value
    
    return ()
end

Cairo Program to find sum of elements in a given array

%builtins output
from starkware.cairo.common.serialize import serialize_word
from starkware.cairo.common.alloc import alloc
func sum_of_array{output_ptr : felt*}(x:felt*,size)->(sum):
if size == 0:
    return(sum=0)
end
let (b)=sum_of_array(x=x+1,size=size-1)
    return(sum=[x]+b)
end
func main{output_ptr : felt*}():
    let (x : felt*) = alloc()
    assert[x]=9
    assert[x+1]=3
    assert[x+2]=1
    assert[x+3]=7
let(a)=sum_of_array(x,4)
    serialize_word(a)
    return()