假定 STL 列表(作为双链表实现)的“push_back”和“pop_front”方法应该是常量 O(1)。然而，我们在 linux 上运行的应用程序中遇到了 cpu 问题，我们发现“pop_front”方法在使用列表时效率极低。这是列表实现问题还是预期行为？

这是示例代码:

class A {
public:
    A() { mA = rand(); mB = rand(); mC = rand(); mD = rand(); }
    u32 mA;
    u32 mB;
    u32 mC;
    u32 mD;
};

#define DELTA(t1, t0) ((t1.tv_sec - t0.tv_sec)*1000 + ((t1.tv_usec - t0.tv_usec)/1000))

int main(int argc, char* argv[]) {
    std::list<A> l;
    std::queue<A> q;
    std::deque<A> dq;
    printf("Creating nodes...");
    std::vector<A> v;
    for (int i = 0; i < 100000; ++i) {
        A a;
        v.push_back(a);
    }
    printf("OK\n");
    timeval t0, t1;

    printf("std::deque test: push back...");
    gettimeofday(&t0, NULL);
    for (std::vector<A>::const_iterator iter = v.begin(); iter != v.end(); ++iter) {
        dq.push_back(*iter);
    }
    gettimeofday(&t1, NULL);
    printf("Done in %d ms, size = %d\n", DELTA(t1, t0), dq.size());
    printf("std::deque test: pop front...");
    gettimeofday(&t0, NULL);
    while (dq.size() > 0) {
        A a = dq.front();
        dq.pop_front();
    }
    gettimeofday(&t1, NULL);
    printf("Done in %d ms, size = %d\n", DELTA(t1, t0), dq.size());

    printf("std::queue test: push back...");
    gettimeofday(&t0, NULL);
    for (std::vector<A>::const_iterator iter = v.begin(); iter != v.end(); ++iter) {
        q.push(*iter);
    }
    gettimeofday(&t1, NULL);
    printf("Done in %d ms, size = %d\n", DELTA(t1, t0), q.size());
    printf("std::queue test: pop front...");
    gettimeofday(&t0, NULL);
    while (q.size() > 0) {
        A a = q.front();
        q.pop();
    }
    gettimeofday(&t1, NULL);
    printf("Done in %d ms, size = %d\n", DELTA(t1, t0), q.size());

    printf("std::list test: push back...");
    gettimeofday(&t0, NULL);
    for (std::vector<A>::const_iterator iter = v.begin(); iter != v.end(); ++iter) {
        l.push_back(*iter);
    }
    gettimeofday(&t1, NULL);
    printf("Done in %d ms, size = %d\n", DELTA(t1, t0), l.size());
    printf("std::list test: pop front...");
    gettimeofday(&t0, NULL);
    while (l.size() > 0) {
        A a = l.front();
        l.pop_front();
    }
    gettimeofday(&t1, NULL);
    printf("Done in %d ms, size = %d\n", DELTA(t1, t0), l.size());
    return 0;
}

对于不同数量的节点，我们得到:

5000 个节点:

std::deque test: push back...Done in 0 ms, size = 5000
std::deque test: pop front...Done in 0 ms, size = 0
std::queue test: push back...Done in 0 ms, size = 5000
std::queue test: pop front...Done in 0 ms, size = 0
std::list test: push back...Done in 0 ms, size = 5000
std::list test: pop front...Done in 202 ms, size = 0

10000 个节点:

std::deque test: push back...Done in 0 ms, size = 10000
std::deque test: pop front...Done in 0 ms, size = 0
std::queue test: push back...Done in 0 ms, size = 10000
std::queue test: pop front...Done in 0 ms, size = 0
std::list test: push back...Done in 1 ms, size = 10000
std::list test: pop front...Done in 279 ms, size = 0

100000 个节点:

std::deque test: push back...Done in 5 ms, size = 100000
std::deque test: pop front...Done in 4 ms, size = 0
std::queue test: push back...Done in 3 ms, size = 100000
std::queue test: pop front...Done in 4 ms, size = 0
std::list test: push back...Done in 12 ms, size = 100000
std::list test: pop front...Done in 31148 ms, size = 0

谢谢!

维森特

最佳答案

如果你想检查一个容器是否为非空，你应该使用!c.empty()，而不是c.size() > 0。

这对 std::list 尤其重要，因为在某些实现中，size 是一个线性时间 操作，而不是 恒定时间操作。

(虽然，正如 vsoftco 在评论中指出的那样，C++11 加强了对 size 的要求，它确实是常量——如果你有一个兼容的编译器/库，你可以尝试启用选项为该标准或更高版本编译)

关于c++ - STL 列表性能很差，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40110020/