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

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

　新たに要素を追加するとき、ソート状態を壊さないよう正しい位置に挿入しないとその後のlower_boundが正しく動かなくなる。その正しい位置はまさにlower_boundが教えてくれる:

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);
}

　このヘルパ関数は要素の挿入に先立って、等しい要素がコンテナ内に存在しないことを確かめている。multisetのように要素の重複を許すなら、この確認処理を取り除くことになる（※4）。

※4

　重複を判定するif文を取り除き、int値の一の位を無視した比較関数オブジェクトで[0,30)を vectorに挿入してみます:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

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

int main() {
  vector<int> V;
  auto comp = [](int x, int y) { return x/10 < y/10; };
  for ( int i = 0; i < 30; ++i ) {
    insert_into_vector(V, i, comp);
  }
  for_each(V.begin(), V.end(), [](int item) { cout << item << ' ';});
}

/* result:
9 8 7 6 5 4 3 2 1 0 19 18 17 16 15 14 13 12 11 10 29 28 27 26 25 24 23 22 21 20
*/

　ごらんのとおり、同値要素の並びが挿入時の逆になってしまいます。挿入時の順序を維持したいなら、upper_boundを使えばよいでしょう。

　setのかわりにソートされたvectorを使えば、より高速な検索およびさらに高速な要素の列挙が可能となる。が、その代償として要素の挿入にはset以上の時間を要する。set::insertによるsetへの挿入に要する時間はlogNオーダであるが、前述のinset_into_vectorによるソートされたvectorへの挿入に要する時間はNオーダとなる。vector::insertによりvectorに要素を挿入する際、挿入位置以降に続く要素列を1つずつ列の後方にずらして挿入位置に空席を設けなければならないからだ。任意の位置に挿入するには平均的にN/2個の要素をずらすことになる。

　Nオーダの挿入時間がさほどに大きなペナルティとはならないケースが2つある。

　1つめ：要素が常に列の末尾に挿入される、すなわち挿入される要素が初めから昇順であったなら、vector::insertにおいて要素をずらして空席を設ける必要がない（ちなみに、ほぼ昇順に挿入するのは完全に昇順と同程度に高速だ／※5）。

※5

　[0,N)をランダムにかき混ぜた列と、その先頭から数十%をソートした列とで処理時間を測定しました:

#include <iostream>
#include <iomanip>
#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());
  for ( int i = 0; i <= 100; i += 10 ) {
    sort(input.begin(), input.begin() + N*i/100);
    vector<int> V;
    system_clock::time_point start = system_clock::now();
    for_each(input.begin(), input.end(),
        [&](int item) { V.insert(lower_bound(V.begin(),V.end(),item), item);});
    duration<double> sec = system_clock::now() - start;
    cout << setw(3) << i << "% ordered : " << sec.count() << "[sec]\n";
  }
}

/* result
  0% ordered : 3.55681[sec]
 10% ordered : 3.52561[sec]
 20% ordered : 3.41641[sec]
 30% ordered : 3.24481[sec]
 40% ordered : 2.99521[sec]
 50% ordered : 2.6676[sec]
 60% ordered : 2.2932[sec]
 70% ordered : 1.8252[sec]
 80% ordered : 1.2792[sec]
 90% ordered : 0.686401[sec]
100% ordered : 0[sec]
*/

　なるほど、確かにほぼ昇順であるほど高速ですね。