はじめに
C++を使い始め、STLのコンテナやアルゴリズムも活用するようになってきた段階で、ある日、コンテナ内でとある条件を満たす最後の要素を探索したい、という状況が発生するかもしれません。
STLにはそのための専用のアルゴリズムは用意されていないため、「自分でカウンタをデクリメントしてコンテナ要素を逆順にたどりながら要素を探索するfor文を書くしかないか」と思ってしまうかもしれません。
しかし、標準ライブラリにはコンテナ要素を逆順にたどる機能がすでに用意されているので、これとアルゴリズムを利用して、最後の位置にある要素を探せるようになっています。
ただ、その仕組みはちょっと分かりにくい部分があるため、この記事でそれを解説したいと思います。
コンテナ内で最後に現れる要素を見つけるには
通常、std::vectorやstd::dequeなどシーケンスコンテナと呼ばれるコンテナから要素を探索するには、<algorithm>ヘッダーのstd::find()／std::find_if()関数を使用します。
これらの関数は、指定された範囲にある要素を先頭からたどって、最初に見つかった要素の位置を返すため、コンテナ内で最後に現れる要素を探索する目的では、（そのままでは）うまく使用できません。
std::find_end()という関数も存在しますが、これは指定した要素列が別の要素列の中で最後に見つかる位置を返すものなので、std::find_if()のように、ある条件を満たすような最後の要素を見つけるためには使用できません。
コンテナ内で最後に現れる要素を探索するには、std::reverse_iteratorというイテレータと、std::find()／std::find_if()関数を使用して、コンテナを逆順に探索するようにします。
コンテナの要素を逆順にたどるためのstd::reverse_iteratorは、コンテナのrbegin()／rend()／crbegin()／crend()メンバ関数によって取得できます。
また、std::rbegin()のような非メンバ関数版の関数も用意されています。これにコンテナを渡してもメンバ関数版と同様のイテレータを取得できます。この関数を使用すると、組み込み配列やstd::initializer_listからもstd::reverse_iteratorを取得できます。
下は、std::reverse_iteratorを使用して要素を探索するコードです。
std::vector<int> xs { 4, 7, 1, 1, 2, 2, 9, 5 };
// 値が1に等しい最後の要素を取得
// 4, 7, 1, 1, 2, 2, 9, 5
// *
auto it1 = std::find(xs.rbegin(), xs.rend(), 1);
// 値が4より小さい最後の要素を取得
// 4, 7, 1, 1, 2, 2, 9, 5
// *
auto it2 = std::find_if(xs.rbegin(), xs.rend(),
[](const auto& x) { return x < 4; });
// std::find()／find_if()の戻り値の型は、
// 引数に渡したイテレータの型になるので
// it1, it2の型はstd::reverse_iteratorになっている
// そのため、xs.begin()／xs.end()で返る通常のイテレータとは比較できない。
// xs.rbegin()／xs.rend()と比較するようにする。
if(it1 != xs.rend()) { std::cout << *it1 << std::endl; }
if(it2 != xs.rend()) { std::cout << *it2 << std::endl; }
1
2
このようにしてstd::reverse_iteratorで目的の要素を見つけることはできました。しかし、ここで取得したイテレータを使用する際にはすこし注意が必要です。
std::reverse_iteratorは、逆順にたどる動作をサポートするために、コンテナのbegin()／end()メンバ関数などから得られるイテレータをラップする仕組みになっています。
この仕組みのため、通常のイテレータとstd::reverse_iteratorは型が異なっており、これらを組み合わせて使用することや、通常のイテレータの代わりにstd::reverse_iteratorを使用することはできません。
if(it1 == xs.end()) { /* ... */ } // コンパイルエラー
xs.erase(it1, xs.end()); // コンパイルエラー
xs.erase(it1); // コンパイルエラー
std::reverse_iteratorから、元のイテレータの型としてイテレータを取得するには、base()メンバ関数を使用します。ただし、このメンバ関数から取得したイテレータの表す位置は、std::reverse_iteratorで要素を参照する位置とは一つずれたものになります。
// `std::reverse_iterator`が指す位置の値と
// base()メンバ関数で返るイテレータが指す位置の値を出力
std::cout << "rev : " << *it1 << ", base : " << *it1.base() << std::endl;
std::cout << "rev : " << *it2 << ", base : " << *it2.base() << std::endl;
rev : 1, base : 2
rev : 2, base : 9
このように、base()メンバ関数で取得したイテレータの位置が一つずれるのは、std::reverse_iteratorの特性が関係しています。
std::reverse_iteratorクラスについて
まず、std::reverse_iteratorがどういうものなのかについて、少し詳しく見ていきましょう。
std::reverse_iteratorは、以下のように、元のイテレータの型をテンプレート引数にとるクラステンプレートとして定義されています。（重要な部分のみ抜粋）
namespace std {
template<class Iterator>
class reverse_iterator
{
public:
explicit reverse_iterator(Iterator x);
constexpr Iterator base() const;
constexpr reference operator*() const;
constexpr pointer operator->() const;
// currentのoperator--()を呼び出し
constexpr reverse_iterator& operator++();
// currentのoperator++()を呼び出し
constexpr reverse_iterator& operator--();
protected:
Iterator current;
};
}
テンプレート引数に指定するイテレータの型は、Bidirectional Iterator（operator++()によって現在位置を一つ前進する操作に加えて、operator--()によって現在位置を一つ後退する操作が可能）という要件を満たしている必要があります。
コンストラクタで元のイテレータを受け取り、それをcurrentというメンバ変数に保持します。
そして、std::reverse_iteratorのoperator++()の定義で、元のイテレータであるcurrentのoperator--()を呼び出すように、逆にstd::reverse_iteratorのoperator--()の定義で、currentのoperator++()を呼び出すようにすることで、std::reverse_iteratorが進む方向とは逆順に元のイテレータを進める仕組みになっています。
ここでちょっと問題が生じます。
通常のイテレータでは、先頭要素を指すイテレータ $i$ と末尾要素の次の位置を指すイテレータ $j$ によって表される半開区間 $[i, j)$ で範囲を指定します。
この範囲指定が可能になるように、コンテナや配列で、要素列の末尾要素の次の位置、コンテナで言うとend()の位置までイテレータを前進させることは合法とされています。（もちろん、その進めた位置で、operator*()を呼び出してはいけません。これは未定義動作となります）
それに対して、要素列の先頭要素の前の位置、コンテナで言うとbegin()の一つ前の位置にイテレータを後退させる操作は未定義動作を引き起こします。
これを逆順にたどるときの目線で考えると、先頭要素の位置（通常の順でたどるときの末尾要素の位置）からは一つ前の位置へ後退でき、末尾要素の位置（通常の順でたどるときの先頭要素の位置）からはその次の位置に前進できないということになります。
このままでは、通常のイテレータと同じようにして範囲を表せないため、std::reverse_iteratorは、あらかじめイテレータの位置を、逆順にたどるときの目線で一つ前の位置へ後退させたものとし（つまり通常のイテレータと同じ範囲を動くようにする）、operator*()の呼び出しは、そのイテレータから一つ前進した位置（つまり、通常のイテレータに対しては、一つ後退させた位置）にある要素の参照を返す、という仕組みになっています。
reference reverse_iterator::operator*()
{
Iterator tmp = current; // もとのイテレータ
return *--tmp; // 一つ後退させた位置の値を返す
}
つまり、冒頭のサンプルにあるxsというコンテナに対しては、std::reverse_iteratorがたどる範囲は、下のテーブルの第4段目にはならず、第5段目のようになります。
| - | xs[0] | xs[1] | xs[2] | xs[3] | xs[4] | xs[5] | xs[6] | xs[7] | - |
|---|---|---|---|---|---|---|---|---|---|
| - | 4 | 2 | 1 | 1 | 2 | 2 | 9 | 5 | - |
| begin() | end() | ||||||||
| rend() | rbegin() |
そして、*rbegin()という呼び出しは、rbegin()の位置から逆順にたどるときの目線で一つ前進した位置、つまりxs[7]の参照を返します。
当然、*rend()という呼び出しは、xs[0]ではなく、逆順にたどるときの目線で一つ前進した位置、コンテナの範囲外にある値の参照を返そうとするため、未定義動作となります。
base()メンバ関数で取得したイテレータの位置がずれている理由
上記の通り、std::reverse_iteratorの現在位置（つまり、currentメンバ変数が指す位置）に対して、operator*()で参照する位置は一つずれたものになります。
base()メンバ関数は、currentメンバ変数をそのまま返すため、これによって、std::reverse_iteratorのoperator()*で参照する位置とbase()メンバ関数で返るイテレータの指す位置が、一つずれた場所の値となったのです。
std::cout << "rev : " << *it1 << ", base : " << *it1.base() << std::endl;
std::cout << "rev : " << *it2 << ", base : " << *it2.base() << std::endl;
rev : 1, base : 2
rev : 2, base : 9
ところで、base()メンバ関数でイテレータを返すときに、operator*()で参照している要素の位置になるように、イテレータの位置を一つ分自動的に補正してくれてもいい気がします。そうなっていないのはなぜでしょうか。
これについては、Effective-STLという書籍や、その著者が公開しているイテレータ関連のドキュメントに記載があり、std::reverse_iteratorで参照している位置に要素を挿入したい状況で自然になるようにするため、ということです。
しかし、要素を削除する状況では依然として位置を補正する必要があり、結局自然ではないケースが残ってしまっているため、個人的にはあまりいい理由付けにはなっていない気がします。
あまり深く考えず、「base()メンバ関数は、名前の通り、元にしているイテレータ（currentメンバ変数）をそのまま返すだけ。」というふうに捉えておくだけでいいと思います。
base()メンバ関数で取得したイテレータの位置を補正する
base()メンバ関数で取得したイテレータは一つ分ずれているので、std::reverse_iteratorのoperator*()で参照した要素を指す通常のイテレータを得るには、以下のような方法で、ずれた分を手動で補正します。（std::reverse_iteratorが、rend()に達していないかどうかを先に確認しておく必要があります。）
std::cout << "rev : " << *it1 << ", base' : " << *(++it1).base() << std::endl;
std::cout << "rev : " << *it2 << ", base' : " << *(++it2).base() << std::endl;
rev : 1, base' : 1
rev : 2, base' : 2
*--(it1.base())という方法もありますが、std::vectorクラスやstd::stringクラスのイテレータに対しては、この方法が使用できない可能性があります。
処理系によっては、std::vectorクラスやstd::stringクラスのイテレータが単にポインタとして実装されている可能性があり、その場合にはbase()メンバ関数からはポインタが返されます。整数型やポインタのような組み込み型は、関数の戻り値（右辺値）に対してデクリメントするコードがコンパイルエラーとなるため、そのような実装のもとでは、この方法は使用できません。
std::reverse_iteratorはインクリメント／デクリメントをoperator++()のオーバーロードで実装しているため、この問題が発生しません。なので、サンプルコードにあるように、先にstd::reverse_iteratorをインクリメントしてからbase()メンバ関数を呼び出す実装を使用するほうがいいでしょう。
最後の要素を探索するアルゴリズム
std::reverse_iteratorの挙動がわかったので、これを利用して、指定した範囲で最後の要素を見つけるアルゴリズムを実装できます。
// 指定した範囲を逆順に探索し、最初に見つかった要素
// （つまり範囲の中で末尾にある要素）を指すイテレータを返す。
// 見つからなかった場合はendを返す
template<class Iterator, class T>
Iterator find_last(Iterator begin, Iterator end, const T& value)
{
const auto rbegin = std::make_reverse_iterator(end);
const auto rend = std::make_reverse_iterator(begin);
auto found = std::find(rbegin, rend, value);
return (found != rend) ? (++found).base() : end;
}
// 指定した範囲を逆順に探索し、条件にあう最初に見つかった要素
// （つまり範囲の中で末尾にある要素）を指すイテレータを返す。
// 見つからなかった場合はendを返す
template<class Iterator, class Predicate>
Iterator find_last_if(Iterator begin, Iterator end, Predicate pred)
{
const auto rbegin = std::make_reverse_iterator(end);
const auto rend = std::make_reverse_iterator(begin);
auto found = std::find_if(rbegin, rend, pred);
return (found != rend) ? (++found).base() : end;
}
// このアルゴリズムには、通常のイテレータを渡し、
// 戻り値の型も通常のイテレータの型になる
auto it3 = find_last(xs.begin(), xs.end(), 2);
auto it4 = find_last_if(xs.begin(), xs.end(),
[](const auto& x) { return x < 4; });
std::cout << *it3 << " : x[" << it3 - xs.begin() << "]" << std::endl;
std::cout << *it4 << " : x[" << it4 - xs.begin() << "]" << std::endl;
1 : x[3]
2 : x[5]
ここでstd::make_reverse_iterator()は、イテレータを引数にとり、その引数からstd::reverse_iteratorのテンプレート引数を推論して、std::reverse_iteratorを生成するヘルパー関数です。このヘルパー関数はC++14から導入されたため、それより前の環境では、
std::reverse_iterator<Iterator>(end);
のようにして、直接テンプレート引数を指定してstd::reverse_iteratorを生成します。
おわりに
このようにして、コンテナ内で最後に現れる要素を探索できるようになりました。
std::reverse_iteratorが元のイテレータと逆順に進むように、ベースとなる型をラップして別の働きをするようにしたイテレータを、イテレータアダプタといいます。
標準ではstd::reverse_iterator以外にも、operator*()で間接参照する値を右辺値参照として返す（つまりmoveされた値として返す）std::move_iteratorや、ちょっと毛色が違いますが、コンテナに要素を挿入する機能を持った挿入イテレータ（std::insert_iteratorやstd::back_insert_iteratorなど）が定義されています。
また、Boost.Iteratorライブラリでは、事前に指定した関数オブジェクトによって、間接参照する値を変換できるようにするtransform_iteratorや、条件を満たす要素以外への移動をスキップする
filter_iteratorなど、いくつかのイテレータアダプタが定義されています。
このように、単に先頭から順に要素をたどるだけではない、より便利なイテレータたちを活用してみましょう！