C++ equivalent of Python's deque with maxlen - sliding window

Question

In Python it is really easy to get sliding window functionality using a deque with maxlen:

from collections import deque
deck = deque(maxlen=4)
deck.append(0x01)
deck.append(0x02)
deck.append(0x03)
deck.append(0x04)
deck.append(0x05)
for item in deck:
 print(item) # outputs 2, 3, 4, 5

This does two things - it grows until maxsize and then once maxsize has been reached items drop off the deque.

I wanted something similar in C++ and wrote the following (note, I know C++ has a deque, but I couldn't see how to reserve the size):

template <typename T>
auto rotate_push(std::vector<T> &container, const T& val) -> void
{
 if (container.size() < container.capacity()) {
 container.resize(deck.size() + 1);
 }
 else {
 std::rotate(container.begin(), container.begin() + 1, container.end());
 }
 container[container.size() - 1] = val;
}
auto deck = std::vector<int>();
deck.reserve(4);
rotate_push(deck, 1);
rotate_push(deck, 2);
rotate_push(deck, 3);
rotate_push(deck, 4);
rotate_push(deck, 5);
for (auto const &item : deck) {
 printf("%d\n", item); // outputs 2, 3, 4, 5
}

My Questions are:

• Are the implementations basically equivalent (If not then why)
• Is there a better custom implementation
• Is there a easier/pre-existing implementation using STL
• Is there a easier/pre-existing implementation using other
• Is there a more performant implementation

Answers:

• No, they have different push complexity [by Johnbot]
• Use a free function or wrap std::deque [by Johnbot]
• (Un-answered)
• Boost Circular Buffer [by ratchet freak]
• Circular Buffer [by ratchet freak]

Answer 1

Are the implementations basically equivalent (If not then why)

No, your rotate_push is O(n), normal deque push and pop are O(1).

You are not guaranteed that capacity() will return the same size you requested, it may be higher.

---

You can either implement your own static push:

template<typename T>
static inline void push_back(const typename std::deque<T>::size_type max_size, std::deque<T>& deque, const T& value)
{
 while (deque.size() >= max_size) {
 deque.pop_front();
 }
 deque.push_back(value);
}
int main(int argc, char* argv[])
{
 auto window = std::deque<int>{};
 push_back(5, window, 1);
 push_back(5, window, 2);
 push_back(5, window, 3);
 push_back(5, window, 4);
 push_back(5, window, 5);
 push_back(5, window, 6);
 for (auto val : window) {
 std::cout << val << std::endl;
 }
}

Create a minimal wrapper around a deque:

//MaxSizeDeque.h
#pragma once
#include <deque>
namespace YourNamespace {
template <typename T>
class MaxSizeDeque
{
public:
 typedef typename std::deque<T>::size_type size_type;
 typedef typename std::deque<T>::iterator iterator;
 typedef typename std::deque<T>::const_iterator const_iterator;
 MaxSizeDeque(const size_type max_size);
 void push_back(const T& val);
 void push_back(T&& val);
 template <class... Args>
 void emplace_back(Args&&... args);
 typename iterator begin() noexcept;
 typename const_iterator begin() const noexcept;
 typename iterator end() noexcept;
 typename const_iterator end() const noexcept;
private:
 size_type max_size_;
 std::deque<T> deque_;
 void PopIfAtMaxSize();
};
template<typename T>
inline MaxSizeDeque<T>::MaxSizeDeque(const size_type max_size)
 : max_size_(max_size)
 , deque_(std::deque<T>{})
{}
template<typename T>
inline void MaxSizeDeque<T>::push_back(const T& val)
{
 PopIfAtMaxSize()
 deque_.push_back(val);
}
template<typename T>
inline void MaxSizeDeque<T>::push_back(T&& val)
{
 PopIfAtMaxSize();
 deque_.push_back(std::move(val));
}
template<typename T>
inline void MaxSizeDeque<T>::PopIfAtMaxSize()
{
 if (deque_.size() >= max_size_) {
 deque_.pop_front();
 }
}
template<typename T>
inline typename MaxSizeDeque<T>::iterator MaxSizeDeque<T>::begin() noexcept
{
 return deque_.begin();
}
template<typename T>
inline typename MaxSizeDeque<T>::const_iterator MaxSizeDeque<T>::begin() const noexcept
{
 return deque_.begin();
}
template<typename T>
inline typename MaxSizeDeque<T>::iterator MaxSizeDeque<T>::end() noexcept
{
 return deque_.end();
}
template<typename T>
inline typename MaxSizeDeque<T>::const_iterator MaxSizeDeque<T>::end() const noexcept
{
 return deque_.end();
}
template<typename T>
template<class ...Args>
inline void MaxSizeDeque<T>::emplace_back(Args && ...args)
{
 PopIfAtMaxSize();
 deque_.emplace_back(std::forward<Args>(args)...);
}
//And so on for the rest of the needed functions
}

And use it:

int main(int argc, char* argv[])
{
 auto window = YourNamespace::MaxSizeDeque<int>(5);
 window.push_back(5);
 window.push_back(4);
 window.push_back(3);
 window.push_back(2);
 window.push_back(1);
 window.push_back(0);
 for (auto val : window) {
 std::cout << val << std::endl;
 }
}

Or just do as rachet freak suggest and use an existing 3rd party implementation.

• user975326: I was going to ask, "Why don't you inherit from deque", then I read this: stackoverflow.com/questions/2034916/….
• user975326: const typename std::deque<T>::size_type max_size - I hadn't come across dependant names before. Thanks. en.cppreference.com/w/cpp/language/dependent_name
• Barry: There's some issues with your MaxSizeDeque, careful with the rvalue references and the forwarding references.
• Johnbot: @Barry I added std::forward to push_back and emplace_back. Thanks!
• Barry: @Johnbot In push_back, you just want std::move

Answer 2

You will get better performance using a ring buffer. (With an existing implementation in Boost)

This will keep an extra set of indexes into the buffer to specify the start and end of where the data is and wrap around automatically.

• user975326: Yes, a ring buffer would have better performance, I guess I'm being lazy and wanted something 'out-of-the-box'. I currently don't use boost and I don't fancy rolling my own which works with iterators and the like!
• ratchet freak: The Boost license is permissive enough that you can copy paste it's implementation into one of your header files (no need to include all of boost for a single container)
• Loki Astari: @user975326: You should be using boost. It is basically well tested code that will eventually end up in the standard.