STLのイテレータは、コンテナとアルゴリズムをつなぐ中間インタフェース。STLではそのイテレータ自体のインタフェースとして、ポインタの構文を採用している。
ここではそのポインタの構文を、好んで使いたい構文ではないものとし、演算子ではなく名前のついた関数によるインタフェースで、イテレータを再設計してみる。
コード全体は以下を参照:
まず、新しいイテレータインタフェースを使用しているところ、すなわちアルゴリズムの中身から見てみる。
namespace my_stl {
…
template <class Iterator, class F>
void for_each(Iterator first, Iterator last, F f)
{
using traits = my_stl::iterator_traits<Iterator>;
Iterator it = first;
while (!traits::equal(it, last)) {
f(traits::dereference(it));
it = traits::next(it);
}
}
}
ここでは、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;
}
};
}
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;
});
}
出力:
1
2
3
4
5
6
まとめ
ここでは、STLの「ポインタもイテレータとして振る舞えるようにする」という設計方針を維持したまま、イテレータのインタフェースを見直してみた。近年、データ構造とアルゴリズムをつなぐ中間インタフェースを用意するライブラリが増えてきた。Boost.Graph、Boost.Geometryなどが参考になる。これらのライブラリによって、中間インタフェースの設計がさらに洗練されたので、それを大元であるSTLの設計に適用した、というのが今回の試みだ。
Rangeが出てくると話はまた違ってくるのだが、いまイテレータを再設計するならこうなる、というのを示してみた。
参照