『STLソース剖析』学習ノート-第3章反復器

1、反復器設計思考-STLキー
反復器:ある容器の内部表現形式を暴露する必要がなく、その容器の各要素に順次アクセスできるようにする方法を提供する.
STLの中心思想は、データコンテナ(containers)とアルゴリズム(algorithms)を分離し、互いに独立して設計し、最後に接着剤で一緒に撮ることである.アルゴリズムに異なる反復器を与えるだけで,異なる容器に対して同じ操作を行うことができる.
アルゴリズムfind()を例にとると、2つの反復器と1つの「ターゲットの検索」を受け入れます.

//   SGI <stl_algo.h>
template <class InputIterator, class T>
InputIterator find(InputIterator first,InputIterator last,const T& value)
{
    while (first != last && *first != value)
        ++first;
    return first;
}

異なる反復器を与えるだけでfind()は異なるコンテナを検索できます.

#include <vector>
#include <list>
#include <deque>
#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
    const int arraySize = 7;
    int ia[arraySize] = { 0,1,2,3,4,5,6 };
    vector<int> ivect(ia, ia+arraySize);
    list<int> ilist(ia, ia+arraySize);
    deque<int> ideque(ia, ia+arraySize);
    vector<int>::iterator it1 = find(ivect.begin(), ivect.end(), 4);
    if (it1 == ivect.end())
        cout << "4 not found." << endl;
    else //   ：4 found. 4
        cout << "4 found. " << *it1 << endl;

    list<int>::iterator it2 = find(ilist.begin(), ilist.end(), 6);
    if (it2 == ilist.end())
        cout << "6 not found." << endl;
    else//   ：6 found. 6
        cout << "6 found. " << *it2 << endl;

    deque<int>::iterator it3 = find(ideque.begin(), ideque.end(), 8);
    if (it3 == ideque.end())
        cout << "8 not found." << endl;
    else//   ：8 not found.
        cout << "8 found. " << *it3 << endl;

    return 0;
}

2、反復器はインテリジェントなポインタである
反復器はポインタのような動作をするオブジェクトであり、ポインタの様々な動作の中で最も一般的で最も重要なのはコンテンツ抽出(dereference)とメンバーアクセス(member access)であるため、反復器の最も重要なプログラミング作業はoperator*とoperator->をリロード(overloading)することである.
すべての実装の詳細をユーザに見られないようにカプセル化したのは,各STL容器が専用反復器を提供しているためである.
3、Traitsプログラミング技法——STLソースゲートキー
反復器は、反復器のvalue typeと呼ばれるオブジェクトのタイプを指します.
我々は,(1)関数テンプレートのパラメータタイプ導出により関数内宣言変数の問題を解決する(2)さらに,関数テンプレートのパラメータタイプ導出により導出されるのはパラメータのみであり,関数の戻り値型別を導出できないことを知っている.この場合、戻りタイプが反復器が指すオブジェクトのタイプである場合、解決策は、反復器の内部に「プロパティ」を追加する埋め込みタイプ宣言です.この「プロパティ」により、アルゴリズムは反復器が指すオブジェクトのタイプを簡単に知ることができます.
しかし、問題が来たのは、すべての反復器がclass typeであるわけではない.オリジナルポインタは反復器ですが、タイプではなく、埋め込みタイプを定義できません.どうしよう?原生ポインタに対して特殊化する処理は,テンプレートを用いて特化すれば可能である.
テンプレートの偏特化により、オリジナルポインタが埋め込まれないタイプの問題を解決します.iterator_traitsが鍵です.
STL実装ではtraitsプログラミング技術は「埋め込みタイプ」のプログラミング技術とC++のtemplateパラメータ導出機能を利用し,C++タイプ識別の不足を補った.traitsにより,アルゴリズムは反復器の属性をそのまま抽出し,アルゴリズムの正確かつ効率的な動作を支援することができる.
traitsとは、template <class I>のI定義に独自のvalue typeがあれば、このtraitsの役割によって抽出されるvalue_typeはI::value_typeです.traitsは「特性抽出機」のように、各反復器の特性を抽出します.
4、反復器基本フレーム
最もよく使われる反復器の対応する型は5種類あります:value type, difference type, pointer, reference, iterator catagoly.
STLが提供するiterator classは以下の通りです.メンバーは含まれておらず、純粋に型別定義にすぎません.

template <class Category,
          class T,
          class Distance = ptrdiff_t,
          class Pointer = T*,
          class Reference = T&>
struct iterator {
    typedef Category    iterator_category;
    typedef T           value_type;
    typedef Distance    difference_type;
    typedef Pointer     pointer;
    typedef Reference   reference;
};

特性抽出機traitsはオリジナルの味で搾り出します.

template <class I>
struct iterator_traits {
  typedef typename I::iterator_category iterator_category;
  typedef typename I::value_type        value_type;
  typedef typename I::difference_type   difference_type;
  typedef typename I::pointer           pointer;
  typedef typename I::reference         reference;
};

これらのタイプの意味は次のとおりです.

value type             ；
difference type             ；            
reference      ；
pointer      ；
iterator_category         ；

反復器の移動特性と実行動作によって、反復器は5種類に分けられる.

1、Input Iterator：         ，       ，  （read 
only）；
2、Output Iterator：  （write only）；
3、Forward Iterator：  「   」  （   replace()）    
              ；
4、Bidirectional Iterator：     。             
    （             ），      Bidirectional 
Iterators；
5、Random Access Iterator：                   
（ 3    operator++ ， 4     operator--）， 5     
       ，   p+n, p-n, p[n], p1-p2, p1<p2.