Virtual Pages

You can use virtual pages to create 2 adjacent regions of virtual memory that are both mapped to the same region of physical memory. For an example of how to do this, see: https://lo.calho.st/posts/black-magic-buffer/.

typedef struct {
    uint8_t *buffer;
    size_t   buffer_size;
    int      fd;
    size_t   head;
    size_t   tail;
} queue_t;

bool init(queue_t *q, size_t size) {
    // Make an anonymous file and set its size
    q->fd = memfd_create("queue_buffer", 0);
    ftruncate(q->fd, size);

    // Ask mmap for an address at a location where we can put both virtual copies of the buffer
    q->buffer = mmap(NULL, 2 * size, PROT_NONE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);

    // Map the buffer at that address
    mmap(q->buffer, size, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_FIXED, q->fd, 0);

    // Now map it again, in the next virtual page
    mmap(q->buffer + size, size, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_FIXED, q->fd, 0);

    // Initialize our buffer indices
    q->head = 0;
    q->tail = 0;
}

You would manage this buffer in much the same way as in G. Sliepen's answer, except that you don't create that second copy of each element. Instead, each element will automatically be reachable from 2 different addresses.

Pros:

• Every operation is O(1).
• There is no copying overhead whatsoever.

Cons:

• This cannot be done in a portable manner. If you need to be platform-independent, consider writing one virtual page-based implementation for each platform that supports that, and writing a different implementation as a fallback for other platforms to use.
• The buffer size must be a multiple of the page size, so if you only need small buffers, it'll cost you lots of extra memory.

What O(N)?

You are correct that copying the bytes is O(N), however there are multiple Ns here, so this can be misleading. In this particular case, it should be noted that you can get away with never copying more than a window-size worth of data, and thus you can have a simple O(window-size) solution.

Vector is good enough!

When handling a similar problem -- TCP bytes, which have to be buffered until a full message is received -- my goto solution is to just use a std::vector (or similar):

1. Buffer all you can in the vector.
2. Unbuffer all complete windows.
3. Trim all complete windows.

For example:

1. Buffer 1018 elements (with push_back).
2. Unbuffer 1010 elements (window-size of 10).
3. Erase the first 1010 elements (with range erase, resulting in copying the last 8).

Even in the case of an unbounded number of buffered bytes, this process is efficient since it never copies more than a window-size worth of data.

std::memcpy is blindingly fast, as long as your elements can be memcpied (int can) and their number is small (a few cache lines), there's little point doing anything more complicated.

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 can be 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';
}