コンテナ(Container)

C/C++の言語仕様として用意されている'物の集まり'が配列です。
  int array[10];
と書くことで10個のintを連続領域に確保してくれ、array[i]でi番目の要素にアクセスできます。プログラム中ではきわめて多くのシチュエーションで配列が使われており、また配列ひとつで十分目的の機能を実現できるのも事実です。しかしながらこの配列には不満な点も少なからずあります。まず第一に固定長であることです。配列の要素数は定数、すなわちコンパイル時に確定していなければなりません。配列の要素数がそのプログラムを動かしてみないとわからないとき、C++では
  int* ary;
  int n = 必要な要素数
  ary = new int[n];
  ...
  delete[] ary;
のような方法で配列の要素数を動的に決定できます。しかしこれとて領域確保の直前までには必要な要素の数がわかっていなければなりません。テキストファイルにint値が1行に1個ずつ書かれていて、これを配列にセットするのなら、一度ファイルを空読みして要素数を求め、それだけの要素を格納するのに必要な大きさの配列を用意してから再度ファイルから読み込めば(多少遅くはなるけれど)なんとかなります。しかしユーザからの入力値を配列に追加するとなるとそうはいきません。要素数が確定できないからです。プログラムの中で配列を大きくしていかなければなりません。
  int  size = 0;                  // 要素数
  int  capacity = 10;             // 配列の大きさ
  int* array = new int[capacity]; // 大きさ10のint配列
  int  data;                      // 配列に挿入する要素
  // arrayにdataを挿入する...
  if ( size >= capacity ) { // 一杯だ! 配列を伸長しよう。
    capacity += 4; // 少し大きく
    int* tmp = new int[capacity];
    for ( int i = 0; i < size; i++ )
        tmp[i] = array[i];
    delete[] ary;
    array = tmp;
  }
  array[size++] = data;
ひとつの配列を管理するのに現在の要素数(size)と許容量(capacity)の2つの変数を抱き合わせ、加えてプログラムのあちこちに上記のような配列伸長ルーチンを埋め込むことになります(実際にはstructとサブルーチンを使うのでしょうが)。また、末尾だけでなく配列の途中に要素を挿入するとき、上記のような配列伸長だけでなく、挿入位置より後にある要素をひとつづつ後にずらして空席を設けなくてはなりませんし、逆に配列の途中から要素を削除するときは削除位置より後にある要素をひとつづつ前にずらして空席を埋めなくてはなりません。配列は確かに便利なデータの集合ではありますが、末尾ではない位置へのデータの挿入/削除が遅く、場合によっては"使い物にならない"こともあるのです。

データの集合を管理する方法として、配列だけでなくリストや2進木などのデータ構造を利用すれば配列の欠点(データの挿入/削除が遅い)をクリアでき、目的に応じたデータ構造を正しく適用することでプログラムのパフォーマンスを向上させることができます。しかしながら今までリストや2進木などのデータ構造を実現したクラスは自作する(あるいはどこかから買ってくる)しかなく、標準のお墨付きをもらったものはありませんでした。

STLはコンテナ(Container)と総称される、以下のデータ構造を提供します:

コンテナに格納された要素に対するアクセスのため、それぞれのコンテナに対応したイテレータが下記のように定義されています。
 コンテナ                         イテレータの種類      コンテナの要素
vector<T,Allocator>               RandomAccessIterator  T
list<T,Allocator>                 BidirectionalIterator T
deque<T,Allocator>                RandomAccessIterator  T
set<Key,Compare,Allocator>        BidirectionalIterator Key
multiset<Key,Compare,Allocator>   BidirectionalIterator Key
map<Key,T,Compare,Allocator>      BidirectionalIterator pair<const Key,T>
multimap<Key,T,Compare,Allocator> BidirectionalIterator pair<const Key,T>

※ コラム Allocator

コンテナにはどれもテンプレート引数'Allocator'があります。それぞれのコンテナは要素の挿入/削除に伴いメモリの取得/解放を行なわなければなりません。通常、メモリの取得/解放には関数new/deleteを用いますが、STLはAllocatorに任せることでメモリ管理をユーザが置き換えることができるようになっています(が、実際にはこのAllocatorをユーザが指定することはほとんどなく、デフォルトであるallocatorをそのまま使えばいいでしょう)。
  // デバッグ用allocator
  template <class T> class debug_allocator {
  public:
    typedef size_t    size_type;
    typedef ptrdiff_t difference_type;
    typedef T*        pointer;
    typedef const T*  const_pointer;
    typedef T&        reference;
    typedef const T&  const_reference;
    typedef T         value_type;
    template <class U>
      struct rebind { typedef debug_allocator<U> other; };

    pointer       address(reference x) const
      { return &x; }
    const_pointer address(const_reference x) const
      { return &x; }
    pointer       allocate(size_type n, const void* hint = 0) {
      cout << "allocate " << n << " of " << typeid(T).name() << endl;
      return (pointer)operator new(n * sizeof(T));
    }
    void      deallocate(pointer p, size_type n) {
      cout << "deallocate " << n << " of " << typeid(T).name() << endl;
      operator delete(p);
    }
    size_type max_size() const
      { return (size_t)-1 / sizeof(T); }
    void      construct(pointer p, const T& val) {
      cout << "construct " << typeid(T).name()
           << '(' << val << ')' << endl;
      new ((void*)p) T(val);
    }
    void      destroy(pointer p) {
      cout << "destroy " << typeid(T).name() << endl;
    }
    char* _Charalloc(size_type n) {
      return allocate(n);
    }
  };

  // お試し
  int main() {
    int a[] = { 0, 1, 2 };
    cout << "CREATE vector (3 ints)" << endl;
    vector< int,debug_allocator<int> > v(a,a+3);
    cout << "ADD 1 MORE ints" << endl;
    v.push_back(3);
    cout << "ERASE 3 ints" << endl;
    v.erase(v.begin()+1, v.begin()+4);
    cout << "CLEAR" << endl;
    v.clear();
    cout << "END" << endl;
    return 0;
  }

  実行結果:
    CREATE vector (3 ints)
    allocate 3 of int
    construct int(0)
    construct int(1)
    construct int(2)
    deallocate 0 of int
    ADD 1 MORE ints
    allocate 6 of int
    construct int(0)
    construct int(1)
    construct int(2)
    construct int(3)
    destroy int
    destroy int
    destroy int
    deallocate 3 of int
    ERASE 3 ints
    destroy int
    destroy int
    destroy int
    CLEAR
    destroy int
    END
    deallocate 6 of int

[すべてのコンテナに対してできること]

型Tを要素とするコンテナXには以下のオペレーションが用意されています。 以下の説明において:
  a,b : Xのインスタンス
  u :   識別子
  r :   Xの参照(X&)
を表します。

[Reversibleコンテナに対してできること]

BidirectionalIteratorまたはRandomAccessIteratorの適用できるコンテナ(要するにSTLコンテナすべて)には、上記(すべてのコンテナに対してできること)に加え、以下のオペレーションが可能です。

※ コラム 計算量

アルゴリズムの性能を測る物差しとして、空間計算量と時間計算量があります。空間計算量はその処理のためにどれだけの記憶領域を必要とするか、時間計算量は、その処理にはどれだけの時間を必要とするかを表す指標です。vectorを例にいくつかの処理に対する時間計算量を求めてみましょう。

まず要素の挿入。vectorは複数の要素を連続領域に配置しています。vectorに要素を挿入するとき、末尾に挿入するのであれば現在の末尾に隣接する空き領域にコピーするだけですから、vectorの持つ要素数がいくら大きかろうがほとんど一瞬のうちに処理が完了します。ところがずらりと並んだ要素の途中に新たな要素を割り込ませるには、後続する複数の要素をひとつづつ後方にずらさなくてはなりません。vector内の要素数がnであるとき、新たな要素の挿入には平均n/2回の'ずらす'処理が必要となります。つまり挿入に要する時間は要素数nに比例することになります。これを"vectorへの要素の挿入に対する時間計算量はO(n)である"と表現します。O(x)は"xに比例する"と読み換えてもかまいません。ある処理がnの二乗に比例するならO(n^2)と表します。vectorから要素を削除するときも挿入と同様、今度は空いた席を順に'つめる'作業が伴うため、時間計算量はO(n)となります。

次に要素の参照です。i番目の要素をアクセスするには、最初の要素の位置からi個分離れた位置をもとめなくてはなりません。これは(i*要素の大きさ)を1度計算すれば求まるのだから要素数に関係なく一定の時間で完了します。したがって時間計算量はO(1)です。

もうひとつ要素の検索。vector中からある値を持つ要素を探し出す場合はどうでしょう。各要素の値はそれぞれの内容を読んでみないとわからないのだから、集合の先頭から順に調べるしかありません。すなわち平均n/2回の参照と比較を行うことになりますから、時間計算量はO(n)となります。

[順序コンテナ(Sequence Container)]

各要素が直線的に配置されたコンテナを順序コンテナと呼んでいます。STLではvector,list,dequeが順序コンテナです。順序コンテナXに許されるオペレーションは以下のとおりです。

以下の説明において:

  n : 非負整数
  t : Xの要素型のインスタンス
i,j : InputIterator
p,q : Xに対応するイテレータ
また[i,j)は"iから始まりjに達しない(i以上j未満)範囲"を表します。

[配列をvectorで置き換える]

'伸長する配列'をSTLコンテナのひとつであるvectorで書き直してみましょう:
  vector<int> array;
  int data;
  ary.push_back(data);
あきれるほど簡単になりました。vectorの中には現在の要素数、許容量、そして要素数が許容量を越えそうなときの領域の伸長などなど、必要な変数や処理が封じ込められています。プログラマは'何をしたいか'をコードとして表現するだけで、'どうやって実現するか'はvectorが面倒みてくれます。プログラマはvectorの特性と使い方だけを知っていればいいのです。

[vector]

vectorはC++が言語仕様として始めから持っている配列とほぼ同様に使えます。配列より便利なのは、可変長であることです。要素数の増加に応じて自動的に領域を広げてくれます。

[list]

listは各要素をポインタによる'数珠つなぎ'によって保持しています。listには次の要素を指すポインタのみを用いる単方向リストと、次の要素/前の要素を指す2つのポインタを用いる双方向リストとがありますが、STLのlistは双方向リストで実装されています。

[deque]

dequeはDouble Ended QUEueの略、vectorの伸長が末端方向のみであるのに対し、dequeは先頭方向にも伸長される、vectorのバリエーションです。
/*
 * phonebook.cpp
 *   vector/list/deque を使った簡単な電話番号簿
 */

#include <iostream>
#include <fstream>
#include <string>
#include <list>
#include <vector>
#include <deque>
#include <queue>
#include <iterator>
#include <algorithm>

/* 次の3つのいずれかを有効にすること */
   #define USE_VECTOR
// #define USE_LIST
// #define USE_DEQUE

using namespace std;

struct record {
  string name;
  string phone;
  record(const string& n, const string& p) : name(n), phone(p) {}
  record(const string& n) : name(n) {}
  record() {}
};

// レコードの比較: nameフィールドのみを比較の対象とする
inline bool operator==(const record& x, const record& y) {
  return x.name == y.name;
}

struct greater_record : binary_function<record,record,bool> {
 bool operator()(const record& x, const record& y) const {
  return x.name > y.name;
 }
};

// レコード(名前と電話番号の組)を出力する
ostream& operator<<(ostream& strm, const record& r) {
  return strm << r.name << " : " << r.phone;
}

// レコード(名前と電話番号の組)を入力する
istream& operator>>(istream& strm, record& r) {
  char dummy;
  return strm >> r.name >> dummy >> r.phone;
}

#if defined(USE_VECTOR)
typedef vector<record> book_type;
#elif defined(USE_LIST)
typedef list<record>   book_type;
#elif defined(USE_DEQUE)
typedef deque<record>  book_type;
#endif

// プロンプト
char prompt() {
  string command;
  cout << "add/delete/find/list/clear/quit [a,d,f,l,c,q] ?" << flush;
  cin >> command;
  return command[0];
}

int main() {

  book_type book;

  // 電話番号簿をファイルから読み出す
  cout << "loading file..." << endl;
  ifstream in("phonebook.txt");
  if ( in.is_open() ) {
    copy(istream_iterator<record>(in),istream_iterator<record>(),
         inserter(book,book.begin()));
    in.close();
  }

  bool quit = false;
  do {
    string name;
    string phone;
    book_type::iterator i;
    switch ( prompt() ) {
    // 追加
    case 'a' : case 'A' : {
      cout << "name:" << flush;
      cin >> name;
      // 登録されていないことを確認する
      if ( find(book.begin(), book.end(), name) != book.end() ) {
        cout << "already exists." << endl;
      } else {
        cout << "phone:" << flush;
        cin >> phone;
        // レコードを追加する
        book.push_back(record(name,phone));
      }
      break;
    }
    // 削除
    case 'd' : case 'D' : {
      cout << "name:" << flush;
      cin >> name;
      // 登録されていればそれを削除する
      i = find(book.begin(), book.end(), name);
      if ( i  == book.end() ) {
        cout << "not found." << endl;
      } else {
        book.erase(i);
      }
      break;
    }
    // 検索
    case 'f' : case 'F' : {
      cout << "name:" << flush;
      cin >> name;
      // 登録されていればそのレコードを出力する
      i = find(book.begin(), book.end(), name);
      if ( i == book.end() ) {
        cout << "not found." << endl;
      } else {
        cout << *i << endl;
      }
      break;
    }
    // リスト
    case 'l' : case 'L' : {
      cout << book.size() << "entries:" << endl;
      // 昇順に出力するためにpriority_queueを使う
      priority_queue<record,vector<record>,greater_record> pqueue;
      for ( i = book.begin(); i != book.end(); ++i )
        pqueue.push(*i);
      // 全レコードを出力する
      while ( !pqueue.empty() ) {
        cout << pqueue.top() << endl;
        pqueue.pop();
      }
      break;
    }
    // クリア
    case 'c' : case 'C' : {
      book.clear();
      break;
    }
    // 終了
    case 'q' : case 'Q' : {
      quit = true;
      break;
    }
    default :
      cout << '?' << endl;
    }
  } while ( !quit );

  // 電話番号簿をファイルに書き込む
  cout << "saving file..." << endl;
  ofstream out("phonebook.txt");
  if ( out.is_open() ) {
    copy(book.begin(), book.end(), ostream_iterator<record>(out,"\n"));
    out.close();
  }

  return 0;
}

※ コラム Compile-time Polymorphism

vector,list,dequeによる電話番号簿の"list"コマンドではコンテナ内の要素を昇順に並び替えて出力するためにpriority_queueを使っています。コンテナ内の要素をソートするのならアルゴリズムsortによって、
  sort(book.begin(), book.end());
とやればよさそうなものですが、ダメなんです。sortの引数として許されるイテレータはRandomAccessIteratorでなくてはならないため、vector,queueはいいとしてもイテレータがBidirectionalIteratorであるlistをコンテナとした場合、アルゴリズムsortが使えません。かといって
#if defined(USING_LIST)
  book.sort(); // listはメンバ関数sortを持っている
#else
  sort(book(), book.end());
#endif
のような条件コンパイルは避けたいものです。できることなら
 generic_sort(book.begin(), book.end());
と書くことでvectorでもdequeでもlistでもソートできないものでしょうか。generic_sortが引数に与えられたイテレータがRandomAccessIteratorであるか否かを判断し、それによって適切なソートアルゴリズムを呼び分けることができればいいわけです。iterator_categoryを使えばそれが可能となります。
  // イテレータがRandomAccessIteratorであるとき
  template<class Iterator>
  void __generic_sort(Iterator first, Iterator last、
                      random_access_iterator_tag) {
    sort(first,last);
  }

  // イテレータがForwardIterator(以上)であるとき
  template<class Iterator>
  void __generic_sort(Iterator first, Iterator last、
                      forward_iterator_tag) {
    // 一旦配列にコピーし、ソートの後に書き戻す
    size_t n = distance(first,last);
    Iterator::value_type* a = new Iterator::value_type[n];
    copy(first,last,a);
    sort(a, a+n);
    copy(a, a+n, first);
    delete[] a;
  }

  // iterator_categoryに応じて呼び分ける
  tempalte<class Iterator>
  void generic_sort(Iterator first, Iterator last) {
    __generic_sort(first, last,
                   iterator_traits<Iterator>::iterator_category());
  }
第3引数の型が異なる2種類の__generic_sortを用意しました。そしてその2つをiterator_traits<Iterator>::iterator_categoryで呼び分けています。iterator_traits<Iterator>::iterator_categoryはIteratorがRandomAccessIteratorであればrandom_access_iterator_tag、BidirectionalIteratorであればbidirectional_iterator_tagのtypedefです。random_access_iterator_tagやbidirectional_iterator_tagにはメンバがひとつもなく、イテレータの種類を区別するためだけに用いられます。
 // ヘッダ<iterator>で定義されている5つのiterator_tag
 struct input_iterator_tag {};
 struct output_iterator_tag {};
 struct forward_iterator_tag:       public input_iterator_tag {};
 struct bidirectional_iterator_tag: public forward_iterator_tag {};
 struct random_access_iterator_tag: public bidirectional_iterator_tag {};
iterator_tagを使ってイテレータの種別を認識し、適した関数をコンパイル時に決定するこの巧妙な手法は"Compile-time Polymorphism"(コンパイル時ポリモーフィズム)と呼ばれています。STLアルゴリズムのあちこちで、この"Compile-time Polymorphism"が効果的に使われています。

[連想コンテナ(Associative Container)]

順序コンテナvector,list,dequeはいずれもコンテナ内の要素が線形(リニア)に配置されており、各要素の並ぶ順序は利用者すなわちプログラマがコントロールしています。各要素の並ぶ順序に意味がある場合に使われるのですが、検索に要する時間計算量は要素の並びに規則性がないのでしらみつぶしに検索するしかないためO(n)すなわち要素数に比例して時間がかかります。連想コンテナ(Associative Container)set/multiset/map/multimapは要素の順序をコンテナにゆだねるかわりに、より高速な検索を可能にします。

連想コンテナはその実装に"2進木"を利用しています。2進木(Binary Tree)は、各要素を保持する節(Node:ノード)それぞれがさらに2つの枝(Branch:ブランチ)を持っており、この枝の先には節がぶら下がります。この構造がまるで木(を逆さにしたもの)に見えることから、木(Tree)と呼ばれています。最上部にある節を根(Root)、左右のどちらの枝にも節をぶら下げていない末端の節を葉(Leaf)と呼びます。そして、set内の木の構造には制約条件が付けられています。それは、木を構成するすべての節Nに対し:

この条件を課することによって、順序コンテナはるかに高速な検索を可能にしてます。木の中から特定の値を持つ要素(節)を探し出すには、まず根と比較します。そして目的とする値の方が大きければ左の枝、小さければ右の枝にぶらさがる節をたどり、その節との比較を見つかるまで繰り返します。枝をひとつたどるごとに比較対象となる節の数が約1/2となりますから、検索に要する時間計算量はO(log(n))となります。ただし時間計算量がO(log(n)となるには、各要素がまんべんなく散らばって枝振りの良い木でなくてはなりません。枝振りの悪い木では最悪O(n)にまで性能が低下します。set内の木はRed-Black-Treeと呼ばれるバランスアルゴリズム(各要素をまんべんなく配置する手法)が使われており、根から最も遠い葉でも、根から最も近い葉までの距離(その節にたどり着くまでの枝の数)が2倍以上にならないように調整されます。

連想コンテナは要素の大小関係に基づいてコンテナ内に要素を配置します。そのために要素の大小を判断するための関数オブジェクト(比較オブジェクト)をテンプレート引数Compareに与えます。比較オブジェクトのインスタンスcompは次のふたつの条件を満足しなければなりません(関数オブジェクトについては[関数オブジェクト]を参照):

  1. comp(x,y) と comp(y,x) が共に真とはならないこと。
  2. comp(x,y) と comp(y,z) が共に真ならば comp(x,z) も真であること。
たとえば次の関数オブジェクトを連想コンテナの比較オブジェクトとして与えてはなりません。
  struct bad_compare : binary_function<int,int,bool> {
    bool operator()(const int& x, const int& y) const {
      return x <= y;
    }
  };

  set<int,bad_compare> s; // まちがい!
bad_compare::operator()の二つの引数が同じ値であったとき、上記の条件[1]を満たさないからです。コンパイルエラーにはならないので注意してください。

comp(c,y)が真であるとき、コンテナ内にはxがyに先行するように配置されます。comp(x,y)とcomp(y,x)が共に偽(すなわち x == y)であるとき、xとyのコンテナ内での順序は不定となります。

したがって、set< T,less<T> >は要素Tを昇順(小さい順)に、set< T,greater<T> >は降順に配置します(less<T>は連想コンテナのデフォルトtemplate引数ですから、set<T> と省略できます)。

  // 比較オブジェクトによる要素の順序の制御
  set< int, less<int> >    as;
  set< int, greater<int> > ds;

  int a[] = { 0, 2, 4, 6, 8, 9, 7, 5, 3, 1 };
  for ( int i = 0; i < 10; ++i ) {
    as.insert(a[i]);
    ds.insert(a[i]);
  }

  cout << "\n昇順: ";
  copy(as.begin(), as.end(), ostream_iterator<int>(cout," "));
  cout << "\n降順: ";
  copy(ds.begin(), ds.end(), ostream_iterator<int>(cout," "));

  実行結果:
    昇順: 0 1 2 3 4 5 6 7 8 9
    降順: 9 8 7 6 5 4 3 2 1 0
また、さきほどの2つの条件を満足するなら、どんな二項関数オブジェクトでも比較オブジェクトとして機能します。
  // 文字列の長さで順序を決める
  struct less_str_len : binary_function<string,string,bool> {
    bool operator()(const string& x, const string& y) const {
      return x.size() < y.size();
    }
  };

  multiset<string,less_str_len> ms;
  const char* fruit[] = { "apple", "banana", "cherry", "lemon", "melon",
                          "strawberry", "peach", "kiwi", "pineapple" };
  for ( int i = 0; i < 9; ++i )
    ms.insert(fruit[i]);

  copy(ms.begin(), ms.end(), ostream_iterator<string>(cout,"\n"));

  実行結果:
    kiwi
    apple
    lemon
    melon
    peach
    banana
    cherry
    pineapple
    strawberry

[set]

setは等しい要素の重複を許さない集合です。setに要素を挿入するとき、そのset内に挿入しようとしている要素と等しいものがすでに存在するとき、setは要素の挿入を許しません。
/*
 * phonebook.cpp
 *   set を使った簡単な電話番号簿
 */

#include <iostream>
#include <fstream>
#include <string>
#include <set>
#include <iterator>
#include <algorithm>

using namespace std;

struct record {
  string name;
  string phone;
  record(const string& n, const string& p) : name(n), phone(p) {}
  record(const string& n) : name(n) {}
  record() {}
};

// レコードの比較: nameフィールドのみを比較の対象とする
struct less_record : binary_function<record,record,bool> {
 bool operator()(const record& x, const record& y) const {
  return x.name < y.name;
 }
};

// レコード(名前と電話番号の組)を出力する
ostream& operator<<(ostream& strm, const record& r) {
  return strm << r.name << " : " << r.phone;
}

// レコード(名前と電話番号の組)を入力する
istream& operator>>(istream& strm, record& r) {
  char dummy;
  return strm >> r.name >> dummy >> r.phone;
}

typedef set<record,less_record> book_type;

// プロンプト
char prompt() {
  string command;
  cout << "add/delete/find/list/clear/quit [a,d,f,l,c,q] ?" << flush;
  cin >> command;
  return command[0];
}

int main() {

  book_type book;

  // 電話番号簿をファイルから読み出す
  cout << "loading file..." << endl;
  ifstream in("phonebook.txt");
  if ( in.is_open() ) {
    copy(istream_iterator<record>(in),istream_iterator<record>(),
         inserter(book,book.begin()));
    in.close();
  }

  bool quit = false;
  do {
    string name;
    string phone;
    switch ( prompt() ) {
    // 追加
    case 'a' : case 'A' : {
      cout << "name:" << flush;
      cin >> name;
      // 登録されていないことを確認する
      if ( book.find(name) != book.end() ) {
        cout << "already exists." << endl;
      } else {
        cout << "phone:" << flush;
        cin >> phone;
        // レコードを追加する
        book.insert(record(name,phone));
      }
      break;
    }
    // 削除
    case 'd' : case 'D' : {
      cout << "name:" << flush;
      cin >> name;
      // 登録されていればそれを削除する
      if ( book.find(name) == book.end() ) {
        cout << "not found." << endl;
      } else {
        book.erase(name);
      }
      break;
    }
    // 検索
    case 'f' : case 'F' : {
      cout << "name:" << flush;
      cin >> name;
      // 登録されていればそのレコードを出力する
      book_type::iterator i = book.find(name);
      if ( i == book.end() ) {
        cout << "not found." << endl;
      } else {
        cout << *i << endl;
      }
      break;
    }
    // リスト
    case 'l' : case 'L' : {
      cout << book.size() << "entries:" << endl;
      // 全レコードを出力する
      for ( book_type::iterator i = book.begin();
            i != book.end(); ++i )
        cout << *i << endl;
      break;
    }
    // クリア
    case 'c' : case 'C' : {
      book.clear();
      break;
    }
    // 終了
    case 'q' : case 'Q' : {
      quit = true;
      break;
    }
    default :
      cout << '?' << endl;
    }
  } while ( !quit );

  // 電話番号簿をファイルに書き込む
  cout << "saving file..." << endl;
  ofstream out("phonebook.txt");
  if ( out.is_open() ) {
    copy(book.begin(), book.end(), ostream_iterator<record>(out,"\n"));
    out.close();
  }

  return 0;
}

[multiset]

setの条件である"要素の重複を許さない"をとっぱらったのがmultisetです。簡単なデータベースもどきを作るとしましょうか。
  struct Person {
    string name;     // 氏名
    date   birthday; // 生年月日
    string address;  // 住所
    ...
  };
このとき、Personの大小関係はメンバ変数nameで決定されるとしましょう。このPersonのコンテナとしてsetを使うと、同性同名の複数のPersonを登録できなくなってしまいます。こんなときにmultisetを使います。multisetは比較の結果が一致しても挿入を許します。

multisetに対する挿入/削除/検索に要する時間計算量はsetと同じくO(log(n))となります。multisetから特定の値を持つ要素を検索すると、当然ながら複数の要素が見つかることでしょう。メソッドlower_bound()/upper_bound()を用いて、見つかった複数の要素を参照できます:

  multiset<int> ms;
  for ( int i = 0; i < 3; ++i )
    for ( int j = 0; j < 3; ++j )
      ms.insert(j);
  const int x = 1;
  multiset<int>::iterator first, last;
  first = ms.lower_bound(x);
  last  = ms.upper_bound(x);
  while ( first != last ) {
    cout << *first << ' ';
    ++first;
  }

  実行結果:
    1 1 1
すなわち、[first,last)言い換えればlower_bound()から始まりupper_bound()に達しない範囲(のiteratorが指す要素)が、検索の結果となります。ちなみにlower_bound()とupper_bound()のそれぞれの値をペアにした値を返すequal_range()も用意されています。
  multiset<int> ms;
  for ( int i = 0; i < 3; ++i )
    for ( int j = 0; j < 3; ++j )
      ms.insert(j);
  const int x = 1;
  typedef multiset<int>::iterator iter;
  pair<iter,iter> range;
  range = ms.equal_range(x);
  while ( range.first != range.second ) {
    cout << *range.first << ' ';
    ++range.first;
  }

  実行結果:
    1 1 1

[map]

mapとは、たとえば名前と電話番号とか、ドメイン名とIPアドレスとの管理だとか、2つの要素の1対1の対応関係を保持します。それゆえ、mapはしばしばDictionary(辞書)と呼ばれています。STLにおけるmapはsetのバリエーションとして実装されています。つまり、検索のキーとなる要素'Key'とそれに対応する値を持つ要素'T'とを組(pair)にして、その組を2進木で管理します。
/*
 * phonebook.cpp
 *   map を使った簡単な電話番号簿
 */

#include <iostream>
#include <fstream>
#include <string>
#include <map>
#include <iterator>
#include <algorithm>

using namespace std;

// 名前(string)をKey, 電話番号(string)をValueとする辞書
typedef map<string,string>    book_type;

// レコード(名前と電話番号の組)を出力する
ostream& operator<<(ostream& strm, const book_type::value_type& v) {
  return strm << v.first << " : " << v.second;
}

// 電話番号簿をファイルに書き込む
ofstream& operator<<(ofstream& strm, const book_type& book) {
  // レコード数を書き込む
  int entries = book.size();
  strm << entries << endl;
  // 全レコードを書き込む
  for ( book_type::const_iterator i = book.begin();
        i != book.end();
        ++i ) {
    strm << i->first << endl
         << i->second << endl;
  }
  return strm;
}

// 電話番号簿をファイルから読み出す
ifstream& operator>>(ifstream& strm, book_type& book) {
  // 要素数を読み出す
  int entries;
  strm >> entries;
  string name;
  string phone;
  // レコードを読み出して電話番号簿に追加する
  while ( entries-- ) {
    strm >> name;
    strm >> phone;
    book[name] = phone;
  }
  return strm;
}

// プロンプト
char prompt() {
  string command;
  cout << "add/delete/find/list/clear/quit [a,d,f,l,c,q] ?" << flush;
  cin >> command;
  return command[0];
}

int main() {

  book_type book;

  // 電話番号簿をファイルから読み出す
  cout << "loading file..." << endl;
  ifstream in("phonebook.txt");
  if ( in.is_open() ) {
    in >> book;
    in.close();
  }

  bool quit = false;
  do {
    string name;
    string phone;
    switch ( prompt() ) {
    // 追加
    case 'a' : case 'A' : {
      cout << "name:" << flush;
      cin >> name;
      // 登録されていないことを確認する
      if ( book.find(name) != book.end() ) {
        cout << "already exists." << endl;
      } else {
        cout << "phone:" << flush;
        cin >> phone;
        // レコードを追加する
        book[name] = phone;
      }
      break;
    }
    // 削除
    case 'd' : case 'D' : {
      cout << "name:" << flush;
      cin >> name;
      // 登録されていればそれを削除する
      if ( book.find(name) == book.end() ) {
        cout << "not found." << endl;
      } else {
        book.erase(name);
      }
      break;
    }
    // 検索
    case 'f' : case 'F' : {
      cout << "name:" << flush;
      cin >> name;
      // 登録されていればそのレコードを出力する
      book_type::iterator i = book.find(name);
      if ( i == book.end() ) {
        cout << "not found." << endl;
      } else {
        cout << *i << endl;
      }
      break;
    }
    // リスト
    case 'l' : case 'L' : {
      cout << book.size() << "entries:" << endl;
      // 全レコードを出力する
      for ( book_type::iterator i = book.begin();
            i != book.end(); ++i )
        cout << *i << endl;
      break;
    }
    // クリア
    case 'c' : case 'C' : {
      book.clear();
      break;
    }
    // 終了
    case 'q' : case 'Q' : {
      quit = true;
      break;
    }
    default :
      cout << '?' << endl;
    }
  } while ( !quit );

  // 電話番号簿をファイルに書き込む
  cout << "saving file..." << endl;
  ofstream out("phonebook.txt");
  if ( out.is_open() ) {
    out << book;
    out.close();
  }

  return 0;
}

[multimap]

mapがsetのバリエーションであるように、multimapはmultisetのバリエーションです。近頃は個人が複数の電話を持つのはちっとも珍しくありません。このような1対多の関連を表現するのがmultimapです。
  typedef multimap< string, string > PhoneBook;
  typedef PhoneBook::value_type Entry;
  PhoneBook book;
  book.insert(Entry("episteme", "045-XXX-XXXX"));
  book.insert(Entry("episteme", "060-YYY-YYYY"));
  book.insert(Entry("police"  , "110"));
  book.insert(Entry("fire"    , "119"));
こうやって電話番号を複数個登録しておくことができます。ただし、ひとつのKeyに対して対応するTが一意に定まらないので、mapにはあった連想配列的な参照のできるoperator[](const Key&)はサポートされません。multimapからKeyに対応する複数のTを検索するにはlower_bound,upper_boundを使います。
  PhoneBook::iterator first = book.lower_bound("episteme");
  PhoneBook::iterator last  = book.upper_bound("episteme");
  while ( first != last ) {
    cout << first->second << endl;
    ++first;
  }

  実行結果:
    045-XXX-XXXX
    060-YYY-YYYY
equal_rangeはlower_bound,uppre_boundのそれぞれの戻り値をpairにして返してくれます。
  pair<PhoneBook::iterator,PhoneBook::iterator> i;
  i = book.equal_range("episteme");
  while ( i.first != i.second ) {
    cout << i.first->second << endl;
    ++i.first;
  }

[ビット集合 bitset]

  template<size_t N> class bitset;
bitsetはSTLコンテナの中でも異色な存在で、boolの集合(固定長bool配列)を管理します。指定したビットのON/OFFや右/左シフト、bitset同士のand,or,xorなどの操作が可能です。
  /*
   *  bitsetを使って200までの素数表を作る
   */

  #include <iostream>
  #include <bitset>

  using namespace std;

  int main() {
    const int N = 200;
    bitset<N> primes; // 長さNのbool配列
    // primes[i] == false ならば i は素数である
    primes[0] = true;
    primes[1] = true;
    // "エラトステネスのふるい"
    for ( int i = 0; i < N; ++i )
      if ( !primes[i] ) {
        // iが素数であったとき、その倍数は素数ではない。
        cout << i << ' ';
        for ( int j = i + i; j < N; j += i )
          primes[j] = true;
    }
    cout << endl;
    return 0;
  }

  実行結果:
    2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83
    89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
    179 181 191 193 197 199

[コンテナ・アダプタ]

STLにはvector,list,dequeなどのコンテナの他にstack,queue,priority_queueの3つのコンテナが用意されています。これらstack,queue,priority_queueはSTLコンテナを内包し、それぞれのメンバ関数は内包されたコンテナのメンバ関数を呼び出すことで実装されています。

[stack]

  template <class T, class Container = deque<T> >
  class stack;
stackはメンバ関数push_back(末尾に挿入),pop_back(末尾要素を削除)を持つコンテナを内包した先入れ後出しバッファです。Sequenceコンテナvector,list,dequeはいずれもpush_back,pop_backを持っていますから、これらをstackの内包コンテナとして用いることができます。
 stack< T,vector<T> >  : vector<T>によるstack
 stack< T,list<T> >    : list<T>によるstack
 stack< T,deque<T> >   : deque<T>によるstack
 stack<T>              : stack< T,deque<T> > と同じ
stackのメンバ関数は以下のとおりです。
  bool empty()                   : 要素数が0ならtrueを返す
  size_type size()               : 要素数を返す
  value_type& top()              : 末尾の要素を返す
  const value_type& top() const  : 末尾の要素を返す
  void push(const value_type& x) : 末尾に挿入する
  void pop()                     : 末尾の要素を削除する
  // 入力された文字列を逆順に出力する
  stack<string> ss;
  string word;
  while ( cin >> word )
    ss.push(word);
  while ( !ss.empty() ) {
    cout << ss.top() << endl;
    ss.pop();
  }

[queue]

  template <class T, class Container = deque<T> >
  class queue;
queueはメンバ関数push_back(末尾に挿入),pop_front(先頭要素を削除)を持つコンテナを内包した先入れ先出しバッファです。Sequenceコンテナlist,dequeをqueueの内包コンテナとして用いることができます。
  queue< T,list<T> >    : list<T>によるqueue
  queue< T,deque<T> >   : deque<T>によるqueue
  queue<T>              : queue< T,deque<T> > と同じ
queueのメンバ関数は以下のとおりです。
  bool empty()                     : 要素数が0ならtrueを返す
  size_type size()                 : 要素数を返す
  value_type& front()              : 先頭の要素を返す
  const value_type& front() const  : 先頭の要素を返す
  value_type& back()               : 末尾の要素を返す
  const value_type& back() const   : 末尾の要素を返す
  void push(const value_type& x)   : 末尾に挿入する
  void pop()                       : 先頭の要素を削除する
  // 入力された文字列を正順に出力する
  queue<string> sq;
  string word;
  while ( cin >> word )
    sq.push(word);
  while ( !sq.empty() ) {
    cout << sq.front() << endl;
    sq.pop();
  }

[priority_queue]

  template <class T, class Container = vector<T>,
            class Compare = less<typename Container::value_type> >
  class priority_queue;
priority_queueは要素の大小関係に従い、大きい要素から順に取り出すことのできるバッファです。要素の大小関係は第3テンプレート引数に与えた関数オブジェクトで指定します。vectorとdequeがpriority_queueの内包コンテナとなることができます。
 priority_queue< T, vector<T> > : vector<T>によるpriority_queue
 priority_queue< T, deque<T> >  : deque<T>によるpriority_queue
 priority_queue< T >            : priority_queue< T, vector<T> >と同じ
queueのメンバ関数は以下のとおりです。
  bool empty()                     : 要素数が0ならtrueを返す
  size_type size()                 : 要素数を返す
  const value_type& top() const    : 先頭の要素(優先順位最大)を返す
  void push(const value_type& x)   : 要素を挿入する
  void pop()                       : 先頭の要素を削除する
  // 入力された整数を大きい順に出力する
  priority_queue<int> pq;
  // priority_queue< int,vector<int>,greater<int> > pq; ならば小さい順
  int n;
  while ( cin >> n )
    pq.push(n);
  while ( !pq.empty() ) {
    cout << pq.top() << ' ';
    pq.pop();
  }

  実行結果:
    1 4 5 2 6 3 4 8
    ^Z
    8 6 5 4 4 3 2 1

[コンテナの選択]

このようにSTLは様々なコンテナを提供してくれています。プログラマはそれぞれのコンテナの特性を理解し、目的に応じたコンテナを選択しなければなりません。挿入/削除/検索に要する時間計算量がコンテナ選択の基準のひとつとなるでしょう。
 ---------------- コンテナ毎の操作と時間計算量 -------------

                    配列  vector list     deque    set         map
                                                 (multiset)   (multimap)
先頭に挿入          不可  O(N)   O(1)     O(1)    --- *2      --- *2
末尾に挿入          不可  O(1)   O(1)     O(1)    --- *2      --- *2
中央部に挿入        不可  O(N)   O(1) *1  O(1)    --- *2      --- *2
先頭の要素を削除    不可  O(N)   O(1)     O(1)    --- *2      --- *2
末尾の要素を削除    不可  O(1)   O(1)     O(1)    --- *2      --- *2
中央部の要素を削除  不可  O(N)   O(1) *1  O(N)    --- *2      --- *2
検索                O(N)  O(N)   O(N)     O(N)    O(logN)     O(logN)
要素の変更/置換     O(1)  O(1)   O(1)     O(1)    O(logN) *3  O(logN) *3
*1 : イテレータが挿入/削除位置にあると仮定した場合。
*2 : set(multiset),map(multimap)は挿入位置を外部から指定することができない。要素の挿入/削除の時間計算量はO(logN)である。
*3 : set(multiset),map(multimap)のKeyの変更/置換は削除と挿入によって実現する。map(multimap)のTの変更/置換はO(1)。

また要素のアクセスはイテレータを介して行ないます。vector,dequeのイテレータはRandomAccessIteratorすなわち任意の位置の要素をアクセスできます。が、list,set(multiset),map(multimap)のイテレータはBidirectionalIteratorですからひとつづつ次/前に移動することしかできません。

以下にコンテナの選択基準に関するいくつかの項目が並んでいます。それぞれの項目にYES,NOに対応するコンテナを選択していけば目的に適したコンテナが見つかることでしょう。

  1. 要素数は固定か?
    YES -> 配列
    NO -> vector, list, deque, set(multiset), map(multimap)

  2. 任意の要素に高速にアクセスしたいか?
    YES -> 配列, vector, deque
    NO -> list, set(multiset), map(multimap)

  3. 要素の重複を許すか?
    YES -> 配列, vector、list、deque, multiset, multimap
    MO -> set, map

  4. 先頭への要素の挿入/削除を頻繁に行なうか?
    YES -> list, deque
    NO -> vector

  5. 末尾への要素の挿入/削除を頻繁に行なうか?
    YES -> vector
    NO -> list、deque

  6. 検索を頻繁に行なうか?
    YES -> set(multiset), map(multimap)
    NO -> 配列, vector, list, deque

  7. 外部キーによる検索を行なうか?
    YES -> map(multimap)
    NO -> 配列, vector, list, deque, set(multiset)

[値ベースコンテナと参照ベースコンテナ]

STLが提供する各種コンテナはすべて"値ベースコンテナ"です。値ベースコンテナは、コンテナに要素xが挿入されるとき、コンテナ内にはxのコピーが格納されます。したがって:
  void insert(vector<Foo>& container) {
    foo* f = new Foo;
    container.push_back(*f);
    delete f;
  }
のような場合、関数insertを抜けたときfはdeleteされますがコンテナには*fのコピーが格納されますから、コンテナ内の要素が不正となることはありません。ただし、コンテナに要素を挿入するたびに要素のコピーが作られるので、コピーに時間のかかる要素の値ベースコンテナは速度的に満足できないこともあるでしょう。さらに、ひとつの要素を複数のコンテナで共有することができません。
  #include <iostream>
  #include <list>
  #include <vector>
  #include <iterator>

  using namespace std;

  int main() {
    vector<int> ll;
    vector<int> vv;
    vv.push_back(1);
    vv.push_back(2);
    vv.push_back(3); // vv = { 1, 2, 3 }
    // vvの要素をllにコピー
    copy(vv.begin(), vv.end(), back_inserter(ll));
    // vvの要素の変更はllに反映されない。
    vv[0] = 0;
    cout << "vv の先頭は " << vv.front() << endl; // 0になってる
    cout << "ll の先頭は " << ll.front() << endl; // 元のまま...
    return 0;
  }

  実行結果:
     vv の先頭は 0
     ll の先頭は 1
複数のコンテナに要素を共有させたいときはポインタをコンテナの要素とし、参照ベースコンテナとして扱います。
  #include <iostream>
  #include <list>
  #include <vector>
  #include <iterator>

  using namespace std;

  int main() {
    list<int*> ll;
    vector<int*> vv;
    vv.push_back(new int(1));
    vv.push_back(new int(2));
    vv.push_back(new int(3));
    // vvの要素をllにコピー
    copy(vv.begin(), vv.end(), back_inserter(ll));
    *vv[0] = 0;
    cout << "vv の先頭は " << *vv.front() << endl;
    cout << "ll の先頭は " << *ll.front() << endl;

    // 全要素をdeleteする
    for ( vector<int*>::iterator i = vv.begin(); i != vv.end(); ++i )
      delete *i;

    return 0;
  }

  実行結果:
     vv の先頭は 0
     ll の先頭は 0
また、コンテナ内の要素が単一ではない場合、値ベースコンテナは全く無力です。
  // ベースクラス: 動物
  class Animal {
    string name_;
  public:
    Animal(const string& n="") : name_(n) {}
    virtual ~Animal() { cout << "~Animal" << endl; }
    const string& name() const { return name_; }
    virtual bool make_sound() const {
      cout << "......" << endl;
      return false;
    }
  };

  // 派生クラス: 犬
  class Dog : public Animal {
  public:
    Dog(const string& n="") : Animal(n) {}
    virtual ~Dog() { cout << "~Dog"; }
    virtual bool make_sound() const {
      cout << name() << ": わんわん" << endl;
      return true;
    }
  };

  // 派生クラス: 猫
  class Cat : public Animal {
  public:
    Cat(const string& n="") : Animal(n) {}
    virtual ~Cat() { cout << "~Cat"; }
    virtual bool make_sound() const {
      cout << name() << ": にゃおーん" << endl;
      return true;
    }
  };

  int main() {
    vector<Animal> pet;
    pet.push_back(Dog("ポチ"));
    pet.push_back(Cat("タマ"));
    cout << "let's make sound!" << endl;
    for ( int i = 0; i < pet.size(); ++i ) {
      pet[i].make_sound(); // 鳴いてくれる...か?
    }
    cout << "end of making sound" << endl;
    return 0;
  }

  実行結果:
    ~Dog:~Animal
    ~Animal
    ~Cat:~Animal
    let's make sound!
    ......
    ......
    end of making sound
    ~Animal
    ~Animal
ご覧の通り、DogやCatをコンテナに挿入したつもりでも、コンテナ内の要素はあくまでAnimalです。参照ベースコンテナを用いるしかありません。
  int main() {
    vector<Animal*> pet;
    pet.push_back(new Dog("ポチ"));
    pet.push_back(new Cat("タマ"));
    int i;
    cout << "let's make sound!" << endl;
    for ( i = 0; i < pet.size(); ++i ) {
      pet[i]->make_sound();
    }
    cout << "end of making sound" << endl;
    // 後始末
    for ( i = 0; i < pet.size(); ++i ) {
      delete pet[i];
    }
    return 0;
  }

  実行結果:
    let's make sound!
    ポチ: わんわん
    タマ: にゃおーん
    end of making sound
    ~Dog:~Animal
    ~Cat:~Animal

[参照ベースコンテナの後始末]

値ベースコンテナを参照ベースコンテナとして使用する場合、コンテナがデストラクトされるときや要素の削除を伴うメンバ関数をコールしたとき、コンテナ内の要素をdeleteしてはくれませんから、プログラマが明示的にdeleteしなくてはなりません。このとき要素の多重deleteには十分注意してください。
  vector<int*> vv;
  int* one = new int(1);
  int* two = new int(2);
  vv.push_back(one);
  vv.push_back(two);
  vv.push_back(one);

  // 危険! oneが2回deleteされる!
  for ( vector<int*>::iterator i = vv.begin(); i != vv.end(); ++i )
    delete *i;
要素の多重deleteを防止するために要素の重複を許さないsetを、deleteしたかどうかのチェックに利用できます。
  template<class InputIterator>
  void delete_all(InputIterator first, InputIterator last) {
    set<iterator_traits<InputIterator>::value_type> d_set;
    while ( first != last ) {
      if ( d_set.find(*first) == d_set.end() ) {
         d_set.insert(*first);
         delete *first;
      }
      ++first;
    }
  }

  vector<int*> vv;
  ...
  delete_all(vv.begin(), vv.end()); // 多重deleteしない
コンテナのデストラクト時に限らず、要素が削除される操作を行なう際にはdeleteを忘れないよう十分注意してください。

[参照ベースコンテナとauto_ptr]

参照ベースコンテナでは要素の削除時にdeleteがつきまといます。ヘッダ<memory>が提供するauto_ptrはポインタを内包し、auto_ptrがデストラクトされるとき内包するポインタに対してdeleteしてくれます。
  template<class X> class auto_ptr {
    template <class Y> struct auto_ptr_ref {};
  public:
    typedef X element_type;

    explicit auto_ptr(X* p =0) throw();
    auto_ptr(auto_ptr&) throw();
    template<class Y> auto_ptr(auto_ptr<Y>&) throw();

    auto_ptr& operator=(auto_ptr&) throw();
    template<class Y> auto_ptr& operator=(auto_ptr<Y>&) throw();
    ~auto_ptr() throw();

    X& operator*() const throw();
    X* operator->() const throw();

    X* get() const throw();
    X* release() throw();
    void reset(X* p =0) throw();
    auto_ptr(auto_ptr_ref<X>) throw();
    template<class Y> operator auto_ptr_ref<Y>() throw();
    template<class Y> operator auto_ptr<Y>() throw();
  };
さきほどの例をauto_ptrを使って実装したコードを示します。
  int main() {
    vector< auto_ptr<Animal> > pet;
    pet.push_back(auto_ptr<Animal>(new Dog("ポチ")));
    pet.push_back(auto_ptr<Animal>(new Cat("タマ")));
    pet.push_back(auto_ptr<Animal>(new Dog("コロ")));
    pet.push_back(auto_ptr<Animal>(new Cat("ミケ")));
    cout << "let's make sound!" << endl;
    for ( int i = 0; i < pet.size(); ++i ) {
      pet[i]->make_sound();
    }
    cout << "end of making sound" << endl;
    cout << "removing the first/last animal from pet" << endl;
    pet.erase(pet.begin());
    pet.erase(pet.end()-1);
    cout << "2 animals were removed." << endl;
    return 0;
  }

  実行結果:
    let's make sound!
    ポチ: わんわん
    タマ: にゃおーん
    コロ: わんわん
    ミケ: にゃおーん
    end of making sound
    removing the first/last animal from pet
    ~Dog:~Animal
    ~Cat:~Animal
    2 animals were removed.
    ~Cat:~Animal
    ~Dog:~Animal
auto_ptrのコピーを行なうと右辺(コピー元)のauto_ptrはポインタの所有権を失うことに注意してください。
   // 例 1
   X* p = new X;
   auto_ptr<X> a(p); // a は p を保持する
   auto_ptr<X> b;
   b = a;      // b は p を保持する。 a は p の所有権を失う

   // 例 2
   // auto_ptrを引数として渡すときは注意!
   void f(auto_ptr<X> ap) {
     ...
     // ここで ap が保持するポインタがdeleteされる。
   }

   // auto_ptrを参照渡しにすれば...
   void g(const auto_ptr<X>& ap) {
     ...
     // ap が保持するポインタはdeleteされない。
   }

   auto_ptr<X> a;
   a = auto_ptr<X>(new X);
   f(a);  // この瞬間、a はポインタの所有権を失う
   a = auto_ptr<X>(new X);
   g(a);  // 参照を渡せば、deleteされることはない
複数の参照ベースコンテナに共有される要素としてauto_ptrを使ってはいけません。auto_ptrがコピーされるとき、コピー元のauto_ptrは0を保持するからです。
   typedef auto_ptr<Animal> AP;
   AP dog(new Dog("ポチ"));
   AP cat(new Cat("タマ"));
   vector<AP> v1;
   vector<AP> v2;
   v1.push_back(dog);
   v1.push_back(cat);
   int i;
   // v1からv2にコピー
   for ( i = 0; i < 2; ++i )
    v2.push_back(v1[i]); // この瞬間、v1のauto_ptrは所有権を失う

   // 要素の確認
   for ( i = 0; i < 2; ++i ) {
     Animal* p;
     p = v1[i].get(); if ( p ) cout << "v1:"; p->make_sound();
     p = v2[i].get(); if ( p ) cout << "v2:"; p->make_sound();
   }

  実行結果:
    v2:ポチ: わんわん
    v2:タマ: にゃおーん
    ~Dog:~Animal
    ~Cat:~Animal
複数の参照ベースコンテナに共有される要素を実現したいときは、参照カウントなどの手法を用いてください。
  /*
   * 参照カウントによる安全な参照ベースコンテナ
   */
  template <class X>
  class count_ptr {
    X*          ptr_;
    unsigned*   cnt_;
    void inc_ref(const count_ptr& r);
    void dec_ref();
  public:
    explicit count_ptr(X* p =0): ptr_(p), cnt_(0)
      { if ( p ) cnt_ = new unsigned(1); }
    count_ptr(const count_ptr& r)
      { inc_ref(r); }
   ~count_ptr()
      { dec_ref(); }
    count_ptr& operator=(const count_ptr& r)
      { if (this != &r) { dec_ref(); inc_ref(r); } return *this; }
    X& operator*() const
      {return *ptr_; }
    X* operator->() const
      {return ptr_; }
    X* get() const
      {return ptr_; }
    bool unique() const
      {return cnt_ ? *cnt_ == 1 : true;}
  };

  template <class X>
  inline void count_ptr<X>::dec_ref(){
    if ( cnt_ ) {
      if (--*cnt_ == 0) {
        delete cnt_;
        delete ptr_;
      }
      cnt_ = 0;
      ptr_ = 0;
    }
  }

  template <class X>
  inline void count_ptr<X>::inc_ref(const count_ptr<X>& r){
    ptr_ = r.ptr_;
    cnt_ = r.cnt_;
    if ( cnt_ )
      ++*cnt_;
  }

  /*
   * お試し
   */
  int main() {
    typedef count_ptr<Animal> CP;
    CP dog(new Dog("ポチ"));
    CP cat(new Cat("タマ"));
    vector<CP> v1;
    vector<CP> v2;
    v1.push_back(dog);
    v1.push_back(cat);
    int i;
    // v1からv2にコピー
    for ( i = 0; i < 2; ++i )
      v2.push_back(v1[i]);
    // 要素の確認
    for ( i = 0; i < 2; ++i ) {
      cout << "v1:"; v1[i]->make_sound();
      cout << "v2:"; v2[i]->make_sound();
    }
    return 0;
  }

  実行結果:
    v1:ポチ: わんわん
    v2:ポチ: わんわん
    v1:タマ: にゃおーん
    v2:タマ: にゃおーん
    ~Cat:~Animal
    ~Dog:~Animal

[参照ベースset/mapの作り方]

set,multiset,map,multimapを参照ベースコンテナとして使うことを考えてみます:
  #include <iostream>
  #include <set>

  using namespace std;

  int main() {
    set<int*> ss;

    int* table[3] = { new int(1), new int(2), new int(3) };
    ss.insert(table[0]);
    ss.insert(table[1]);
    ss.insert(table[2]);

    // sの中から2を探す
    int n = 2;
    set<int*>::iterator i = ss.find(&n);
    if ( i != ss.end() )
      cout << "見つかりました" << endl;
    else
      cout << "見つかりませんでした" << endl;

    delete table[0];
    delete table[1];
    delete table[2];

    return 0;
  }
実行すると"見つかりませんでした"と出力されます。それもそのはず、set<int*>はポインタ値を要素とし、ポインタ値の大小関係を頼りに要素の検索を行ないます。&nと同じポインタ値がss中に存在するはずがありません。正しく動作させるには要素の比較を"ポインタ値の比較"から"ポインタが指す内容の比較"に変更しなければなりません。
  template<class T>
  struct ptr_less : binary_function<T*,T*,bool> {
    bool operator()(const T* x, const T* y) const {
      return *x < *y;
    }
  };
関数オブジェクトptr_lessが与えられたポインタ値の指す内容の比較を行ないます。このコードをソースに追加し、
  set<int*> ss;
  set< int*,ptr_less<int> > ss;
に置き換えてください。
  #include <iostream>
  #include <set>

  using namespace std;

  template<class T>
  struct ptr_less : binary_function<T*,T*,bool> {
    bool operator()(const T* x, const T* y) const
     { return *x < *y; }
  };

  int main() {
    set< int*,ptr_less<int> > ss;

    int* table[3] = { new int(1), new int(2), new int(3) };

    ss.insert(table[0]);
    ss.insert(table[1]);
    ss.insert(table[2]);

    // sの中から2を探す
    int n = 2;
    set< int*,ptr_less<int> >::iterator i = ss.find(&n);
    if ( i != ss.end() )
      cout << "見つかりました" << endl;
    else
      cout << "見つかりませんでした" << endl;

    delete table[0];
    delete table[1];
    delete table[2];

    return 0;
  }

[参照ベースコンテナでの注意点]

このように、ポインタをコンテナの要素とすることで参照ベースコンテナを作ることができるのですが、前述の後始末問題だけでなくもうひとつ注意しなければならないことがあります。
class Integer {
  int N;
public:
  Integer(int n=0) : N(n) {}
  int get() const { return N; }
  void set(int n) { N = n; }
};

int main() {

  vector<Integer*> v;
  int i;
  for ( i = 0; i < 5; ++i )
    v.push_back(new Integer(i));

  vector<Integer*>::const_iterator ci = v.begin();
  (*ci)->set(100); // あれ?

  for ( i = 0; i < 5; ++i ) {
    cout << v[i]->get() << ' ';
    delete v[i];
  }

  return 0;
}
mainの中ほどで、vector<Integer*>のconst_iteratoeを手に入れて、要素を書き換えています。不思議なことにconstであるにもかかわらず、その要素が変更可能です。

値ベースコンテナvector<Integer>::const_iteratorが指すのはconst Integer&ですが、vector<Integer*>::const_iteratorはconst Integer*ではなく、Integer* constなのです。つまり、ポインタ値を変更できないということであり、そのポインタが指す要素は変更可能です。十分注意してください。