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

In day-to-day C++ work, std::vector is the default container. It is fast, cache-friendly, and good enough for almost everything. Except for one thing: removing elements from the middle. That operation is always O(n) because the vector has to shift all subsequent elements to fill the gap.

Every time I erase from the middle, I feel the same irritation: a tiny change, half of the array shuffled.

There is, however, an idiomatic trick that collapses this O(n) operation into O(1). The cost: you lose the ordering of elements. If order is irrelevant (and in many systems it truly is), it’s the right tool.

Here is the core idea:

1
2
3
4
5
6
7
8
9

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]

This does two constant-time operations:

1. Move the last element into the position we want to delete (swap).
2. Remove the now-unused last element (pop_back).

No shifting, no linear cost. Just two simple, predictable operations.

What is surprising is that C++ does not expose this pattern as part of the standard vector API. Rust does: swap_remove is built-in.

In C++, we write our own helper:

1
2
3
4
5
6

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

This is all you need. If ordering doesn’t matter, this is the correct way to erase elements from a vector-fast, minimal, and predictable.

Edge Cases and Practical Notes

You cannot rely on container magic here; you must handle edge cases explicitly.

1. Empty vector

Calling this function on an empty vector is undefined behavior. The caller must check:

if (v.empty()) return; // or throw

2. Removing the last element

If index == v.size() - 1, the swap does nothing, and pop_back() simply removes the final element.
This case is safe and cheap. No special handling required.

3. Iterator invalidation

All iterators, pointers, and references to elements become invalid after this operation.

• pop_back() invalidates the iterator to the last element.
• swapping elements means the content at the target index changes identity.

If your code stores iterators into the vector (e.g., in ECS systems, intrusive structures, or index caches), you must update them or avoid storing iterators at all. Storing raw indices is usually more robust.

4. Bounds checking

index must be < v.size(). The function will happily blow up (undefined behavior) if you pass an invalid index. No guard rails here.

5. Type considerations

The technique works best for trivial or cheap-to-move types.
If your type has expensive swap logic, evaluate whether the performance gain is still worth it.

Source: PVS‑Studio