Delete Items from an Unsorted Vector in Constant Time

Using the uniform erasure functions (or the erase-remove idiom) to delete items from the middle of a vector takes $O(n)$ (linear) time. This is because elements must be shifted from the end of the vector to close the gap of the deleted items. If the order of items in the vector is not important, we can optimize this process to take $O(1)$ (constant) time. Here’s how.