从向量中删除比从列表中删除花费的时间更少.为什么？

Question

在C++手册中我找到了下一个:

向量相对有效地从其末尾添加或移除元素.对于涉及在末尾以外的位置插入或删除元素的操作,它们的性能比其他位置差,并且与列表和forward_lists相比具有更少的一致的迭代器和引用.

此外,在矢量的'擦除'方法的'复杂性'我发现下一个:

删除的元素数量(destructions)加上最后一个元素删除(移动)后的元素数量.

在下一个列表的'擦除'方法的'复杂性'中:

线性的元素数量被删除(破坏).

但是当我在每个容器中的30百万个元素中测试它时(我从24357元素删除到2746591元素),我得到了从vector中删除花了5毫秒,但是从列表8857毫秒.差异巨大且令人困惑......

这是我的代码:

#include "stdafx.h"
#include <vector>
#include <list>
#include <iostream>
#include <ctime>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    const long int x = 30000000;
    vector<char> v;
    vector<char>::iterator itv1, itv2;
    list<char> l;
    list<char>::iterator itl1, itl2;
    unsigned start, end;

    long int first, last;

    cout << "Please enter first position: \n";
    cin >> first;
    cout << "Please enter last position: \n";
    cin >> last;

    for (long int i = 0; i < x; ++i)    {
        char c;
        c = (rand() % 26) + 'a';
        v.push_back(c);
        l.push_back(c);
    }

    cout << "Starting deletion\n";
    start = clock();
    itv1 = v.begin() + first;
    itv2 = v.begin() + last;
    v.erase(itv1, itv2);
    end = clock();
    cout << "End " << end-start << "\n";

    start = clock();
    itl1 = itl2 = l.begin();
    advance(itl1, first);
    advance(itl2, last);
    l.erase(itl1, itl2);
    end = clock();
    cout << "End " << end-start << "\n";
    return 0;
}

你能解释一下 - 是什么导致了这种差异？我的观点 - 在列表中移动迭代器比在向量中慢得多 - 但我不确定.

非常感谢!

Answer 1

在您的情况下,可能是因为您没有测量擦除时间,您需要测量两次advance通话和erase通话所需的时间.

但更一般地说:因为O()复杂性只告诉你算法的复杂性而不是实际的时间.O(1)可以具有巨大的恒定时间值.更糟糕的是,复杂性是理论上的; 它没有考虑硬件如何工作的现实.

事实上,因为向量删除以线性方式访问存储器,所以可以有效地高速缓存和预测存储器,同时列表删除以随机访问方式操作.这可能意味着当您有一个小向量时,矢量删除在实践中比列表删除更快.