【C++11/C++17】std::vector高效删除(O(1))

今天继续讨论一下std::vector的erase方法及其优化策略。
我们已经指导从std::vector中间的某个位置删除项需要O(n)时间。这是因为移除一个项所产生的空间必须通过将空间后面的所有项移动到左边来填补。在像这样移动项目时，如果它们非常复杂或着非常大并且包含许多项目，虽然保留它们的顺序但会很损耗性能。
如果保持顺序并不重要，我们可以对其进行优化。优化的核心是，如何避免删除元素后，数据的大量或者频繁移动。有了这个前提，我们可以使用这个思路：

• 首先，简单地取vector中最后一项的值，并用它覆盖要删除的项。
• 其次，我们切断向量的最后一项。

当然，安全性检查是必不可少的。如果索引值明显超出向量范围，则不执行任何操作。否则，例如，代码将在vector上崩溃。参考代码如下：
1、先构造两个相同的vector：

	std::vector<int> v, v1;
    for (size_t i = 0; i < 1000; i++)
    {
        v.emplace_back(i);
        v1.emplace_back(i);
    }

2、采用常规的删除方式执行500次删除，统计程序运行时间

    //删除位置为2的元素（索引从0开始）
    auto start = std::chrono::steady_clock::now();
    //执行500次删除
    for (int j = 0; j < 500; ++j)
    {
        v.erase(v.begin() + 1);
    }
    auto end = std::chrono::steady_clock::now();
    double duration_millsecond = std::chrono::duration<double, std::milli>(end - start).count();
    std::cout << "普通删除方式：" << duration_millsecond << " ms" << std::endl;

3、采用优化后的删除算法执行500次删除，统计程序运行时间。这里的精髓是每次删除，都用vector末尾的元素去替换需要删除的元素，然后将末尾的元素删除。删除vector末尾的元素，就不在元素移动的情况，这样就达到了优化的目的。当然，删除后的vector是无序的。但以此换来的是删除效率的极大提升。

	start = std::chrono::steady_clock::now();
    //执行500次删除
    for (int j = 0; j < 500; ++j)
    {
        if (j <v1.size()-1 && v1.size() > 0)
        {
            v1.at(j+1) = std::move(v1.back());
            v1.pop_back();
        }
    }
    end = std::chrono::steady_clock::now();
    duration_millsecond = std::chrono::duration<double, std::milli>(end - start).count();
    std::cout << "优化后的删除方式：" << duration_millsecond << " ms" << std::endl;

然后我们将两个vector删除后剩余的元素也打印出来：

	std::cout << "v: ";
    for (auto item :v)
    {
        std::cout << item << " ";
    }
    std::cout << std::endl;
    std::cout << "v1: ";
    for (auto item : v1)
    {
        std::cout << item << " ";
    }
    std::cout << std::endl;

最后，来看看输出结果。可以看到，优化后的元素删除方式效率提升非常明显。常规删除方式的时间复杂度是O(n)，而优化后的时间复杂度是O(1)，在大规模的数据删除中，性能提升会更加显著。

最后，附上测试源码，有兴趣的小伙伴可以自行修改研究：

#include <iostream>
#include <vector>
#include <chrono>

int main()
{
    std::vector<int> v, v1;
    for (size_t i = 0; i < 1000; i++)
    {
        v.emplace_back(i);
        v1.emplace_back(i);
    }

    //删除位置为2的元素（索引从0开始）
    auto start = std::chrono::steady_clock::now();
    //执行500次删除
    for (int j = 0; j < 500; ++j)
    {
        v.erase(v.begin() + 1);
    }
    auto end = std::chrono::steady_clock::now();
    double duration_millsecond = std::chrono::duration<double, std::milli>(end - start).count();
    std::cout << "普通删除方式：" << duration_millsecond << " ms" << std::endl;

    start = std::chrono::steady_clock::now();
    //执行500次删除
    for (int j = 0; j < 500; ++j)
    {
        if (j+1 < v1.size() && v1.size() > 0)
        {
            v1.at(j+1) = std::move(v1.back());
            v1.pop_back();
        }
    }
    end = std::chrono::steady_clock::now();
    duration_millsecond = std::chrono::duration<double, std::milli>(end - start).count();
    std::cout << "优化后的删除方式：" << duration_millsecond << " ms" << std::endl;

    std::cout << "v: ";
    for (auto item :v)
    {
        std::cout << item << " ";
    }
    std::cout << std::endl;
    std::cout << "v1: ";
    for (auto item : v1)
    {
        std::cout << item << " ";
    }
    std::cout << std::endl;
    
    return 0;
}