HOME BLOG ARCHIVE TAGS

Tricks of the Trade #0: std::vector O(1) removals

September 16, 2017

C++ std::vector is practical and fast, but its erase method has linear complexity (triggering potentially slow dtors and [re]assignments).

With constant time member functions back and pop_back, it’s possible to work in O(1) when deleting elements from unordered std::vectors 0:

1
2
3
4
5
6
// it == erase() target, as v::iterator
std::vector<some_type> v;
// (...)
*it = v.back();
v.pop_back();
// (...)

Before container pruning, move semantics 1 can express/optimize the intent of bringing last item to removal position 2:

1
2
3
// (...)
*it = std::move(v.back());
// (...)

Game programmers are known to use this idiom.


Notes:
[0] - error handling left out for brevity;
[1] - depends on compiler versions, etc; full gains demand move assignment availability, see std::move;
[2] - code clarity and optimization happening at the same time - a rare combination;