1

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;
}
TobiMcNamobi
  • 4,687
  • 3
  • 33
  • 52
Thomas Hsieh
  • 731
  • 1
  • 6
  • 26
  • 2
    [std::deque](http://en.cppreference.com/w/cpp/container/deque) should be used instead. And there are no reference types in C++. If you think `class` is a reference type and `struct` is a value type, then no that's not the case. – Jagannath May 04 '15 at 05:44
  • @Jagannath Thanks for pointing that out! I have reworded to **primitive** (what I meant by value type) and **non-primitive** (what I meant by reference type). – Thomas Hsieh May 04 '15 at 06:33
  • So, the answer is to [std::deque](http://en.cppreference.com/w/cpp/container/deque). – Jagannath May 04 '15 at 06:41
  • 3
    You can assign `T()` to the element, or use placement new and explicit destructor calls. The latter is more correct; the former is easier to write. – T.C. May 04 '15 at 06:46
  • @Jagannath I guess the OP wants the [circular buffer](http://en.wikipedia.org/wiki/Circular_buffer) to be fixed size. So no deque. – TobiMcNamobi May 04 '15 at 07:04

2 Answers2

2

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.

TobiMcNamobi
  • 4,687
  • 3
  • 33
  • 52
  • Thank you! I actually meant to ask how to "reset"; I've edited the question. So `T()` can be applied on primitive types as well? As to the exception handling, I was convinced by [this post](http://stackoverflow.com/questions/4892108/c-stl-stack-question-why-does-pop-not-throw-an-exception-if-the-stack-is-em) and thought I would return nothing instead. – Thomas Hsieh May 04 '15 at 12:05
  • 1
    @ThomasHsieh I see, in case you want to save the time for an empty-check, you may consider removing the whole `if` statement. – TobiMcNamobi May 04 '15 at 12:25
  • @ThomasHsieh Please mark the answer that suits your needs as "accepted" by clicking the check (near vote count). – TobiMcNamobi May 05 '15 at 13:11
1

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();
}
sp2danny
  • 7,488
  • 3
  • 31
  • 53