std.container

Construction: To implement the different containers both struct and class based approaches have been used. std.container.util.make allows for uniform construction with either approach.

import std.container;
// Construct a red-black tree and an array both containing the values 1, 2, 3.
// RedBlackTree should typically be allocated using `new`
RedBlackTree!int rbTree = new RedBlackTree!int(1, 2, 3);
// But `new` should not be used with Array
Array!int array = Array!int(1, 2, 3);
// `make` hides the differences
RedBlackTree!int rbTree2 = make!(RedBlackTree!int)(1, 2, 3);
Array!int array2 = make!(Array!int)(1, 2, 3);

import std.container;
auto rbTree = make!RedBlackTree(1, 2, 3); // RedBlackTree!int
auto array = make!Array("1", "2", "3"); // Array!string

Reference semantics: All containers have reference semantics, which means that after assignment both variables refer to the same underlying data.

import std.container, std.range;
Array!int originalArray = make!(Array!int)(1, 2, 3);
Array!int secondArray = originalArray;
assert(equal(originalArray[], secondArray[]));

// changing one instance changes the other one as well!
originalArray[0] = 12;
assert(secondArray[0] == 12);

// secondArray now refers to an independent copy of originalArray
secondArray = originalArray.dup;
secondArray[0] = 1;
// assert that originalArray has not been affected
assert(originalArray[0] == 12);

import std.container;

RedBlackTree!int rbTree;
rbTree.insert(5); // null pointer dereference

import std.container;

// create an uninitialized array
Array!int array1;
// array2 does _not_ refer to array1
Array!int array2 = array1;
array2.insertBack(42);
// thus array1 will not be affected
assert(array1.empty);

// after initialization reference semantics work as expected
array1 = array2;
// now affects array2 as well
array1.removeBack();
assert(array2.empty);

import std.container, std.range;

auto arrOfArrs = make!Array(generate!(() => make!(Array!int)).take(10));

Submodules: This module consists of the following submodules:

• The std.container.array module provides an array type with deterministic control of memory, not reliant on the GC unlike built-in arrays.
• The std.container.binaryheap module provides a binary heap implementation that can be applied to any user-provided random-access range.
• The std.container.dlist module provides a doubly-linked list implementation.
• The std.container.rbtree module implements red-black trees.
• The std.container.slist module implements singly-linked lists.
• The std.container.util module contains some generic tools commonly used by container implementations.

The primary range of a container: While some containers offer direct access to their elements e.g. via opIndex, c.front or c.back, access and modification of a container's contents is generally done through its primary range type, which is aliased as C.Range. For example, the primary range type of Array!int is Array!int.Range.

import std.algorithm : equal, find;
import std.container;
import std.range : take;

auto array = make!Array(1, 2, 3);

// `find` returns an Array!int.Range advanced to the element "2"
array.linearRemove(array[].find(2));

assert(array[].equal([1]));

array = make!Array(1, 2, 3);

// the range given to `linearRemove` is a Take!(Array!int.Range)
// spanning just the element "2"
array.linearRemove(array[].find(2).take(1));

assert(array[].equal([1, 3]));

import std.algorithm : equal;
import std.container;
import std.range : iota;

auto array = make!Array(1, 2);

// the range type returned by `iota` is completely unrelated to Array,
// which is fine for Array.insertBack:
array.insertBack(iota(3, 10));

assert(array[].equal([1, 2, 3, 4, 5, 6, 7, 8, 9]));

Container primitives: Containers do not form a class hierarchy, instead they implement a common set of primitives (see table below). These primitives each guarantee a specific worst case complexity and thus allow generic code to be written independently of the container implementation.

Source: std/container/package.d