std.container

В этом модуле определены обобщенные контейнеры.

Создание

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

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

Семантика ссылок

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

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));

Подмодули

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

• Модуль 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` 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.comparison : 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]));

Примитивы контейнера

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

Источник

std/container/package.d

Лицензия:

Распространяется по лицензии Boost Software License, версия 1.0. (См. прилагаемый файл LICENSE_1_0.txt или копию по адресу boost.org/LICENSE_1_0.txt).

Авторы:

Steven Schveighoffer, Andrei Alexandrescu