↓ Skip to main content
Side Effects
  1. posts/

A Small Trick That Turns O(n) Vector Erase Into O(1)

··
Cpp
Table of Contents

A Small Trick That Turns O(n) Vector Erase Into O(1)
#

std::vector is my default container in C++. It is fast and cache-friendly. The one weak spot is removing an element from the middle. That is O(n), because the vector shifts everything after the gap. Every time I do it, it annoys me: a tiny change, half of the array moved.

There is an idiom that makes it O(1). You lose the order of the elements. If order does not matter, use it.

std::vector<int> v {
  2, 10, 3, 666, 7, 14, 2137
};

// delete the element at index 3 (value = 666)
std::swap(v[3], v.back());
v.pop_back();

// result: [2, 10, 3, 2137, 7, 14]

Two constant-time steps:

  1. Swap the last element into the position to delete.
  2. Remove the last element.

C++ has no such function in the vector API. Rust does: swap_remove. In C++ I write a helper:

template<typename T>
void unorderedErase(std::vector<T>& v, int index)
{
  std::swap(v[index], v.back());
  v.pop_back();
}

Edge cases
#

  • Empty vector. Calling it is undefined behavior. The caller checks: if (v.empty()) return;
  • Last element. If index == v.size() - 1, the swap does nothing and pop_back() removes the element. This is safe.
  • Iterators. All iterators, pointers and references into the vector become invalid. pop_back() invalidates the iterator to the last element, and the swap changes what sits at the target index. If you keep iterators (in an ECS, intrusive structures, index caches), update them. Raw indices are usually safer.
  • Bounds. index must be less than v.size(). There is no check. A bad index is undefined behavior.
  • Types. It works best for trivial or cheap-to-move types. If swap is expensive, check that the gain is still worth it.

Source: PVS‑Studio

Related