std.range
このモジュールは、レンジの有用な操作を定義しています。 いくつかのアイデアは Leonardo Maffi によるものです。 Source:std/range.d License:
Boost License 1.0. Authors:
Andrei Alexandrescu, David Simcha
- R が入力レンジ（Input Range）のとき true を返します。
入力レンジは基本操作 empty、popFront、front を提供する必要があります。
以下のコードはどんな入力レンジに対してもコンパイルが通ります。
R r; // レンジオブジェクトを定義できる if (r.empty) {} // 空かどうかテストできる r.popFront; // 次の要素へ進めることができる auto h = r.front; // レンジの先頭要素を取り出せる
入力レンジの意味論 (コンパイル時チェックできない性質) としては、 以下があります (r の型が R であるとして):- r.empty は、レンジにまだ値が残っているとき、そのときに限り false を返す
- r.front は、 レンジの現在の先頭要素を返す。値返しまたは参照返しのどちらでもよい。r.front は、仮に r.empty を呼び出したら false を返す状況でのみ使用できる
- r.popFront は、レンジの指す先頭を一つ次の要素に進める。 r.popFront の呼び出しは、仮に r.empty を呼び出すと false を返す状況でのみ使用できる
- e を r に書き出します。 何が行われるかの詳細は二つの型に依存します。R は出力レンジである必要があります。 以下に挙げるように、いくつかのケースがあります。 以下のコード片のうち最初にコンパイルが通るものが実行されます。
- R がE型の要素を扱う出力レンジ（Output Range）のとき true を返します。 出力レンジは、上に定義した put(r, e) が可能な値のことを言います。
- R が前進レンジ（Forward Range）のとき true を返します。
前進レンジは、入力レンジの機能に加え、単純にコピーすることで同じ型のレンジの "チェックポイント"
を作ることができるものです。
入力レンジだけれど前進レンジではないよくある例としては、ファイルやソケットを読み取りレンジがあります;
これらのレンジをコピーしてもストリーム中の位置を保存せず、
ほとんどの場合、ストリーム全体をメモリに置かないための内部バッファを再利用します。
結果として、コピー元とコピー先のどちらのストリームを進めても、
もう一方に影響してしまいます。
以下のコードはどんな前進レンジに対してもコンパイルが通ります。
static assert(isInputRange!(R)); R r1; R r2 = r1; // レンジを他へコピーできる
前進レンジの意味論 (コンパイル時チェックできない性質) は、 入力レンジのそれに加え、 レンジオブジェクトのコピーを取ることで バックトラックが可能であることが要求されます。 - R が双方向レンジ（Bidirectional Range）のとき true を返します。
双方向レンジは、前進レンジの機能に加え基本操作 back と
popBack を提供する必要があります。
以下のコードはどんな双方向レンジに対してもコンパイルが通ります。
R r; static assert(isForwardRange!(R)); // range is an input range r.popBack; // レンジの終端側を一つ縮めることができる auto t = r.back; // レンジの最後の要素を取得できる
双方向レンジの意味論 (コンパイル時チェックできない性質) としては、 以下があります (r の型が R であるとして):- r.back がレンジの最後の要素を（値もしくは参照で）返す。 r.back は、仮に r.empty を呼び出したら false を返す状況でのみ使用できる
- R がランダムアクセスレンジ（Random Access Range）のとき true を返します。
ランダムアクセスレンジは、双方向レンジの機能に加えて基本関数opIndexを提供する有限レンジか、あるいは前進レンジの機能に加えて基本関数opIndexを提供する無限レンジです。
どちらの場合にせよ、length
を提供するか無限レンジであるかのいずれかでなければなりません。
以下のコードはどんなランダムアクセスレンジに対してもコンパイルが通ります。
R r; static assert(isForwardRange!(R)); // 前進レンジである static assert(isBidirectionalRange!(R) || isInfinite!(R)); // 双方向または無限 auto e = r[1]; // 添え字アクセス可能
ランダムアクセスレンジの意味論 (コンパイル時チェックできない性質) としては、 以下がります (r の型が R であるとして):- r.opIndex(n) がレンジの n番目の要素への参照を返す
- レンジが moveFront プリミティブと、 双方向あるいはランダムアクセスレンジなら更に moveBack と moveAt をサポートするとき、true となります。これらは明示的に実装されることも、 モジュール関数 moveFront その他のデフォルト実装が使われることもあります。
- R の要素の型。R は必ずしもレンジでなくとも良い。 要素の型は、型 R のオブジェクト r に対する r.front の結果で決まります。例えば、ElementType!(T[]) は T です。
- R が前進レンジでswap可能な要素型を持つときに true
を返します。
以下のコードはどんなランダムアクセスレンジに対してもコンパイルが通ります。
R r; static assert(isForwardRange!(R)); // 前進レンジである swap(r.front, r.front); // レンジの要素をswap可能
- R が前進レンジで代入可能な要素型を持つときに true
を返します。
以下のコードはどんなランダムアクセスレンジに対してもコンパイルが通ります。
R r; static assert(isForwardRange!(R)); // 前進レンジである auto e = r.front; r.front = e; // 要素に代入が可能
- R が左辺値要素を持つかどうかをチェックします。 左辺値要素とは、参照渡しが行われ、アドレスが取れる要素のことをいいます。
- R が、整数型の値を返す length メンバを持っているときに true を返します。 R は必ずしもレンジでなくても構いません。注意点として、length はオプション的な基本操作で、どのレンジもこれを実装することは必須ではありません。 レンジによっては明示的に長さを保持しない実装もありえますし、 実際にレンジの端まで行かなければ終端のわからないレンジ (ソケットストリーム等) もあり、 さらに無限の長さをもつレンジもあり得ます。
- 無限入力レンジに対して true を返します。
無限入力レンジは、
静的に定義された常に false となる empty メンバを持ちます。
example:
struct InfiniteRange { enum bool empty = false; ... }
- Range が整数を指定するスライス演算子を持ち、
入力レンジを返す時に、true となります。
以下のコードは hasSlicing が true の時にコンパイルが通ります:
Range r; auto s = r[1 .. 2]; static assert(isInputRange!(typeof(s)));
- 任意のレンジに適用できる、 ベストエフォート型の length の実装です。 hasLength!(Range) が true ならば、単に range.length を返し、upTo は無視します。 そうでなければ、レンジを先頭から順に読んでいき、 見つかった要素数を返します。Ο(n) 回の range.empty と range.popFront の呼び出し（ただし n は range の実際の長さ）を行います。upTo パラメタは、 レンジの長さが最低いくつか以上であるかどうかだけに興味があるようなケースに役立ちます。 パラメタ upTo が指定されていれば、upTo ステップ進んだ時点で計算を止め、upTo を返します。
- 双方向レンジを逆向きにたどります。
Example:
int[] a = [ 1, 2, 3, 4, 5 ]; assert(equal(retro(a), [ 5, 4, 3, 2, 1 ][]));
- input.empty へと転送されます
- this のコピーを返します。
- input.popBack へと転送されます
- moveBack(input) へと転送されます
- input.popFront へと転送されます
- moveFront(input) へと転送されます。
- 代入サポート
- 代入サポート
- input[input.length - n + 1] へと転送されます。R がランダムアクセスレンジで R に R.length がある場合に限り定義されます。
- input[input.length - n + 1] へと転送されます。R がランダムアクセスレンジで R に R.length がある場合に限り定義されます。
- input[input.length - n + 1] へと転送されます。R がランダムアクセスレンジで R に R.length がある場合に限り定義されます。
- input[input.length - n + 1] へと転送されます。R がランダムアクセスレンジで R に R.length がある場合に限り定義されます。
- レンジの長さを返す基本操作です。 input.length に転送されるため、hasLength!(R) が真なときにのみ定義されます。
- レンジ r をストライド n でアクセスします。
ランダムアクセスレンジならば、添え字アクセスによってレンジ上を動きます。
そうでなければ、popFront を必要な回数呼び出して動作します。
Example:
int[] a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]; assert(equal(stride(a, 3), [ 1, 4, 7, 10 ][]));
- this(R input, size_t n);
- ストライドを初期化
- this を返します。
- input.empty へと転送されます。
- moveFront(input) へと転送されます。
- @@@
- input.popBack へと転送されます
- 余分な要素を除いた後 input.back へと転送されます。
- moveBack(input)へと転送されます。
- 余分な要素を除いた後 input.back へと転送されます。
- input[input.length - n + 1] へと転送されます。R がランダムアクセスレンジで R に R.length があるときに限り定義されます。
- moveAt(input, n) へと転送されます。
- input[input.length - n + 1] へと転送されます。R がランダムアクセスレンジで R に R.length があるときに限り定義されます。
- Stride のスライスは、元のレンジがスライスをサポートしていれば使用可能です。
- レンジの長さを返す基本関数です。 input.length に転送されるため、 hasLength!(R) が真のときに限り定義されます。
- 複数のレンジを順にたどるレンジです。関数 chain
は任意の個数のレンジを引数にとり、Chain!(R1, R2,...) オブジェクトを返します。
レンジ自体の型は異なっていても構いませんが、要素型は統一されている必要があります。
結果は front, popFront, empty を提供するレンジになります。
入力が全て length を持つランダムアクセスレンジならば、
Chain その二つの機能も同時に提供します。
レンジが１つだけ Chain や chain に渡された場合
Chain
型はそのレンジへのaliasとなります。
Example:
int[] arr1 = [ 1, 2, 3, 4 ]; int[] arr2 = [ 5, 6 ]; int[] arr3 = [ 7 ]; auto s = chain(arr1, arr2, arr3); assert(s.length == 7); assert(s[5] == 6); assert(equal(s, [1, 2, 3, 4, 5, 6, 7][]));
- ランダムアクセスレンジを、
指定されたインデックスから始めて左右に広がりながら順にアクセスします。
始点を与えなかった場合、
レンジのちょうど中央から開始します。元のレンジ全体を列挙し終わると終了します。
Example:
int[] a = [ 1, 2, 3, 4, 5 ]; assert(equal(radial(a), [ 3, 4, 2, 5, 1 ][])); a = [ 1, 2, 3, 4 ]; assert(equal(radial(a), [ 2, 3, 1, 4 ][]));
- this(R input);
- レンジを受け取って中央からの列挙を開始します。 長さが偶数のレンジの場合は、中心のすぐ左の要素から列挙が始まります。 二番目は、一番目のすぐ右の要素です。 このコンストラクタを簡単に呼び出すには、 補助関数 radial(input) を使用します。
- this(R input, size_t startingPoint);
- レンジを受け取って input[mid] からの列挙を開始します。 二番目は、 一番目のすぐ右の要素です。input[mid] の右に要素がない場合は、input[mid - 1] から降順に列挙が行われます。このコンストラクタを簡単に呼び出すには、 補助関数 radial(input,startingPoint) を使用します。
- this を返します。
- 全ての要素を列挙し終わっていれば true を返す、 レンジの基本操作です
- レンジを一つ次の要素に進める基本操作です
- レンジから（遅延評価で）最大 n 個までの要素を取り出します。
特に、無限レンジを扱うときに有用です。
入力が ランダムアクセスレンジで length がサポートされていた場合、Take もそれらの機能を同様にサポートします。
Example:
int[] arr1 = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]; auto s = take(arr1, 5); assert(s.length == 5); assert(s[4] == 5); assert(equal(s, [ 1, 2, 3, 4, 5 ][]));
- レンジ r 自身 (コピーではない) を、n 回
r.popFront を呼び出して先に進めます。r は popFrontN
に参照渡しされるので、元々のレンジが影響されます。スライス操作をサポートするレンジならば Ο(1)
ステップ、それ以外では Ο(n)
ステップの時間がかかります。
Example:
int[] a = [ 1, 2, 3, 4, 5 ]; a.popFrontN(2); assert(a == [ 3, 4, 5 ]);
- レンジ r 自身 (コピーではない) を、n 回
r.popBack を呼び出して終端を縮めます。
r は popBackN に参照渡しされるので、元々のレンジが影響されます。
スライス操作をサポートするレンジならば Ο(1) ステップ、それ以外では
Ο(n) ステップの時間がかかります。
Example:
int[] a = [ 1, 2, 3, 4, 5 ]; a.popBackN(2); assert(a == [ 1, 2, 3 ]);
- 一つの値を永久に繰り返します。例:
enforce(equal(take(repeat(5), 4), [ 5, 5, 5, 5 ][]));
- レンジプリミティブの実装
- value をちょうど n 回繰り返します。take(repeat(value), n) と同等です。
- struct Cycle(Range) if (isForwardRange!(Unqual!(Range)) && !isInfinite!(Unqual!(Range)));
template Cycle(R) if (isInfinite!(R))
struct Cycle(R) if (isStaticArray!(R));
Cycle!(R) cycle(R)(R input);
Cycle!(R) cycle(R)(R input, size_t index);
Cycle!(R) cycle(R)(R input);
Cycle!(R) cycle(R)(ref R input, size_t index = 0); - 指定された前進レンジを無限に繰り返します。
元々のレンジが無限だった場合（Cycle を適用しても結果は変わらないので)、
Cycle はそのことを検出し、元のレンジ型へのaliasとして定義されます。
元のレンジがランダムアクセスならば、Cycle
もランダムアクセスになり、初期インデックス
index を受け取るコンストラクタを提供します。Cycle
は、パフォーマンス上の理由で、静的配列に対しては特殊化した定義が適用されます。
Example:
assert(equal(take(cycle([1, 2][]), 5), [ 1, 2, 1, 2, 1 ][]));Tip:
このテンプレートは、単純な環状バッファを実装する優れた方法です。- Ditto
- 複数のレンジを並行してたどります。
Zipレンジの要素型はプロキシとなっているタプルで、n番目のレンジに対応する値は
e[n] で取得できます。
Example:
int[] a = [ 1, 2, 3 ]; string[] b = [ "a", "b", "c" ]; // prints 1:a 2:b 3:c foreach (e; zip(a, b)) { write(e[0], ':', e[1], ' '); }
Zip は、渡されたレンジの最大公約数的な機能を提供します。 たとえば、全てのレンジがランダムアクセス可能ならランダムアクセス可能になりますし、 書き換えやswapが可能ならZipレンジでもそれは可能です。この機能によって、Zip は複数レンジを同時に操作できる非常に強力な機能となります。 たとえば、 以下のコードは２つの配列を並列してソートします。int[] a = [ 1, 2, 3 ]; string[] b = [ "a", "b", "c" ]; sort!("a[0] > b[0]")(zip(a, b)); assert(a == [ 3, 2, 1 ]); assert(b == [ "c", "b", "a" ]);
- this(R rs, StoppingPolicy s = StoppingPolicy.shortest);
- オブジェクトを構築します。通常、 std.range.zip 補助関数から間接的に呼び出されます。
- レンジが終端に来ていれば true を返します。 終端の定義はStoppingPolicy依存です。
- 現在の先頭要素へのプロキシを返します。
- 全てのレンジへ front を設定します。
- Frontを除きます
- 現在の末尾要素へのプロキシを返します。
- 末尾を除いて返します。
- 現在の末尾要素を設定します。
- 全てのレンジを popFront で進めます。
- 全てのレンジを popBack で縮めます。
- このレンジの length を返します。全ての内蔵レンジが length を定義しているときのみ定義されます。
- スライスを返します。 全ての内蔵レンジがスライスを計算できる場合にのみ定義されます。
- 複合レンジの第 n 要素を返します。 全てのレンジがランダムアクセスな場合に定義されます。
- 複合レンジの第 n 要素へ代入します。 全てのレンジがランダムアクセスな場合に定義されます。
- 破壊的に複合レンジの第 n 要素を読み取ります。 全てのレンジがランダムアクセスな場合に定義されます。
- Zip の終了条件を定義します。
デフォルトでは、一番短いレンジの長さに合わせます。
- 一番短いレンジが終わったタイミングで終了
- 一番長いレンジが終わったタイミングで終了
- 全てのレンジが同じ長さであることを要求
- 複数のレンジを並行して foreach ループで回るための補助型です。
一つしかレンジが渡されなければ、Lockstep はその引数へのaliasになります。
違う長さのレンジが渡され s == StoppingPolicy.shortest
ならば、一番短いレンジに合わせます。
違う長さのレンジが渡され s == StoppingPolicy.requireSameLength ならば、
例外が飛びます。s に StoppingPolicy.longest は指定できず、
指定すると例外が飛びます。
BUGS:
左辺値アクセスできないレンジで ref を foreach に使うと、コンパイルは通ってしまいますが、 意図した書き換えなどは行えません。 Examples:auto arr1 = [1,2,3,4,5]; auto arr2 = [6,7,8,9,10]; foreach(ref a, ref b; lockstep(arr1, arr2)) { a += b; } assert(arr1 == [7,9,11,13,15]); // Lockstep ではインデックスによるアクセスも可能です: foreach(index, a, b; lockstep(arr1, arr2)) { writefln("Index %s: a = %s, b = %s", index, a, b); }
- 初期値と、前の値から次の値を計算する漸化式を与えて、
数列を生成します。
結果は無限の前進レンジとなります。
Recurrence 型を直接宣言することは稀で、
多くの場合は、補助関数 recurrence を使ってレンジを作成します。
recurrence を呼び出すと、テンプレート引数で指定された式を使って、
通常の引数で指定された初期値から次の値を計算します。
例えば、
フィボナッチ数列の場合、
直前の2つの値を使って次のフィボナッチ数を計算する必要があるため、
初期値は2つとなります（従ってサイズ2のステートを持ちます）。
文字列形式で関数を渡す場合、状態は "a"
という名前を持ち、数列の何番目の要素であるかを表す "n" という名前のゼロベースのインデックスを持ちます。
文字列では、a[n] の値を a[n
- 1], a[n - 2], a[n - 3],..., a[n - stateSize] から計算する式を書きます。
ステート数は、
recurrence に渡された実引数の個数で決まります。
ステート数やその管理は適切にRecurrenceの内部で行われます。
Example:
// a[0] = 1, a[1] = 1, 以下 a[n+1] = a[n-1] + a[n] で計算 auto fib = recurrence!("a[n-1] + a[n-2]")(1, 1); // 最初の10個のフィボナッチ数を表示 foreach (e; take(fib, 10)) { writeln(e); } // 最初の10個の階乗数を表示 foreach (e; take(recurrence!("a[n-1] * n")(1), 10)) { writeln(e); }
- Sequence は Recurrence eと似ていますが、
数式が closed form であることが違う点です。これはつまり、数列のn番目の値は
初期値と n そのものから直接計算できるという意味です。
結果として、Sequence
はランダムアクセスレンジとなり、通常の Recurrence
が前進レンジにしかならないのと対照的です。
ステートは Tuple で保持されるため、
違う型の要素を持たせることも可能です。
Example:
// a[0] = 1, a[1] = 2, a[n] = a[0] + n * a[1] auto odds = sequence!("a[0] + n * a[1]")(1, 2);
- Iota!(CommonType!(Unqual!(B),Unqual!(E)),S) iota(B, E, S)(B begin, E end, S step);
Iota!(CommonType!(Unqual!(B),Unqual!(E)),uint) iota(B, E)(B begin, E end);
Iota!(Unqual!(E),uint) iota(E)(E end);
struct Iota(N,S) if ((isIntegral!(N) || isPointer!(N)) && isIntegral!(S));
struct Iota(N,S) if (isFloatingPoint!(N) && isNumeric!(S)); - begin, begin +
step, begin + 2 * step, ..., と進めて end まで（ただしendは含まない）の部分列をレンジとして取り出します。結果はランダムアクセスレンジになります。
2引数バージョンは step = 1 の扱いになります。
Example:
auto r = iota(0, 10, 1); assert(equal(r, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9][])); r = iota(0, 11, 3); assert(equal(r, [0, 3, 6, 9][])); assert(r[2] == 6); auto rf = iota(0.0, 0.5, 0.1); assert(approxEqual(rf, [0.0, 0.1, 0.2, 0.3, 0.4]));
- FrontTransversal と Transversal
(下参照) に対するオプション
- レンジ内の各レンジは異なる長さであると仮定されます。 (例: jagged array)
- レンジ内の全てのレンジは同じ長さであることが強制されます。 (例： 長さが一定の二次元配列) チェックは構築時に最初に一度だけ行われます。
- チェックなしで、レンジ内の全てのレンジは同じ長さであることを仮定します。 このオプションは、 既に長さが一定であることをチェック済みのレンジに適用するときなどに有用です。
- レンジのレンジを受け取り、
それぞれの先頭要素を順に列挙します。
Example:
int[][] x = new int[][2]; x[0] = [1, 2]; x[1] = [3, 4]; auto ror = frontTransversal(x); assert(equal(ror, [ 1, 3 ][]));
- this(RangeOfRanges input);
- 入力からの構築
- 前進レンジの基本操作
- RangeOfRanges がスライシング可能で、 インデックスアクセス可能な条件が全て満たされていれば、全体としてスライシング可能です。
- レンジのレンジを受け取り、それぞれの第 n 要素を順に列挙します。
ランダムアクセスレンジのレンジを渡す必要があります。
Example:
int[][] x = new int[][2]; x[0] = [1, 2]; x[1] = [3, 4]; auto ror = transversal(x, 1); assert(equal(ror, [ 2, 4 ][]));
- this(RangeOfRanges input, size_t n);
- 入力とインデックスから構築
- 前進レンジの基本操作
- RangeOfRanges がスライシング可能で、 インデックスアクセス可能な条件が全て満たされていれば、全体としてスライシング可能です。
- r のfrontをムーブし返します。r.front はどんなリソースも保持していない破棄可能な状態になります (通常、 .init 値と等しくなります)
- r のbackをムーブし返します。r.front はどんなリソースも保持していない破棄可能な状態になります (通常、 .init 値と等しくなります)
- r の第i要素をムーブし返します。r.front はどんなリソースも保持していない破棄可能な状態になります (通常、 .init 値と等しくなります)
- このインターフェイスは、要素型 E の入力レンジに対する仮想関数ベースのアクセスを提供することを目的としています。
これは、DLL関数や、汎用のレンジを受け取りたい仮想関数など、
定まったバイナリインターフェイスが必要な場合に役立ちます。
注意点として、
isInputRange やその他テンプレートは、構造的なインターフェイス適合を検査するもので、
この特定のインターフェイス型をimplementしていることを検査する物ではありません。
Examples:
class UsesRanges { void useRange(InputRange range) { // Function body. } } // 新しいレンジ型 auto squares = map!"a * a"(iota(10)); // interface でラップ auto squaresWrapped = inputRangeObject(squares); // 使う auto usesRanges = new UsesRanges; usesRanges.useRange(squaresWrapped);
Limitations:
これらのインターフェイスは要素への ref アクセスは転送できません。 また、ラップしたレンジの無限性は伝搬されません。 ランダムアクセスレンジでない場合、length も伝搬されません。 - 前進レンジ型 E のインターフェイスです
- 双方向レンジ型 E のインターフェイスです
- 有限のランダムアクセスレンジ型 E のインターフェイスです
- 無限のランダムアクセスレンジ型 E のインターフェイスです
- InputRange を代入可能にします。
- ForwardRange を代入可能にします。
- BidirectionalRange を代入可能にします。
- RandomAccessFinite を代入可能にします。
- 出力レンジ型 E のインターフェイスです。使い方は
InputRange などなどと同様です。
- OutputRange インターフェイスを全ての型Eに対して実装し、 put メソッドをそれぞれの E について仮想関数としてラップして提供します。
- R にもっともよくマッチするインターフェイス型を返します。
- R に最もよくマッチするインターフェイス型を実装し、 関連するレンジプリミティブを全て仮想関数でラップし提供します。R が既に InputRange インターフェイスを継承していれば、単なるaliasとなります。
- InputRangeObject を作る便利関数です。
- OutputRangeObject
をレンジ型 R と受理する要素型のリスト E から作る便利関数です。
Examples:
uint[] outputArray; auto app = appender(&outputArray); auto appWrapped = outputRangeObject!(uint, uint[])(app); static assert(is(typeof(appWrapped) : OutputRange!(uint[]))); static assert(is(typeof(appWrapped) : OutputRange!(uint)));
- ソート済みのランダムアクセスレンジを表します。
通常のレンジプリミティブに加え、二分探索による高速な検索が実装されています。
SortedRange をソートしていないレンジ r から作るには、std.algorithm.sort を使用し r
を破壊的に並び替えて対応する SortedRange を作ります。既にソート済みとわかっているレンジ
r から SortedRange を作るには、assumeSorted
を以下のように使用します。
Example:
auto a = [ 1, 2, 3, 42, 52, 64 ]; auto r = assumeSorted(a); assert(r.canFind(3)); assert(!r.canFind(32)); auto r1 = sort!"a > b"(a); assert(r1.canFind(3)); assert(!r1.canFind(32)); assert(r1.release() == [ 64, 52, 42, 3, 2, 1 ]);
SortedRange はランダムアクセスより弱いレンジを受け取ることもできますが、 それらに対しては意味のある機能を提供できません。したがって、 SortedRange は今のところランダムアクセスレンジに限定されています。 元のレンジのコピーが作られることはありません。 ソート済みという仮定が壊される形で SortedRange の裏で元のレンジが変更された場合 SortedRange は間違った動作をします。 Example:
auto a = [ 1, 2, 3, 42, 52, 64 ]; auto r = assumeSorted(a); assert(r.canFind(42)); swap(a[2], a[5]); // 元のレンジをソート済みでなくするのは不正 assert(!r.canFind(42)); // 通るべきでないが通ってしまう
- レンジプリミティブ.
- コントロールしているレンジを解放し返します。
- この関数は、レンジ r が左右に分割でき、左側 r1
の要素 e1 は pred(e1, value) が true になり、
右側 r2 の要素 e2 は pred(e2, value) が false になる、と仮定して実行されます。この仮定の下で、lowerBound
は二分探索によって r1、つまり
pred が常に true となる左レンジを見つけだします。Ο(log(r.length))
回 pred を呼び出します。
この計算量を上回ってしまうため、前提条件はチェックされません。
value の型と ElementType!(Range) とが違っていても、
pred 適用できれば問題ありません。参照: STL の lower_bound
Precondition:
find!(not!(pred))(r, value).length + find!(pred)(retro(r), value).length == r.length Example:
auto a = assumeSorted([ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]); auto p = a.lowerBound(4); assert(p.release == [ 0, 1, 2, 3 ]);
- この関数は、レンジ r が左右に分割でき、左側 r1
の要素 e1 は pred(value, e1) が false になり、
右側 r2 の要素 e2 は pred(value, e2) が true になる、と仮定して実行されます。 (lowerBound の定義との違いに注意して下さい。
pred の引数順とtrue/falseが逆転しています) この仮定の下で、lowerBound
は二分探索によって r2、つまり
pred が常に true となる左レンジを見つけだします。Ο(log(r.length))
回 pred を呼び出します。
この計算量を上回ってしまうため、前提条件はチェックされません。value の型と ElementType!(Range) とが違っていても、
pred 適用できれば問題ありません。参照: STL の upper_bound
Precondition:
find!(pred)(r, value).length + find!(not!(pred))(retro(r), value).length == r.length Example:
auto a = assumeSorted([ 1, 2, 3, 3, 3, 4, 4, 5, 6 ]); auto p = a.upperBound(3); assert(p == [4, 4, 5, 6]);
- レンジが lowerBound!(pred)(r, value) と upperBound!(pred)(r, value) の両方を満たしているという仮定の下で、
equalRange!(pred)(r, v) を呼び出すと、
pred(e, value)==true と pred(value,
e)==false を同時に満たす全ての要素 e を含むレンジを返します。Ο(log(r.length))
回 pred を呼び出します。参照: STL の equal_range
Precondition:
find!(not!(pred))(r, value).length + find!(pred)(retro(r), value).length == r.length && find!(pred)(r, value).length + find!(not!(pred))(retro(r), value).length == r.length Example:
auto a = [ 1, 2, 3, 3, 3, 4, 4, 5, 6 ]; auto r = equalRange(a, 3); assert(r == [ 3, 3, 3 ]);
- ソート済みと仮定されるレンジ range の中に value があれば true を返します。Ο(log(r.length)) 回 less を呼び出します。参照: STL の binary_search