↓ Skip to main content
Side Effects
  1. posts/

Unordered erase

·
PARA/Project Blog Cpp Programming
Table of Contents

Unordered erase
#

vector is probably the most used collection in C++. It is good at everything except inserting or deleting in the middle. That takes O(n), because about half of the contents shifts left. I always feel a bit sad deleting from the middle of a vector.

An idiom turns O(n) into O(1), at the cost of the element order. If you can pay that:

std::vector<int> v {
  17, -2, 1084, 1, 17, 40, -11
};

// we delete 1 from the vector
std::swap(v[3], v.back()); 
v.pop_back();

// we get [17, -2, 1084, -11, 17, 40]

We swapped the element marked for deletion with the last one, then dropped the last. Both steps are cheap.

The vector interface has no such method, and it is unclear why. Rust has one: swap_remove. For our code base we write a helper:

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

Source: PVS‑Studio

Related