为什么std :: list :: pop_front对大型列表来说似乎很慢？

Question

我试图通过在将新节点添加到结尾之前从前面删除节点来限制列表的大小.我期望无论列表大小如何,速度都是恒定的,但我看到更大的列表的执行时间更长.我实现它是错误的,还是pop_front实际上不是恒定的时间？

以下代码执行以下结果:

$ time ./testlist 2 1000000
MAX is 2
NUM is 1000000
DELETED 999998

real    0m0.835s

$ time ./testlist 10 1000000
MAX is 10
NUM is 1000000
DELETED 999990

real    0m1.070s

$ time ./testlist 100 1000000
MAX is 100
NUM is 1000000
DELETED 999900

real    0m3.612s

$ time ./testlist 1000 1000000
MAX is 1000
NUM is 1000000
DELETED 999000

real    0m28.838s

源代码:

#include <iostream>
#include <stdlib.h>
#include <list>

int deletes=0;
std::list<int> l;
void insert(int x, size_t maxsize) {
    if (l.size() == maxsize)
    {
        l.pop_front();
        deletes++;
    }
    l.push_back(x);
}
int main(int argc, char *argv[])
{
    size_t v = atoi(argv[1]);
    size_t n = atoi(argv[2]);
    std::cout << "MAX is " << v << std::endl;
    std::cout << "NUM is " << n << std::endl;
    for (size_t i=0; i<n; i++)
    {
        insert(i, v);
    }
    std::cout << "DELETED " << deletes << std::endl;

    return 0;
}

Answer 1

std::list::size()即使在优化的构建中,也需要线性时间(GCC 4.9.2).请改用:

#include <iostream>
#include <stdlib.h>
#include <list>
#include <deque>

int deletes=0;
int size=0;
std::list<int> l;
void insert(int x, size_t maxsize) {
    if (size == maxsize)
    {
        l.pop_front();
        deletes++;
    size--;
    }
    size++;
    l.push_back(x);
}
int main(int argc, char *argv[])
{
    size_t v = atoi(argv[1]);
    size_t n = atoi(argv[2]);
    std::cout << "MAX is " << v << std::endl;
    std::cout << "NUM is " << n << std::endl;
    for (size_t i=0; i<n; i++)
    {
        insert(i, v);
    }
    std::cout << "DELETED " << deletes << std::endl;

    return 0;
}

注意:deque可能更快(如果实现使用数组,否则它们是相同的,但是,deque提供list与此优化相同的性能- YMMV)

附录:C++ 11似乎没有提供O(n)的余地,size()如23.2.1 通用容器要求中所述:

表达式:a.size()

复杂性:不变

在C++ 11之前,它在这个地方说"常量或线性",这导致了在这种特定情况下的性能问题.

GCC 5.0将解决此问题:https://gcc.gnu.org/bugzilla/show_bug.cgi？id = 49561