Deleting items from an unsorted std::vector in O(1) time

Deleting items from somewhere in the middle of an std::vector takes O(n) time. This is because the resulting gap from removing an item must be filled by moving all the items which come after the gap one slot to the left.

While moving items around like this, which might be expensive if they are complex and/or very large and include many items, we preserve their order. If preserving the order is not important, we can optimize this, as this section shows.

How to do it...

In this section, we will fill an std::vector instance with some example numbers, and implement a quick remove function, which removes any item from a vector in O(1) time.

1. First, we need to include...