为什么双端队列比队列快？

Question

我有以下工作代码（g++ 8.2，C++17 标准。）

    queue<TreeNode*> q{};

    q.push(root);
    q.push(nullptr);
    int sum = root -> val;
    while (!q.empty()) {
        TreeNode *n = q.front();
        q.pop();

        if (n != nullptr) {
            sum += n->val;
            if (n-> left != nullptr) q.push(n->left);
            if (n-> right != nullptr) q.push(n->right);   
        } else {
            if (q.empty()) break;
            q.push(nullptr);
            sum = 0;
        }

    }
    return sum;

然后我用deque<TreeNode*>替换了queue<TreeNode*>。事实证明，速度至少提高了 20%。为什么 deque<TreeNode*> 比 queue<TreeNode*> 快这么多？

Answer 1

来自cppreference.com: std::queue

template<
    class T,
    class Container = std::deque<T>
> class queue;

Container - The type of the underlying container to use to store the elements.

所以 std::queue - 默认情况下 - 使用 std::deque 作为它的内部容器，因为它最多只能和 std::deque 一样快（或者一般的底层容器), 并且因为它是一个包装器 - 取决于编译器可以做的优化 - 更慢。因此，如果您正确测量了 20% 的减速，那么您就可以测量编译器在给定优化级别优化包装代码方面的表现。

由于 std::queue 的存在是为了保证 FIFO 的使用，通过仅公开这些函数，我怀疑 - 但我现在无法测试它 - 开启优化后速度会急剧下降。如果是，我会将其视为编译器或库实现功能的 bug/defect。

为什么双端队列比队列快？

Why is deque faster than queue?

c++

data-structures

queue

deque