std.container.dlist

import std.algorithm.comparison : equal;
import std.container : DList;

auto s = DList!int(1, 2, 3);
assert(equal(s[], [1, 2, 3]));

s.removeFront();
assert(equal(s[], [2, 3]));
s.removeBack();
assert(equal(s[], [2]));

s.insertFront([4, 5]);
assert(equal(s[], [4, 5, 2]));
s.insertBack([6, 7]);
assert(equal(s[], [4, 5, 2, 6, 7]));

// 範囲操作を適用したい場合は、単純にスライスする。
import std.algorithm.searching : countUntil;
import std.range : popFrontN, popBackN, walkLength;

auto sl = DList!int([1, 2, 3, 4, 5]);
writeln(countUntil(sl[], 2)); // 1

auto r = sl[];
popFrontN(r, 2);
popBackN(r, 2);
assert(r.equal([3]));
writeln(walkLength(r)); // 1

// DList.Rangeは、spanリストから要素を削除するために使用できる
auto nl = DList!int([1, 2, 3, 4, 5]);
for (auto rn = nl[]; !rn.empty;)
    if (rn.front % 2 == 0)
        nl.popFirstOf(rn);
    else
        rn.popFront();
assert(equal(nl[], [1, 3, 5]));
auto rs = nl[];
rs.popFront();
nl.remove(rs);
assert(equal(nl[], [1]));

struct DList(T);

双方向リンクリストを実装する。

DList参照セマンティクスを使用する。

this(U)(U[] values...)
if (isImplicitlyConvertible!(U, T));

複数のノードを受け取るコンストラクタ

this(Stuff)(Stuff stuff)
if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T));

入力範囲を受け取るコンストラクタ

const bool opEquals()(const ref DList rhs)
if (is(typeof(front == front)));

等価性の比較。

複雑さ Ο(min(n, n1)) ここで、n1 は 要素の数である rhs。

struct Range;

コンテナの主たる範囲を定義し、双方向の範囲を体現する。

const nothrow @property bool empty();

コンテナに要素が含まれていない場合にのみ、true を返すプロパティ。

複雑性 Ο(1)

void clear();

DList からすべてのコンテンツを削除する。

事後条件empty

複雑性 Ο(1)

@property DList dup();

コンテナを複製する。要素自体は間接的に複製されない。

複雑度 Ο(n)。

Range opSlice();

コンテナのすべての要素を順に繰り返す範囲を返す。 順序は

複雑性 Ο(1)

inout @property ref inout(T) front();

次へ opSlice().front。

複雑性 Ο(1)

inout @property ref inout(T) back();

転送する opSlice().back。

Complexity Ο(1)

DList opBinary(string op, Stuff)(Stuff rhs)
if (op == "~" && is(typeof(insertBack(rhs))));

this と引数を連結した新しいDList を返す rhs。

DList opBinaryRight(string op, Stuff)(Stuff lhs)
if (op == "~" && is(typeof(insertFront(lhs))));

引数とDList を連結した新しい を返す lhs this を連結したものを返します。

DList opOpAssign(string op, Stuff)(Stuff rhs)
if (op == "~" && is(typeof(insertBack(rhs))));

引数の内容を rhsthis に追加する。

size_t insertFront(Stuff)(Stuff stuff);

size_t insertBack(Stuff)(Stuff stuff);

alias insert = insertBack;

alias stableInsert = insert;

alias stableInsertFront = insertFront;

alias stableInsertBack = insertBack;

コンテナの stuffコンテナの前方または後方に挿入する。 stuff値は、T に変換できる値、またはT に変換できるオブジェクトの範囲である。安定版も同様に動作するが、 コンテナを反復する範囲が決して無効にならないことを保証する。

Returns:

挿入される要素の数

複雑さ Ο(log(n))

size_t insertBefore(Stuff)(Range r, Stuff stuff);

alias stableInsertBefore = insertBefore;

size_t insertAfter(Stuff)(Range r, Stuff stuff);

alias stableInsertAfter = insertAfter;

stuff範囲の後ろに挿入する r、これは 事前にこのコンテナから抽出された空ではない範囲でなければならない。

stuffT に変換できる値、またはT に変換できるオブジェクトの範囲 である。安定版も同様に動作するが、 コンテナを反復処理する範囲が決して無効にならないことを保証する。

Returns:

挿入された値の数。

複雑さ Ο(k + m) ここで、k は要素の数でありr、m は長さである。 stuff。

T removeAny();

alias stableRemoveAny = removeAny;

コンテナ内の不特定の位置にある値を1つ選択し、 コンテナからそれを削除し、それを返す。安定版の動作も同じだが、 コンテナを反復する範囲が決して無効にならないことが保証される。

前提条件 !empty

Returns: 要素が削除された。

要素が削除された。

複雑性 Ο(1)。

void removeFront();

alias stableRemoveFront = removeFront;

void removeBack();

alias stableRemoveBack = removeBack;

コンテナの前/後ろの値を削除する。安定版は 同様に動作するが、コンテナを反復する範囲が 無効化されることは決してないことを保証する。

前提条件!empty

複雑さ Ο(1)。

size_t removeFront(size_t howMany);

alias stableRemoveFront = removeFront;

size_t removeBack(size_t howMany);

alias stableRemoveBack = removeBack;

howManyコンテナの最初または最後の値を削除する。 上記のパラメータ化されていないバージョンとは異なり、これらの関数は 要素を削除できなかった場合に"スロー"しない howMany代わりに、howMany > n の場合、すべての要素が削除される。返される値は 削除された要素の有効な数である。安定版も同様に動作するが、 コンテナを反復処理する範囲が 無効になることは決してない。

Returns:

削除された要素の数

複雑さ Ο(howMany).

Range remove(Range r);

Range linearRemove(Range r);

alias stableRemove = remove;

に属するすべての要素を削除する。 r。これは、 もともとこのコンテナから取得した範囲でなければならない。

Returns:

コンテナ内の残りの要素にまたがる範囲で、 最初は r。

複雑性 Ο(1)

void popFirstOf(ref Range r);

最初の要素を削除する r。これは、もともと このコンテナから取得された範囲である必要があり、DListインスタンスと範囲の両方から r。

複雑度 Ο(1)

void popLastOf(ref Range r);

最後の要素を削除する r。これは、このコンテナから取得された範囲でなければならず、 DListインスタンスと範囲の両方から取得される r。

複雑性 Ο(1)

Range linearRemove(Take!Range r);

alias stableLinearRemove = linearRemove;

linearRemoveremove として機能するが、take 操作の結果である範囲も受け入れる。 これは、範囲から一定の要素を削除する便利な方法である。

複雑さ Ο(r.walkLength)

bool linearRemoveElement(T value);

リストから最初の要素を線形時間で削除する。

Returns:

要素が存在し、正常に削除された場合は真、そうでない場合は偽。

Parameters:

T value

削除されるノードの値

複雑さ Ο(n)