双端队列与队列速度

我正在研究 LeetCode 上的一个问题（Here https://leetcode.com/problems/moving-average-from-data-stream/）。当我完成这个问题后，我想出了：

class MovingAverage {
    std::deque<int> numsToAverage;
    int maxSize;
    int currentTotal;
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        maxSize = size;
        currentTotal = 0;
    }

    double next(int val) 
    {
        currentTotal += val;
        numsToAverage.push_back(val);

        if (numsToAverage.size() > maxSize)
        {
            currentTotal -= numsToAverage[0];
            numsToAverage.pop_front();
        }

        return (double)currentTotal / (double)numsToAverage.size();
    }
};

后来，我看到另一个解决方案与我的非常相似，但使用了队列。出于好奇，我换了只有双端队列到队列我从第 18 个百分点（双端队列）跳到第 56 个百分点（队列）。这是队列代码：

class MovingAverage {
    std::queue<int> numsToAverage;
    int maxSize;
    int currentTotal;
public:
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        maxSize = size;
        currentTotal = 0;
    }

    double next(int val) 
    {
        currentTotal += val;
        numsToAverage.push(val);

        if (numsToAverage.size() > maxSize)
        {
            currentTotal -= numsToAverage.front();
            numsToAverage.pop();
        }

        return (double)currentTotal / (double)numsToAverage.size();
    }
};

我的问题是具体的why?我检查了标准::队列 http://en.cppreference.com/w/cpp/container/queue它默认为双端队列！为什么仅仅因为它是一个队列就会更快？我唯一的猜测是它在某个地方缓存了该值？但同时，队列默认是双端队列！插入/删除时间简直不能再好了！

（旁注，我没有考虑 size == 0 的情况，因为这个问题没有测试它。事实上，如果你把它交给 0，他们的代码就会剧烈崩溃）

这是一个有根据的猜测：

• 内存控制器具有预取“惯用手性”，它会奖励连续的升序内存访问，但按降序访问的速度会较慢。

• 因此，用作 FIFO 容器的双端队列具有在一侧推入并在另一侧弹出的首选方向。

• 您的双端队列代码可能使用最不受欢迎的方向。但队列实现已经经过优化，可以在其最喜欢的方向上使用底层双端队列。

• 有一种简单的方法可以测试这个假设（假设这些是非保证的实现细节）。在您的双端队列代码中，切换push_back --> push_front and pop_front --> pop_back。如果假设正确，双端队列代码应该加速到与队列实现一样快:-)