↓ Skip to main content
Side Effects
  1. posts/

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

··Index: 2·
Cpp
Table of Contents

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

In day-to-day C++ work std::vector is my default container, fast, cache-friendly and good enough for almost everything except removing elements from the middle. Erasing there always costs O(n), since the vector has to shift everything after the gap to fill it, and every time I do it I get the same irritation over a tiny change that shuffles half of the array.

There’s an idiomatic trick that collapses this into O(1), and you pay for it with the order of the elements. When order doesn’t matter (and in many systems it really doesn’t), use the trick.

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]

The code above does two constant-time operations and no shifting at all.

  1. Swap the last element into the position we want to delete.
  2. Remove the now unused last element with pop_back.

I’m surprised that C++ doesn’t offer this pattern in the standard vector API, while Rust has it built in as swap_remove. In C++ we write our own helper.

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

Edge cases
#

There’s no container magic to rely on here, so the edge cases are yours to handle.

  • Calling it on an empty vector is undefined behavior, so the caller has to check first with if (v.empty()) return; or throw.
  • Removing the last element is safe and cheap. When index already points at the last element, the swap does nothing and pop_back() simply removes it.
  • All iterators, pointers and references into the vector become invalid, because pop_back() invalidates the iterator to the last element and the swap changes which element sits at the target index. If your code stores iterators into the vector (in ECS systems, intrusive structures or index caches), you have to update them or stop storing iterators at all, and raw indices are usually safer.
  • index has to be less than v.size(), and there’s no guard for that. Pass a bad index and the function will happily blow up with undefined behavior.
  • The trick works best for trivial or cheap-to-move types. If your type has an expensive swap, check whether the gain is still worth it.

Source: PVS‑Studio

Related