c++ - 为什么双端队列比队列快？

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;

然后我替换了queue<TreeNode*>与 deque<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 使用，仅通过公开这些函数，我怀疑 - 但我现在无法测试它 - 优化后速度会大幅下降打开。如果是的话，我会认为这是编译器或库实现的功能的错误/缺陷。