To Be or Not to Be (イテレータ)

最初の C++ 標準のインクがまだ湿っていた 1999 年にさかのぼりますが、Herb Sutter はまだ現存する C++ レポート で GoTW パズルを提起しました。 (RIP):コンテナーがコンテナーではない場合その記事で、Herb は今では悪名高い vector<bool> の問題について説明しました。 .標準独自のコンテナー要件によると、vector<bool> ではない コンテナ。

要するにvector<bool>だからです の反復子はランダム アクセスであると主張していますが、そうではありません。ランダム アクセス イテレータは、逆参照する場合、しなければならない 実際の参照を返します。彼らが指し示すものがどこかに実際に存在する場合にのみ、彼らはそれを行うことができます.しかし、bool その vector<bool>::iterator を指す しない どこにでも存在します。実際にはパックされた整数のビットであり、vector<bool> を逆参照しています のイテレータは、単に bool& のように動作する何らかの型のオブジェクトを返します 実際に bool& でなくても .

Herb は次のように言っています:

Herb は記事の最後で vector<bool> の使用をやめるよう提案しています。 std::bitset を使用します ビットパッキングが必要な場合。しかし、それは問題を押し進めるだけです。 std::bitset すべきではない理由 ランダム アクセス イテレータを持つ適合するコンテナになるか?プロキシ化されたコレクションが非常に有用である場合、それらを二流市民のように扱う標準ライブラリで満足する必要があるでしょうか?

プロキシ イテレータの簡単な歴史

Herb は 1999 年に記事を書いたので、私たちは長い間この問題と向き合ってきました。多くの人がそれを修正しようとしましたが、最終的に何らかの理由で失敗しました.ほとんどの場合、すべてのソリューションが下位互換性を維持しようとしており、より豊富なイテレータ階層を簡単に許可しない標準に押し込んだり、イテレータ自体をトラバーサルと要素アクセスを制御する個別のオブジェクトに分割したりしたためです。委員会が躊躇するたびに、代わりにそれが知っている悪魔を好む.

興味深い歴史的なメモ:元の STL 設計には、問題の原因となる「真の参照」要件がありませんでした。 Forward Iterator の概念については、SGI ドキュメントを参照してください。 *it とはどこにも書いてありません 本当の参考にしてください。 Trivial Iterators のドキュメントでは、特にプロキシ参照について言及しており、それらは正当であると述べています。

最近、C++ の著名人が N3351、いわゆる Palo Alto TR に名前を付けました。 これは、Concepts Lite の構文を使用して、STL の概念ベースの再設計を提案しています。興味深いことに、Palo Alto TR は元の SGI 設計への回帰です。*it の戻り型に「真の参照」要件はありません。; const ValueType<I> & に変換できる必要があります。 :

// This must work, according to the Palo Alto TR
const ValueType<I> & val = *it;

プロキシ参照型がこのような変換を提供することは難しくありません。たとえば、今日のコンパイルは次のとおりです。

std::vector<bool> vb{true, false, true, false};
auto it = vb.begin();
const bool & val = *it;

*it bool への暗黙的な変換があります 、 const bool& にバインドします .素晴らしい！問題は解決しましたよね？そうではありません。

一連のプロキシ問題

プロキシ イテレータの問題をよりよく理解するために、もっと興味深い例を見てみましょう:zip 見る。 2 つのシーケンスを一緒に圧縮すると、各要素が std::pair である単一のシーケンスが得られます 2 つのソース シーケンスからの要素の。これは、zip ビューが繰り返されるときにオンデマンドでペアを作成して、遅延して行うことができます。

std::vector<int> v1 { 1,2,3 };
std::vector<int> v2 { 9,8,7 };

auto z = view::zip( v1, v2 );
auto it = z.begin();

assert( *it   == std::make_pair(1,9) );
assert( *++it == std::make_pair(2,8) );
assert( *++it == std::make_pair(3,7) );

zip ビューはオンデマンドでペアを生成するため、メモリ内のどこにも存在しません。 しかし、それらが参照する要素はそうです! ほら？

std::pair<int&,int&> p = *z.begin();
assert( &p.first  == &v1[0] );
assert( &p.second == &v2[0] );

zip ビューは非常に興味深い野獣です。その参照型は pair<T&,U&> です 値の型は pair<T,U> です .これは、反復子の概念に非常に興味深い課題をもたらします。

1.値と参照

Palo Alto TR には *it が必要であることを思い出してください。 const ValueType<I>& に変換可能 .したがって、これを行うことができるはずです:

auto z = view::zip( v1, v2 );
const pair<int,int>& val = *z.begin();

それはうまくいきます！たまたま、std::pair<T&,U&> からの変換があります。 std::pair<T,U> へ — ただし、落とし穴があります:T の場合にのみ機能します そして U コピー可能です！そうでない場合でも、コピーが *it を使用するときに期待される動作ではないことは明らかです const 参照を初期化します。 T の場合 または U コピーするのにコストがかかり、期待するパフォーマンスや動作が得られず、unique_ptr の場合 まったくコンパイルされません。 🙁

イテレータの参照型が const ValueType<I>& に変換可能であることを要求する 拘束しすぎです。では、これら 2 つのタイプの関係について、どのような有用なことを言えますか?

2.アルゴリズムの制約

Palo Alto TR のすべてのアルゴリズム署名は ValueType を使用します テンプレートを制約するために概念チェックで。たとえば、これは for_each の制約付き署名です。 :

template<InputIterator I, Semiregular F>
    requires Function<F, ValueType<I>>
F for_each(I first, I last, F f);

C++ の概念に慣れていない場合、1 行目と 2 行目は次のようになります:first と last InputIterator の要件を満たす必要があります コンセプト、F Semiregular でなければなりません (これについては詳しく説明します)、イテレータの値の型の 1 つの引数で呼び出せる必要があります。

次のようなコードを想像してみてください:

// As before, v1 and v2 are vectors of ints:
auto z = view::zip( v1, v2 );
// Let Ref be the zip iterator's reference type:
using Ref = decltype(*z.begin());
// Use for_each to increment all the ints:
for_each( z.begin(), z.end(), [](Ref r) {
    ++r.first;
    ++r.second;
});

これは完全に合理的に思えます。ラムダは pair<int&,int&> である zip ビューの参照型のオブジェクトを受け入れます 、そして最初と 2 番目のメンバーの両方をインクリメントします。 しかし、これは型チェックを行いません。 なぜですか?

概念チェックを思い出してください:Function<F, ValueType<I>> . for_each に渡す関数 イテレータの値型のオブジェクトで呼び出せる必要があります .この場合、値の型は pair<int,int> です .それから、関数が期待する型 (pair<int&,int&>) への変換はありません。 .残念。

pair<int,int>& を取るようにラムダを変更すると の場合、概念チェックはパスしますが、テンプレートは正しくインスタンス化できません。典型的な for_each を見ればその理由は簡単にわかります 実装:

template<InputIterator I, Semiregular F>
requires Function<F, ValueType<I>>
F for_each(I first, I last, F f) {
    for(; first != last; ++first)
        f(*first);
    return f;
}

ラムダは *first で呼び出されます タイプ pair<int&,int&> を持つもの 、しかしそれは pair<int,int>& に変換されません .ガッ!!!

最も厄介なのは、上で書いたコード (参照型を受け取るラムダのコード) が、単に requires Function<F, ValueType<I>> を削除するだけで問題なく動作することです。 制約。明らかに、制約、概念、または私たちの期待に何か問題があります.

この問題は zip に固有のものではないことを付け加えておきます。 見る。プロキシ参照タイプを持つシーケンスには、この問題 vector<bool> があります。 含まれています。これらの制約を既存のアルゴリズムに平手打ちすると、現在機能している一部のコードが機能しなくなり、唯一の「修正」は標準アルゴリズムの使用を停止することになります。 🙁

3. Move-Only 型の順列性

残念ながら、問題はそれだけではありません。 sort アルゴリズムはシーケンスがpermutableである必要があります;つまり、その要素をシャッフルできる必要があります。また、移動のみの型をサポートする必要があるため、シーケンスのイテレータは間接的に移動可能にする必要があります。 .パロアルト TR はそれについて次のように述べています。

しかし、*in の場合はどうなるでしょうか プロキシを返しますか?次に move(*in) プロキシが参照するオブジェクトではなく、プロキシを移動しています。 zip ビューを並べ替える場合、(一時的な) pair<T&,U&> を移動しようとしています。 pair<T&,U&> に .問題 (1) と同様に、移動のみのタイプではまったく機能しません。しかし、おそらくそれより前の sort で失敗するでしょう。 問題（2）のため、句が必要です。なんてこった！

まとめ、とりあえず…

パロアルト TR は ForwardIterator という過剰な制約要件を解除しますが、 s が実際の参照を返す場合、プロキシ イテレータの問題は残ります。一方では、プロキシ イテレータは問題ないと言っています。一方、いくつかの興味深いプロキシ イテレータは Iterator をモデル化できません。 概念またはアルゴリズムの制約を満たすか、適切なセマンティクスまたはパフォーマンス特性を持たないもの。選択肢は何ですか?

オプション (1) はあまり好きではありません。真の参照を返すことができない興味深い前方反復子が多すぎます。オプション (2) については、次の投稿で説明する予定の基本的なアイデアがいくつかあります。オプション (3) を除外することはできませんが、IANALL (私は言語弁護士ではありません) であり、何が関係するのかわかりません。 C++17 が形成され、Concepts Lite TR が最終的に PDTS ステータスに到達したことは明らかです 、範囲化、概念化された STL が進行中です。このことについて決定を下すのは 今 です。 .

"\e"