イテレータ++、パート3

これは、プロキシ イテレータに関するシリーズの 4 回目で最後の投稿です。 、既存の STL イテレータ概念階層の制限、およびそれに対して何ができるか。最初の 3 つの投稿では、プロキシ イテレータの問題、それらの要素を交換および移動する方法、およびイテレータとは何かを厳密に定義する方法について説明しています。

今回は、最後の問題に焦点を当てます。高階アルゴリズムを適切に制約して、プロキシ イテレータと連携させる方法です。

独自のアルゴリズム

この投稿では、特に 1 つのアルゴリズムと、それがプロキシ イテレータとどのように相互作用するかを見ていきます:unique_copy .これがそのプロトタイプです:

template <class InIter, class OutIter, class Fn>
OutIter unique_copy(InIter first, InIter last,
                    OutIter result, Fn binary_pred);

このアルゴリズムは、比較のための述語を使用して、等しい隣接要素をスキップして、ある範囲から別の範囲に要素をコピーします。

次の呼び出しを検討してください:

std::stringstream sin{"1 1 2 3 3 3 4 5"};
unique_copy(
  std::istream_iterator<int>{sin},
  std::istream_iterator<int>{},
  std::ostream_iterator<int>{std::cout, " "},
  std::equal_to<int>{} );

これは sin から一連の int を読み取ります 一意のものを cout に書き込みます .シンプルですね。このコードは以下を出力します:

1 2 3 4 5

unique_copy をどのように実装するか少し考えてみてください .まず、ストリームから int を読み取ります。次に、それを他のストリームに書き出します。次に、別の int を読み取ります。あなたはそれを最後のものと比較したい。ああ! 保存する必要があります 最後の要素をローカルに保存して、比較を行うことができます。興味深い。

STL のある部分がどのように機能するかを本当に理解したいときは、古い SGI STL でその機能がどのように実装されているかを調べます。このコードベースは非常に古いため、最初は羊皮紙に書かれ、修道士によって編集された可能性があります。しかし、これは私が知っている中で最もクリーンでわかりやすい STL 実装であり、一読することをお勧めします。ここでは、読みやすくするためにいくつかの編集を行っていますが、unique_copy の関連部分です。 :

// Copyright (c) 1994
// Hewlett-Packard Company
// Copyright (c) 1996
// Silicon Graphics Computer Systems, Inc.
template <class InIter, class OutIter, class Fn,
          class _Tp>
OutIter
__unique_copy(InIter first, InIter last,
              OutIter result,
              Fn binary_pred, _Tp*) {
  _Tp value = *first;
  *result = value;
  while (++first != last)
    if (!binary_pred(value, *first)) {
      value = *first;
      *++result = value;
    }
  return ++result;
}

(呼び出しコードは first != last 、これは、このコードがそのチェックをスキップする理由を説明しています。そして奇妙な _Tp* 引数は、反復子の値の型を推測できるようにするためのものです。修道士は特性クラスをコンパイルできませんでした。) value に注意してください。 11 行目のローカル変数。特に 14 行目に注意してください。ここで value を渡します。 とリファレンス binary_pred へ .重要なので覚えておいてください!

陰謀は深まる

おそらく unique_copy についてもっと知っているでしょう あなたが今までに気にかけたよりも今。なぜ私はそれを持ち出すのですか?それは非常に問題だからです プロキシ イテレータで使用する場合。 vector<bool>::iterator を渡そうとするとどうなるか考えてみてください 上記の __unique_copy に 関数:

std::vector<bool> vb{true, true, false, false};
using R = std::vector<bool>::reference;
__unique_copy(
  vb.begin(), vb.end(),
  std::ostream_iterator<bool>{std::cout, " "},
  [](R b1, R b2) { return b1 == b2; }, (bool*)0 );

これはすべき cout に「真」と「偽」を書き込む 、しかしコンパイルされません。なんで?ラムダは vector<bool> の 2 つのオブジェクトが渡されることを期待しています のプロキシ参照タイプですが、__unique_copy の方法を覚えておいてください 述語を呼び出します:

if (!binary_pred(value, *first)) { /*...*/

bool& です そして vector<bool>::reference .痛い!

それらはただの bool であり、bool は安価にコピーできるため、値で判断してください。問題が解決しました。確かに、しかし、それらが bool でない場合はどうなるでしょうか?コピーするのにコストがかかる一連のものをプロキシした場合はどうなるでしょうか?問題は難しくなりました。

したがって、これ以上優れたものがないため (ブール値をコピーするのにコストがかかるふりをしますが、ご容赦ください)、次のようにラムダを記述します:

[](bool& b1, R b2) { return b1 == b2; }

ユク。ここで、このコードを別の STL に移植し、逆の引数で述語を呼び出すと、コードが再び壊れます。 🙁

私の要点は次のとおりです。プロキシ イテレータをミックスに導入すると、アルゴリズムで使用する述語を定義する方法が明確ではなくなります。アルゴリズムは、参照を使用して述語を呼び出す場合もあれば、値を使用する場合もあれば、unique_copy のように述語を呼び出す場合もあります。 — 両方が混在しています。 sort のようなアルゴリズム 最初に述語を 1 つの方法で呼び出してから、後で別の方法で呼び出します。 Vive la différence!

一般的な修正

この問題には、C++14 の非常に単純な解決策があります:ジェネリック ラムダです。上記のコードは、次のように簡単に、移植可能に、最適に書くことができます:

std::vector<bool> vb{true, true, false, false};
std::unique_copy(
  vb.begin(), vb.end(),
  std::ostream_iterator<bool>{std::cout, " "},
  [](auto&& b1, auto&& b2) { return b1 == b2; } );

何があっても unique_copy この述語をスローすると、優雅さとスタイルで対応します。

それでも。多態的な関数オブジェクトは大きなハンマーのように感じます。一部の設計では、std::function のようなモノモーフィック関数が必要です。 C とのインターフェイスが必要な場合は、おそらく関数ポインタです。私の言いたいことは、STL が 要求 するのは間違っていると感じるということです。 正確性のための多相関数の使用。

問題を言い換えると、unique_copy の単形述語の書き方がわかりません。 value_type& のためにシーケンスがプロキシされるとき reference に変換できない場合があります 、および reference value_type& に変換できない場合があります .他のタイプ、他の参照のようなものがあればいいのに タイプ、両方とも…に変換できます

しかし〜がある!私の前回の投稿を読んだら、common_reference についてご存知でしょう 、他の 2 つの参照がバインド (または変換) できる参照のような型 (おそらくプロキシ) を計算する特性。プロキシ イテレータがイテレータの概念をモデル化するために、イテレータの reference が必要でした。 タイプとその value_type& 共通の参照を共有する必要があります。当時、私は、そのようなタイプの唯一の用途は概念チェック機構を満たすことだとほのめかしました。しかし、それには別の用途があります。共通参照は、単相述語を定義するために使用できる型です。

次の特性を提供する将来の STL を想像できます:

// An iterator's common reference type:
template <InputIterator I>
using iterator_common_reference_t =
  common_reference_t<
    typename iterator_traits<I>::value_type &
    typename iterator_traits<I>::reference>;

この特性を使用して、述語を次のように記述できます。

using I = vector<bool>::iterator;
using C = iterator_common_reference_t<I>;
auto binary_pred = [](C r1, C r2) {
  return r1 == r2;
};

これは確かに、述語を定義するためだけにかなりのフープジャンプです。しかし、私が紹介するのは新しい複雑さではありません。 unique_copy そして vector<bool> 1998年以来そこにいます.私は彼らがうまくプレイできるように努めています.

そして、これらのフープをジャンプする必要はほとんどありません。次のすべてが当てはまる場合にのみ、共通の参照型を使用する必要があります。値が望ましくない、および (c) 何らかの理由で多相関数を使用することが不可能または非現実的である。それほど頻繁ではないと思います。

アルゴリズムの制約

つまり、エンドユーザーの視点からは物事がどのように見えるかです。アルゴリズム作成者の観点から、反対側からはどのように見えるでしょうか?特に、unique_copy をどのようにすべきか Concepts Lite を使用してアルゴリズムを制約してみたらどうですか?

Palo Alto TR はそれに挑戦します。 unique_copy を制約する方法は次のとおりです。 :

template <InputIterator I, WeaklyIncrementable Out,
          Semiregular R>
requires Relation<R, ValueType<I>, ValueType<I>> &&
         IndirectlyCopyable<I, Out>
Out unique_copy(I first, I last, Out result, R comp);

そこには多くのことが起こっていますが、関連する部分は Relation<R, ValueType<I>, ValueType<I>> です .つまり、タイプ R 範囲の値の型の引数を受け入れる同値関係でなければなりません .これまで説明してきたすべての理由から、vector<bool> のようなプロキシ範囲を扱う場合には機能しません。 .

では、制約はどうあるべきか?多分それは Relation<R, ValueType<I>, Reference<I>> であるべきです ?でもダメ、unique_copy 常にではない 値をローカルにコピーする必要があります。入力反復子も出力反復子も ForwardIterator をモデル化しない場合のみ。だから時々 unique_copy pred(*i,*j) のような述語を呼び出します 時には pred(value, *i) のように .制約は、それに対応するのに十分一般的でなければなりません.

イテレータの共通参照型も使用できるのではないでしょうか? unique_copy を制約するとどうなるでしょうか このように:

template <InputIterator I, WeaklyIncrementable Out,
          Semiregular R>
requires Relation<R, CommonReferenceType<I>,
                     CommonReferenceType<I>> &&
         IndirectlyCopyable<I, Out>
Out unique_copy(I first, I last, Out result, R comp);

この制約は、呼び出し元に次の約束をします。「CommonReferenceType<I> 型のオブジェクトのみを渡します。 述語に。しかし、それは嘘です。 unique_copy ではありません 実際に実装されています。引数を述語に渡す前にキャストすることで、この約束を果たすように実装を変更できますが、それは醜く、潜在的に非効率的です。

本当に、述語が値と参照の可能なすべての組み合わせで呼び出し可能であることを確認する必要があると思います。それは残念ですが、これ以上の選択肢はありません。いくつかの剪定を行った上で、これらは必須であると私が考える十分に重要なチェックです:

Relation<R, ValueType<I>, ValueType<I>> &&
Relation<R, ValueType<I>, ReferenceType<I>> &&
Relation<R, ReferenceType<I>, ValueType<I>> &&
Relation<R, ReferenceType<I>, ReferenceType<I>> &&
Relation<R, CommonReferenceType<I>, CommonReferenceType<I>>

実装者として、私はそのすべてを書きたくないし、ユーザーはそれを読みたくないので、きれいにまとめることができます:

IndirectRelation<R, I, I>

目にも脳にも負担がかかりません。

興味深い間接的な呼び出し可能な意味

要するに、アルゴリズムが関数、述語、または関係を取るすべての場所で、 IndirectFunction のような制約を追加する必要があると思います 、 IndirectPredicate 、または IndirectRelation .これらの概念では、関数が値と参照の外積で呼び出し可能であることが必要であり、関数が共通の参照型の引数でも呼び出し可能であるという追加の要件があります。

これは非常に厳密に思えるかもしれませんが、非プロキシ イテレータの場合、正確に ゼロ を追加します 新しい要件。また、プロキシ イテレータの場合でも、いずれにせよ必ず true でなければならないことをコードで記述しているだけです。物事を難しくするのではなく、共通の参照型はそれらを より簡単に します。 :述語が共通の参照型によって引数を取る場合、すべてのチェックが成功することが保証されます。

共通の参照型を使用すると効率が悪い可能性があります。たとえば、bool& 間の一般的な参照型 と vector<bool>::reference バリアント型である可能性が高いです。その場合、述語が共通参照によって引数を取ることを望まない場合があります。代わりに、ジェネリック ラムダを使用するか、必要なオーバーロードを含む関数オブジェクトを定義します。概念チェックにより、オーバーロードを忘れていないかがわかるため、コードが正しく移植可能であることが保証されます。

まとめ

それが理論です。これらすべてを Range-v3 ライブラリに実装しました。 sortできるようになりました zip unique_ptr の範囲 秒。とてもクールです。

簡単に言うと、STL がプロキシ イテレータを完全にサポートするために必要な変更は次のとおりです。

<オール>
  • アルゴリズムは iter_swap を使用する必要があります 要素を交換する必要があるときはいつでも一貫して。 iter_swap 文書化されたカスタマイズ ポイントである必要があります。
  • iter_move が必要です カスタマイズ ポイントを使用して、要素をシーケンスから外したり、シーケンスに戻したりできるようにします。これにより、イテレータに新しい rvalue_reference が与えられます 関連型。
  • 新しい common_reference が必要です common_type のような特性 、ユーザー定義型に特化できます。
  • すべてのイテレータは value_type であることを保証する必要があります と reference 関連付けられた型は、共通の参照を共有します。 value_type も同様 /rvalue_reference 、および reference の場合 /rvalue_reference .
  • IndirectFunctionが必要です 、 IndirectPredicate 、および IndirectRelation 上記のような概念。高次のアルゴリズムは、それらに制約されるべきです。
  • エンド ユーザーの観点からは、多くの変更はありません。すべての既存のコードは以前と同じように機能し、現在有効なすべての反復子は将来も引き続き有効です。 vector<bool> などの一部のプロキシ イテレータ イテレータの概念をモデル化するためにいくつかの小さな変更が必要になりますが、その後、これらのイテレータは初めて他のすべてのイテレータと対等な立場にあります。プロキシ シーケンスを処理するコードでは、common_reference を使用する必要がある場合があります 述語を定義するとき、または代わりに汎用ラムダを使用する必要がある場合があります。

    それだけです。私の知る限りでは、これはプロキシ イテレータの問題に対する最初の包括的な解決策です。この問題は、私たちが最初から抱えていた問題であり、範囲ビューの導入によってさらに悪化することが約束されています。確かに多少の複雑さはありますが、その複雑さは必要かつ本質的なものであるように思われます。正直なところ、それほど悪いことではないと思います。

    今後の方向性

    ここから先はわかりません。もう少し待って、より良い解決策がないかどうかを確認する予定です.プロキシ参照の可能な言語ソリューションについていくつかのつぶやきがありましたが、プロキシ反復子には固有の複雑さがあり、言語ソリューションがどのように役立つかは現時点では明らかではありません.

    私は現在、Ranges TS の最初のドラフトになると思われるものに取り組んでいます。その論文では、プロキシ イテレータの問題は扱いません。上記で提案した変更を提案する将来の論文を書くことは想像できます。その前に、委員会のメーリングリストで議論を始めて、人々の気持ちを確かめようとするでしょう。委員会のメンバーがこれを読んでいる場合は、お気軽に以下にコメントしてください。

    フォローしていただきありがとうございます。また、励みになり、示唆に富むコメントをお寄せいただきありがとうございます。最近、C++ の世界は急速に進んでいます。すべてを把握するのは大変です。皆さんが私と一緒にこれらの問題を探求するために多くの時間を割いてくれたことを嬉しく思います. <3

    いつものように、ここで説明されているすべてのコードは、github の range-v3 リポジトリにあります。

    "\e"