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:
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:
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)