0

在编写一个处理相对大量元素（~100k）的程序时，我注意到std::list和QList之间有一个奇怪的区别。起初我使用了一个std::vector，它表现很好。但是因为程序经常需要在向量中的随机位置插入元素，所以当迭代器位于所需位置时，我切换到std::list，它具有恒定的插入时间。

问题是，std::list 在 insert() 和 push_back() 方法中的表现都比 std::vector 差。测量将 100 个连续元素添加到具有 100k 个元素的列表中，我得到：

  • std::vector 约 25 毫秒（最坏的情况是在开始时添加）
  • std::list 超过 600 毫秒（！）（任何位置，即使使用 push_back() 或 insert(list.begin()）。

请注意，插入元素的时间不包括使用迭代器到达位置的时间。

我知道列表的性能问题是由于列表导致缓存未命中，但这似乎超出了缓存未命中的限制。此外，插入元素（具有 5 个恒定长度变量的简单结构）的时间随着列表的大小而增加。即使是获取列表大小的操作也需要更多时间。这与列表的两个操作保证的时间复杂度完全相反：常量。

见：这里

出于好奇，从std::list更改为QList和 viola：插入时间是恒定的，介于 0ms 和 1ms 之间。

这是用于测量插入时间的代码。

两个时间点之间没有执行其他操作：错误：使用了 size() 方法

标准::列表：

    QTime time;
    time.start();

    for (int a = 1; a <= lineChange; a++)
    {
        listData.insert(listIterator, newElement); 
    }        
    int elapsed = time.restart();
    qDebug() << "elapsed: " << elapsed << "ms";

结果：经过：662ms

问题清单：

    QTime time;
    time.start();

    for (int a = 1; a <= lineChange; a++)
    {
        QListData.insert(iteratorPos, newElement);
        position++;
    } 

    int elapsed = time.restart();
    qDebug() << "elapsed: " << elapsed << "ms";

结果：经过：1ms

标准：：向量：

    QTime time;
    time.start();

    for (int a = 1; a <= lineChange; a++)
    {
        vectorData.insert(vectorIterator, newElement);

        /*update of the iterator when it was 
        invalidated due to resize of the vector*/
    }    

    int elapsed = time.restart();
    qDebug() << "elapsed: " << elapsed << "ms";

结果：经过：27ms

那么，为什么 QList 和 std::list 之间存在如此巨大的差异呢？或者更好：为什么std::list的性能如此糟糕？

作为附带信息：我在 Linux (Mint) 下使用带有 gcc 的 QtEditor，并将标志设置为 c++11

编辑：

数据类型和声明：

typedef struct TOKELEMENT {
    unsigned int column;
    unsigned int lenght;
    unsigned int tType;
    std::string value;
} tokElement;

// the three lists
std::vector<okElement> vectorData;
std::list<tokElement> listData;
QList<tokElement> QListData;

tokElement newElement;

unsigned int iteratorPos;
std::vector<std::vector<tokElement> >::iterator vectorIterator;
std::list<std::vector<tokElement> >::iterator listIterator;

//lineChange is an unsigned int, given as function parameter
unsigned int lineChange;
4

1 回答 1

3

与我在问题中提到的相反（我感到羞耻），我在for 循环中对std::list的大小进行了另一次检查，以确定是在列表上使用 insert() 还是 push_back()。由于这个函数没有 O(1) 但 O(n) 的时间复杂度，这大大减慢了整个插入的速度。感谢Leeor指出这一点。

将此检查移出for 循环后，std::list 的执行与预期一样，甚至比 QList 更快。

于 2014-03-16T03:44:11.513 回答