Step 3 of 7
deque, the double-ended queue
std::vector is fast at the back but slow at the front: removing element 0 shifts every other element down. std::deque (a "double-ended queue", said "deck") is fast at both ends: push_back, push_front, pop_back and pop_front are all O(1). It still supports d[i] indexing.
#include <deque>
#include <iostream>
#include <string>
int main() {
std::deque<std::string> history;
const std::size_t limit = 3;
for (const char* page : {"home", "news", "sports", "weather", "mail"}) {
history.push_back(page);
if (history.size() > limit) history.pop_front(); // forget the oldest
}
for (const auto& p : history) std::cout << p << " ";
std::cout << "\n";
history.push_front("start");
std::cout << history.front() << " ... " << history.back() << " (" << history.size() << ")\n";
}
sports weather mail
start ... mail (4)
The sliding window pattern
The example keeps only the most recent 3 pages: push the new one at the back, and if that makes it too big, pop the oldest from the front. That's a sliding window, and it's exactly what a moving average needs.
To keep an average cheap, don't add up the whole window every time. Keep a running sum as a member:
- when a value enters,
sum += value, - when a value leaves from the front,
sum -= d.front()beforepop_front().
Then average() is just sum / size, in constant time. Remember to divide as double, and decide what an empty window returns (0 is a safe choice).
std::queue is a restricted wrapper around a deque that only allows the queue operations.
Your turn: write class MovingAverage that remembers only the last n values added and reports their average.