为什么从vector和list中删除随机元素花费几乎相同的时间?

Question

如cppreference所示

列表是序列容器，允许在序列的任意位置进行常量时间的插入和擦除操作，并允许两个方向的迭代。

考虑std::vector使用的连续存储器，其中擦除时间应为线性时间。因此，std::list上的随机擦除操作比std::vector上的随机擦除操作效率更高是合理的。

但是如果程序显示不同。

int randi(int min, int max) {
return rand()%(max-min)+min; // Generate the number, assign to variable.
}
int main() {
srand(time(NULL)); // Seed the time
int N = 100000;
int M = N-2;
int arr[N];
for (int i = 0; i < N; i++) {
arr[i] = i;
}
list<int> ls(arr, arr+N);
vector<int> vec(arr, arr+N);
std::chrono::time_point<std::chrono::system_clock> start, end;

start = std::chrono::system_clock::now();
for (int i = 0; i < M; i++) {
int j = randi(0, N - i);
ls.erase(next(ls.begin(), j));
}
end = std::chrono::system_clock::now();
std::chrono::duration<double> elapsed_seconds_1 = end - start;
cout << "list time cost: " << elapsed_seconds_1.count()) << "n";
for (int i = 0; i < M; i++) {
int j = randi(0, N - i);
vec.erase(vec.begin() + j);
}
end = std::chrono::system_clock::now();
std::chrono::duration<double> elapsed_seconds_2 = end - start;
cout << "vector time cost: " << elapsed_seconds_2.count()) << "n";
return 0;
}

~/cpp_learning/list$ ./demo
list time cost: 8.114993171
vector time cost: 8.306458676

Answer 1

因为在list中查找元素需要很长时间。在list中插入或删除是O(1)，如果您已经将迭代器保存到所需的插入/删除位置。在这种情况下，你没有，std::next(ls.begin(), j)调用正在做O(n)的工作，消除了便宜的O(1)erase的所有节省(坦率地说，我有点惊讶它没有输给vector;我希望O(n)指针跟踪操作比O(n)连续的memmove类操作花费更多，但是我知道什么呢?)Update:在检查时，您忘记在vector测试之前保存新的start点，事实上，一旦您解决了这个问题，vector的要快得多，所以我的直觉是正确的:在线尝试!

对于-std=c++17 -O3，输出为:

list time cost: 9.63976
vector time cost: 0.191249

同样，vector获取相关索引(O(1))的成本很低，但(相对而言)删除它的成本很高(O(n)随后进行了复制操作)。

当你不迭代它时，如果你执行随机访问插入和删除，list不会为你节省任何东西。在这种情况下，需要使用std::unordered_map和相关的容器。