Unordered erase

I believe the most frequently used collection in C++ is vector. We know that a vector is great for everything except inserting or deleting items from random parts of the collection. This takes O(n) time, which is why I always feel a bit sad deleting something from the middle of a vector—since it has to shuffle about half of its contents just to shift slightly to the left.

There’s an idiomatic trick that can turn O(n) into O(1), but it comes at the cost of losing the element order in the vector. So, if you’re ready to pay the price, this simple trick is definitely the way to go:

1
2
3
4
5
6
7
8
9

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]

What did we do? First, we replaced the last element of the vector with the one marked for deletion, and then simply discarded it. Both operations are super cheap—it’s simple and beautiful.

Why the vector interface doesn’t have such a simple alternative to the usual erase method is unclear. In Rust, for example, it exists.

Well, we’ll have to create our own helper function for the code base:

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();
}

Source: PVS‑Studio