■

http://d.hatena.ne.jp/Nobuhisa/20070901/1188583208 のエントリで
師匠のid:uskzさんに大変丁寧なコメントを頂いていたのですが，
入院していたためずっと読めてませんでした。。
# コメントがあったこと自体は携帯にメールが転送されてきたので知ってました。笑
コメント欄に置いておくのは勿体無いので，転載しておきます。（まずかったら言って下さい

これってGeneric Programmingでは基本的なテクニックの１つなのですが，なぜかあまり知られていない気がしますし，なかなか解説も見当たらないんですよね．やっぱりGeneric Programmingはまだあまり浸透していないのかもしれません．というわけでSTLの関数を例にもうちょっと詳しい解説をば．
STLにはstd::distanceと言う２つのイテレータの距離を求める関数があります．

vector v;

std::distance(v.begin(), v.end());

や

int a[N];

std::distance(a, a + N);

は，

list l;

std::distance(l.begin(), l.end());

等と違い，実装は高速なv.end() - v.begin()ですみます．

こういう風に，引数の種類に応じてコンパイル時に適切な実装を選択させると言うのがこのテクニックの目的です．
まず，Iterator Conceptのrefinement階層に応じたタグを用意しておきます．
struct input_iterator_tag { };

struct output_iterator_tag { };

struct forward_iterator_tag : input_iterator_tag { };

struct bidirectional_iterator_tag : forward_iterator_tag { };

struct random_access_iterator_tag : bidirectional_iterator_tag { };
イテレータの特性を取得する次のようなtraits classも用意しておきます．
template 

struct iterator_traits

{

　typedef typename Iterator::iterator_category iterator_category;

　typedef typename Iterator::difference_type difference_type;

　// 以下略

};
そしてdistanceの実装は次のようになります．
// impl1

template 

inline typename iterator_traits::difference_type

distance_(InputIterator first, InputIterator last, input_iterator_tag)

{

　typename iterator_traits::difference_type n = 0;

　while (first != last) ++first, ++n;

　return n;

}
// impl2

template 

inline typename iterator_traits::difference_type

distance_(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag)

{

　return last - first;

}
template 

inline typename iterator_traits::difference_type

distance(InputIterator first, InputIterator last)

{

　return distance_(first, last, typename iterator_traits::iterator_category()); // 危険！ADL対策してません！

}


vector::iterator::iterator_categoryはrandom_access_iterator_tagのtypedefですので，高速なimpl2が選択されます．

list::iterator::iterator_categoryはbidirectional_iterator_tagのtypedefで，直接対応する実装は存在しませんが，bidirectional_iterator_tagはinput_iterator_tagを継承していますので，impl1が選択されます．
最後にint*に対する実装ですが，iterator_traitsは
template 

struct iterator_traits

{

　typedef random_access_iterator_tag iterator_category;

　typedef ptrdiff_t difference_type;

　// 以下略

};
のように特殊化されていますので，impl2を利用できます．

メモするだけじゃなくちゃんとお勉強しなきゃ・・・