CODEWITHSUNDEEP
arraysc++11circular-bufferstdarray
Thomas Hsieh
Thomas Hsieh

Reputation: 731

Reset an element in a circular buffer

I was asked to implement a circular buffer that takes an unspecified type in C++. I assume the generic type to be of primitive type. (or should it consider non-primitive types?) For the buffer, I am using a basic array, e.g. T[] with new and delete to initialize and destroy it.

I have implemented the buffer class and tested it on integers with the expected output. But it does not work on std::string. The problem is that, when I pop the buffer, I clear the element by setting it to zero, and the compiler complains that doing so is ambiguous. As such, I need a generic way to clear an element, and I thought the std::array might support this feature, but I cannot find it in the documentation.

Is there a generic way to clear an element in a std::array or basic array, or is std::allocator my only option? Or, if I am completely in the wrong direction, How should I implement the pop method to reset the first element and increment the front index to that of the next element?

Thanks in advance!

In case it helps, below is my related code:

template<class T> T CircularBuffer<T>::pop_front()
{
    if (_size == 0)
        return 0;
    T value = buffer[_front];
    buffer[_front] = 0;
    if (--_size == 0)
    {
        _front = -1;
        _back = -1;
    }
    else
    {
        _front = (_front + 1) % _capacity;
    }
    return value;
}

Upvotes: 1

Views: 2529

Answers (2)

TobiMcNamobi
TobiMcNamobi

Reputation: 4813

In a circular buffer you do not really remove elements from memory, otherwise as Jagannath pointed out std::deque is your option. You more like "reset" the elements that have been popped.

buffer[_front] = 0;

means "assign 0 to a T". There are two methods that do that for T = std::string which explains the ambiguity. A bit simplified they look like this:

std::string std::string::operator=(char c);

std::string std::string::operator=(const char *cPtr);

I guess you don't want any of this, so my choice would be (as T.C. wrote):

buffer[_front] = T();

Additionally (and for a very similar reason) 

if (_size == 0)
    return 0;

is also a problem since it will crash, watch this:

std::string a = circularBuffer.pop_front(); // crashes on empty buffer

You could return T() here but the cleaner way would certainly be throwing an std::out_of_range exception.

Upvotes: 2

sp2danny
sp2danny

Reputation: 7687

One way you could do this, is by treating the memory as raw memory, and using placement new, and manual destructor call.

It could look something like this:

void push(const T& val)
{
    new ( data + sizeof(T)*idx++ ) T { val };
}

void pop()
{
    ( (T*) (data + sizeof(T)*--idx) ) -> ~T();
}

Upvotes: 1

Related Questions