Unordered erase#
I believe the most frequently used collection in C++ is vector. We know it’s great for everything except inserting or deleting items in random parts of the collection, which takes O(n) time, and that’s why I always feel a bit sad deleting something from the middle of a vector: it has to shuffle about half of its contents just to shift them slightly to the left.
There’s an idiomatic trick that turns O(n) into O(1), but you pay for it with the order of elements in the vector. If you’re ready to pay that price, this simple trick is the way to go.
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? We swapped the element marked for deletion with the last element of the vector and simply discarded it. Both operations are super cheap, and it’s simple and beautiful.
Why the vector interface doesn’t have such a simple alternative to the usual erase method is unclear to me. Rust, for example, has swap_remove, and in C++ we’ll have to create our own helper function for the code base.
template<typename T>
void unorderedErase(std::vector<T>& v, int index)
{
std::swap(v[index], v.back());
v.pop_back();
}Source: PVS‑Studio