2

考虑一个二维向量vector < vector <int> > 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()一个整体，因为我只是想分析这个功能。

4

6 回答 6

16

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

于 2011-01-11T22:36:22.813 回答
6

因为你的算法是 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 的“Effective STL”第 43 条：Prefer Algorithm Calls to Explicit Loops。

于 2011-01-11T22:38:58.650 回答
2

std::vector 在内部只是一个元素数组。如果删除中间的一个元素，它后面的所有元素都必须向下移动。operator=这可能非常昂贵 - 如果元素具有可以做很多工作的自定义，则更是如此！

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

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

至于std::map(and std::set) - 这根本不是问题。std::map能够随时间随机删除元素，以及随机搜索元素O(lg n)——这对于大多数用途来说是相当合理的。即使是你的幼稚循环也不应该太糟糕；手动迭代并一次性删除您想要删除的所有内容会更有效，但远不std::list及与朋友一起使用的程度。

于 2011-01-11T22:39:12.523 回答
1

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

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

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

例如： i = 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);
}
于 2011-01-11T22:56:08.013 回答
0

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

现在，当你在中间删除时会发生什么？好吧，这意味着在被擦除的元素之后存在的任何东西都必须向后移动一个位置。这是非常昂贵的。

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

于 2011-01-11T22:37:55.320 回答
0

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

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

于 2011-01-11T22:40:07.883 回答