koturnの日記

転職したい社会人2年生の技術系日記.ブログ上のコードはコピペ自由です.

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に劣る点を挙げるならば,

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

の2点がある.

まとめ

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