C++11 STL Container Efficiency その２（範囲挿入)

各STLコンテナの効率比較調査その２。範囲指定で挿入する場合。

調査データ

重複のない整数100万要素とする。

static const int N = 1000000;
std::vector<int> elems(N, 0);
for (int i = 0; i < N; i++) {
    eelms[i] = i;
}

調査コード

対象コンテナは vector, deque, list, set, unordered_set の5つ。

// vector::insert()
std::vector<int> v;
v.insert(v.end(), elems.cbegin(), elems.cend());

// deque::insert()
std::deque<int> d;
d.insert(d.end(), elems.cbegin(), elems.cend());

// list::insert()
std::list<int> l;
l.insert(l.end(), elems.cbegin(), elems.cend());

// set::insert()
std::set<int> s;
s.insert(elems.cbegin(), elems.cend());

// unordered_set::insert()
std::unordered_set<int> us;
us.insert(elems.cbegin(), elems.cend());

結果

コンテナ	メンバ関数	挿入位置	計算量	時間
vector	insert()	末尾	O(N)	2 ms
deque	insert()	末尾	O(N)	3 ms
list	insert()	末尾	O(N)	117 ms
set	insert()	-	O(N*log(M+N))	256 ms
unordered_set	insert()	-	O(N)平均、O(N*(M+N))最悪	162 ms

※ N:挿入する範囲、M:自身の範囲
測定環境: Intel Core i7-4850HQ 2300 MHz (4 cores), Apple LLVM version 5.0