安全にイテレータ演算をするには？

Question

C++ のイテレータは演算ができますが、例えば以下のようなコードを書くと、簡単に無限ループになってしまいます。

#include <vector>
#include <iostream>

int main()
{
        std::vector<int> a = {1, 2, 3};
        for (auto it = a.begin(); it != a.end(); std::advance(it, 2)) {
                std::cout << *it << std::endl;
        }
        return 0;
}

原因は、イテレータ演算を安全に扱う方法が無いせいだと思うのですが、普通はどのように行うのでしょうか。
つまり、

1. イテレータが範囲外の位置を指しているかどうかを判定する方法が無い
2. イテレータが範囲外の位置を指さないように演算する方法が無い

ということが原因だと思うのですが、これらをイテレータの機能で解決する方法はありますか？
それとも、範囲外にならないようにプログラマーが気をつけてコーディングするしか回避方法がないのでしょうか。

Answer 1

こんにちは。

原因は、イテレータ演算を安全に扱う方法が無いせいだと思うのですが、普通はどのように行うのでしょうか。

残念ですが「普通」はプログラマが注意深く制御するしかないと思います。
だから、個人的にはイテレータはどうも苦手です。インデックスなら大小比較を使えるので安心感があるんですよね。

でも、Rangeが来たら改善する筈です。
以前C++：コンテナに入って無かったことを示すiteratorについてと言う質問をしたのですが、その時yohhoyさんから頂いた回答でRangeについて情報を頂きました。

Comments

[yuki23]

ご回答ありがとうございます。
Range はイテレータよりも良さそうですが、質問文の例のような複雑な状況では使えなさそうですね。

[Chironian]

イテレータの最大の問題は単独ではend()にアクセスできないことと思います。
逆にRangeはend()を内蔵するのでできると思いますよ。

boostは既にrangeを実装しています。boostの仕様が標準規格に取り入れられることも少なくないようですので、参考になると思います。
boost_1_60_0\boost\range\iterator_range_core.hppに関連コードがありました。void drop_front(difference_type n)を見ると、BOOST_ASSERT()で範囲外チェックしてからstd::advance()してます。
従って、少なくともデバッグ・モードでは特殊なことをしなくてもチェックしてくれそうです。

[yuki23]

> イテレータの最大の問題は単独ではend()にアクセスできないことと思います。
> 逆にRangeはend()を内蔵するのでできると思いますよ。
具体的にはどういうことでしょうか？
例えば、質問文の例ならどのように実装しますか？

> 従って、少なくともデバッグ・モードでは特殊なことをしなくてもチェックしてくれそうです。
yohhoy さんの回答にもありますが、デバッグモードだけチェックするなら STL でも多くのライブラリでやっていますね。

[Chironian]

> 例えば、質問文の例ならどのように実装しますか？

イメージ的には例えば下記ができるようになることを期待しています。releaseモードでもdrop_front()で例外です。

std::vector<int> a = {1, 2, 3};
for (auto&& ir=begin(a); !ir.empty(); ir.drop_front(2)) {
　　std::cout << ir.front() << std::endl;
}

上記はイテレータ単独では無理ですがレンジなら単独で可能です。
もし、標準規格がサポートしなかった時は、rangeを派生してdrop_front()をオーバーライドすれば比較的簡単に作れると思います。必要ならdrop_front()でend()を越えたらempty()にする等の実装も可能でしょう。

いずれにしても、現在はプログラマが頑張る（注意深く作るか、簡単に使えるクラスを作るのどちらか）しかないと言う結論が変わるわけではありませんし、この辺で。

Answer 2

それとも、範囲外にならないようにプログラマーが気をつけてコーディングするしか回避方法がないのでしょうか。

はい。

C++言語は基本的な設計方針として「ゼロ・オーバーヘッド原則(Zero-Overhead Principal)」を掲げています。その気になれば"安全な"イテレータを実装することも可能ですが、安全性検査のためにあまりにオーバーヘッド（利用メモリと計算量の双方）が大きくなってしまうため、標準ライブラリとしては提供されません。

これらをイテレータの機能で解決する方法はありますか？

上記が建前ですが、プログラマは万能ではないためどうしてもバグの温床になります。各種C++標準ライブラリでは「デバッグモード」の一種として"安全な"イテレータを提供しており、デバッグ時にはこれらを利用してください。

• GCC：libstdc++, Debug Mode
• Clang：libc++ debug mode status
• VisualC++：反復子のデバッグのサポート

Answer 3

Chironianさんの意見に全面的に同意しますが、いくつか追記。
イテレータは、何種類もあるデータ構造を同じような手法で取り扱えるようにしてますが、基本的にはほぼ｢ポインタ｣で、扱いは慎重にされるべきものなのだと私は考えています。標準コンテナのイテレータは、ライブラリとして(安全性を犠牲に)最高速度を出せるよう設計されているので、どうしても扱いは気を付ける必要があります。
が、標準コンテナのイテレータに限らなければ、安全性を高めた(実行速度を犠牲に)イテレータは作れますし、質問者さんの例であれば、advance関数を安全に再実装することで解決できます。

Comments

[yuki23]

ご回答ありがとうございます。
やはりプログラマーが気をつけるしか無いのでしょうかね。
速度が重要なのはわかりますが、速度が重要でないアプリケーションでは、速度を犠牲にして安全性を高める方法も用意していただかないと、使う側としては困ってしまいますね。

> が、標準コンテナのイテレータに限らなければ、安全性を高めた(実行速度を犠牲に)イテレータは作れますし、質問者さんの例であれば、advance関数を安全に再実装することで解決できます。
イテレータを作るほどの手間を掛けるほど多用するわけでもないので、安全なイテレータ演算関数を作成して、メンバーに使用を徹底させてお茶を濁すのが落とし所になりそうです。

Answer 4

C++11が使えるのであれば、範囲forを使えるか検討したほうがいいでしょう。
C++11じゃなくてもboostライブラリが使えるのであれば、BOOST_FOREACHマクロを使う手もあります。

Comments

[yuki23]

申し訳ありませんが、範囲forを使って何をどのように解決できるということでしょうか？
例えば、質問文の例ならどうしますか？

[PineMatsu]

int i = 0;
for(auto n : a) {
if ((i % 2) == 0) {
cout << n << endl;
}
i++;
}

な感じですかね。i の様なループ変数を使う必要があるのでスマートさには欠けるかもしれませんが、1個飛ばしに処理していることに変わりはありません。
Chironianさんの言うようにRangeを使ったほうがスマートになるかも。
詳しくは↓を参照ください。
http://qiita.com/rinse_/items/f00bb2a78d14c3c2f9fa

[PineMatsu]

ちなみにBoost.Rangeを使えばこのように書けます。

#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/adaptor/strided.hpp>

vector<int> ar = { 1, 2, 3 };

for_each(ar | adaptors::strided(2), [](int n) {
cout << n << endl;
});

インクルードと必要なものしか書いていないので動かす時はnamespaceなど適当に追加してください。

[PineMatsu]

範囲forとboost.rangeのadapterなら

for(auto n : a | adaptors::strided(2)) {
cout << n << endl;
}
とも書けます。