ひっさしぶりに boost 触ってみた。
最新版 1.48.0 におもしろそげなコンテナ: flat族を見つけたのね。
標準の std::set(およびその一味)は連想コンテナの実装に二分木を使ってるんだが、
boost::container::flat_set(およびその一味)はベタなvectorを使ってる。
そのため要素の格納の際、左右の枝のためのポインタを要するstd::setより省メモリ。
要素の挿入にはそこそこの時間がかかるけど、
lookup(検索)はバイナリ・サーチが使え、二分木のトラバースよか高速との触れ込み。
試してみんべ:
#include <iostream>
#include <set>
#include <boost/container/flat_set.hpp>
#include <boost/chrono.hpp>
using namespace std;
using namespace boost::container;
using namespace boost::chrono;
int main() {
const int N = 1000000;
std::set<int> s;
flat_set<int> f;
// [0..N) を set/flat_setに挿入
for ( int i = 0; i < N; ++i ) {
s.insert(i);
f.insert(i);
}
system_clock::time_point start;
duration<double> sec;
// [0..N) を set から lookup
start = system_clock::now();
for ( int i = 0; i < N; ++i ) {
s.find(i);
}
sec = system_clock::now() - start;
std::cout << "set " << sec.count() << " seconds\n";
// [0..N) を flat_set から lookup
start = system_clock::now();
for ( int i = 0; i < N; ++i ) {
f.find(i);
}
sec = system_clock::now() - start;
std::cout << "flat_set " << sec.count() << " seconds\n";
}
実行結果:
set 0.069004 seconds
flat_set 0.0480028 seconds
ホンマや。確かに速い。