std.container

構築 さまざまなコンテナを実装するために、構造体ベースとクラスベースの両方のアプローチが使用されている。 std.container.util.makeどちらのアプローチでも 均一な構造を構築できる。

import std.container;
// 値1、2、3の両方を含むred-black treeと配列を構築する。
// 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
assert(originalArray[0] == 12);

import std.container;

RedBlackTree!int rbTree;
rbTree.insert(5); // ヌルポインタの非参照

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モジュールは、 メモリを決定論的に制御する配列型を提供し、 組み込み配列とは異なり、GCに依存しない。
• この 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`は要素"2"まで進んだArray!int.Rangeを返す
array.linearRemove(array[].find(2));

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

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

// `linearRemove`に与えられた範囲は、
// 要素"2"のみにまたがるTake!(Array!int.Range)である
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 sourceソース