C++11 STL Container Efficiency その５（削除)

その２（範囲挿入）後の状態の各コンテナ内100万要素を１要素ずつ削除。

調査コード

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

// vector::pop_back() ※末尾から削除
// vector<int> v;
while (!v.empty()) {
    v.pop_back();
}

// vector::erase() ※先頭から削除
// vector<int> v;
auto i = v.begin();
while (i != v.end()) {
    i = v.erase(i);
}

// deque::pop_back() ※末尾から削除
// deque<int> d;
while (!d.empty()) {
    d.pop_back();
}

// deque::pop_front() ※先頭から削除
// deque<int> d;
while (!d.empty()) {
    d.pop_front();
}

// list::pop_back() ※末尾から削除
// list<int> l;
while (!l.empty()) {
    l.pop_back();
}

// list::pop_front() ※先頭から削除
// list<int> l;
while (!l.empty()) {
    l.pop_front();
}

// set::erase()
// set<int> s;
auto i = s.begin();
while (i != s.end()) {
    i = s.erase(i);
}

// unordered_set::erase()
// unordered_set<int> us;
auto i = us.begin();
while (i != us.end()) {
    i = us.erase(i);
}

結果

コンテナ	メンバ関数	削除位置	計算量	時間
vector	pop_back()	末尾	O(1)	0 ms
vector	erase()	先頭	O(N)	78378 ms
deque	pop_back()	末尾	O(1)	2 ms
deque	pop_front()	先頭	O(1)	3 ms
list	pop_back()	末尾	O(1)	72 ms
list	pop_front()	先頭	O(1)	67 ms
set	erase()	-	O(1)償却定数時間	94 ms
unordered_set	erase()	-	O(1)平均、O(N)最悪	103 ms

測定環境: Intel Core i7-4850HQ 2300 MHz (4 cores), Apple LLVM version 5.0