std.container

Построение: Для реализации различных контейнеров были использованы подходы как на основе структуры, так и класса. Использование std.container.util.make даёт единообразное построение с любым подходом.

import std.container;
// Строит красное-черное дерево и массив, каждый из которых содержит значения 1, 2, 3.
// RedBlackTree обычно должно распределять память, используя `new`
RedBlackTree!int rbTree = new RedBlackTree!int(1, 2, 3);
// Но `new` не должно использоваться с Array
Array!int array = Array!int(1, 2, 3);
// `make` скрывает различия
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

Ссылочная семантика: Все контейнеры имеют ссылочную семантику, и это означает, что после присвоения, две переменные ссылаются на одни и те же лежащие в основе данные.

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

// изменение одного экземпляра изменяет также другой!
originalArray[0] = 12;
assert(secondArray[0] == 12);

// secondArray теперь ссылается на независимую копию originalArray
secondArray = originalArray.dup;
secondArray[0] = 1;
// утверждается, что originalArray не был изменён
assert(originalArray[0] == 12);

import std.container;

RedBlackTree!int rbTree;
rbTree.insert(5); // Ошибка! Разыменование указателя на null.

import std.container;

// создание неинициализированного массива
Array!int array1;
// array2 НЕ ссылается на array1
Array!int array2 = array1;
array2.insertBack(42);
// таким образом, на array1 эффект не действует
assert(array1.empty);

// после инициализации ссылочная семантика работает как ожидалось
array1 = array2;
// теперь воздействие влияет также и на array2 
array1.removeBack();
assert(array2.empty);

import std.container, std.range;

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

Подмодули: Этот модуль состоит из следующих подмодулей:

• Модуль std.container.array предоставляет тип массива с детерминированным управлением памятью, не полагающимся на сборщик мусора, в отличие от встроенных массивов.
• Модуль std.container.binaryheap предоставляет реализацию двоичной кучи, которая может быть приложена к любому предоставленному пользователем диапазону с произвольным доступом.
• Модуль std.container.dlist предоставляет реализацию двусвязного списка.
• Модуль std.container.rbtree предоставляет реализацию красно-чёрных деревьев.
• Модуль std.container.slist предоставляет реализацию односвязного списка.
• Модуль std.container.util содержит несколько общих инструментов, обычно используемых реализациями контейнеров.

Первичный диапазон контейнера: В то время как некоторые контейнеры предлагают прямой доступ к своим элементам, например, с помощью opIndex, c.front или c.back, доступ к содержимому контейнера и его модификация, как правило, осуществляется через тип его первичного диапазона, который объявлен через псевдоним C.Range. Например, тип первичного диапазона Array!int – это Array!int.Range.

import std.algorithm.comparison : equal;
import std.algorithm.iteration : find;
import std.container;
import std.range : take;

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

// `find` возвращает Array!int.Range, продвинутый к элементу "2"
array.linearRemove(array[].find(2));

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

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

// диапазон, переданный в `linearRemove` – это Take!(Array!int.Range),
// перекрывающий именно элемент "2"
array.linearRemove(array[].find(2).take(1));

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

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

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

// тип диапазона, возвращаемый функцией `iota` не имеет никакого отношения к Array,
// но отлично подходит для Array.insertBack:
array.insertBack(iota(3, 10));

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

Примитивы контейнеров: Контейнеры не формируют иерархию классов, вместо этого они реализуют общий набор примитивов (смотрите таблицу внизу). Каждый из этих примитивов гарантирует специфическую сложность для самого неблагоприятного случая, и, таким образом, позволяет писать обобщённый код, независимый от реализации контейнера.

Исходный код: std/container/package.d