为什么erase()函数如此昂贵？

Question

考虑一个 2d 向量 vector <向量> N并且假设它的内容如下：

1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4

所以这里N的大小是4，即N.size() = 4

现在，考虑下面的代码：

int i = 0;
while(N != empty()){
N.erase(i);
++i;
}

我计算了时间这段代码单独具有不同大小的 N，结果如下：

N 的大小为 1000 执行时间：0.230000s

N的大小为10000 执行时间：22.900000s

N的大小为20000 执行时间：91.760000s

N的大小为30000 执行时间：206.620000s

N的大小为47895 执行时间：526.540000s

我的问题是为什么这个函数如此昂贵？如果是这样，那么许多程序中的条件擦除语句可能会因为这个函数而永远花费下去。当我在 std::map 中使用擦除函数时也是同样的情况。这个功能有什么替代方案吗？其他库（例如 Boost）是否提供任何功能？

请不要说我可以整体执行 N.erase() 因为我只是想分析这个函数。

Answer 1

向量是一个数组，当您向其中添加元素时，它会自动增长。因此，向量中的元素在内存中是连续的。这允许对元素进行恒定的时间访问。因为它们是从末尾开始增长的，所以它们也需要摊销常数时间来添加或删除到末尾。

现在，当你从中间移除时会发生什么？嗯，这意味着擦除元素后存在的任何内容都必须向后移动一个位置。这是非常昂贵的。

如果您想在中间进行大量插入/删除操作，请使用链表，例如 std::deque 的 std::list。

Answer 2

正如 Oli 所说，从向量的第一个元素中删除意味着必须向下复制其后面的元素，以便数组能够按预期运行。

这就是为什么链表用于从列表中的随机位置删除元素的情况 - 它更快（在较大的列表上），因为没有复制，仅重置一些节点指针。

Answer 3

考虑一下当删除向量的第一个元素时会发生什么。向量的其余部分必须向下“移动”一个索引，这涉及到复制它。尝试从另一端擦除，看看这是否会产生影响（我怀疑它会......）

Answer 4

因为你的算法是O(n^2)。每次调用 erase 都会强制 vector 将已擦除元素之后的所有元素移回原位。因此，在具有 4 元素向量的循环中，第一个循环导致 3 个元素移动，第二次迭代导致 1 个元素移动，之后您将出现未定义的行为。

如果有 8 个元素，则第一次迭代将移动 7 个元素，下一次迭代将移动 5 个元素，下一次迭代将移动 3 个元素，最后的枚举将移动 1 个元素。 （同样，你有未定义的行为）

当你遇到这样的情况时，通常你应该使用标准算法（即 std::remove、std::remove_if），因为它们运行一次容器并将典型的 O(n^2) 算法转换为 O(n) 算法。有关详细信息，请参阅 Scott Meyers 的“有效 STL”第 43 项：优先使用算法调用而不是显式循环。

Answer 5

std::vector 在内部只是一个元素数组。如果删除中间的一个元素，则该元素后面的所有元素都必须下移。这可能非常昂贵 - 如果元素有一个可以完成大量工作的自定义 operator= ，则成本会更高！

如果您需要 erase() 速度更快，您应该使用 std::list - 这将使用双向链表结构，允许从中间快速擦除（但是，其他操作会稍微慢一些）。如果您只需要快速从列表的开始中删除，请使用std::deque - 这会创建一个数组的链接列表，并提供 std::vector 的大部分速度优势，同时仍然允许快速擦除仅开始或结束。

此外，请注意，您的循环使问题变得更糟 - 您首先扫描所有等于零的元素并删除它们。扫描需要 O(n) 时间，擦除也需要 O(n) 时间。然后重复 1，依此类推 - 总体时间为 O(n^2)。如果您需要删除多个值，您应该使用迭代器并使用 erase()。或者，如果您使用向量，您会发现复制到新向量中的速度会更快。

至于 std::map （和 std::set） - 这根本不是问题。 std::map 既能够随机删除元素，也能够随机搜索元素，时间为 O(lg n) - 这对于大多数用途来说是相当合理的。即使你的天真循环也不应该太糟糕；手动迭代并一次性删除您想要删除的所有内容在某种程度上更有效，但远没有达到 std::list 和朋友的程度。

Answer 6

vector.erase 会将 i 之后的所有元素向前推进 1。这是一个 O(n) 操作。

此外，您是按值而不是按引用传递向量。

您的代码也不会删除整个向量。

例如：
我=0
擦除N[0]
N = {{2, 2, 2, 2}, {3, 3, 3, 3}, {4, 4, 4, 4}}

i = 1
擦除N[1]
N = {{2, 2, 2, 2}, {4, 4, 4, 4}}

i = 2
擦除 N[2] 没有任何反应，因为最大索引是 N[1]

最后，我认为这是 vector.erase() 的正确语法。您需要将迭代器传递到开始位置以删除所需的元素。
试试这个：

vector<vector<int>> vectors; // still passing by value so it'll be slow, but at least erases everything
for(int i = 0; i < 1000; ++i)
{
    vector<int> temp;
    for(int j = 0; j < 1000; ++j)
    {
        temp.push_back(i);
    }
    vectors.push_back(temp);
}

// erase starting from the beginning
while(!vectors.empty())
{
    vectors.erase(vectors.begin());
}

您还可以将其与从末尾擦除进行比较（它应该明显更快，特别是在使用值而不是引用时）：

// just replace the while-loop at the end
while(!vectors.empty())
{
    vectors.erase(vectors.end()-1);
}