【C++】reverse／reverse_copy - reversed関数の実現【関数型プログラミング】

C++標準ライブラリにはreverse関数が予め用意されていますが、破壊的な関数であるため、場合によってはreverse_copy関数の利用が求められます。

reverse関数

reverse関数はコンテナの要素を逆順に入れ替える用途で利用できます。第一引数と第二引数に要素範囲を指定します。

std::vector<int> v = {1, 2, 3};
std::reverse(v.begin(), v.end());
v; // {3, 2, 1}

両引数に指定するイテレータはswap処理に対応している必要があります。内部的には次のような処理が行われると考えてください。 

std::vector<int> v = {1, 2, 3, 4};
auto begin = v.begin(), end = v.end();
std::swap(*begin++, *--end); // v == {4, 2, 3, 1}
std::swap(*begin++, *--end); // v == {4, 3, 2, 1}

reverse関数では指定されたイテレータが直接操作されます。そのためコンテナ側の値が変化します。コンテナをイミュータブルに扱いたい場合や、逆順のコンテナを新規オブジェクトとして受け取りたいような場合には、次に説明するreverse_copy関数を用いる必要があります。

reverse_copy関数

reverse_copy関数はコンテナの要素を逆向きにコピーする用途で利用できます。第三引数にコピー先のイテレータを指定します。

std::vector<int> v = {1, 2, 3};
std::vector<int> w; // w.reserve(v.size());
std::reverse_copy(v.begin(), v.end(), std::back_inserter(w));
(v); // {1, 2, 3}
(w); // {3, 2, 1}

w.reserve(v.size());で事前にキャパシティを明示しておくと、より効率的な動作が期待できます。

reversed関数の実現

非破壊的なreverse関数の作り方です。受け取ったコンテナをイミュータブルなオブジェクトして扱います。戻り値はリバース済みのコンテナを新規オブジェクトとして返します。

template<class Container>
Container reversed(const Container& c) {
  using std::begin;
  using std::end;
  Container r;
  r.reserve(c.size());
  std::reverse_copy(begin(c), end(c), std::back_inserter(r));
  return r;
}

reverse(std::vector<int>{1, 2, 3}); // {3, 2, 1}
広告