【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, 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() の前要素を指す)
広告