c++ - 为什么从 std::vector 中随机删除比 std::list 快？

Question

为什么从 std::vector 中随机删除比 std::list 快？我正在做的加快它的是将随机元素与最后一个交换，然后删除最后一个。我原以为该列表会更快，因为它是为随机删除而构建的。

for(int i = 500; i < 600; i++){
    swap(vector1[i], vector1[vector1.size()-1]);
    vector1.pop_back();
}

for(int i = 0; i < 100; i++){
        list1.pop_front();
}

结果（以秒为单位）：
Vec 交换删除：0.00000909461232367903
列表正常删除：0.00011785102105932310

Answer 1

您正在做的不是随机删除。您要从最后删除，这就是构建向量的目的（除其他外）。

并且在交换时，您正在执行单个随机索引操作，这也是向量所擅长的。

Answer 2

std::list和之间的区别std::vector不仅仅取决于性能。它们也有不同的迭代器失效语义。如果您从 a 中删除一个项目std::list，则指向列表中其他项目的所有迭代器仍然有效。不是这样std::vector，擦除一个项目会使指向该项目的所有迭代器无效。（在某些实现中，它们可能仍然充当有效的迭代器，但根据标准，它们现在不可用，如果您尝试使用它们，检查实现应该断言。）

所以你对容器的选择也与你需要的语义有关。

Answer 3

这不是随机的。试试 vector1.erase(vector.begin() + rand() % vector.size()); 反而。

Answer 4

该列表erase将导致删除已删除的列表元素，这将调用对delete操作员的调用。矢量擦除只会导致交换，然后是整数递减 - 这要快得多。

Answer 5

实际上，如果您想进一步加快速度，您应该通过iterators索引向量中的元素。众所周知，它们对于某些架构具有更好的性能。