为什么从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 swap delete:0.00000909461232367903
列表正常删除:0.00011785102105932310

Answer 1

你正在做的不是随机删除.你将从最后删除,这是为其他东西构建的向量.

在交换时,您正在进行单个随机索引操作,这也是矢量擅长的.

Answer 2

std::list和之间的区别std::vector不仅仅取决于性能.它们还具有不同的迭代器失效语义.如果从a中删除项目std::list,则指向列表中其他项目的所有迭代器仍然有效.不是这样std::vector,擦除项目会使指向该项目之后的所有迭代器无效.(在某些实现中,它们仍然可以作为有效的迭代器,但根据标准,它们现在不可用,并且如果您尝试使用它们,则应该断言检查实现.)

因此,您选择的容器也与您需要的语义有关.