随着CPU缓存越来越好，即使在测试std::list的强度时，std::vector通常表现得更好。因此，即使在需要在容器中间删除/插入的情况下，我通常会选择std::vector，但我意识到我从未测试过这一点以确保假设是正确的，因此我设置了一些测试代码：
#include <iostream>
#include <chrono>
#include <list>
#include <vector>
#include <random>
void TraversedDeletion()
{
std::random_device dv;
std::mt19937 mt{ dv() };
std::uniform_int_distribution<> dis(0, 100000000);
std::vector<int> vec;
for (int i = 0; i < 100000; ++i)
{
vec.emplace_back(dis(mt));
}
std::list<int> lis;
for (int i = 0; i < 100000; ++i)
{
lis.emplace_back(dis(mt));
}
{
std::cout << "Traversed deletion...\n";
std::cout << "Starting vector measurement...\n";
auto now = std::chrono::system_clock::now();
auto index = vec.size() / 2;
auto itr = vec.begin() + index;
for (int i = 0; i < 10000; ++i)
{
itr = vec.erase(itr);
}
std::cout << "Took " << std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now() - now).count() << " μs\n";
}
{
std::cout << "Starting list measurement...\n";
auto now = std::chrono::system_clock::now();
auto index = lis.size() / 2;
auto itr = lis.begin();
std::advance(itr, index);
for (int i = 0; i < 10000; ++i)
{
auto it = itr;
std::advance(itr, 1);
lis.erase(it);
}
std::cout << "Took " << std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now() - now).count() << " μs\n";
}
}
void RandomAccessDeletion()
{
std::random_device dv;
std::mt19937 mt{ dv() };
std::uniform_int_distribution<> dis(0, 100000000);
std::vector<int> vec;
for (int i = 0; i < 100000; ++i)
{
vec.emplace_back(dis(mt));
}
std::list<int> lis;
for (int i = 0; i < 100000; ++i)
{
lis.emplace_back(dis(mt));
}
std::cout << "Random access deletion...\n";
std::cout << "Starting vector measurement...\n";
std::uniform_int_distribution<> vect_dist(0, vec.size() - 10000);
auto now = std::chrono::system_clock::now();
for (int i = 0; i < 10000; ++i)
{
auto rand_index = vect_dist(mt);
auto itr = vec.begin();
std::advance(itr, rand_index);
vec.erase(itr);
}
std::cout << "Took " << std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now() - now).count() << " μs\n";
std::cout << "Starting list measurement...\n";
now = std::chrono::system_clock::now();
for (int i = 0; i < 10000; ++i)
{
auto rand_index = vect_dist(mt);
auto itr = lis.begin();
std::advance(itr, rand_index);
lis.erase(itr);
}
std::cout << "Took " << std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::system_clock::now() - now).count() << " μs\n";
}
int main()
{
RandomAccessDeletion();
TraversedDeletion();
std::cin.get();
}
所有结果都使用/02（最大化速度）编译。
首先，RandomAccessDeletion()生成一个随机索引并删除该索引10,000次。我的假设是正确的，向量确实比列表快得多：
随机访问删除...
开始测量向量...
花费240299微秒
开始测量列表...
花费1368205微秒
向量比列表快5.6倍。我们很可能要感谢我们的缓存统治者为此性能利益，尽管我们需要在每次删除时移动向量中的元素，但它的影响小于列表的查找时间，正如我们在基准测试中所看到的。
然后我添加了另一个测试，见于TraversedDeletion()。它不使用随机位置进行删除，而是选择一个容器中间的索引，并将其用作基本迭代器，然后遍历容器以擦除10,000次。
我的假设是列表仅会略微优于向量或与向量一样快。
相同执行的结果：
遍历删除...
开始测量向量...
花费195477微秒
开始测量列表...
花费581微秒
哇。列表快了336倍。这与我的预期相差甚远。因此，在列表中有一些缓存未命中似乎根本不重要，因为减少列表的查找时间的权重更大。
因此，在处理角落/不寻常情况时，列表显然仍然具有非常强的性能优势，或者我的测试用例存在某些缺陷吗？
这是否意味着对于在容器中间进行许多插入/删除并遍历的情况下，列表现在只是一个合理的选项，还是有其他情况？
有没有办法改变TraversedDeletion()中的向量访问和擦除，使其至少与列表竞争一些？
回应@BoPersson的评论：
vec.erase(it, it+10000)比执行10000个单独的删除要快得多。
更改为：
for (int i = 0; i < 10000; ++i)
{
itr = vec.erase(itr);
}
收件人：
vec.erase(itr, itr + 10000);
给了我：
开始向量测量...
花费19微秒
这已经是一个重大的改进了。
vec.erase(it)会使itr失效，而他在每个后续迭代中都使用了它。我看的是RandomAccessDeletion而不是TraversedDeletion。 - NathanOliver