STLのイテレータインタフェース再考 - Faith and Brave

STLのイテレータは、コンテナとアルゴリズムをつなぐ中間インタフェース。STLではそのイテレータ自体のインタフェースとして、ポインタの構文を採用している。

ここではそのポインタの構文を、好んで使いたい構文ではないものとし、演算子ではなく名前のついた関数によるインタフェースで、イテレータを再設計してみる。

コード全体は以下を参照：

faithandbrave / modern_stl_iterator_interface_2014.cpp - Gist

新しいイテレータインタフェースによるアルゴリズムの実装

まず、新しいイテレータインタフェースを使用しているところ、すなわちアルゴリズムの中身から見てみる。

namespace my_stl {
…
template <class Iterator, class F>
void for_each(Iterator first, Iterator last, F f)
{
    using traits = my_stl::iterator_traits<Iterator>;
 
    // no use raw pointer interface
    Iterator it = first;
    while (!traits::equal(it, last)) {
        f(traits::dereference(it));
        it = traits::next(it);
    }
}

} // namespace my_stl

ここでは、iterator_traitsというクラスが、イテレータのインタフェースとなっている(標準ライブラリに同名のクラスがあるが、それとは別物)。

このクラスは、以下の静的メンバ関数で、イテレータを操作する：

関数	説明
`dereference()`	イテレータが指している要素を間接参照する
`next()`	イテレータをひとつ進める
`equal()`	2つのイテレータを等値比較する

これらは、STLのイテレータインタフェースとしてはそれぞれ、operator*()、operator++()、operator==()に相当する。

イテレータインタフェースの実装

このイテレータは、これらのメンバ名前による操作を直接サポートするイテレータクラスのみならず、従来のSTLと同様に、ポインタもサポートする。iterator_traitsクラスの実装は以下のようになっている：

namespace my_stl {
 
template <class Iterator>
struct iterator_traits {
    static typename Iterator::reference dereference(Iterator& it)
    {
        return it.dereference();
    }
 
    static Iterator next(const Iterator& it)
    {
        return it.next();
    }
 
    static bool equal(const Iterator& a, const Iterator& b)
    {
        return a.equal(b);
    }
};
 
template <class T>
struct iterator_traits<T*> {
    static T& dereference(T* it)
    {
        return *it;
    }
 
    static T* next(T* it)
    {
        return ++it;
    }
 
    static bool equal(const T* a, const T* b)
    {
        return a == b;
    }
};

} // namespace my_stl

iterator_traitsは、デフォルト実装としてのインタフェースのほかに、ポインタに対する特殊化を行っている。これによって、ポインタもイテレータとして振る舞えるようにしてある。

また、これと同じように、自分が使っているコンテナのイテレータが、デフォルトのインタフェースを持っておらず、ポインタでもない場合は、iterator_traitsクラスを特殊化してアダプトすれば、そのイテレータもまたアルゴリズムに適用可能になる。

今回用意したコンテナクラスは、singly_linked_listという名前の単方向リンクリスト。このコンテナクラスには、デフォルト実装の、dereference()、next()、equal()というメンバ関数を持つイテレータを持たせている。

ユーザーコード

コンテナとイテレータの実装は簡単なものなので省略して、コンテナと配列(ポインタ)をアルゴリズムに適用できているところを確認する。

#include <iostream>
int main()
{
    my_stl::singly_linked_list<int> ls;
    ls.push_front(3);
    ls.push_front(2);
    ls.push_front(1);
 
    my_stl::for_each(ls.begin(), ls.end(), [](int& x) {
        std::cout << x << std::endl;
    });
 
    int ar[3] = {4, 5, 6};
    my_stl::for_each(ar, ar + 3, [](int& x) {
        std::cout << x << std::endl;
    });
}

出力：

まとめ

ここでは、STLの「ポインタもイテレータとして振る舞えるようにする」という設計方針を維持したまま、イテレータのインタフェースを見直してみた。近年、データ構造とアルゴリズムをつなぐ中間インタフェースを用意するライブラリが増えてきた。Boost.Graph、Boost.Geometryなどが参考になる。これらのライブラリによって、中間インタフェースの設計がさらに洗練されたので、それを大元であるSTLの設計に適用した、というのが今回の試みだ。

Rangeが出てくると話はまた違ってくるのだが、いまイテレータを再設計するならこうなる、というのを示してみた。