ランダムアクセスイテレータの operator+ の挙動について

Question

疑問点

C++ のランダムアクセスイテレータを幾つか進めるとき、
終端を越えることはありえるのでしょうか？

コード

たとえば以下のコードです。

std::vector<int> vs = { /* 何か値が入っている */ };
auto it = vs.cbegin();
auto end = vs.cend();
while (it != end) {
  if (*it % 2 == 0) break;
  it += 2; // ← ここ！
  // it + 1 == end のとき it + 2 はどうなるの？
}

コメントに書いた通りですが、規格や STL の動作で、
ランダムアクセスイテレータが末端を越えるような末端を越えるような操作を行った場合、
規格か何かで該当のイテレータがどうなるかは規定されているのでしょうか？

Answer 1

C++ のランダムアクセスイテレータを幾つか進めるとき、終端を越えることはありえるのでしょうか？

あらゆるイテレータは、コンテナの「終端要素の次(end())」を指すことは可能ですが、それより後ろの位置を指すことは出来ません。

std::vector<int> v = {1, 2, 3};

auto it = v.begin();
it += 2;

 begin()      end()
 |            |
 V            V
+---+---+---+...+
| 1 | 2 | 3 |   .
+---+---+---+...+
          ^
          |
          it

上図の状態から it += 2; を 行なってはいけません。2つ進めた後の it は 「end()の次」を指すように思えるでしょうが、C++ライブラリがそのように振る舞う 保証はありません。

---

ランダムアクセスイテレータが末端を越えるような末端を越えるような操作を行った場合、規格か何かで該当のイテレータがどうなるかは規定されているのでしょうか？

C++言語仕様上は 未定義の動作(undefined behavior) と規定されています。つまりそのようなプログラムの実行結果はなんら保証されません。偶然動くこともあり得えますし、実行時にクラッシュすることもあり得ます。

Comments

[pute]

ありがとうございます！
> C++言語仕様上は 未定義の動作(undefined behavior) と規定されています。
これが知りたかったことでした。

Answer 2

こんにちは。

C++は基本的に性能を落とさない処理と安全な処理が両立しない場合、前者を取る言語です。
イテレータも同様ですので、基本的に有効でない範囲を指していないことのチェックは行いません。
更に残念ながら、そのチェックを行うような機能も定義されていません。

必要であれば自分で作ることも可能です。範囲外なら例外を投げると安心ですね。
ただ、範囲外チェックをするためにはイテレータの内部で「範囲」を保持しないといけないのでイテレータのコピーが重くなります。安易にコピーしないようコピー禁止するとか遅くても良いと割り切る等あれこれ考えた方がより良いプログラムになります。

boostに入っているrangeを使うというのも手です。

Comments

[pute]

> 基本的に有効でない範囲を指していないことのチェックは行いません
なるほどー。
ということは、今回の場合 it != end でなく it < end と書くべきですね。
ありがとうございます。

[Chironian]

> it != end でなく it < end と書くべきですね。
ランダムアクセス・イテレータには大小比較演算子が定義されているので大丈夫です。
http://www.cplusplus.com/reference/iterator/RandomAccessIterator/

しかし、その他のイテレータには定義されていない場合が多いので、必ずしも好ましいとは限りません。他のコンテナへ変更したくてもし辛くなりますので。
http://www.cplusplus.com/reference/iterator/BidirectionalIterator/

[yumetodo]

MSVC独自拡張でstdext::checked_iteratorというものがあり・・・

Answer 3

参照先が有効であることを保証するのはプログラマの責任ですね。例えば、配列のポインタはランダムアクセスイテレータの要件を満たしますが、確保したメモリの外側の読み込み/書き込みは何が起きるか分からないですし。

Comments

[pute]

参照先についてはそうですね。たとえば *((vector<int>{}).end()) が不正だということは分かります。
気になっているのはイテレータ自体の有効性のことで、↑のコードを以下のように書くのは嫌だなあ、というのが質問した動機です。
どうでしょうか？

std::vector<int> vs = { /* 何か値が入っている */ };
auto it = vs.cbegin();
auto end = vs.cend();
while (it != end) {
if (*it % 2 == 0) break;
// ↓ここを it += 2 と書いていいのかな？
it++;
if (it != end) it++;
}

[tachikoma]

要素数が偶数であることを保証出来るなら書いても良いような気がします。奇数だとend条件にたどり着かず…になりますし。Chironianさんが紹介して下さってるboost/rangeのstridedを使えばやりたいことが出来そうですね。

[pute]

そういうことですね。ありがとうございます！