🔖

C++のrangeを理解しつつアダプタを自作してメタプログラミングを学ぶ(2)

2022/06/08に公開約5,100字

前回の記事

https://zenn.dev/rita0222/articles/a078fbe43f80c8

メタプログラミング時の思考を追ってみる

今回はC++でテンプレートを使ってコネコネする時に、どういう発想でどういう落とし所を見つけていくのか、というのをライブ感覚でお届けしようと思います。ベストプラクティスではないかもしれないし、もっと効率のいい方法があるかもしれません。そこらへんはご指摘いただけますとありがたいです。早速やっていきましょう。

range を表す型とファクトリー関数を作ろう

さて、まず考えることは任意のrangeを表現する型を作ることです。範囲for文で使えるrangeの要件は

  • begin()end() というメンバ関数を持ち、それらが範囲の先頭と末尾を示すイテレータを返すこと
  • 上記で得られるイテレータは * 演算子で要素への参照が取得でき、++ 演算子で次の要素を指し示すこと
  • イテレータが end() と等しいと判定された時点でループを終了すること

でした。イテレータが機能の主立った部分を担っているので、rangeオブジェクト自体はbeginとendを返せれば十分そうです。というわけで

template<typename Ite>
class CustomRange {
public:
    CustomRange(Ite begin, Ite end) : m_begin(begin), m_end(end) {}
    Ite begin() const { return m_begin; }
    Ite end() const { return m_end; }
private:
    Ite m_begin;
    Ite m_end;
};

こんな感じで良いんじゃないでしょうか。Iteにちゃんとしたイテレータ型が入れば、十分機能しそうです。
で、このオブジェクトを簡単に作るためのファクトリー関数を用意します。クラステンプレートは実体化するのに型名を指定しないといけませんが、関数テンプレートなら引数に渡した値の型で実体化してくれるので便利です。

template<typename AnyRange>
auto MakeRange(const AnyRange& range) {
    auto begin = range.begin();
    auto end = range.end();
    return CustomRange<decltype(begin)>(begin, end);
}

というわけで、既存のrangeから得られるイテレータを注入するだけのラッパーができました。

    std::vector<std::string> data = { "ABC", "DEF", "GHI" };
    for (auto&& str : MakeRange(data)) {
        std::cout << str << std::endl;
    }

これが動くなら、後はカスタマイズした処理を突っ込んだイテレータを注入すれば、狙ったことはできそうな気がしてきますね。

filter(LINQで言うところのWhere)を作る

https://zenn.dev/rita0222/articles/9950ff78cab71371c085 でもWhereは作ったので、やるべきことはわかっています。++ する際に、条件に合致しない値は飛ばすようにすればいいだけです。そのためには、条件を評価する関数オブジェクトを持つ必要があります。また、イテレータの内部でインクリメントを進めた結果、endをぶち抜いてしまってはいけないので、イテレータ自身がendを知っている必要があります。

とにかく今回は、範囲for文で使えることだけを考えてるので、厳密なイテレータ要件を満たすことは考えません。ベースとなるイテレータをラップして、最低限のメンバだけを整えてしまいます。というわけで書いてみたのがこちら。

template<typename BaseIte, typename Predicate>
class FilterIterator {
public:
    FilterIterator(BaseIte ite, BaseIte end, Predicate& pred) : _baseIte(ite), _end(end), _predicate(pred) {
        if (!_predicate(*_baseIte)) {
            advance_until_valid_or_end();
        }
    }

    bool operator ==(const FilterIterator& r) const {
        return _baseIte == r._baseIte;
    }

    bool operator !=(const FilterIterator& r) const {
        return !(*this == r);
    }

    auto operator *() const {
        return *_baseIte;
    }

    FilterIterator& operator ++() {
        advance_until_valid_or_end();
        return *this;
    }

private:
    void advance_until_valid_or_end() {
        while (_baseIte != _end) {
            ++_baseIte;
            if (_predicate(*_baseIte)) break;
        }
    }

    BaseIte _baseIte;
    const BaseIte _end;
    Predicate& _predicate;
};

template<typename AnyRange, typename Predicate>
auto FilterRange(const AnyRange& range, Predicate&& predicate) {
    auto begin = range.begin();
    auto end = range.end();
    auto beginConvert = FilterIterator<decltype(begin), Predicate>(begin, end, predicate);
    auto endConvert = FilterIterator<decltype(end), Predicate>(end, end, predicate);
    return CustomRange<decltype(beginConvert)>(beginConvert, endConvert);
}

コンストラクタ

ベースとなるイテレータを、beginとendのペアで受け取ります。endは終端判定にしか使わないのでconstで保護しておきます。条件判定を行う述語関数は参照で受け取ってしまいます。どうせ範囲for文を抜けたらrangeもイテレータも破棄されるでしょうから、余計なコピーは避けます。

そして、 *begin をpredicateで評価した結果falseとなる可能性は十分にありますから、コンストラクタの時点で_baseIteが、条件を満たす値かendを指すようにしておく必要があります。advance_until_valid_or_end() が「条件を満たす値か終端まで進める」という関数なので、*begin を評価した結果がfalseの場合にこれを呼んでおきます。

比較演算子

基本的にはベースイテレータの比較処理に丸投げです。いくらendとの判定にしか使わないとはいえ != だけ定義して == を定義しないのはさすがにアレなので、定石通り == を定義した上で != はその否定で定義しておきます。

デリファレンス演算子

これも丸投げです。返り値型すら auto で丸投げです。

インクリメント演算子

これがfilterのキモとなる部分ですが、やることはコンストラクタで既に紹介したadvance_until_valid_or_end() の呼び出しと、インクリメント結果である自身の参照を返すだけです。

使い勝手

こんな感じで使えます。

    std::vector<int> data = { 1, 2, 3, 4 };
    for (auto&& i : FilterRange(data, [](auto& ii) { return ii % 2 == 0; })) {
        std::cout << i << std::endl;
    }

だいぶLINQっぽい感じになってきました。 | 演算子を定義すればもっとそれっぽくなります。やってみましょう。

template<typename Predicate>
struct FilterAdapterType {
    FilterAdapterType(Predicate&& predicate) : _predicate(predicate) {}
    Predicate& _predicate;
};

template<typename AnyRange, typename Predicate>
auto operator |(const AnyRange& range, FilterAdapterType<Predicate>&& adapter) {
    return FilterRange(range, adapter._predicate);
}

template<typename Predicate>
auto Filter(Predicate&& predicate) { return FilterAdapterType<Predicate>(std::forward<Predicate>(predicate)); }

まず、単なるラムダ式だと演算子定義の際に他の用途と衝突してしまうので、Filterの用途であることを明示しつつラムダ式を保持する FilterAdapterType を作ります。
で、何かしらのrangeを左辺に、FilterAdapterTypeを右辺に取る | 演算子を定義します。この返り値をさっきの利用例で使ったFilterRangeとします。
最後に、FilterAdapterTypeを簡単に作るためのファクトリー関数Filterを作っていっちょあがりです。

    std::vector<int> data = { 1, 2, 3, 4 };
    for (auto&& i : data | Filter([](auto& ii) { return ii % 2 == 0; })) {
        std::cout << i << std::endl;
    }

おお!ぽい!とってもそれっぽい!イテレータの厳密な定義とか、const参照の有無とか、その他の規格に沿って様々なアルゴリズムに対応するだとか、本気でやり出すともっともっと色々やらないといけないんですが、とりあえず要点を絞って、テンプレートメタプログラミングや演算子定義を使ってみると、そんなにコード量が膨れることなく、こういった環境を作り出せますよ!といったことが伝われば嬉しいですね。

次回はtransform(LINQで言うところのSelect)を作って一区切りにしたいと思います。

Discussion

ログインするとコメントできます