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.

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.