C++ による Python のスライス

この投稿では、最近私の Range-v3 ライブラリに追加された楽しいハッカーについて説明します。これは、かわいらしい短い構文を備えた Python のような範囲スライシング機能です。機能の観点からすれば驚くようなものではありませんが、ライブラリ設計の楽しいケーススタディであり、ライブラリ設計の私の哲学をうまく説明しています。

Python スライス

Python では、スライスできます 非常に簡潔な構文を使用して、コンテナー (つまり、連続した部分範囲のビューを作成) を作成します。例:

>>> letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g']
>>> letters
['a', 'b', 'c', 'd', 'e', 'f', 'g']
>>> # access a subrange with a slice operation
>>> letters[2:5]
['c', 'd', 'e']
>>> # replace some values
>>> letters[2:5] = ['C', 'D', 'E']
>>> letters
['a', 'b', 'C', 'D', 'E', 'f', 'g']

5 行目で、リスト letters の要素にアクセスします。 構文 letters[2:5] を使用した半開シーケンス [2,5) .短くて甘い。 8 行目で、～ を代入します。 基礎となる letters を変更するスライス リスト。これは、Python スライスに参照セマンティクスがあることを証明しています。

Python のスライス オペレータでできることはそれだけではありません。スライス オフセットを省略できます。その場合、Python はスマートなデフォルトを使用します:

>>> # A missing first offset means "from the beginning"
>>> letters[:5]
['a','b','C', 'D', 'E']
>>> # A missing end offset means "to the end"
>>> letters[5:]
['f','g']

最後からスライスすることもできます 負のオフセット:

>>> # Take the last two elements:
>>> letters[-2:]

これはすべて非常に便利で、非常に優れた機能です。

Range-v3 を使用した C++ での古いスタイルのスライス

私の range-v3 ライブラリには長い間スライス操作がありましたが、それほど強力ではなく、構文もクールではありませんでした:

using namespace ranges;
auto letters = view::iota('a','g');
std::cout << letters << '\n';
// prints: {a,b,c,d,e,f,g}
std::cout << (letters | view::slice(2,5)) << '\n';
// prints: {c,d,e}

上記のコードでは、 view::iota 'a' からすべての文字を生成するビューです 'g' まで (包括的)、および view::slice オフセット 2 から 5 (排他的) までの要素のビューです。 Python のスライスと同様に、このスライスは軽量で非所有です。

この構文は、それ自体ひどいものではありません ですが、確かに Python ほど楽しくはありません。そして view::slice 最後からスライスするための負のオフセットを受け入れなかったため、それほど強力ではありませんでした.

Range-v3 を使用した C++ での新しいスタイルのスライス

まず、スライスを作成するための短い形式を見つけたかったので、array_view からページを取得しました。 この提案には、多次元配列にインデックスを付けるための非常に巧妙な構文があります。以下は、提案からそのまま引用した例です:

char a[3][1][4] {{{'H', 'i'}}};
auto av = array_view<char, 3>{a};
// the following assertions hold:
assert((av.bounds() == bounds<3>{3, 1, 4}));
assert((av[{0, 0, 0}] == 'H'));

行 1 ～ 2 では、文字の 3-D 配列を宣言し、その 3-D ビューを作成します。 5 行目で魔法が起こります。少し異質な av[{0,0,0}] で (0,0,0) の位置にある要素にアクセスします。 構文。これは一体何?!

それは非常に単純です:統一された初期化構文の斬新な使い方です。このタイプを検討してください:

struct indices
{
    std::size_t i, j, k;
};
struct my_array_view
{
    double & operator[](indices x);
};

これで my_array_view にインデックスを付けることができます av[{0,0,0}] を持つオブジェクト 構文。ニートオ!

このトリックを使用して、スライス範囲の非常に短くてかわいい構文を人々に提供できることに気付きました。チェックしてください:

using namespace ranges;
auto letters = view::iota('a','g');
std::cout << letters << '\n';
// prints: {a,b,c,d,e,f,g}
std::cout << letters[{2,5}] << '\n';
// prints: {c,d,e}

ねえ、それは半分悪くない!

最後からの切り取り、ジレンマ

しかし、それだけでは不十分です。最後からスライスする便利な機能が必要です。しかし、ライブラリ設計の観点からすると、ちょっと… 興味深い… ところがあります。 すべての範囲タイプが最後からのスライスをサポートしているわけではありません. 意味を理解するために、istream から読み取った int の範囲を考えてみましょう。 .これは入力です 範囲。到達するまで終わりはわかりません。つまり、最後のマイナス N がわからないということです。 N になるまでエレメント それを過ぎた要素!

つまり、次のコードは意味がありません:

using namespace ranges;
// An input range of ints read from cin
auto ints = istream<int>(std::cin);
// I'm sorry, I can't do that, Dave:
std::cout << ints[{0,-2}] << '\n';

istream によって返される istream 範囲 コンパイル時で完全に把握 端から切れないこと。ただし、オフセットが負か正かはランタイムです プロパティなので、コンパイル時にチェックできません。これはランタイム エラーになります。

さらに悪いことに、負のオフセットを受け入れる範囲のカテゴリに関するルールは驚くほど微妙です。上記のコードのバリエーションを考えてみましょう:

using namespace ranges;
// Take the first 10 ints read from cin:
auto ints = istream<int>(std::cin) | view::take(10);
// This should work! It should take the first 8 ints:
std::cout << ints[{0,-2}] << '\n';

この場合、istream から最初の 10 個の整数を取得しました。 ints range は入力範囲のままですが、サイズ 入力範囲。 できる 終わりがどこにあるかを知っているので、最後からスライスします。

フォワードがある場合 シーケンスの長さを計算し、前方から距離マイナス N を進めることで、それがどこにあるか (たとえば、ヌルで終わる文字列) がわからなくても、いつでも最後からスライスできます (ただし、それは常に最も効率的な方法とは限りません)。

そして、あなたは決してすべきではありません 範囲が無限の場合は、負のオフセットを指定します。決して、決して、決して。

さらに微妙になります。両方のオフセットが負の場合、または両方のオフセットが負でない場合、結果のスライスは O(1) でのサイズを認識します。それ以外の場合、基になる範囲がそのサイズを知っている場合にのみ、そのサイズを認識します。 O(1) サイズの場合 の範囲は型システムの一部であり、あらゆる種類の最適化を可能にします。実行時までオフセットの符号がわからない場合、サイズ として自身をアドバタイズする型を返すことはできません。 .

私が言いたいのは、最後からスライスしてもよいかどうかのルールは微妙だということです — 実行時までエラー報告を残すには微妙すぎるのです。そうすることで、フロアに貴重な最適化が残されます。

最後からスライスする、解決策

私が思いついた解決策は、無条件のアサートで負のオフセットを許可しないことでした。しかし、あなたが私を炎上させる前に待ってください！最後からのオフセットを表す代替構文を追加しました。チェックしてください:

using namespace ranges;
auto letters = view::iota('a','g');
std::cout << letters << '\n';
// prints: {a,b,c,d,e,f,g}
std::cout << letters[{2,end-2}] << '\n';
// prints: {c,d,e}

負のオフセットを使用する代わりに、end-2 と言います。 最後から2番目という意味です。 end とは ここ？ endと同じです Iterable の最後を取得するために呼び出す関数 (std::end を考えてください) )、私のライブラリでのみ関数ではありません。関数オブジェクトです。 (私が begin を作ることにした理由について詳しくは および end 無料関数の代わりにグローバル関数オブジェクトについては、カスタマイズ ポイントの設計に関する私のブログ投稿を参照してください。) end 以降 はオブジェクトです。オーバーロードされた operator- を定義できます end かかる 左側が int で、右側が int です。それは、型システムの一部であるオフセットの終りからを作る何らかの型のオブジェクトを返すことができます.

struct from_end { int i; };

from_end operator-( decltype(ranges::end), int i )
{
    assert(i >= 0); // No funny business, please
    return {i};
}

オーバーロードされた operator[] を定義できるようになりました std::pair<int,from_end> を受け入れる範囲タイプ :

struct my_range
{
    // callable as rng[{2,end-2}]
    slice_view<my_range>
    operator[](std::pair<int, from_end> p)
    {
        // ... slicing happens here
    }
};

ほら！今では、最適化の機会を無駄にすることなく、短くて読みやすい構文とコンパイル時の型チェックを使用して、最後からスライスすることができます。

はい、でも…

それは素晴らしいことですが、「rng[{2,-2}]」のようなコード 」は引き続きコンパイルされ、実行時に失敗します。状況はどのように改善されていますか？現在の違いは、slice に負のオフセットを渡すことは 常に であることです。 実行時エラー。範囲タイプがおそらくそれをサポートできたとしても、それが成功してあなたが望むことをする状況はありません。ユーザーは、それが正しい方法ではないことをすぐに理解します。

負のオフセットが機能する場合と機能しない場合があるようにすると、インターフェースがはるかに危険になります。ユーザーはそれを試し、ある程度の成功を収め、常に機能すると誤った結論を下します。アプリケーションがデプロイされた後、彼らは自分のエラーを苦労して発見します。

図書館デザインの哲学 :

そして、この問題に関連する結果:

図書館の設計に関するこの小さなケース スタディをお楽しみいただければ幸いです。

謝辞

Python のスライス演算子の簡潔でクールな点に注意を向けてくれた Chandler Carruth に感謝します。

脚注:

C++ コンテナーでは、O(1) で要素にアクセスできるランダム アクセス コンテナーに対してのみ、インデックス作成操作が許可されます。ここでは、O(N) 操作である可能性がありますが、ユーザーがインデックスのような表記法で範囲をスライスできるようにしています。この決定を正当化するために、スライシングがインデックス作成と十分に異なるかどうかは、現時点ではわかりません。考えを歓迎します。

"\e"
"\e"