std::vectorやstd::string等のコンテナを逆向きに走査する方法を紹介します。リストやコンテナに対して、逆方向によるループ処理を実現することが可能になります。後半では逆イテレータへの対応方法も解説します。
逆イテレータの使い方
reverse_iterator(逆反復子)を返す特殊なメンバ関数(rbegin
, rend
)を使用します。イテレータを進める際には通常のインクリメント演算子++
の利用が可能です。
std::vector<std::string> v = {"a", "b", "c"};
for (auto i = v.rbegin(), e = v.rend(); i != e; ++i) {
printf("%s", i->c_str()); // "cba"
}
std::for_each(v.rbegin(), v.rend(), [](auto&& s) {
printf("%s", s.c_str()); // "cba"
});
このように簡単に逆ループの実現が可能になります。
配列の場合はフリー関数版のrbegin
, rend
を利用します。
int a[] = {1, 2, 3};
std::for_each(std::rbegin(a), std::rend(a), [](int v) {
printf("%i", v); // "321"
});
逆イテレータの注意点
rbeginメンバ関数/rbegin関数の戻り値は末尾を指すイテレータとなりますが、この逆イテレータが指す値はendの物とは異なる点に注意して下さい。rendとbegin関数にも同様の注意が必要です。
std::string s = "abc";
printf("%c", *s.begin()); // "a"
printf("%c", *s.end()); // "\0"
printf("%c", *s.rbegin()); // "c" (end() の前要素を指す)
printf("%c", *s.rend()); // "" (begin() の前要素を指す)
逆イテレータの自作方法
逆順イテレータへの対応方法を解説します。
逆イテレータに対応するためにはrbegin
関数とrend
関数の実装が必要になりますが、既存のbegin/end関数を再利用することができるため、作り方はとても簡単です。
以下のように既存のイテレータをreverse_iterator
クラスでラップします。
struct Range {
int location, length;
Iterator begin() { return {location}; }
Iterator end() { return {location + length}; }
auto rbegin() { return std::reverse_iterator<Iterator>(end()); }
auto rend() { return std::reverse_iterator<Iterator>(begin()); }
};
このようにrbeginではend、rendではbeginをラップする形で実装します。なおstd::reverse_iterator<Iterator>(value)
形式の代わりにヘルパー関数を用いてstd::make_reverse_iterator(value)
形式で記述することも可能です。
なおラップ前のイテレータは事前に、型特性クラスiterator_traits
に準拠しておく必要があります。そのためにはiterator
クラスの継承がもっとも手っ取り早い方法です(ただしiteratorはC++17で非推奨になる予定)。
struct Iterator : std::iterator<std::input_iterator_tag, int> {
int i;
Iterator(int i) : i(i) {}
int& operator*() { return i; }
Iterator& operator++() { ++i; return *this; }
Iterator& operator--() { --i; return *this; }
bool operator!=(const Iterator& v) { return i != v.i; }
};
デクリメント演算子に対応していない場合はIterator& operator--()
演算子を自前で定義して下さい。
std::iteratorはC++17で非推奨になるため注意して下さい。自前でiterator_traitsに準拠するための方法については以下のページが参考になります。
iterator_traitsに準拠する方法 #メンバ型の宣言
以上で逆向き走査が可能になりました。
auto r = Range{2, 4};
std::for_each(r.rbegin(), r.rend(), [](auto i) {
printf("%d", i); // "5432"
});
printf("%d", *r.begin()); // "2"
printf("%d", *r.end()); // "6"
printf("%d", *r.rbegin()); // "5" (end() の前要素を指す)
printf("%d", *r.rend()); // "1" (begin() の前要素を指す)