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

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

　2つめ：検索に先立って全要素を挿入しておくことができるとき、例えばスペルチェックを行うプログラムではあらかじめ用意された大きな辞書を用意し、必要に応じて新たな単語をいくつか追加した後で検索を行えばよい。検索を始めるまでは要素の列がソートされている必要はないのだから、前述のinsert_into_vectorなど使わず、要素の順などお構いなしにvector_push_backで全要素を追加し、検索処理の直前で一度だけ

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

でソートしてしまえばいい（※6）。

※6

　[0,N)をランダムにかき混ぜた列をpush_backし、最後にsortすると...

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <boost/chrono.hpp>

using namespace boost::chrono;
using namespace std;

int main() {
  const int N = 100000;
  vector<int> input(N);
  iota(input.begin(), input.end(), 0);
  random_shuffle(input.begin(), input.end());

  vector<int> V;
  system_clock::time_point start = system_clock::now();
  for_each(input.begin(), input.end(),
      [&](int item) { V.push_back(item); });
  sort(V.begin(), V.end());
  duration<double> sec = system_clock::now() - start;
  cout << sec.count() << "[sec]\n";
}

/* result
0.01[sec]
*/

　ここまでに述べたテクニックをまとめてちょっとしたコンテナ・アダプタを作っておくのもよいだろう。STLコンテナに求められているよくある決まり文句は省かせてもらうけれども、核となる部分は単純だ:

template <class T, class Compare = std::less<T> >
struct sorted_vector {
  using std::vector;
  using std::lower_bound;
  vector<T> V;
  Compare cmp;
  typedef typename vector<T>::iterator iterator;
  typedef typename vector<T>::const_iterator const_iterator;
  iterator begin() { return V.begin(); }
  iterator end() { return V.end(); }
  const_iterator begin() const { return V.begin(); }
  const_iterator end() const { return V.end(); }
  ...
  sorted_vector(const Compare& c = Compare())
    : V(), cmp(c) {}
  template <class InputIterator>
  sorted_vector(InputIterator first, InputIterator last,
                Const Compare& c = Compare())
    : V(first, last), cmp(c) {
    std::sort(begin(), end(), cmp);
  }
  ...
  iterator insert(const T& t) {
    iterator i = lower_bound(begin(), end(), t, cmp);
    if (i == end() || cmp(t, *i))
      V.insert(i, t);
    return i;
  }
  const_iterator find(const T& t) const {
    const_iterator i = lower_bound(begin(), end(), t, cmp);
    return i == end() || cmp(t, *i) ? end() : i;
  }
};

　このクラスはinsertに要する時間計算量がNオーダであり、logNオーダではないため標準の連想コンテナの要件を満たしてはいない。が、多くのケースでsetと丸ごと置き換えることができる。

※7

　Boost 1.48.0では、ソートされたvectorを内部実装に用いたboost::container::flat_set/flat_multiset/flat_map/flat_multimapが提供されています:

#include <iostream>
#include <vector>
#include <set>
#include <numeric>
#include <boost/container/flat_set.hpp>
#include <boost/chrono.hpp>

using namespace boost::container;
using namespace boost::chrono;
using namespace std;

int main() {
  const int N = 200000;

  std::vector<int> input(N);
  iota(input.begin(), input.end(), 0);
  random_shuffle(input.begin(), input.end());

  system_clock::time_point start;
  duration<double> sec;

  std::set<int> s;
  start = system_clock::now();
  for_each( input.begin(), input.end(),
      [&](int n) { s.insert(n); });
  sec = system_clock::now() - start;
  cout << N << " insertion : " << sec.count() << " [sec] (set)\n";

  start = system_clock::now();
  for ( int i = 0; i < N; ++i) {
    if ( s.find(i) == s.end() ) {
      cout << "gimme a break!!\n";
      break;
    }
  }
  sec = system_clock::now() - start;
  cout << N << " lookup    : " << sec.count() << " [sec] (set)\n";

  flat_set<int> f;
  start = system_clock::now();
  for_each( input.begin(), input.end(),
      [&](int n) { f.insert(n); });
  sec = system_clock::now() - start;
  cout << N << " insertion : " << sec.count() << " [sec] (flat_set)\n";

  start = system_clock::now();
  for ( int i = 0; i < N; ++i) {
    if ( f.find(i) == f.end() ) {
      cout << "gimme a break!!\n";
      break;
    }
  }
  sec = system_clock::now() - start;
  cout << N << " lookup    : " << sec.count() << " [sec] (flat_set)\n";

}

/* result
200000 insertion : 0.0624002 [sec] (set)
200000 lookup    : 0.0156 [sec] (set)
200000 insertion : 5.16361 [sec] (flat_set)
200000 lookup    : 0.0156 [sec] (flat_set)
*/

setが有用な場合とは

　覚えていてほしいのは「setの使用が必ずしもベストな選択とは限らない」ということだ。前述のsorted_vectorあるいはそれと同等なものよりもsetの方が良いケースを並べておこう:

• NオーダとlogNオーダとの差が顕著になるくらいに要素数が大きいと思われるとき
• 挿入回数が検索回数と同程度もしくはそれ以上である、すなわち挿入に要する時間を無視できないとき
• 要素の挿入順がランダム（昇順でない）なとき
• 挿入/検索が交互に行われ、挿入フェーズと検索フェーズとに分離できないとき

　これら4つのケースがすべて当てはまるなら、setを使うべきだろう。setはまさにそれが目的で設計されたものなのだから。しかしながら、4つのケースのどれかがあてはまらないのであれば、setのような複雑な実装によるデータ構造は無駄であり、単純なソート済みvectorの方がずっと高いパフォーマンスを手にできるだろう。

　標準C++ライブラリにあるあらゆるコンポーネントはそれぞれの目的に応じたものとして用意されている。しかしながら時としてその目的が限定的でまれなこともある。原則として、要求を満たす限りできるだけ単純なデータ構造を利用するべきであろう。複雑なデータ構造は思ったほどには広範囲に有効なものとは言い難いのだ。