为什么出队列比队列快？

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-用于存储元素的基础容器的类型。

因此std::queue-默认情况下-使用std::deque作为其内部容器，因此它最多只能与std::deque（或一般的基础容器）一样快，并且由于是包装器，因此-在优化上，编译器可以做到-速度较慢。因此，如果您正确地将速度降低了20％，则可以衡量编译器在给定的优化级别上优化包装器代码的能力。

由于std::queue的存在是为了保证FIFO的使用，仅通过公开这些功能，我怀疑-但我现在无法对其进行测试-放慢速度是因为启用了优化会大大降低速度。如果是这样，我认为这是编译器或库实现功能的错误/缺陷。