std.container.slist

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

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

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

s.insertFront([5, 6]);
assert(equal(s[], [5, 6, 2, 3]));

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

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

auto r = sl[];
popFrontN(r, 2);
writeln(walkLength(r)); // 3

struct SList(T) if (!is(T == shared));

シンプルで高速な単方向リンクリストを実装する。 スタックとして使用できる。

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

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

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

this(Stuff)(Stuff stuff)
if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T) && !is(Stuff == T[]));

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

const bool opEquals(const SList rhs);

const bool opEquals(const ref SList rhs);

等価比較。

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

struct Range;

コンテナの主要な範囲を定義し、前方の範囲を具体化する。

const @property bool empty();

@property ref T front();

void popFront();

入力範囲のプリミティブ。

@property Range save();

前方範囲のプリミティブ。

const @property bool empty();

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

複雑度 Ο(1)

@property SList dup();

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

複雑度 Ο(n)。

Range opSlice();

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

複雑性 Ο(1)

@property ref T front();

次へ opSlice().front。

複雑性 Ο(1)

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

SList opBinaryRight(string op, Stuff)(Stuff lhs)
if (op == "~" && !is(typeof(lhs.opBinary!"~"(this))) && is(typeof(SList(lhs))));

this と引数を結合した新しいSList を返す。 opBinaryRightStuff が定義されていない場合にのみ定義される。 opBinary。

void clear();

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

事後条件empty

複雑さ Ο(1)

void reverse();

SListをその場で逆順にする。メモリ割り当ては行わない。

Complexity Ο(n)

size_t insertFront(Stuff)(Stuff stuff)
if (isInputRange!Stuff || isImplicitlyConvertible!(Stuff, T));

alias insert = insertFront;

alias stableInsert = insert;

alias stableInsertFront = insertFront;

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

Returns:

挿入される要素の数

複雑さ Ο(m) ここで、m は長さである。 stuff

T removeAny();

alias stableRemoveAny = removeAny;

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

前提条件 !empty

Returns: 要素が削除された。

要素が削除された。

複雑性 Ο(1)。

void removeFront();

alias stableRemoveFront = removeFront;

コンテナの最初の値を削除する。安定版では 同じ動作だが、コンテナを反復する範囲が 無効化されることは決してない。

前提条件!empty

複雑さ Ο(1)。

size_t removeFront(size_t howMany);

alias stableRemoveFront = removeFront;

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

Returns:

削除された要素の数

複雑さ Ο(howMany * log(n))。

size_t insertAfter(Stuff)(Range r, Stuff stuff)
if (isInputRange!Stuff || isImplicitlyConvertible!(Stuff, T));

stuff範囲の後ろに挿入する r。これは、 事前にこのコンテナから抽出された範囲でなければならない。リストのすべての範囲が リストの最後に位置していることを前提にすると、この関数は本質的にはリストに追加し、 rリストの最後のノードに到達する可能性の高い方法として 使用されます。理想的には、 rリストの最後の要素の近くか、その位置に配置される。

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

Returns:

挿入された値の数。

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

例

auto sl = SList!string(["a", "b", "d"]);
sl.insertAfter(sl[], "e"); // 最後に挿入する(最も遅い)
assert(std.algorithm.equal(sl[], ["a", "b", "d", "e"]));
sl.insertAfter(std.range.take(sl[], 2), "c"); // "b"の後に挿入する
assert(std.algorithm.equal(sl[], ["a", "b", "c", "d", "e"]));

size_t insertAfter(Stuff)(Take!Range r, Stuff stuff)
if (isInputRange!Stuff || isImplicitlyConvertible!(Stuff, T));

alias stableInsertAfter = insertAfter;

上記と同様だが、 insertAfterが、countで限定された範囲を受け入れる。 これは、リストの途中への高速挿入を確実に行うために重要である。 指定した位置以降への高速挿入を行うには、 r場合は、insertAfter(take(r, 1), stuff) を使用する。その操作の複雑さは、 要素の数のみに依存する stuff。

前提条件 r.original.empty || r.maxLength > 0

Returns: 挿入された値の数。

挿入された値の数。

複雑さ Ο(k + m) ここで、k はr、m は長さである。 stuff。

Range linearRemove(Range r);

リストから範囲を線形時間で削除する。

Returns: 空の範囲。

空の範囲。

複雑性 Ο(n)

Range linearRemove(Take!Range r);

alias stableLinearRemove = linearRemove;

Take!Range を線形時間でリストから削除する。

Returns:

削除された範囲の要素を含む範囲。

複雑度 Ο(n)

bool linearRemoveElement(T value);

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

Returns:

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

Parameters:

T value

削除されるノードの値

複雑さ Ο(n)