Deque vs Queue Speed

I worked on a problem on LeetCode ( here ). When I finished the problem, I came up with:

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

Subsequently, I saw that the other solution was very similar to mine, but used the queue. Out of curiosity, I switched only the deck into the queue, and I jumped from the 18th percentile (deque) to the 56th percentile (turn). Here's the queue code:

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

My question is specifically why? I checked std :: queue and deque is used by default! Why simply faster because it's the turn? My only guess is caching that values ​​somewhere? But at the same time, the default queue is IS deque! Insert / delete times literally could not be better!

( , , size == 0, . , , 0)

+4

Source: https://habr.com/ru/post/1664379/


All Articles