【C++】逆イテレータ – コンテナを逆向きに走査する方法と作り方


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関数は末尾を指すイテレータとなりますが、イテレータが指す値はendの物とは異なる点に注意して下さい。rendとbegin関数にも同様の注意が必要です。

std::string s = "abc";

printf("%c", *s.rbegin()); // "c" (end()   の前要素を指す)
printf("%c", *s.rend());   // ""  (begin() の前要素を指す)
printf("%c", *s.begin());  // "a"
printf("%c", *s.end());    // "\0"

std::for_each(s.rbegin(), s.rend(), [](auto c) {
  printf("%c", c); // "cba"
});

逆イテレータの自作方法

逆順イテレータへの対応方法を解説します。

逆イテレータに対応するためには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をラップする形で実装します。

なおラップ前のイテレータは事前に、型特性クラスiterator_traitsに準拠しておく必要があります。そのためにはiteratorクラスの継承がもっとも手っ取り早い方法です。

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--()演算子を自前で定義して下さい。

以上で逆向き走査が可能になりました。

auto r = Range{2, 4};
std::for_each(r.rbegin(), r.rend(), [](auto i) {
  printf("%d", i); // "5432"
});

printf("%d", *r.rbegin()); // "5" (end() の前要素を指す)
printf("%d", *r.rend());   // "1" (begin() の前要素を指す)
printf("%d", *r.begin());  // "2"
printf("%d", *r.end());    // "6"

広告