以O(1)的时间复杂度删除未排序std::vector中的元素

因为其他元素要填补删除元素所留下来的空隙，从而需要进行移动，所以从std::vector中删除元素的时间复杂度为O(n)。

移动其他元素也与此类似，当很多很大或很复杂的元素需要移动，那么就会花费很长的时间。当无法保证顺序时，我们需要对其进行优化，这就是本节的内容。

How to do it...

我们继续使用一些数字来填充std::vector实例，并且实现一个快速删除函数，以O(1)的时间复杂度删除vector中的元素。

1. 首先，包含必要的头文件：

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

2. 定义主函数，并定义一个vector实例：

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

3. 下一步就要删除索引为2的元素(789)。我们所要用的来删除元素的函数在后面进行实现，我们先假设已经实现好了。执行完成后，来看下vector中的内容。

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

4. 现在，我们将删除另外一个元素。我们想删除123，但是要假装不知道其索引。因此，我们要使用std::find函数在vector的合法范围内查找这个值，并返回其位置信息。得到索引信息后，我们就可以用quick_remove_at将对应元素删除了，这里所使用到的是一个重载版本，能接受迭代器作为输入参数。

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

5. 我们实现了两种quick_remove_at函数。具体实现代码中，需要注意与main函数的前后关系。两个函数都能接收一个vector实例的引用，所以这里允许用户使用各种类型的变量作为元素。对于我们来说，其类型就是T。第一个 quick_remove_at函数用来接收索引值，是一个具体的数，所以其接口如下所示：

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

6. 现在来展示一下本节的重点——如何在不移动其他元素的情况下，快速删除某个元素？首先，将vector中最后一个元素进行重写。第二，删除vector中最后一个元素。就这两步。我们的代码会对输入进行检查。如果输入的索引值超出了范围，函数不会做任何事情。另外，该函数会在传入空vector的时候崩溃。

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

7. 另一个quick_remove_at实现也很类似。用std::vector<T>的迭代器替换了具体的索引数值。因为泛型容器已经定义了这样的类型，所以获取它的类型并不复杂。

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

8. 现在我们来访问这些迭代器所指向的值。和另一个函数一样，我们会将最后一个元素进行重写。因为这次处理的是迭代器，所以我们要对迭代器指向的位置进行检查。如果其指向了一个错误的位置，我们就会阻止其解引用。

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

9. 在该代码块中，我们会做和之前一样的事情——我们要覆盖最后一个位置上的值——然后将最后一个元素从vector中剪掉。

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

10. 这就完事了。让我们来编译程序，并运行：

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

How it works...

quick_remove_at函数移除元素非常快，而且不需要动其他元素。这个函数使用了更加具有创造性的做法：这是一种与实际元素交换的方式，然后将最后一个元素从vector中删除。虽然，最后一个元素与选中的元素没有实际的关联，但是它在这个特别的位置上，而且删除最后一个元素的成本最低！vector的长度在删除完成后，也就减少1，这就是这个函数所要做的。并且无需移动任何元素。看一下下面的图，可能有助于你理解这个函数的原理。

完成这两步的代码如下：

v.at(idx) = std::move(v.back());
v.pop_back();

迭代器版本实现几乎一模一样：

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

逻辑上，我们将选定元素与最后一个元素进行交换。不过，在代码中元素并没有进行交换，代码直接使用最后一个值覆盖了选定元素的值。为什么要这样？当我们交换元素时，就需要将选定的元素存储在一个临时变量中，并在最后将这个临时变量中的值放在vector的最后。这个临时变量是多余的，而且要删除的值对于我们来说是没有意义的，所以这里选择了直接覆盖的方式，更加高效的实现了删除。

好了，交换是无意义的，覆盖是一种更好的方式。让我们来看下这个，当我们要获取vector最后元素的迭代器时，只需要简单的执行*it = v.back();就行了，对吧？完全正确，不过试想我们存储了一些非常长的字符串在vector中，或存储了另一个vector或map——这种情况下，简单的赋值将对这些值进行拷贝，那么就会带来非常大的开销。这里使用std::move可将这部分开销优化掉：比如字符串，指向堆内存上存储的一个大字符串。我们无需拷贝它。只需要移动这个字符串即可，就是将目标指针指向这块地址即可。移动源保持不变，不过出于无用的状态，这样做可以类似的让目标指针指向源指针所在的位置，然后将原始位置的元素删除，这样做即完成了元素移动，又免去了移动消耗。