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
std/container.d License:
Boost License 1.0. Authors:
Steven Schveighoffer, Andrei Alexandrescu
構文 | Ο(·) | 説明 |
---|---|---|
C(x) | lx | 型 C のコンテナを別のコンテナまたはレンジから作る |
c.dup | lc | コンテナの複製を返す |
c ~ x | lc + lx | c と x の連結を返す。x は単一要素でも、入力レンジでもよい |
x ~ c | lc + lx | x と c の連結を返す。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 で初期化されます。このルーチンは、front が ref を返すならば定義する必要はありません。 |
c.front = v | log lc | コンテナの先頭要素に v を代入する |
c.back | log lc | コンテナ定義の順序で、末尾の要素を返す |
c.moveBack | log lc | 破壊的に末尾の要素を読み取り、返します。 要素の配置されていたスロット自体はコンテナからは取り除かれず、 T.init で初期化されます。このルーチンは、front が ref を返すならば定義する必要はありません。 |
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 | x を c に追加する。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 | v を c の先頭に挿入 |
c.stableInsertFront(v) | log lc | c.insertFront(v) と同様だが、既存のレンジを無効化しないことを保証する |
c.insertBack(v) | log lc | v を c の末尾に挿入 |
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 | レンジ r を c から取り除く |
c.stableRemove(r) | l r * log lc | c.remove(r) と同様だが、既存のレンジを無効化しないことを保証する |
c.linearRemove(r) | l c | レンジ r を c から取り除く |
c.stableLinearRemove(r) | l c | c.linearRemove(r) と同様だが、既存のレンジを無効化しないことを保証する |
c.removeKey(k) | log l c | c の中の、キー k に指されている要素を取り除く |
- コンテナを初期化して返します。 この関数の用途は、class 型のコンテナと struct 型のコンテナでの初期化方式の違いを吸収することです。
- 簡潔で高速な単方向リンクリストの実装です。
- ノード数を受け取るコンストラクタ
- 入力レンジを受け取るコンストラクタ
- 等値性の比較
Complexity:
Ο(min(n, n1)) n1 は rhs の要素数 - コンテナの基本レンジ型の定義です。前進レンジとなっています。
- 前進レンジの基本操作
- コンテナが要素を持たないときに限り true
となるプロパティ
Complexity:
Ο(1) - コンテナの複製を返します。 要素が推移的に複製されることはありません。
Complexity:
Ο(n). - 先頭から順に全要素をたどるレンジを返します。
Complexity:
Ο(1) - opSlice().front へ転送
Complexity:
Ο(1) - opSlice().front(value) へ転送
Complexity:
Ο(1) - 新しい SList を、this と引数の結合で作ります。opBinaryRight は、Stuff が opBinary を定義していないときのみ定義されます。
- SList から全要素を取り除きます。
Postcondition:
empty Complexity:
Ο(1) - stuff をコンテナの先頭に挿入します。stuff
には要素型 T に変換可能な値、あるいはそのレンジを指定できます。stable版では、
挙動は同じですが、さらにこのコンテナを指すレンジが無効化されないことが保証されます。
Returns:
挿入された要素数 Complexity:
Ο(log(n)) - コンテナの先頭から値を一つ拾い、
それをコンテナから取り除いてから返します。
Precondition:
!empty Returns:
取り除かれた要素 Complexity:
Ο(1). - コンテナの先頭要素を取り除きます。
stable版では、 挙動は同じですが、
さらにこのコンテナを指すレンジが無効化されないことが保証されます。
Precondition:
!empty Complexity:
Ο(1). - howMany 個の要素をコンテナの先頭から取り除きます。
上記のパラメタ無しのバージョンと違い、
この関数は howMany 個のremoveを行えなくても例外は投げません。
代わりに、howMany > n であれば、全要素が削除されます。
返値は実際に取り除かれた要素数。
stable版では、 挙動は同じですが、
さらにこのコンテナを指すレンジが無効化されないことが保証されます。
Returns:
取り除かれた要素数 Complexity:
Ο(howMany * log(n)). - stuff をレンジ r の後ろに挿入します。
r はこのコンテナから取り出したレンジでなければなりません。
SListのレンジは全てリスト末尾を指して終わっているという事実を使って、
この関数は、実質的にはリスト末尾への追記を行います。r は、
リスト末尾への潜在的に高速な可能性のあるアクセス手段として使用されます。(理想的には、r
はリストの末尾か末尾近くを指しています。)
stuff
には要素型 T に変換可能な値、あるいはそのレンジを指定できます。
stable版では、
挙動は同じですが、さらにこのコンテナを指すレンジが無効化されないことが保証されます。
Returns:
挿入された要素数 Complexity:
Ο(k + m)。 k は r の要素数、 m は stuff の長さ - insertAfter と似ていますが、
個数制限のついたレンジを受け取ります。これは、リストの途中への高速な挿入を保証するのに重要です。
r の先頭の指す位置への高速挿入を保証するには
insertAfter(take(r, 1), stuff) を使います。
この計算量は stuff の要素数だけに依存します。
Precondition:
r.original.empty || r.maxLength > 0 Returns:
挿入された要素数 Complexity:
Ο(k + m)。 k は r の要素数、 m は stuff の長さ - レンジをリストから線形時間で取り除きます。
Returns:
空レンジ Complexity:
Ο(n) - リストから Take!Range を線形時間で取り除きます。
Returns:
削除されたレンジの後ろを表すレンジ Complexity:
Ο(n)
- メモリ制御を deterministicにした配列型です。配列のために割り当てられたメモリは、
不要になると直ちに解放されます。
ガベージコレクションに頼ることはありません。Array は malloc と free
で独自のメモリ管理を行います。
- 等値性の比較
- コンテナの基本レンジ。ランダムアクセスレンジです。
- コンテナに要素がないときのみ true となるプロパティ
Complexity:
Ο(1) - コンテナの複製を返します。 要素が推移的に複製されることはありません。
Complexity:
Ο(n). - コンテナの要素数を返します。
Complexity:
Ο(1). - (a) メモリ再割り当て (b) 挿入に伴うイテレータの無効化、
のどちらもなしに拡大できる最大の要素数を返します。
Complexity:
Ο(1) - elements 要素の格納が確実に可能なようにメモリ領域を割り当てます。
Postcondition:
capacity >= e Complexity:
Ο(1) - 先頭から順に全要素をたどるレンジを返します。
Complexity:
Ο(1) - コンテナを
a から b まで(b を含まず)列挙するレンジを返します。
Precondition:
a <= b && b <= length Complexity:
Ο(1) - @@@BUG@@@ まだ動作しません
- opSlice().front と opSlice().back へ転送されます
Precondition:
!empty Complexity:
Ο(1) - 指定位置の要素を取得したり変更したりする演算子です
Precondition:
i < length Complexity:
Ο(1) - 新しいコンテナを this と引数の結合で作ります。
opBinaryRight は、Stuff が
opBinary を定義していないときのみ定義されます。
Complexity:
Ο(n + m), m は stuff の要素数 - insertBack(stuff) へ転送
- コンテナの全要素を削除します。capacity をどうするかはコンテナが決定します。
Postcondition:
empty Complexity:
Ο(n) - コンテナの要素数を newSize に変更します。newSize が length より大きければ、
追加要素はコンテナ中の未規定の場所に追加され T.init で初期化されます。
Complexity:
Ο(abs(n - newLength)) Postcondition:
length == newLength - コンテナ中の未規定の位置から要素を一つ取り除き、それを返します。
実装はコンテナにとってもっとも利点の大きい位置から要素を取り除くべきですが、
その正確な挙動はドキュメント化する必要があります。
stable版では、 挙動は同じですが、
さらにこのコンテナを指すレンジが無効化されないことが保証されます。
Precondition:
!empty Returns:
取り除かれた要素 Complexity:
Ο(log(n)). - value をコンテナの先頭や末尾に挿入します。stuff
には要素型 T に変換可能な値、あるいはそのレンジを指定できます。
to T. stable版では、 挙動は同じですが、
さらにこのコンテナを指すレンジが無効化されないことが保証されます。
Returns:
挿入された要素数 Complexity:
Ο(m * log(n))。m は stuff の要素数 - コンテナの末尾から要素を取り除きます。
stable版では、 挙動は同じですが、
さらにこのコンテナを指すレンジが無効化されないことが保証されます。
Precondition:
!empty Complexity:
Ο(log(n)). - 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)。m は stuff の長さ - このコンテナから取り出したレンジ r
に属する全要素を削除します。
stable版では、 挙動は同じですが、
さらにこのコンテナを指すレンジが無効化されないことが保証されます。
Returns:
元々 r の後ろにあった要素全体をわたるレンジを返します。 Complexity:
Ο(n - m)。m は r の要素数。
- 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
はレンジのサイズ以上には成長しません。Store が insertBack できるコンテナならば、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 がレンジの時) 要素が、あるいは特に上限無く (もし Store が insertBack を持つコンテナの時)、ヒープを拡大するときに使用されます。 Ο(min(r.length, initialSize)) 回 less を評価します。
- 領域 s の所有を開始します。この後 s に対して外部から操作を加えるとヒープが正しく動作しなくなります。
- 既にヒープとして整列済みと仮定して、領域 s の所有を開始します。
- ヒープが空なら true を、そうでなければ false を返します。
- ヒープの複製を返します、内部領域が dup メソッドをサポートする時のみ使用可能です
- ヒープの長さを返します。
- ヒープの capacity を返します。内部領域がレンジのときはその長さで、 コンテナの時は、 そのcapacityを返します。
- ヒープの先頭のコピーを返します。 これは less に関する最大要素です。
- ヒープを、内部領域を切り離すことで空にします。
- value をヒープに挿入します。内部領域がレンジで length == capacity の時は例外を投げます。
- ヒープから最大要素を取り除きます。
- ヒープから最大要素を取り除き、そのコピーを返します。 要素はヒープの内部領域に残り続けます。 パフォーマンスを重視するばあい、コピーのコストが高いデータ型では removeFront の使用を考慮して下さい。
- 最大要素を value に置き換えます。
- ヒープにまだ余裕があれば value を内部領域に挿入し、 true を返します。余裕がなければ、less(value, front) ならば replaceFront(value) を呼び出し、これも true を返します。それ以外の場合、 ヒープを変更せずに false を返します。 個のメソッドは小さい方から k 個などの候補値の集合を求めたいときに有用です。
- BinaryHeap!Store オブジェクトを s と initialSize で初期化して作成する便利関数
- bool に特殊化された Array。
一要素に一ビットを割り当てることで値をパッキングして格納します。
- コンテナの基本レンジ
- レンジの基本操作
-
コンテナに要素がないときのみ true となるプロパティ
Complexity:
Ο(1) - コンテナの複製を返します。
要素が推移的に複製されることはありません。
Complexity:
Ο(n). - コンテナの要素数を返します。
Complexity:
Ο(log(n)). - (a) メモリ再割り当て (b) 挿入に伴うイテレータの無効化、
のどちらもなしに拡大できる最大の要素数を返します。
Complexity:
Ο(log(n)). - n 要素の格納が確実に可能なようにメモリ領域を割り当てます。
Postcondition:
capacity >= n Complexity:
Ο(log(e - capacity)) if e > capacity, otherwise Ο(1). - コンテナ定義の順で全要素をたどるレンジを返します。
コンテナは最も効率の良い順序を選択するべきです。
Complexity:
Ο(log(n)) - 指定された2点間を辿るレンジを返します。
Complexity:
Ο(log(n)) - opSlice().front と opSlice().back
と同じ意味になります。
Complexity:
Ο(log(n)) - 指定位置の要素を取得したり変更したりする演算子です
- 新しいコンテナを this
と引数の結合で作ります。
Complexity:
Ο(n + m)。m は stuff の要素数 - insertAfter(this[], stuff) へ転送
- コンテナの全要素を削除します。
capacity をどうするかはコンテナが決定します。
Postcondition:
empty Complexity:
Ο(n) - コンテナの要素数を newSize に変更します。 newSize が length より大きければ、
追加要素はコンテナに追加され
ElementType.init で初期化されます。
Complexity:
Ο(abs(n - newLength)) Postcondition:
length == newLength - stuff をコンテナに挿入します。stuff
には ElementType に変換可能な値か、
そのレンジを指定できます。
stable 版では、 挙動は同じですが、
さらにこのコンテナを指すレンジが無効化されないことが保証されます。
無効化されない保証が必要なコードでは stableInsert を使用して下さい。
Returns:
追加された要素数 Complexity:
Ο(m * log(n))。m は stuff の要素数 - insert(stuff) や stableInsert(stuff) と同等ですが、計算量の制約が線形に『緩められています。
- 値を一つコンテナから取り除き、
それを返します。
stable版では、 挙動は同じですが、
さらにこのコンテナを指すレンジが無効化されないことが保証されます。
Precondition:
!empty Returns:
取り除かれた要素 Complexity:
Ο(log(n)) - 値をコンテナに挿入します。stuffには
ElementType に変換可能な値か、
そのレンジを指定できます。
stable版では、挙動は同じですが、
さらにこのコンテナを指すレンジが無効化されないことが保証されます。
Returns:
挿入された要素数 Complexity:
Ο(log(n)) - コンテナの先頭や末尾から要素を取り除きます。
stable版では、挙動は同じですが、
さらにこのコンテナを指すレンジが無効化されないことが保証されます。
オプション引数 howMany は、
その個数の要素を削除するよう命令します。 howMany > n
の時は単に全要素が削除され、例外は投げられません。
Precondition:
!empty Complexity:
Ο(log(n)). - howMany 個の要素をコンテナの先頭や末尾から取り除きます。
上記のパラメタ無しのバージョンと違い、
この関数は howMany 個のremoveを行えなくても例外は投げません。
代わりに、howMany > n であれば、全要素が削除されます。
返値は実際に取り除かれた要素数。
stable版では、 挙動は同じですが、
さらにこのコンテナを指すレンジが無効化されないことが保証されます。
Returns:
削除された要素数 Complexity:
Ο(howMany * log(n)). - stuff をレンジ r の前、後、あるいは置き換えとして挿入します。
r にはこのコンテナから取り出したレンジのみを指定できます。
stuff は ElementType に変換可能な値、またはそのレンジを指定できます。
stable版では、 挙動は同じですが、
さらにこのコンテナを指すレンジが無効化されないことが保証されます。
Returns:
挿入された要素数 Complexity:
Ο(n + m)。m は stuff の長さ - r に属する全ての要素を取り除きます。
r には元々このコンテナから取られたレンジのみを指定できます。
stable版では、 挙動は同じですが、
さらにこのコンテナを指すレンジが無効化されないことが保証されます。
Returns:
元々 r の後ろにあった要素全体を指すレンジ Complexity:
Ο(n)
- 赤黒木 コンテナの実装です。
挿入、削除、探索、その他の関数は全て基本的に
Ο(lg(n)) の計算量となります。
"a < b" 以外の比較を行うには、
std.functional.binaryFun で使える演算子文字列を渡すか、
関数、デリゲートなど less(a, b) が bool
型の値となる関数オブジェクトを渡して下さい。
less は狭義の順序関係である必要があります。
つまり、任意の等しくない要素 a と b について less(a, b) == !less(b, a) である必要があります。
さらに less(a, a) は必ず false です。
allowDuplicates が true であれば、同じ値を複数回挿入すると、
複数個の要素として挿入されます。これが false の時は、
二回目以降の挿入は無視されます。重複を許す場合には、
新しい要素は同値な要素達のすぐ後ろに挿入されます。
- ツリーの要素型
- RedBlackTree のレンジ型
- レンジが空なら true
- レンジの先頭要素を返す
- レンジの末尾要素を返す
- 先頭要素をレンジから取る
complexity:
償却 Ο(1) - 末尾要素をレンジから取る
complexity:
償却 Ο(1) - isForwardRange を満たすためのトリビアルな実装
- コンテナが要素を持っているかチェックします。1つでも要素があれば true。
- コンテナの複製。
返すコンテナは元の要素の浅いコピーを保持します。
Complexity:
Ο(n) - コンテナの要素全体を含むレンジを取得します。
Complexity:
Ο(log(n)) - コンテナの先頭要素
Complexity:
Ο(log(n)) - コンテナの末尾要素
Complexity:
Ο(log(n)) - 要素がコンテナ内に存在するかのチェック
Complexity:
Ο(log(n)) - コンテナから全要素を削除
Complexity:
Ο(1) - コンテナに一つ要素を追加。
これによって既存のレンジが無効化されることはありません。
Complexity:
Ο(log(n)) - コンテナに、レンジとして与えた一連の要素を追加。
これによって既存のレンジが無効化されることはありません。
Complexity:
Ο(m * log(n)) - 要素を一つコンテナから取り除きその値を返します。
Complexity:
Ο(log(n)) - コンテナから先頭要素を除きます。
Complexity:
Ο(log(n)) - コンテナから末尾要素を除きます。
Complexity:
Ο(log(n)) - 指定されたレンジをコンテナから取り除きます。
除いたレンジの後ろの要素全体を指すレンジを返します。
Complexity:
Ο(m * log(n)) - > e な要素全体を含むレンジを返します。
Complexity:
Ο(log(n)) - < e な要素全体を含むレンジを返します。
Complexity:
Ο(log(n)) - == e
な要素全体を含むレンジを返します。
Complexity:
Ο(log(n)) - ツリーを表示します。 これはアスキーアートとして、インデントでノードの深さを表す形で整形します。 値の出力は行わず、ツリー構造とノードの色のみが表示されます。
- ツリーの整合性をチェックします。これは追加や削除のたびに呼び出されます。 この昨日は赤黒木の実装のデバッグ中にのみ有効化されるべきです。
- コンストラクタ。ツリーを初期化する要素や要素の配列を渡して下さい。
- コンストラクタ。ツリーを初期化するレンジを渡して下さい。