Skip to main content
missing words
Source Link
Toby Speight
  • 88.7k
  • 14
  • 104
  • 327

That simplifies the shift operation, too - it can be something like

That simplifies the shift operation, too - it something like

That simplifies the shift operation, too - it can be something like

Source Link
Toby Speight
  • 88.7k
  • 14
  • 104
  • 327

G. Sliepen's answer shows how to get consistent insertion times, but I'll review some other aspects:

    writeIndex = (writeIndex + 1) % buffer.size();

    if (writeIndex == 0) {
        // Perform O(N) copy when we reach the end of the buffer
        for (size_t i = 0; i < windowSize; ++i) {
            buffer[i] = buffer[buffer.size() - windowSize + i];
        }
        writeIndex = windowSize;
    }

Here, we do the expensive % every time, but we only need to test whether we have reached the capacity:

    if (++writeIndex == buffer.size()) {
        // Perform O(N) copy when we reach the end of the buffer
        for (size_t i = 0; i < windowSize; ++i) {
            buffer[i] = buffer[buffer.size() - windowSize + i];
        }
        writeIndex = windowSize;
    }

The loop that shifts the content is just the std::copy() algorithm written out long-hand. Prefer to use standard algorithms when available, to keep the logic simple.


printBuffer() is quite inflexible - in particular, this debugging information is much more suited to std::clog than std::cout. Consider instead providing a function that returns a std::span that any caller can use:

std::span<int> buffer_content() const;

That simplifies the shift operation, too - it something like

        std::ranges::copy(buffer_content(), buffer.begin());

We'll probably want to generalise this to types other than int - at which point, we should think about whether the content-type will be default- and copy-constructible.

If it's not default-constructible, then we can't initialise the content as buffer{bufferSize} - we'll need to initialise it as an empty vector, reserve its capacity, then emplace_back() in the add function.

If it's not copy-constructible, then we'll need to std::move() rather than std::copy() when shifting.

And we'll need to erase() or resize() to destruct the moved-from elements after copying content to the beginning. Or just erase() the earlier content and let the vector deal with moving - as always, the most maintainable code is that which you don't have to write!


Give the member functions names that conform to standard container members, so that the class is more usable in generic code. E.g. push_back() is a better choice than addElement().


Modified code

#include <stdexcept>
#include <span>
#include <vector>

template<class T>
class SlidingWindowBuffer
{
    std::vector<T> buffer = {};
    std::size_t windowSize;

public:
    SlidingWindowBuffer(size_t bufferSize, size_t windowSize)
        : windowSize{windowSize}
    {
        if (windowSize > bufferSize) {
            throw std::invalid_argument("Window size exceeds storage capacity");
        }
        buffer.reserve(bufferSize);
    }

    auto begin() const {
        return (buffer.size() < windowSize)
            ? buffer.begin()
            : buffer.end() - windowSize;
    }
    auto end() const {
        return buffer.end();
    }

    void push_back(T element)
    {
        if (buffer.size() == buffer.capacity()) {
            buffer.erase(buffer.begin(), begin());
        }

        buffer.push_back(std::move(element));
    }

    std::span<const T> content() const
    {
        return {begin(), end()};
    }

    // for debugging use
    std::span<const T> buffer_content() const
    {
        return buffer;
    }
};
// Demo

#include <algorithm>
#include <iostream>
#include <iterator>

int main()
{
    std::size_t bufferSize = 15;
    std::size_t windowSize = 10;
    SlidingWindowBuffer<int> swb(bufferSize, windowSize);

    // Example usage
    for (int i = 0; i < 20; ++i) {
        swb.push_back(i);
        std::ranges::copy(swb, std::ostream_iterator<int>(std::cout, " "));
        std::cout << '\n';
    }

    std::cout << '\n';
    std::ranges::copy(swb.buffer_content(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';
}