为什么 deque 比 queue 快？

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的使用，只暴露了这些功能，我对此表示怀疑-但现在我不能测试它-这慢下来是大大优化与开启。如果是这样，我会将其视为编译器或库实现功能的错误/缺陷。