Range-based forで逆順走査したい

はじめに

C++を書いていると，Range-based forで逆順操作をしたいことがたまにある． Range-based forは順方向の走査のみで，逆順に走査することはできない．なので，通常のインデックスベースのforを用いて，

std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto i = v.size() - 1; i != static_cast<decltype(i)>(-1); i--) {
  std::cout << v[i] << std::endl;
}

と書いたり，イテレータを利用して，

std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
for (auto itr = std::rbegin(v); itr != std::rend(v); ++itr) {
  std::cout << *itr << std::endl;
}

と書いたりする．

だが，このようなループにおいて欲しいのはインデックスやイテレータではなく，要素そのものが欲しい．ここにRange-based forで逆順に走査したいというモチベーションがある．

`boost::adaptors::reverse`

天下のBoostライブラリにはまさにそういうものがある．

#include <iostream>
#include <vector>

#if defined(__GNUC__) && __GNUC_PREREQ(4, 6)
#  pragma GCC diagnostic push
#  pragma GCC diagnostic ignored "-Wconversion"
#  pragma GCC diagnostic ignored "-Weffc++"
#  pragma GCC diagnostic ignored "-Wparentheses"
#  if __cplusplus >= 201103L
#    pragma GCC diagnostic ignored "-Wzero-as-null-pointer-constant"
#    if __GNUC_PREREQ(5, 0)
#      pragma GCC diagnostic ignored "-Wsuggest-override"
#    endif  // __GNUC_PREREQ(5, 0)
#  endif  // __cplusplus >= 201103L
#endif  // defined(__GNUC__) && __GNUC_PREREQ(4, 6)
#include <boost/range/adaptors.hpp>
#if defined(__GNUC__) && __GNUC_PREREQ(4, 6)
#  pragma GCC diagnostic pop
#endif  // defined(__GNUC__) && __GNUC_PREREQ(4, 6)

int
main()
{
  std::vector v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  for (const auto& e : boost::adaptors::reverse(v)) {
    std::cout << e << std::endl;
  }

  return 0;
}

ワーニングオプションを盛り沢山にしていると，Boostからそれなりにワーニングが出てくるので，ある程度抑えるようにしておいた．

boostを使わずにやりたい

場合によっては，boostに頼らずにやりたいこともあると思われる． range-based forが受理するのは，begin() と end() というメンバ関数を持つクラスのインスタンスである．なので，以下のようにしてみる．

#include <iostream>
#include <iterator>
#include <type_traits>
#include <vector>


// C++11ではrbegin(), rend()を持つかどうかを判定するメタ関数
// C++14以降では，std::rbegin(), std::rend()に受理されるかどうかを判定するメタ関数
template<typename T>
struct has_rbegin_rend
{
private:
  template<typename U>
  static auto
#if __cplusplus >= 201402L
  check(U&& obj) -> decltype(std::rbegin(obj), std::rend(obj), std::true_type{});
#else
  check(U&& obj) -> decltype(obj.rbegin(), obj.rend(), std::true_type{});
#endif

  static std::false_type
  check(...);

public:
  static constexpr bool value = decltype(check(std::declval<T>()))::value;
};


#if __cplusplus >= 201402L
template<typename T>
constexpr bool has_rbegin_rend_v = has_rbegin_rend<T>::value;
#endif


template<typename Iterator>
class Range
{
public:
  Range(Iterator&& begin, Iterator&& end) noexcept
    : m_begin(std::forward<Iterator>(begin))
    , m_end(std::forward<Iterator>(end))
  {}

  Iterator
  begin() const noexcept
  {
    return m_begin;
  }

  Iterator
  end() const noexcept
  {
    return m_end;
  }

private:
  const Iterator m_begin;
  const Iterator m_end;
};  // class Range


template<typename Iterator>
static inline Range<Iterator>
makeRange(Iterator&& begin, Iterator&& end) noexcept
{
  return Range<Iterator>{std::forward<Iterator>(begin), std::forward<Iterator>(end)};
}


#if __cplusplus >= 201402L
// std::initiaizer_listをわざわざ逆順にしたい人は皆無だと思うけど，一応...
template<typename T>
static inline decltype(auto)
makeReversedRange(const std::initializer_list<T>& iniList) noexcept
{
  return makeRange(std::rbegin(iniList), std::rend(iniList));
}


template<
  typename T,
  typename std::enable_if_t<has_rbegin_rend_v<T>, std::nullptr_t> = nullptr
>
static inline decltype(auto)
makeReversedRange(T&& c) noexcept
{
  return makeRange(std::rbegin(c), std::rend(c));
}
#else
template<typename T>
static inline auto
makeReversedRange(const std::initializer_list<T>& iniList) noexcept
  -> decltype(makeRange(iniList.rbegin(), iniList.rend()))
{
  return makeRange(iniList.rbegin(), iniList.rend());
}


template<
  typename T,
  typename std::enable_if<has_rbegin_rend<T>::value, std::nullptr_t>::type = nullptr
>
static inline auto
makeReversedRange(T&& c) noexcept
  -> decltype(makeRange(c.rbegin(), c.rend()))
{
  return makeRange(c.rbegin(), c.rend());
}
#endif


// rbegin(), rend()を持たないものはこっちに分岐させて，エラーメッセージを少なくする
template<
  typename T,
  typename std::enable_if<!has_rbegin_rend<T>::value, std::nullptr_t>::type = nullptr
>
static inline void
makeReversedRange(T&&) noexcept
{
  static_assert(has_rbegin_rend<T>::value, "Specified argument doesn't have reverse iterator.");
}


int
main()
{
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  for (const auto& e : makeReversedRange(v)) {
    std::cout << e << std::endl;
  }

  return 0;
}

どうしてもC++11でなくてはならないときに備えて，C++11でもコンパイルが通るようにした．（この部分のコードを削除すれば，上記コードは少し短くなるだろう．） C++11はフリー関数版の rbegin() と rend() が無いので，メンバ関数を呼び出すようにしている．そのため上記コードは，C++11において，組み込み配列の逆順走査はできない．わざわざフリー関数の rbegin() と rend() を実装するのは面倒なので，その点は妥協した．

また， makeReversedRange に，STLコンテナや配列以外を与えた場合のコンパイルエラーメッセージを抑えるため，SFINAEを利用している．その部分も省けば，上記コードはもっと短くなる．

おまけ

本記事の趣旨とは外れるが，そもそも std::for_each() で逆順走査ができる． C++14以降なら，

#include <algorithm>
#include <iostream>
#include <vector>


int
main()
{
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  std::for_each(std::rbegin(v), std::rend(v), [](const auto& e){
    std::cout << e << std::endl;
  });

  return 0;
}

で，C++11なら，

#include <algorithm>
#include <iostream>
#include <vector>


int
main()
{
  std::vector<int> v{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  std::for_each(v.rbegin(), v.rend(), [](const decltype(v)::value_type& e){
    std::cout << e << std::endl;
  });

  return 0;
}

と書ける．だが，どうしてもRang-based forで書きたいのだ！という人達もいるはずである（ホンマか？）

一応，std::for_each() のRange-based forに劣る点を挙げるならば，

イテレータの指定が必要な分，どうしてもユーザコードが膨れ上がる．
C++11にはジェネリックラムダが無いため，forの処理部分のラムダの引数の記述が冗長になりがちである．

の2点がある．

まとめ

Boost.Range の boost::adaptors::reverse() にSTLコンテナ等を渡せば，簡単に逆順走査できる
boost::adaptors::reverse() 相当のものは簡単に作れる

koturnの日記

普通の人です．ブログ上のコードはコピペ自由です．

Range-based forで逆順走査したい

はじめに

`boost::adaptors::reverse`

boostを使わずにやりたい

おまけ

まとめ