双端队列与队列速度

Question

我正在处理LeetCode（在这里）上的问题。解决问题后，我想到了：

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();
    }
};

我的问题是为什么？我检查了std :: queue，它默认为双端队列！为什么到底是因为排队，它会更快吗？我唯一的猜测是它将值缓存在哪里？但同时，默认情况下，队列是双端队列！从字面上看，插入/删除时间再好不过了！

（附带说明，我不考虑size == 0的情况，因为问题无法对其进行测试。实际上，如果将其递为0，它们的代码将急剧崩溃）

Answer 1

这是一个有根据的猜测：

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

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

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

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