vector

Module

Defines several vector-like classes.

You can import these APIs from the collections package. For example:

from collections.vector import InlinedFixedVector

InlinedFixedVector

A dynamically-allocated vector with small-vector optimization and a fixed maximum capacity.

The InlinedFixedVector does not resize or implement bounds checks. It is initialized with both a small-vector size (specified at compile time) and a maximum capacity (specified at runtime).

The first size elements are stored in the statically-allocated small vector storage. Any remaining elements are stored in dynamically-allocated storage.

When it is deallocated, it frees its memory.

TODO: It should call its element destructors once we have traits.

This data structure is useful for applications where the number of required elements is not known at compile time, but once known at runtime, is guaranteed to be equal to or less than a certain capacity.

Parameters:

  • ​type (AnyRegType): The type of the elements.
  • ​size (Int): The statically-known small-vector size.

Aliases:

  • ​static_size = _69x23_size
  • ​static_data_type = StaticTuple[size, *"type"]

Fields:

  • ​static_data (StaticTuple[size, *"type"]): The underlying static storage, used for small vectors.
  • ​dynamic_data (Pointer[*"type", 0]): The underlying dynamic storage, used to grow large vectors.
  • ​current_size (Int): The number of elements in the vector.
  • ​capacity (Int): The maximum number of elements that can fit in the vector.

Implemented traits:

AnyType, Sized

Methods:

__init__

__init__(inout self: Self, capacity: Int)

Constructs InlinedFixedVector with the given capacity.

The dynamically allocated portion is capacity - size.

Args:

  • ​capacity (Int): The requested maximum capacity of the vector.

__copyinit__

__copyinit__(inout self: Self, existing: Self)

Creates a shallow copy (doesn’t copy the underlying elements).

Args:

  • ​existing (Self): The InlinedFixedVector to copy.

__getitem__

__getitem__(self: Self, i: Int) -> *"type"

Gets a vector element at the given index.

Args:

  • ​i (Int): The index of the element.

Returns:

The element at the given index.

__setitem__

__setitem__(inout self: Self, i: Int, *value: "type")

Sets a vector element at the given index.

Args:

  • ​i (Int): The index of the element.
  • ​value (*"type"): The value to assign.

deepcopy

deepcopy(self: Self) -> Self

Creates a deep copy of this vector.

Returns:

The created copy of this vector.

append

append(inout self: Self, *value: "type")

Appends a value to this vector.

Args:

  • ​value (*"type"): The value to append.

__len__

__len__(self: Self) -> Int

Gets the number of elements in the vector.

Returns:

The number of elements in the vector.

clear

clear(inout self: Self)

Clears the elements in the vector.

__iter__

__iter__(inout self: Self) -> _VecIter[*"type", InlinedFixedVector[*"type", size], _deref_iter_impl[*"type", size]]

Iterate over the vector.

Returns:

An iterator to the start of the vector.

DynamicVector

The DynamicVector type is a dynamically-allocated vector.

It supports pushing and popping from the back resizing the underlying storage as needed. When it is deallocated, it frees its memory.

Parameters:

  • ​T (CollectionElement): The type of the elements.

Fields:

  • ​data (AnyPointer[T]): The underlying storage for the vector.
  • ​size (Int): The number of elements in the vector.
  • ​capacity (Int): The amount of elements that can fit in the vector without resizing it.

Implemented traits:

AnyType, CollectionElement, Copyable, Movable, Sized

Methods:

__init__

__init__(inout self: Self)

Constructs an empty vector.

__init__(inout self: Self, capacity: Int)

Constructs a vector with the given capacity.

Args:

  • ​capacity (Int): The requested capacity of the vector.

__copyinit__

__copyinit__(inout self: Self, existing: Self)

Creates a deepcopy of the given vector.

Args:

  • ​existing (Self): The vector to copy.

__moveinit__

__moveinit__(inout self: Self, owned existing: Self)

Move data of an existing vector into a new one.

Args:

  • ​existing (Self): The existing vector.

__del__

__del__(owned self: Self)

Destroy all elements in the vector and free its memory.

__getitem__

__getitem__(self: Self, i: Int) -> T

Gets a copy of the vector element at the given index.

FIXME(lifetimes): This should return a reference, not a copy!

Args:

  • ​i (Int): The index of the element.

Returns:

A copy of the element at the given index.

__setitem__

__setitem__(inout self: Self, i: Int, owned value: T)

Sets a vector element at the given index.

Args:

  • ​i (Int): The index of the element.
  • ​value (T): The value to assign.

__len__

__len__(self: Self) -> Int

Gets the number of elements in the vector.

Returns:

The number of elements in the vector.

append

append(inout self: Self, owned value: T)

Appends a value to this vector.

Args:

  • ​value (T): The value to append.

push_back

push_back(inout self: Self, owned value: T)

Appends a value to this vector.

Args:

  • ​value (T): The value to append.

pop_back

pop_back(inout self: Self) -> T

Pops a value from the back of this vector.

Returns:

The popped value.

reserve

reserve(inout self: Self, new_capacity: Int)

Reserves the requested capacity.

If the current capacity is greater or equal, this is a no-op. Otherwise, the storage is reallocated and the date is moved.

Args:

  • ​new_capacity (Int): The new capacity.

resize

resize(inout self: Self, new_size: Int, value: T)

Resizes the vector to the given new size.

If the new size is smaller than the current one, elements at the end are discarded. If the new size is larger than the current one, the vector is appended with new values elements up to the requested size.

Args:

  • ​new_size (Int): The new size.
  • ​value (T): The value to use to populate new elements.

clear

clear(inout self: Self)

Clears the elements in the vector.

steal_data

steal_data(inout self: Self) -> AnyPointer[T]

Take ownership of the underlying pointer from the vector.

Returns:

The underlying data.

CollectionElement

A collection element is a value type that can be moved, copied, and default-constructed in a collection.

Implemented traits:

AnyType, Copyable, Movable

Methods:

__copyinit__

__copyinit__(inout self: T, existing: T, /)

Create a new instance of the value by copying an existing one.

Args:

  • ​existing (T): The value to copy.

__moveinit__

__moveinit__(inout self: T, owned existing: T, /)

Create a new instance of the value by moving the value of another.

Args:

  • ​existing (T): The value to move.

__del__

__del__(owned self: T, /)

Destroy the contained value.

The destructor receives an owned value and is expected to perform any actions needed to end the lifetime of the object. In the simplest case, this is nothing, and the language treats the object as being dead at the end of this function.