双方向イテレータのoperator <をどのように定義できますか？

Question

双方向イテレータのオペレータ<はどのように定義できますか？ （リスト::イテレータ）

（私はリストではなく、ベクターを使用したいと思います。）

Answer 1

インポッシブル。 endまで歩く必要があります。そのためにはlist::iteratorでコード化されていないlist（起源）を知る必要があります。

（この目的のためには、listまたは起点をコンストラクタ引数として使用する関数オブジェクトを作成することができます。あるイテレータが他のイテレータより小さいかどうかを調べるには、O（n）時間がかかります。あなたは、このような比較を行うためには、リストの開始および/または終了を知る必要があるだろうので

Answer 2

あなたはこれを行うことはできません。ランダムアクセスイテレータのみがoperator<を定義します。

Answer 3

あなたはそれを直接行うことはできませんが、std::distance(x.begin(), it1)とstd::distance(x.begin(), it2)を計算し、それらを比較することができます。リストにはランダムアクセスがないので、リスト全体をトラバースする必要があるため、そのようなクエリの価格を支払わなければならないと予想されます。

---

編集：両方のイテレータがリストの終わり近くにある場合は、これはうまく機能しません。あなたは基本的にfwd1/rev1とfwd2/rev2、それぞれに2つのコピーを続けるだろう、とあなたはrev*をデクリメント

[ .... <-- it1 --> .... <-- it2 --> .... ] 

：あなたはより多くの空想を取得したい場合は、両方のイテレータから外側に向かって移動し、いくつかの探検アルゴリズムを書くことができますあなたがx.begin()を打ち、x.end()に達するまでfwd*イテレータを進めるまで、イテレータを繰り返します。イテレータのペアが均等に分散されている場合、これはおそらくより良い実行時間を持つでしょう。 ++(list.end())を想定

Answer 4

は未定義の動作ではなく、list.end()に等しい、方法があります。しかし、私はこの仮説についてはわかりません。

有効な場合は、簡単なアルゴリズムを定義して、必要な結果を得ることができます。