为什么从 std::vector 中随机删除比 std::list 更快？
为什么从 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
How come that random deletion from a std::vector is faster than a std::list? What I'm doing to speed it up is swapping the random element with the last and then deleting the last.
I would have thought that the list would be faster since random deletion is what it was built for.
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();
}
Results (in seconds):
Vec swap delete: 0.00000909461232367903
List normal delete: 0.00011785102105932310
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
不过，您所做的并不是随机删除。 您将从末尾删除，这就是构建向量的目的（除其他外）。
当交换时，您正在执行单个随机索引操作，这也是向量所擅长的。
What you're doing is not random deletion though. You're deleting from the end, which is what vectors are built for (among other things).
And when swapping, you're doing a single random indexing operation, which is also what vectors are good at.
std::list和std::vector之间的区别不仅仅在于性能。 它们还具有不同的迭代器失效语义。 如果从std::list中删除一个项目，则指向列表中其他项目的所有迭代器仍然有效。std::vector则不然，删除一个项目会使指向该项目之后的所有迭代器失效。 （在某些实现中，它们仍然可以用作有效的迭代器，但根据标准，它们现在不可用，并且如果您尝试使用它们，检查实现应该断言。）因此，您对容器的选择也与语义有关你需要。
The difference between
std::listandstd::vectoris not merely down to performance. They also have different iterator invalidation semantics. If you erase an item from astd::list, all iterators pointing to other items in the list remain valid. Not so withstd::vector, where erasing an item invalidates all iterators pointing after that item. (In some implementations, they may still serve as valid iterators, but according to the standard they are now unusable, and a checking implementation ought to assert if you try to use them.)So your choice of container is also to do with what semantics you require.
这不是随机的。 尝试 vector1.erase(vector.begin() + rand() % vector.size()); 反而。
That's not random. Try vector1.erase(vector.begin() + rand() % vector.size()); instead.
列表擦除将导致删除已擦除的列表元素，这将调用对删除运算符的调用。 矢量擦除只会导致交换，然后导致整数递减 - 这要快得多。
The list
erasewill cause to delete the erased list element, this will invoke a call to thedeleteoperator. The vector erase just causes a swap and then a integer decrement - this is a lot faster.实际上，如果您想要进一步加快速度，您应该通过迭代器对向量中的元素进行索引。 众所周知，它们对于某些架构具有更好的性能。
Actually if you want further speed-ups you should index elements in the vector via iterators. They are known to have better performance for some architectures.