D 2.0
About Japanese Translation

Last update Sun Dec 19 23:27:23 2010

std.container

Jump to: Array BinaryHeap Elem Range RedBlackTree SList __ctor acquire assume back capacity check clear conditionalInsert dup empty equalRange front heapify insert insertAfter insertBack insertBefore insertFront length linearInsert linearRemove lowerBound make moveAt moveBack moveFront opBinary opBinaryRight opDollar opEquals opIndex opIndexAssign opIndexOpAssign opOpAssign opSlice popBack popFront printTree remove removeAny removeBack removeFront replace replaceFront reserve save stableInsert stableInsertAfter stableInsertBack stableInsertBefore stableInsertFront stableLinearInsert stableLinearRemove stableRemoveAny stableRemoveBack stableRemoveFront stableReplace upperBound

総称コンテナを定義しています。

Source:
std/container.d

License:
Boost License 1.0.

Authors:
Steven Schveighoffer, Andrei Alexandrescu

コンテナのプリミティブ操作。 以下では、 C はコンテナ型、 c はコンテナ型の値、l は値 x の実際の長さ (x には単一の要素(この場合 l1)、コンテナ、 レンジのいずれかが入ります)を意味します。
構文 Ο(·) 説明
C(x) lx C のコンテナを別のコンテナまたはレンジから作る
c.dup lc コンテナの複製を返す
c ~ x lc + lx cx の連結を返す。x は単一要素でも、入力レンジでもよい
x ~ c lc + lx xc の連結を返す。x は単一要素でも、入力レンジでもよい
Iteration
c.Range コンテナに関連づけられた基本のレンジ型
c[] log lc コンテナ全体を、コンテナ定義の順序で走査するレンジを返す
c[a, b] log lc キー a から b までのコンテナの一部を取得
Capacity
c.empty 1 コンテナに要素がなければ true、あれば false を返す
c.length log lc コンテナの要素数を返す
c.length = n lc + n コンテナの要素数を強制的に n する。 結果的に要素数が増える場合、 追加の要素はコンテナ依存の方法で初期化される (通常は T.init になる)
c.capacity log lc 現在メモリの再割り当て無しでコンテナに格納できる要素の最大数
c.reserve(x) lc capacity を最低でも x にする。減らすことはしない
Access
c.front log lc コンテナ定義の順序で、先頭の要素を返す
c.moveFront log lc 破壊的に先頭の要素を読み取り、返します。 要素の配置されていたスロット自体はコンテナからは取り除かれず、 T.init で初期化されます。このルーチンは、frontref を返すならば定義する必要はありません。
c.front = v log lc コンテナの先頭要素に v を代入する
c.back log lc コンテナ定義の順序で、末尾の要素を返す
c.moveBack log lc 破壊的に末尾の要素を読み取り、返します。 要素の配置されていたスロット自体はコンテナからは取り除かれず、 T.init で初期化されます。このルーチンは、frontref を返すならば定義する必要はありません。
c.back = v log lc コンテナの末尾要素に v を代入する
c[x] log lc コンテナに、インデックスベースのアクセス手段を提供します。 インデックスの型がコンテナ毎に定義されます。複数のインデックス型を持つことも可能です (この場合インデックス操作関数はオーバーロードされることになります)
c.moveAt(x) log lc インデックス x の値を破壊的に読み取り、返します。 コンテナの元の位置は T.init に初期化されます。
c[x] = v log lc コンテナの指定されたインデックスに要素をセットします。
c[x] op= v log lc コンテナの指定されたインデックスに read-modify-write 操作を実行します。
Operations
e in c log lc e が c の中に見つかれば非ゼロを返す
c.lowerBound(v) log lc v より真に小さい要素全てからなるレンジを返す
c.upperBound(v) log lc v より真に大きい要素全てからなるレンジを返す
c.equalRange(v) log lc v と等しい要素全てからなるレンジを返す
Modifiers
c ~= x lc + lx xc に追加する。x は単一要素でも入力レンジでもよい
c.clear() lc c から全ての要素を取り除く
c.insert(x) lx + log lc x を、c 毎に定められた c 中の(場合によっては複数の)位置に挿入
c.stableInsert(x) lx + log lc c.insert(x) と同様だが、既存のレンジを無効化しないことを保証する
c.linearInsert(v) lc c.insert(v) と同様だが、計算量を線形まで許容する
c.stableLinearInsert(v) lc c.stableInsert(v) と同様だが、計算量を線形まで許容する
c.removeAny() log lc c の要素をどれか取り除いて返す
c.stableRemoveAny() log lc c.removeAny(v) と同様だが、既存のレンジを無効化しないことを保証する
c.insertFront(v) log lc vc の先頭に挿入
c.stableInsertFront(v) log lc c.insertFront(v) と同様だが、既存のレンジを無効化しないことを保証する
c.insertBack(v) log lc vc の末尾に挿入
c.stableInsertBack(v) log lc c.insertBack(v) と同様だが、既存のレンジを無効化しないことを保証する
c.removeFront() log lc c の先頭要素を取り除く
c.stableRemoveFront() log lc c.removeFront() と同様だが、既存のレンジを無効化しないことを保証する
c.removeBack() log lc c の末尾要素を取り除く
c.stableRemoveBack() log lc c.removeBack() と同様だが、既存のレンジを無効化しないことを保証する
c.remove(r) l r * log lc レンジ rc から取り除く
c.stableRemove(r) l r * log lc c.remove(r) と同様だが、既存のレンジを無効化しないことを保証する
c.linearRemove(r) l c レンジ rc から取り除く
c.stableLinearRemove(r) l c c.linearRemove(r) と同様だが、既存のレンジを無効化しないことを保証する
c.removeKey(k) log l c c の中の、キー k に指されている要素を取り除く

Container make(Container, T...)(T arguments);
Container make(Container, T...)(T arguments);
コンテナを初期化して返します。 この関数の用途は、class 型のコンテナと struct 型のコンテナでの初期化方式の違いを吸収することです。

struct SList(T);
簡潔で高速な単方向リンクリストの実装です。

template __ctor(U) if (isImplicitlyConvertible!(U,T))
ノード数を受け取るコンストラクタ

template __ctor(Stuff) if (isInputRange!(Stuff) && isImplicitlyConvertible!(ElementType!(Stuff),T) && !is(Stuff == T[]))
入力レンジを受け取るコンストラクタ

const bool opEquals(ref const SList rhs);
等値性の比較

Complexity:
Ο(min(n, n1)) n1rhs の要素数

struct Range;
コンテナの基本レンジ型の定義です。前進レンジとなっています。

const bool empty();
Range save();
T front();
void front(T value);
void popFront();
前進レンジの基本操作

const bool empty();
コンテナが要素を持たないときに限り true となるプロパティ

Complexity:
Ο(1)

SList dup();
コンテナの複製を返します。 要素が推移的に複製されることはありません。

Complexity:
Ο(n).

Range opSlice();
先頭から順に全要素をたどるレンジを返します。

Complexity:
Ο(1)

T front();
opSlice().front へ転送

Complexity:
Ο(1)

void front(T value);
opSlice().front(value) へ転送

Complexity:
Ο(1)

SList opBinary(string op,Stuff)(Stuff rhs) if (op == "~" && is(typeof(SList(rhs))));
新しい SList を、this と引数の結合で作ります。opBinaryRight は、StuffopBinary を定義していないときのみ定義されます。

void clear();
SList から全要素を取り除きます。

Postcondition:
empty

Complexity:
Ο(1)

size_t insertFront(Stuff)(Stuff stuff) if (isInputRange!(Stuff) && isImplicitlyConvertible!(ElementType!(Stuff),T));
template insertFront(Stuff) if (isImplicitlyConvertible!(Stuff,T))
alias insert;
alias stableInsert;
alias stableInsertFront;
stuff をコンテナの先頭に挿入します。stuff には要素型 T に変換可能な値、あるいはそのレンジを指定できます。stable版では、 挙動は同じですが、さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Returns:
挿入された要素数

Complexity:
Ο(log(n))

T removeAny();
alias stableRemoveAny;
コンテナの先頭から値を一つ拾い、 それをコンテナから取り除いてから返します。

Precondition:
!empty

Returns:
取り除かれた要素

Complexity:
Ο(1).

void removeFront();
alias stableRemoveFront;
コンテナの先頭要素を取り除きます。 stable版では、 挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Precondition:
!empty

Complexity:
Ο(1).

size_t removeFront(size_t howMany);
alias stableRemoveFront;
howMany 個の要素をコンテナの先頭から取り除きます。 上記のパラメタ無しのバージョンと違い、 この関数は howMany 個のremoveを行えなくても例外は投げません。 代わりに、howMany > n であれば、全要素が削除されます。 返値は実際に取り除かれた要素数。 stable版では、 挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Returns:
取り除かれた要素数

Complexity:
Ο(howMany * log(n)).

size_t insertAfter(Stuff)(Range r, Stuff stuff);
alias stableInsertAfter;
stuff をレンジ r の後ろに挿入します。 r はこのコンテナから取り出したレンジでなければなりません。 SListのレンジは全てリスト末尾を指して終わっているという事実を使って、 この関数は、実質的にはリスト末尾への追記を行います。r は、 リスト末尾への潜在的に高速な可能性のあるアクセス手段として使用されます。(理想的には、r はリストの末尾か末尾近くを指しています。)

stuff には要素型 T に変換可能な値、あるいはそのレンジを指定できます。 stable版では、 挙動は同じですが、さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Returns:
挿入された要素数

Complexity:
Ο(k + m)kr の要素数、 mstuff の長さ

size_t insertAfter(Stuff)(Take!(Range) r, Stuff stuff);
alias stableInsertAfter;
insertAfter と似ていますが、 個数制限のついたレンジを受け取ります。これは、リストの途中への高速な挿入を保証するのに重要です。 r の先頭の指す位置への高速挿入を保証するには insertAfter(take(r, 1), stuff) を使います。 この計算量は stuff の要素数だけに依存します。

Precondition:
r.original.empty || r.maxLength > 0

Returns:
挿入された要素数

Complexity:
Ο(k + m)kr の要素数、 mstuff の長さ

Range linearRemove(Range r);
レンジをリストから線形時間で取り除きます。

Returns:
空レンジ

Complexity:
Ο(n)

Range linearRemove(Take!(Range) r);
alias stableLinearRemove;
リストから Take!Range を線形時間で取り除きます。

Returns:
削除されたレンジの後ろを表すレンジ

Complexity:
Ο(n)

struct Array(T) if (!is(T : const(bool)));
メモリ制御を deterministicにした配列型です。配列のために割り当てられたメモリは、 不要になると直ちに解放されます。 ガベージコレクションに頼ることはありません。Arraymallocfree で独自のメモリ管理を行います。

const bool opEquals(ref const Array rhs);
等値性の比較

struct Range;
コンテナの基本レンジ。ランダムアクセスレンジです。

const bool empty();
コンテナに要素がないときのみ true となるプロパティ

Complexity:
Ο(1)

Array dup();
コンテナの複製を返します。 要素が推移的に複製されることはありません。

Complexity:
Ο(n).

const size_t length();
コンテナの要素数を返します。

Complexity:
Ο(1).

size_t capacity();
(a) メモリ再割り当て (b) 挿入に伴うイテレータの無効化、 のどちらもなしに拡大できる最大の要素数を返します。

Complexity:
Ο(1)

void reserve(size_t elements);
elements 要素の格納が確実に可能なようにメモリ領域を割り当てます。

Postcondition:
capacity >= e

Complexity:
Ο(1)

Range opSlice();
先頭から順に全要素をたどるレンジを返します。

Complexity:
Ο(1)

Range opSlice(size_t a, size_t b);
コンテナを a から b まで(b を含まず)列挙するレンジを返します。

Precondition:
a <= b && b <= length

Complexity:
Ο(1)

const size_t opDollar();
@@@BUG@@@ まだ動作しません

T front();
void front(T value);
T back();
void back(T value);
opSlice().frontopSlice().back へ転送されます

Precondition:
!empty

Complexity:
Ο(1)

T opIndex(size_t i);
void opIndexAssign(T value, size_t i);
template opIndexOpAssign(string op)
指定位置の要素を取得したり変更したりする演算子です

Precondition:
i < length

Complexity:
Ο(1)

Array opBinary(string op,Stuff)(Stuff stuff) if (op == "~");
新しいコンテナを this と引数の結合で作ります。 opBinaryRight は、StuffopBinary を定義していないときのみ定義されます。

Complexity:
Ο(n + m), m は stuff の要素数

void opOpAssign(string op,Stuff)(Stuff stuff) if (op == "~");
insertBack(stuff) へ転送

void clear();
コンテナの全要素を削除します。capacity をどうするかはコンテナが決定します。

Postcondition:
empty

Complexity:
Ο(n)

void length(size_t newLength);
コンテナの要素数を newSize に変更します。newSizelength より大きければ、 追加要素はコンテナ中の未規定の場所に追加され T.init で初期化されます。

Complexity:
Ο(abs(n - newLength))

Postcondition:
length == newLength

T removeAny();
alias stableRemoveAny;
コンテナ中の未規定の位置から要素を一つ取り除き、それを返します。 実装はコンテナにとってもっとも利点の大きい位置から要素を取り除くべきですが、 その正確な挙動はドキュメント化する必要があります。 stable版では、 挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Precondition:
!empty

Returns:
取り除かれた要素

Complexity:
Ο(log(n)).

size_t insertBack(Stuff)(Stuff stuff) if (isImplicitlyConvertible!(Stuff,T) || isInputRange!(Stuff) && isImplicitlyConvertible!(ElementType!(Stuff),T));
alias insert;
value をコンテナの先頭や末尾に挿入します。stuff には要素型 T に変換可能な値、あるいはそのレンジを指定できます。 to T. stable版では、 挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Returns:
挿入された要素数

Complexity:
Ο(m * log(n))mstuff の要素数

void removeBack();
alias stableRemoveBack;
コンテナの末尾から要素を取り除きます。 stable版では、 挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Precondition:
!empty

Complexity:
Ο(log(n)).

size_t removeBack(size_t howMany);
alias stableRemoveBack;
howMany 個の要素をコンテナの先頭から取り除きます。 上記のパラメタ無しのバージョンと違い、 この関数は howMany 個のremoveを行えなくても例外は投げません。 代わりに、howMany > n であれば、全要素が削除されます。 返値は実際に取り除かれた要素数。 stable版では、 挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Returns:
削除された要素数

Complexity:
Ο(howMany).

size_t insertBefore(Stuff)(Range r, Stuff stuff) if (isImplicitlyConvertible!(Stuff,T));
template insertBefore(Stuff) if (isInputRange!(Stuff) && isImplicitlyConvertible!(ElementType!(Stuff),T))
template insertAfter(Stuff)
template replace(Stuff) if (isInputRange!(Stuff) && isImplicitlyConvertible!(ElementType!(Stuff),T))
template replace(Stuff) if (isImplicitlyConvertible!(Stuff,T))
stuff をレンジ r の前に挿入します。 r はこのコンテナから取り出されたレンジでなければいけません。stuff には要素型 T に変換可能な値、あるいはそのレンジを指定できます。 stable版では、 挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Returns:
挿入された要素数

Complexity:
Ο(n + m)mstuff の長さ

Range linearRemove(Range r);
alias stableLinearRemove;
このコンテナから取り出したレンジ r に属する全要素を削除します。 stable版では、 挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Returns:
元々 r の後ろにあった要素全体をわたるレンジを返します。

Complexity:
Ο(n - m)mr の要素数。

struct BinaryHeap(Store,alias less = "a < b") if (isRandomAccessRange!(Store) || isRandomAccessRange!(typeof(Store.init[])));
binary heap コンテナを、 与えられたランダムアクセスレンジ (多くの場合は T[]) または、ランダムアクセスコンテナ (多くの場合は Array!T) の上に構築します。 BinaryHeap のドキュメントでは、元になるレンジやコンテナのことを、 内部領域 (store) と呼びます。

バイナリヒープは、 格納された要素の最大値 (front プロパティ) が Ο(1) 操作で読み取れ、その削除が (removeFront() によって) 高速に Ο(log n) でできるデータ構造です。

less がデフォルトの「小なり」演算子ならば、 BinaryHeap は、いわゆる max-heap となり、 最大値の取得に最適化されます。min-heap を作るには、BinaryHeap を述語 "a > b" によって初期化して下さい。

単純に BinaryHeap コンテナから要素を取り出すと、Store から降順で遅延評価的に値が取り出されます。BinaryHeap から完全に値を取り出し尽くすと、Store には昇順で要素が並びますが、やはり、 取り出される順序は降順です。yields elements in descending order.

もし Store がレンジならば、BinaryHeap はレンジのサイズ以上には成長しません。StoreinsertBack できるコンテナならば、BinaryHeap は内部でコンテナに要素を追加することでサイズを拡大します。

Example:
// 例は "Introduction to Algorithms" Cormen et al, p 146 から
int[] a = [ 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 ];
auto h = heapify(a);
// 最大要素
assert(h.front == 16);
// ヒープ性を満たす
assert(equal(a, [ 16, 14, 10, 9, 8, 7, 4, 3, 2, 1 ]));

this(Store s, size_t initialSize = size_t.max);
領域 s をヒープに変換します。もし initialSize が 指定されていれば、先頭 initialSize 要素のみがヒープ化し、 残りの r.length ( Store がレンジの時) 要素が、あるいは特に上限無く (もし StoreinsertBack を持つコンテナの時)、ヒープを拡大するときに使用されます。 Ο(min(r.length, initialSize))less を評価します。

void acquire(Store s, size_t initialSize = size_t.max);
領域 s の所有を開始します。この後 s に対して外部から操作を加えるとヒープが正しく動作しなくなります。

void assume(Store s, size_t initialSize = size_t.max);
既にヒープとして整列済みと仮定して、領域 s の所有を開始します。

bool empty();
ヒープが空なら true を、そうでなければ false を返します。

BinaryHeap dup();
ヒープの複製を返します、内部領域が dup メソッドをサポートする時のみ使用可能です

size_t length();
ヒープの長さを返します。

size_t capacity();
ヒープの capacity を返します。内部領域がレンジのときはその長さで、 コンテナの時は、 そのcapacityを返します。

ElementType!(Store) front();
ヒープの先頭のコピーを返します。 これは less に関する最大要素です。

void clear();
ヒープを、内部領域を切り離すことで空にします。

size_t insert(ElementType!(Store) value);
value をヒープに挿入します。内部領域がレンジで length == capacity の時は例外を投げます。

void removeFront();
ヒープから最大要素を取り除きます。

ElementType!(Store) removeAny();
ヒープから最大要素を取り除き、そのコピーを返します。 要素はヒープの内部領域に残り続けます。 パフォーマンスを重視するばあい、コピーのコストが高いデータ型では removeFront の使用を考慮して下さい。

void replaceFront(ElementType!(Store) value);
最大要素を value に置き換えます。

bool conditionalInsert(ElementType!(Store) value);
ヒープにまだ余裕があれば value を内部領域に挿入し、 true を返します。余裕がなければ、less(value, front) ならば replaceFront(value) を呼び出し、これも true を返します。それ以外の場合、 ヒープを変更せずに false を返します。 個のメソッドは小さい方から k 個などの候補値の集合を求めたいときに有用です。

BinaryHeap!(Store) heapify(Store)(Store s, size_t initialSize = size_t.max);
BinaryHeap!Store オブジェクトを sinitialSize で初期化して作成する便利関数

struct Array(T) if (is(T == bool));
bool に特殊化された Array。 一要素に一ビットを割り当てることで値をパッキングして格納します。

struct Range;
コンテナの基本レンジ

Range save();
bool empty();
T front();
void front(bool value);
T moveFront();
void popFront();
T back();
T moveBack();
void popBack();
T opIndex(size_t i);
void opIndexAssign(T value, size_t i);
T moveAt(size_t i);
const ulong length();
レンジの基本操作

bool empty();
コンテナに要素がないときのみ true となるプロパティ

Complexity:
Ο(1)

Array!(bool) dup();
コンテナの複製を返します。 要素が推移的に複製されることはありません。

Complexity:
Ο(n).

ulong length();
コンテナの要素数を返します。

Complexity:
Ο(log(n)).

ulong capacity();
(a) メモリ再割り当て (b) 挿入に伴うイテレータの無効化、 のどちらもなしに拡大できる最大の要素数を返します。

Complexity:
Ο(log(n)).

void reserve(ulong e);
n 要素の格納が確実に可能なようにメモリ領域を割り当てます。

Postcondition:
capacity >= n

Complexity:
Ο(log(e - capacity)) if e > capacity, otherwise Ο(1).

Range opSlice();
コンテナ定義の順で全要素をたどるレンジを返します。 コンテナは最も効率の良い順序を選択するべきです。

Complexity:
Ο(log(n))

Range opSlice(ulong a, ulong b);
指定された2点間を辿るレンジを返します。

Complexity:
Ο(log(n))

bool front();
void front(bool value);
bool back();
void back(bool value);
opSlice().frontopSlice().back と同じ意味になります。 Complexity:
Ο(log(n))

bool opIndex(ulong i);
void opIndexAssign(bool value, ulong i);
template opIndexOpAssign(string op)
T moveAt(ulong i);
指定位置の要素を取得したり変更したりする演算子です

Array!(bool) opBinary(string op,Stuff)(Stuff rhs) if (op == "~");
新しいコンテナを this と引数の結合で作ります。

Complexity:
Ο(n + m)。m は stuff の要素数

Array!(bool) opOpAssign(string op,Stuff)(Stuff stuff) if (op == "~");
insertAfter(this[], stuff) へ転送

void clear();
コンテナの全要素を削除します。 capacity をどうするかはコンテナが決定します。

Postcondition:
empty

Complexity:
Ο(n)

void length(ulong newLength);
コンテナの要素数を newSize に変更します。 newSizelength より大きければ、 追加要素はコンテナに追加され ElementType.init で初期化されます。

Complexity:
Ο(abs(n - newLength))

Postcondition:
length == newLength

alias insert;
alias stableInsert;
stuff をコンテナに挿入します。stuff には ElementType に変換可能な値か、 そのレンジを指定できます。

stable 版では、 挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。 無効化されない保証が必要なコードでは stableInsert を使用して下さい。

Returns:
追加された要素数

Complexity:
Ο(m * log(n))mstuff の要素数

alias linearInsert;
alias stableLinearInsert;
insert(stuff)stableInsert(stuff) と同等ですが、計算量の制約が線形に『緩められています。

T removeAny();
alias stableRemoveAny;
値を一つコンテナから取り除き、 それを返します。 stable版では、 挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Precondition:
!empty

Returns:
取り除かれた要素

Complexity:
Ο(log(n))

ulong insertBack(Stuff)(Stuff stuff) if (is(Stuff : bool));
template insertBack(Stuff) if (isInputRange!(Stuff) && is(ElementType!(Stuff) : bool))
alias stableInsertBack;
値をコンテナに挿入します。stuffには ElementType に変換可能な値か、 そのレンジを指定できます。 stable版では、挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Returns:
挿入された要素数

Complexity:
Ο(log(n))

void removeBack();
alias stableRemoveBack;
コンテナの先頭や末尾から要素を取り除きます。 stable版では、挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。 オプション引数 howMany は、 その個数の要素を削除するよう命令します。 howMany > n の時は単に全要素が削除され、例外は投げられません。

Precondition:
!empty

Complexity:
Ο(log(n)).

ulong removeBack(ulong howMany);
howMany 個の要素をコンテナの先頭や末尾から取り除きます。 上記のパラメタ無しのバージョンと違い、 この関数は howMany 個のremoveを行えなくても例外は投げません。 代わりに、howMany > n であれば、全要素が削除されます。 返値は実際に取り除かれた要素数。 stable版では、 挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Returns:
削除された要素数

Complexity:
Ο(howMany * log(n)).
ulong insertBefore(Stuff)(Range r, Stuff stuff);
alias stableInsertBefore;
template insertAfter(Stuff)
alias stableInsertAfter;
template replace(Stuff) if (is(Stuff : bool))
alias stableReplace;
stuff をレンジ r の前、後、あるいは置き換えとして挿入します。 r にはこのコンテナから取り出したレンジのみを指定できます。 stuffElementType に変換可能な値、またはそのレンジを指定できます。 stable版では、 挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Returns:
挿入された要素数

Complexity:
Ο(n + m)mstuff の長さ

Range linearRemove(Range r);
alias stableLinearRemove;
r に属する全ての要素を取り除きます。 r には元々このコンテナから取られたレンジのみを指定できます。 stable版では、 挙動は同じですが、 さらにこのコンテナを指すレンジが無効化されないことが保証されます。

Returns:
元々 r の後ろにあった要素全体を指すレンジ

Complexity:
Ο(n)

struct RedBlackTree(T,alias less = "a < b",bool allowDuplicates = false) if (is(typeof(less(T.init,T.init)) == bool) || is(typeof(less) == string));
赤黒木 コンテナの実装です。

挿入、削除、探索、その他の関数は全て基本的に Ο(lg(n)) の計算量となります。

"a < b" 以外の比較を行うには、 std.functional.binaryFun で使える演算子文字列を渡すか、 関数、デリゲートなど less(a, b)bool 型の値となる関数オブジェクトを渡して下さい。

less は狭義の順序関係である必要があります。 つまり、任意の等しくない要素 ab について less(a, b) == !less(b, a) である必要があります。 さらに less(a, a) は必ず false です。

allowDuplicatestrue であれば、同じ値を複数回挿入すると、 複数個の要素として挿入されます。これが false の時は、 二回目以降の挿入は無視されます。重複を許す場合には、 新しい要素は同値な要素達のすぐ後ろに挿入されます。

alias Elem;
ツリーの要素型

struct Range;
RedBlackTree のレンジ型

const bool empty();
レンジが空なら true

Elem front();
レンジの先頭要素を返す

Elem back();
レンジの末尾要素を返す

void popFront();
先頭要素をレンジから取る

complexity:
償却 Ο(1)

void popBack();
末尾要素をレンジから取る

complexity:
償却 Ο(1)

Range save();
isForwardRange を満たすためのトリビアルな実装

bool empty();
コンテナが要素を持っているかチェックします。1つでも要素があれば true

RedBlackTree dup();
コンテナの複製。 返すコンテナは元の要素の浅いコピーを保持します。

Complexity:
Ο(n)

Range opSlice();
コンテナの要素全体を含むレンジを取得します。

Complexity:
Ο(log(n))

Elem front();
コンテナの先頭要素

Complexity:
Ο(log(n))

Elem back();
コンテナの末尾要素

Complexity:
Ο(log(n))

bool opBinaryRight(string op)(Elem e) if (op == "in")
要素がコンテナ内に存在するかのチェック

Complexity:
Ο(log(n))

void clear();
コンテナから全要素を削除

Complexity:
Ο(1)

size_t stableInsert(Stuff)(Stuff stuff) if (isImplicitlyConvertible!(Stuff,Elem))
コンテナに一つ要素を追加。 これによって既存のレンジが無効化されることはありません。

Complexity:
Ο(log(n))

size_t stableInsert(Stuff)(Stuff stuff) if (isInputRange!(Stuff) && isImplicitlyConvertible!(ElementType!(Stuff),Elem))
alias insert;
コンテナに、レンジとして与えた一連の要素を追加。 これによって既存のレンジが無効化されることはありません。

Complexity:
Ο(m * log(n))

Elem removeAny();
要素を一つコンテナから取り除きその値を返します。

Complexity:
Ο(log(n))

void removeFront();
コンテナから先頭要素を除きます。

Complexity:
Ο(log(n))

void removeBack();
コンテナから末尾要素を除きます。

Complexity:
Ο(log(n))

Range remove(Range r);
指定されたレンジをコンテナから取り除きます。 除いたレンジの後ろの要素全体を指すレンジを返します。

Complexity:
Ο(m * log(n))

Range upperBound(Elem e);
> e な要素全体を含むレンジを返します。

Complexity:
Ο(log(n))

Range lowerBound(Elem e);
< e な要素全体を含むレンジを返します。

Complexity:
Ο(log(n))

Range equalRange(Elem e);
== e な要素全体を含むレンジを返します。

Complexity:
Ο(log(n))

void printTree(Node n, int indent = 0);
ツリーを表示します。 これはアスキーアートとして、インデントでノードの深さを表す形で整形します。 値の出力は行わず、ツリー構造とノードの色のみが表示されます。

void check();
ツリーの整合性をチェックします。これは追加や削除のたびに呼び出されます。 この昨日は赤黒木の実装のデバッグ中にのみ有効化されるべきです。

this(U)(U[] elems...) if (isImplicitlyConvertible!(U,Elem))
コンストラクタ。ツリーを初期化する要素や要素の配列を渡して下さい。

this(Stuff)(Stuff stuff) if (isInputRange!(Stuff) && isImplicitlyConvertible!(ElementType!(Stuff),Elem) && !is(Stuff == Elem[]))
コンストラクタ。ツリーを初期化するレンジを渡して下さい。