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.

How to do it…

This recipe takes advantage of the fact that removing an element from the end of a vector is quick and easy.

• Let's start by defining a function to print out a vector:

  void printc(auto & r) {
      cout << format("size({}) ", r.size());
      for( auto & e : r ) cout << format("{} ", e);
      cout << '\n';
  }

• In our main() function we define a vector of int and print it using printc():

  int main() {
     ...