「なぜsetを使っちゃいけないの？」

標準C++ライブラリが提供する連想コンテナsetを使うことが必ずしもベストな選択ではない

setを使うのは"間違い"か？

　いや、間違ってなんかいない。正確に言えば完璧ではないということだ。setを用いるのが妥当と思えるだけのまっとうな理由をまだ示してはいない。要素の挿入（追加）と検索が目的であるなら、特別なデータ構造やメンバ関数は必要としないのだ。いかなるSTLコンテナであろうが、その中から特定の要素を探し出すにはジェネリックなfindアルゴリズムが使えるではないか:

i = std::find(C.begin(), C.end(), "foo");

　メンバ関数set::findと同様、findアルゴリズムはお目当ての要素を指すイテレータを返し、見つからなければC.end()を返してくれる。両者の唯一にして重要な差異は、std::findは線形検索であり、検索に要する時間は要素数Nに比例するのに対し、set::findはlogNに比例する。すなわち、Nが大きいほどその速度差は拡がっていく。

　setあるいはそのほかの連想コンテナに対し、パフォーマンスに関する保証がなされている。要素の検索に要する時間（時間計算量）は要素数Nの対数: logNに比例し、要素の挿入についても同じくlogNに比例することが保証されている。他にも例外安全やイテレータが無効になる条件など、時として重要となる保証もある。

　これらさまざまな特性のすべてを必要としていないのであれば、使ってもいないものに無駄金を払っているようなものだ。高速な要素の挿入と検索を実現するためのデータ構造はそれ相応に複雑なものとなる。setの場合、赤黒木（red-black tree）による実装が典型的であり、それにより相当な空間と時間のオーバヘッドが課せられる。赤黒木で管理される各要素ごとに4つ以上の余分な領域（色マーカー、2つの子と親を指すポインタ）が必要だ（※2）。さらに要素の挿入時には木のバランスを保つ処理、検索と列挙にはポインタの走査処理が時間を消費する。

※2

　Visual C++ 10.0では、set<T>の各要素は:

struct Node {
  Node* _Left;   // 左の子（枝）
  Node* _Parent; // 親
  Node* _Riight; // 右の子（枝）
  T     _Myval;  // 要素
  char  _Color;  // 色マーカー（赤/黒）
  char  _Isnil;  // 親がないときtrue
};

のような構造体となっていました。

　要素の導入と検索において、本当に時間計算量logNが保証されていることが必須であるなら、setは納得のいく選択の一つだ。しかしもしその必要がないのなら、（set以外の）別の選択肢も考えられる。例えば要素の挿入に要する時間計算量がlogNオーダであるという要請を緩和しても構わないとしよう。これはそれほどありそうにないことではない。要素の挿入回数より検索回数の方がはるかに多いケースはよくあることだ。

　対数オーダでの検索を可能にするデータ構成は赤黒木だけではない。計算機科学の基本アルゴリズムの一つにバイナリ・サーチ（binary search）がある。検索範囲を半分、また半分...と絞っていく検索法だ。バイナリ・サーチの時間計算量はlogNに比例するだけでなく、（赤黒木のような）凝ったデータ構造を必要とせず、単なるデータの列に対して適用できる。

　バイナリ・サーチはSTLに用意されているが、それはコンテナとしてではなく、ジェネリックなアルゴリズム: lower_bound, upper_bound, equal_rangeそしてbinary_searchで提供されている。実用上はlower_boundが最も有用だろう。[first,last)が昇順にソートされた範囲であるなら、

std::lower_bound(first, last, x);

はxと等値な要素を指すイテレータを返す（そのような要素が範囲内にあるなら）。xと等値な要素がなかったときは、ソート順を維持してxを挿入する際の挿入位置を返してくれる。STLイテレータを提供するほとんどのデータ構造に対して適用できるが、通常最もお手軽なのはC配列あるいはvectorに対してであろう。

　std::lower_boundとset::findの双方とも検索をlogNに比例した時間で処理するが、両者の比例定数はなかり異なる。450MHz PentiumIIIとg++を用いて、ソートされた100万の要素を詰め込んだvector<double>に対して100万回の検索を行うと0.9秒かかったが、setではそのほぼ倍の1.71秒だった。さらに、setで消費されたメモリ量（48MB）はvectorでの場合（16.8MB）の約3倍におよんだ（※3）。

※3

　メモリ領域の取得/解放時にcout出力を行うアロケータを用意し、setとvectorのそれぞれに要素を追加したときの挙動を調べてみました。

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include "myalloc.h"

using namespace std;

template<typename Vector, typename T>
void insert_into_vector(Vector& v, const T& t) {
  typename Vector::iterator i = lower_bound(v.begin(), v.end(), t);
  if ( i == v.end() || t < *i ) {
    v.insert(i, t);
  }
}

int main() {
  const int N = 10;
  {
    cout << "--- set\n";
    set<int, std::less<int>, my::allocator<int>> s;
    // [0..N) を挿入
    for ( int i = 0; i < N; ++i ) {
      s.insert(i);
    }
  }
  {
    cout << "--- vector\n";
    vector<int, my::allocator<int>> v;
    // [0..N) を挿入
    for ( int i = 0; i < N; ++i ) {
      insert_into_vector(v, i);
    }
  }
}

/* result
--- set
allocate   006A79B0 20bytes
allocate   006A79F0 20bytes
allocate   006A7A10 20bytes
allocate   006A7A30 20bytes
allocate   006A7A50 20bytes
allocate   006A7A70 20bytes
allocate   006A7A90 20bytes
allocate   006A7AB0 20bytes
allocate   006A7AD0 20bytes
allocate   006A7AF0 20bytes
allocate   006A7B10 20bytes
deallocate 006A7B10
deallocate 006A7AF0
deallocate 006A7AD0
deallocate 006A7AB0
deallocate 006A7A90
deallocate 006A7A70
deallocate 006A7A50
deallocate 006A7A30
deallocate 006A7A10
deallocate 006A79F0
deallocate 006A79B0
--- vector
allocate   00861818 4bytes
allocate   00861858 8bytes
deallocate 00861818
allocate   00863D10 12bytes
deallocate 00861858
allocate   00863D28 16bytes
deallocate 00863D10
allocate   006A79B0 24bytes
deallocate 00863D28
allocate   00863D10 36bytes
deallocate 006A79B0
allocate   00863E78 52bytes
deallocate 00863D10
deallocate 00863E78
*/

　setの場合、挿入のたびに20byteの領域を取得しています。これに対し、vectorではより大きな領域を取得し旧領域を解放を繰り返しています。vector::reserve(N)によってN個分の領域をあらかじめ確保しておくことができます。