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 the required header files.

      #include <iostream>
      #include <vector>
      #include <algorithm>

1. Then, we define a main function where we instantiate a vector with example numbers.

      int main()
      {
          std::vector<int> v {123, 456, 789, 100, 200};

1. The next step is to delete the value at index 2 (counting from zero of course, so it's the third number 789). The function we will use for that task is not implemented yet. We do that some steps later. Afterward, we print the vector's content.

          quick_remove_at(v, 2);
      
          for (int i : v) {
              std::cout << i << ", ";
          }                                           
          std::cout << '\n';

1. Now, we will delete another item. It will be the value 123, and let's say we don't know its index. Therefore, we will use the std::find function, which accepts a range (the vector), and a value, and then searches for the value's position. Afterward, it returns us an iterator pointing to the 123 value. We will use the same quick_remove_at function, but this is an overloaded version of the previous one which accepts iterators. It is also not implemented, yet.

          quick_remove_at(v, std::find(std::begin(v), std::end(v), 123));
      
          for (int i : v) {
              std::cout << i << ", ";
          }
          std::cout << '\n';
      }

1. Apart from the two quick_remove_at functions, we are done. So let's implement these. (Note that they should be at least declared before the main function. So let's just define them there.)
   Both the functions accept a reference to a vector of something (in our case, its int values), so we leave that open what kind of vector the user will come up with. For us, it's a vector of T values. The first quick_remove_at function we used accepts index values, which are numbers, so the interface looks like the following:

      template <typename T>
      void quick_remove_at(std::vector<T> &v, std::size_t idx)
      {

1. Now comes the meat of the recipe--how do we remove the item quickly without moving too many others? First, we simply take the value of the last item in the vector and use it to overwrite the item which shall be deleted. Second, we cut off the last item of the vector. These are the two steps. We surround this code with a little sanity check. If the index value is obviously out of the vector range, we do nothing. Otherwise, the code would, for example, crash on an empty vector.

          if (idx < v.size()) {
              v[idx] = std::move(v.back());
              v.pop_back();
          }
      }

1. The other implementation of quick_remove_at works similar. Instead of accepting a numeric index, it accepts an iterator for std::vector<T>. Obtaining its type in a generic manner is not complicated because STL containers already define such types.

      template <typename T>
      void quick_remove_at(std::vector<T> &v, 
                           typename std::vector<T>::iterator it)
      {
 

1. Now, we will access the value, at which the iterator is pointing. Just as in the other function, we will overwrite it by the last element in the vector. Because we are handling not a numeric index, but an iterator this time, we need to check a bit differently if the iterator position is sane. If it points to the artificial end position, we are not allowed to dereference it.

          if (it != std::end(v)) {

1. Within that if block, we do the same thing as before--we overwrite the item to be removed with the value of the item from the last position--then we cut off the last element from the vector:

              *it = std::move(v.back());
              v.pop_back();
          }
      }

1. That's it. Compiling and running the program leads to the following output:

      $ ./main 
      123, 456, 200, 100,                           
      100, 456, 200,