std.container.array

This module provides an Array type with deterministic memory usage not reliant on the GC, as an alternative to the built-in arrays.

This module is a submodule of std.container.

Source

std/container/array.d

License:

Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at boost.org/LICENSE_1_0.txt).

Authors:

Andrei Alexandrescu

Examples:

auto arr = Array!int(0, 2, 3);
writeln(arr[0]); // 0
writeln(arr.front); // 0
writeln(arr.back); // 3

// reserve space
arr.reserve(1000);
writeln(arr.length); // 3
assert(arr.capacity >= 1000);

// insertion
arr.insertBefore(arr[1..$], 1);
writeln(arr.front); // 0
writeln(arr.length); // 4

arr.insertBack(4);
writeln(arr.back); // 4
writeln(arr.length); // 5

// set elements
arr[1] *= 42;
writeln(arr[1]); // 42

Examples:

import std.algorithm.comparison : equal;
auto arr = Array!int(1, 2, 3);

// concat
auto b = Array!int(11, 12, 13);
arr ~= b;
writeln(arr.length); // 6

// slicing
assert(arr[1 .. 3].equal([2, 3]));

// remove
arr.linearRemove(arr[1 .. 3]);
assert(arr[0 .. 2].equal([1, 11]));

Examples:

Array!bool packs together values efficiently by allocating one bit per element

Array!bool arr;
arr.insert([true, true, false, true, false]);
writeln(arr.length); // 5

public import std.container.util;

struct Array(T) if (!is(Unqual!T == bool));

Array type with deterministic control of memory. The memory allocated for the array is reclaimed as soon as possible; there is no reliance on the garbage collector. Array uses malloc, realloc and free for managing its own memory.

This means that pointers to elements of an Array will become dangling as soon as the element is removed from the Array. On the other hand the memory allocated by an Array will be scanned by the GC and GC managed objects referenced from an Array will be kept alive.

Note

When using Array with range-based functions like those in std.algorithm, Array must be sliced to get a range (for example, use array[].map! instead of array.map!). The container itself is not a range.

this(U)(U[] values...)
Constraints: if (isImplicitlyConvertible!(U, T));

Constructor taking a number of items.

this(Range)(Range r)
Constraints: if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T) && !is(Range == T[]));

Constructor taking an input range

const bool opEquals(const Array rhs);

const bool opEquals(ref const Array rhs);

Comparison for equality.

alias Range = RangeT!Array;

alias ConstRange = RangeT!(const(Array));

alias ImmutableRange = RangeT!(immutable(Array));

Defines the array's primary range, which is a random-access range.

ConstRange is a variant with const elements. ImmutableRange is a variant with immutable elements.

@property Array dup();

Duplicates the array. The elements themselves are not transitively duplicated.

Complexity

Ο(length).

const @property bool empty();

Returns:

true if and only if the array has no elements.

Complexity

Ο(1)

const @property size_t length();

const size_t opDollar();

Returns:

The number of elements in the array.

Complexity

Ο(1).

@property size_t capacity();

Returns:

The maximum number of elements the array can store without reallocating memory and invalidating iterators upon insertion.

Complexity

Ο(1)

void reserve(size_t elements);

Ensures sufficient capacity to accommodate e elements. If e < capacity, this method does nothing.

Postcondition

capacity >= e

Note

If the capacity is increased, one should assume that all iterators to the elements are invalidated.

Complexity

at most Ο(length) if e > capacity, otherwise Ο(1).

Range opSlice();

Returns:

A range that iterates over elements of the array in forward order.

Complexity

Ο(1)

Range opSlice(size_t i, size_t j);

Returns:

A range that iterates over elements of the array from index i up to (excluding) index j.

Precondition

i <= j && j <= length

Complexity

Ο(1)

inout @property ref inout(T) front();

Returns:

The first element of the array.

Precondition

empty == false

Complexity

Ο(1)

inout @property ref inout(T) back();

Returns:

The last element of the array.

Precondition

empty == false

Complexity

Ο(1)

inout ref inout(T) opIndex(size_t i);

Returns:

The element or a reference to the element at the specified index.

Precondition

i < length

Complexity

Ο(1)

void opSliceAssign(T value);

void opSliceAssign(T value, size_t i, size_t j);

void opSliceUnary(string op)()
Constraints: if (op == "++" || op == "--");

void opSliceUnary(string op)(size_t i, size_t j)
Constraints: if (op == "++" || op == "--");

void opSliceOpAssign(string op)(T value);

void opSliceOpAssign(string op)(T value, size_t i, size_t j);

Slicing operators executing the specified operation on the entire slice.

Precondition

i < j && j < length

Complexity

Ο(slice.length)

Array opBinary(string op, Stuff)(Stuff stuff)
Constraints: if (op == "~");

Returns:

A new array which is a concatenation of this and its argument.

Complexity

Ο(length + m), where m is the number of elements in stuff.

void opOpAssign(string op, Stuff)(auto ref Stuff stuff)
Constraints: if (op == "~");

Forwards to insertBack.

void clear();

Removes all the elements from the array and releases allocated memory.

Postcondition

empty == true && capacity == 0

Complexity

Ο(length)

@property void length(size_t newLength);

Sets the number of elements in the array to newLength. If newLength is greater than length, the new elements are added to the end of the array and initialized with T.init.

Complexity

Guaranteed Ο(abs(length - newLength)) if capacity >= newLength. If capacity < newLength the worst case is Ο(newLength).

Postcondition

length == newLength

T removeAny();

alias stableRemoveAny = removeAny;

Removes the last element from the array and returns it. Both stable and non-stable versions behave the same and guarantee that ranges iterating over the array are never invalidated.

Precondition

empty == false

Returns:

The element removed.

Complexity

Ο(1).

Throws:

Exception if the array is empty.

size_t insertBack(Stuff)(Stuff stuff)
Constraints: if (isImplicitlyConvertible!(Stuff, T) || isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));

alias insert = insertBack;

Inserts the specified elements at the back of the array. stuff can be a value convertible to T or a range of objects convertible to T.

Returns:

The number of elements inserted.

Complexity

Ο(length + m) if reallocation takes place, otherwise Ο(m), where m is the number of elements in stuff.

void removeBack();

alias stableRemoveBack = removeBack;

Removes the value from the back of the array. Both stable and non-stable versions behave the same and guarantee that ranges iterating over the array are never invalidated.

Precondition

empty == false

Complexity

Ο(1).

Throws:

Exception if the array is empty.

size_t removeBack(size_t howMany);

alias stableRemoveBack = removeBack;

Removes howMany values from the back of the array. Unlike the unparameterized versions above, these functions do not throw if they could not remove howMany elements. Instead, if howMany > n, all elements are removed. The returned value is the effective number of elements removed. Both stable and non-stable versions behave the same and guarantee that ranges iterating over the array are never invalidated.

Returns:

The number of elements removed.

Complexity

Ο(howMany).

size_t insertBefore(Stuff)(Range r, Stuff stuff)
Constraints: if (isImplicitlyConvertible!(Stuff, T));

size_t insertBefore(Stuff)(Range r, Stuff stuff)
Constraints: if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));

alias stableInsertBefore = insertBefore;

size_t insertAfter(Stuff)(Range r, Stuff stuff);

size_t replace(Stuff)(Range r, Stuff stuff)
Constraints: if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));

size_t replace(Stuff)(Range r, Stuff stuff)
Constraints: if (isImplicitlyConvertible!(Stuff, T));

Inserts stuff before, after, or instead range r, which must be a valid range previously extracted from this array. stuff can be a value convertible to T or a range of objects convertible to T. Both stable and non-stable version behave the same and guarantee that ranges iterating over the array are never invalidated.

Returns:

The number of values inserted.

Complexity

Ο(length + m), where m is the length of stuff.

Throws:

Exception if r is not a range extracted from this array.

Range linearRemove(Range r);

Removes all elements belonging to r, which must be a range obtained originally from this array.

Returns:

A range spanning the remaining elements in the array that initially were right after r.

Complexity

Ο(length)

Throws:

Exception if r is not a valid range extracted from this array.

struct Array(T) if (is(Unqual!T == bool));

Array specialized for bool. Packs together values efficiently by allocating one bit per element.

struct Range;

Defines the array's primary range.

@property Range save();

@property bool empty();

@property T front();

@property void front(bool value);

T moveFront();

void popFront();

@property T back();

@property void back(bool value);

T moveBack();

void popBack();

T opIndex(size_t i);

void opIndexAssign(T value, size_t i);

T moveAt(size_t i);

const @property size_t length();

Range opSlice(size_t low, size_t high);

Range primitives

@property bool empty();

Property returning true if and only if the array has no elements.

Complexity

Ο(1)

@property Array dup();

Returns:

A duplicate of the array.

Complexity

Ο(length).

const @property size_t length();

Returns the number of elements in the array.

Complexity

Ο(1).

@property size_t capacity();

Returns:

The maximum number of elements the array can store without reallocating memory and invalidating iterators upon insertion.

Complexity

Ο(1).

void reserve(size_t e);

Ensures sufficient capacity to accommodate e elements. If e < capacity, this method does nothing.

Postcondition

capacity >= e

Note

If the capacity is increased, one should assume that all iterators to the elements are invalidated.

Complexity

at most Ο(length) if e > capacity, otherwise Ο(1).

Range opSlice();

Returns:

A range that iterates over all elements of the array in forward order.

Complexity

Ο(1)

Range opSlice(size_t a, size_t b);

Returns:

A range that iterates the array between two specified positions.

Complexity

Ο(1)

@property bool front();

@property void front(bool value);

Returns:

The first element of the array.

Precondition

empty == false

Complexity

Ο(1)

Throws:

Exception if the array is empty.

@property bool back();

@property void back(bool value);

Returns:

The last element of the array.

Precondition

empty == false

Complexity

Ο(1)

Throws:

Exception if the array is empty.

bool opIndex(size_t i);

void opIndexAssign(bool value, size_t i);

void opIndexOpAssign(string op)(bool value, size_t i);

T moveAt(size_t i);

Indexing operators yielding or modifyng the value at the specified index.

Precondition

i < length

Complexity

Ο(1)

Array!bool opBinary(string op, Stuff)(Stuff rhs)
Constraints: if (op == "~");

Returns:

A new array which is a concatenation of this and its argument.

Complexity

Ο(length + m), where m is the number of elements in stuff.

Array!bool opOpAssign(string op, Stuff)(Stuff stuff)
Constraints: if (op == "~");

Forwards to insertBack.

void clear();

Removes all the elements from the array and releases allocated memory.

Postcondition

empty == true && capacity == 0

Complexity

Ο(length)

@property void length(size_t newLength);

Sets the number of elements in the array to newLength. If newLength is greater than length, the new elements are added to the end of the array and initialized with false.

Complexity

Guaranteed Ο(abs(length - newLength)) if capacity >= newLength. If capacity < newLength the worst case is Ο(newLength).

Postcondition

length == newLength

T removeAny();

alias stableRemoveAny = removeAny;

Removes the last element from the array and returns it. Both stable and non-stable versions behave the same and guarantee that ranges iterating over the array are never invalidated.

Precondition

empty == false

Returns:

The element removed.

Complexity

Ο(1).

Throws:

Exception if the array is empty.

size_t insertBack(Stuff)(Stuff stuff)
Constraints: if (is(Stuff : bool));

size_t insertBack(Stuff)(Stuff stuff)
Constraints: if (isInputRange!Stuff && is(ElementType!Stuff : bool));

alias stableInsertBack = insertBack;

alias insert = insertBack;

alias stableInsert = insertBack;

alias linearInsert = insertBack;

alias stableLinearInsert = insertBack;

Inserts the specified elements at the back of the array. stuff can be a value convertible to bool or a range of objects convertible to bool.

Returns:

The number of elements inserted.

Complexity

Ο(length + m) if reallocation takes place, otherwise Ο(m), where m is the number of elements in stuff.

void removeBack();

alias stableRemoveBack = removeBack;

Removes the value from the back of the array. Both stable and non-stable versions behave the same and guarantee that ranges iterating over the array are never invalidated.

Precondition

empty == false

Complexity

Ο(1).

Throws:

Exception if the array is empty.

size_t removeBack(size_t howMany);

alias stableRemoveBack = removeBack;

Removes howMany values from the back of the array. Unlike the unparameterized versions above, these functions do not throw if they could not remove howMany elements. Instead, if howMany > n, all elements are removed. The returned value is the effective number of elements removed. Both stable and non-stable versions behave the same and guarantee that ranges iterating over the array are never invalidated.

Returns:

The number of elements removed.

Complexity

Ο(howMany).

size_t insertBefore(Stuff)(Range r, Stuff stuff);

alias stableInsertBefore = insertBefore;

size_t insertAfter(Stuff)(Range r, Stuff stuff);

alias stableInsertAfter = insertAfter;

size_t replace(Stuff)(Range r, Stuff stuff)
Constraints: if (is(Stuff : bool));

alias stableReplace = replace;

Inserts stuff before, after, or instead range r, which must be a valid range previously extracted from this array. stuff can be a value convertible to bool or a range of objects convertible to bool. Both stable and non-stable version behave the same and guarantee that ranges iterating over the array are never invalidated.

Returns:

The number of values inserted.

Complexity

Ο(length + m), where m is the length of stuff.

Range linearRemove(Range r);

Removes all elements belonging to r, which must be a range obtained originally from this array.

Returns:

A range spanning the remaining elements in the array that initially were right after r.

Complexity

Ο(length)