Implementing a dynamically sized array

Let’s say we want an array but we don’t know at compile time how many elements it will hold. We also want to be able to add more items, even when the underlying array is already full. In C++ and Rust, this is provided by std::vector, in Go by slices, and in scripting languages by Python lists and Ruby/JavaScript arrays.

For our simple use case, we don’t care about Go’s slicing behaviour (multiple mutable “views” of the same backing array).

We also don’t need it to be generic w.r.t. the type of the elements. Go, C++, etc. allow creating vectors of any element type as long as the type is known at compile time. We’re just going to stick to a single element type: int.

Here is an implementation in Go:

package main

import (
    "bytes"
    "fmt"
    "log"
    "slices"
)

type Vector struct {
    array []int
    cap   int
    size  int
}

func NewVector() *Vector {
    log.Println("initial capacity:", 4)
    return &Vector{array: make([]int, 4), cap: 4, size: 0}
}

func (v *Vector) grow() {
    log.Println("increasing capacity to:", v.cap*2)
    new := make([]int, v.cap*2)
    copy(new, v.array)
    v.array = new
    v.cap *= 2
}

func (v *Vector) Append(i int) {
    if v.size == v.cap {
        v.grow()
    }
    v.array[v.size] = i
    v.size++
}

func (v *Vector) Slice() []int {
    return v.array[:]
}

func (v *Vector) String() string {
    var buf bytes.Buffer
    fmt.Fprint(&buf, "[")
    for i, n := range v.array[:v.size] {
        if i > 0 {
            fmt.Fprint(&buf, ", ")
        }
        fmt.Fprintf(&buf, "%d", n)
    }
    fmt.Fprint(&buf, "]")
    return buf.String()
}

func main() {
    log.SetFlags(0)
    log.SetPrefix("debug: ")

    v := NewVector()
    for i := range 11 {
        v.Append(i * i)
    }
    fmt.Printf("max(%s) = %d\n", v, slices.Max(v.Slice()))
}

Running this program with go run main.go produces the following output:

debug: initial capacity: 4
debug: increasing capacity to: 8
debug: increasing capacity to: 16
max([0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100]) = 100