Gaming Life

一日24時間、ゲームは10時間

C++のRange-based for文(範囲for文)で逆順に走査するイテレータを自作した

モチベーション

Pythonのfor文は、C++でいうところのRange-based for文、C#で言うところのforeachと同等の動作をする。つまり、

    for (int i = 0; i < 10; i++) {}

のようなforが存在しない。

Pythonのfor文において、iterable objectをenumerate メソッドに渡すと、添字付きRange-based forができる。

    l = [100, 200, 300]
    for i, num in enumerate(l):
        print(i, num)
    # 0 100
    # 1 200
    # 2 300

これが非常に便利なのでC++でも同じ事ができないかなーと調べてみると、あった。

reedbeta.com

(リンク先に載っている実際のソースコードはここには載せない)

というわけでC++のRange-based for文でもPythonenumerate 同等の、インデックス付き走査が可能ということが分かった……

と、ここで終わってはクソ記事もいいとこなので、この実装を参考に逆順に走査するイテレータを自作することにした。

仕様

まず、リンク先の実装で問題なところを挙げてみる。

  1. operator++ の返り値がvoidになっている
  2. std::beginstd::end の形でイテレータを取得しているので、ユーザが独自に定義したiterable objectに対応できない(わざわざ std::beginstd::end をオーバーラップしなければならない)
  3. beginとendの型が違う場合に対応していない (C++17でbeginとendの型が違っても動作するようになった。詳しくは↓の記事で)

cpprefjp.github.io

今回の実装では 面倒なので 3. の問題については無視することにした。

また逆順に走査するためには、対象のiterable objectは rbeginrend 、つまり逆イテレータを持っていなければならない。従って SFINAE を使って rbegin rend を持たないオブジェクトを渡した時はコンパイルを通さないような実装とした。

実装

(2020/04/12/18:30 コメントでの指摘通りに修正)

    template <typename Range,
              typename reversed_iterator = decltype(std::declval<Range>().rbegin()),
              typename = decltype(std::declval<Range>().rend())>
    constexpr auto Reversed(Range&& range) {
        struct iterator {
            reversed_iterator iter;
            bool operator!= (const iterator& end) const { return iter != end.iter; }
            auto& /* void */ operator++() { ++iter; return iter; }
            auto& operator*() const { return *iter; }
        };
        struct iterator_wrapper {
            Range iterable;
            auto begin() {
                return iterator{ iterable.rbegin() };
            }
            auto end() { 
                return iterator{ iterable.rend() };
            }
        };
        return iterator_wrapper{ std::forward<Range>(range) };
    }

wandbox.org

operator++の戻り値について

operator++の行に謎のコメントが残っている。

    auto& /* void */ operator++() { ++iter; return iter; }

実は今の実装のままだと、MSVCではコンパイルが通らない。

調べてみると、どうやら現在のgccvectorの実装では vector::begin() をデクリメントしても、エラー終了しないらしい(当然Undefined Behaviorなので本来はやるべきでない)。一方MSVCの場合、 vector::begin() をデクリメントした時点で、 can't decrement vector iterator before begin というエラーメッセージと共にエラー終了する。

そのため、この関数をMSVCで使いたいときは、悪い実装ではあるがoperator++の実装を以下の通りに変える必要がある。

    /* auto& */ void operator++() { ++iter; /* return iter; */ }

参考サイト

Python-Like enumerate() In C++17

C++ 範囲ベースforに自分で作ったclassを対応させる - ゲーム作りは楽しい