Circular Buffer C++ Implementation

Question

I was asked this question in an interview, and didn't go through. I know, it needs some improvements, but probably I am missing something big? I would highly appreciate if someone can review it for me, so that I can get to know what I need to work on.

The problem is to complete this skeleton class to implement a circular buffer. I could have done the C++ and header in a different source, but they insisted on doing it all here, assuming it is not part of a big project.

class CircularBuffer {
public:
    CircularBuffer(int size)
        : data_(size, 0)
        , next_(0)
        , head_(-1)
    {
    }

    ~CircularBuffer()
    {
    }

    bool empty() 
    {
        return size() == 0;
    }

    int size()
    {
        // TODO: check if head is valid.
        // TODO: check emptiness properly.
        int sz = 0;
        if (head_ >= 0)
        {
            if (next_ > head_)
                sz = next_ - head_;
            else
                sz = next_ + (data_.size() - head_);
        }
        return sz;
    }

    void push(char val) 
    {
        // TODO: check if circularbuffer is full.
        if( size() == data_.size())
        {
            std::cout<<"Buffer is full, can't push anything"<< std::endl;
            return;
        }
        data_[next_++] = val;
        if(head_ < 0)
            head_ = 0;
        if (next_ == data_.size()) 
            next_ = 0;

        displayBuffer(); 
    }

    char pop()
    {
        // TODO: check if head_ is valid.
        if (head_ < 0)
        {
            std::cout<<"Empty Buffer, nothing to pop" << std::endl;
            return -1;
        }

        // TODO: adjust head_ after pop.
        char popVal = data_[head_];
        data_[head_++] = 0; // Clean the popped memory- display   purpose

        //Wrap around head_ move
        if (head_ == data_.size())
            head_ = 0;

        // Check if the buffer is empty now?
        if (head_ == next_)
        {
            head_ = -1; //Buffer is empty now
            next_ = 0;
        }

        return popVal;
    }

    void displayBuffer()
    {
        std::cout << std::endl;
        for (auto c: data_)
        {
            std::cout << c << ' ';
        }    
        std::cout << "  |   HEAD = " << head_ << "  NEXT = " << next_ << std::endl;     
    }
private:
    std::vector<char> data_;
    int next_;
    int head_;
};

Answer 1

#include

The code was in error until I prefixed it with

#include <vector>
#include <iostream>

~CircularBuffer()

There's no need to define a destructor that does nothing - just let the compiler generate a default one.

If you wanted this to be a base class, you would provide a virtual destructor, but you can explicitly default it:

virtual ~CircularBuffer() = default;

I'd say that you are right to omit copy constructor and assignment operator, as the compiler-provided ones will work correctly.

empty()

The reason containers have empty() is so that it can be quicker than testing size is non-zero. So implementing empty() in terms of size() should be a last resort. In this case, we set head negative to indicate an empty buffer, so we can just test that:

bool empty() const
{
    return head < 0;
}

Note that I've made this a const method, as we may want to call it on a buffer we don't intend to modify.

size()

There's no need for the sz variable, as we set it only to return immediately:

size_t size() const
{
    if (head < 0)
        return 0;
    if (next > head)
        return next - head;
    return next + (data.size() - head);
}

I've made this const, too, and changed the return type to be more in line with what users will expect. If I were to be really pedantic, I'd consider std::vector<char>::size_type, and adjust the head and next members accordingly.

You could write a single return with a tertiary expression here, but I think the if ladder is slightly clearer - that's obviously a judgement call.

push()

As in empty(), it's inefficient to call size() when we just want to know whether the container is full. Instead, we can just test next == head. If you must produce output, send it to std::cerr, not std::cout! Generally, in a library, it's better to report the error to the caller (by exceptions, or perhaps as a return value) rather than to output diagnostics ourselves, but I'll let that stand for now.

It wasn't obvious at first reading that if head was negative, then we could depend on next being zero. I would probably not made that assumption, and written something like:

    data[next] = val;
    if (head < 0)
        head = next;
    if (++next == data.size())
        next = 0;

pop()

Most of the critique of push() applies here, so I won't repeat it. It's not clear why -1 is chosen as the value to return on failure - was this specified in the requirements?

main()

You provide no main() function, which is a shame - it would have been nice to use your unit tests when refactoring.

---

Modified version

I changed the index types to size_t, and defined a constant to indicate empty (as size_t doesn't have negative values).

#include <vector>
#include <stdexcept>

class CircularBuffer
{
    static const size_t EMPTY = ~0u;

    std::vector<char> data;
    size_t next = 0;               // index at which next insert will occur
    size_t head = EMPTY;           // index of next pop, or EMPTY marker

public:
    CircularBuffer(size_t size)
        : data(size)
    {
    }

    virtual ~CircularBuffer() = default;

    bool empty() const
    {
        return head == EMPTY;
    }

    size_t size() const
    {
        if (empty())
            return 0;
        if (next > head)
            return next - head;
        return data.size() - head + next;
    }

    void push(char val)
    {
        if (next == head)
            throw std::logic_error("Buffer overrun");

        data[next] = val;
        if (empty())
            head = next;
        if (++next == data.size())
            next = 0;
    }

    char pop()
    {
        if (empty())
            throw std::logic_error("Buffer underrun");

        const char popVal = data[head];

        if (++head == data.size())
            head = 0;

        if (head == next)
            head = EMPTY;

        return popVal;
    }
};

---

Future directions

If you want to set yourself some more challenges, I'd recommend looking at the standard containers (especially std::queue) and seeing how you can make the interface look more like theirs. Implement front() and back() (easy!), emplace(), and some iterators.

Also, you might want to make this a template class, so it can hold any kind of element, not just char.

Answer 2

• Both methods modify both head and next, and the class invariant is quite hard to follow. As an interviewer I'd at least expect an assertion

      if (head < 0) {
          assert(next == 0);
          head = 0;
      }
  

  Better yet, the class should maintain an explicit size member. A price for increment/decrement per operation is less than the price of if, and the code would be much cleaner.

• void push()/char pop() do not inform the caller whether the action was successful or not. Printing an error message doesn't help a client to recover. As an interviewer I'd expect bool push() and std::pair<bool, char> pop().

• In any case, the error message should go to std::cerr

• The C++ containers uniformly discriminate between pop() which only pops (and returns nothing), and top()/front() which returns the value but does not modify the container. As an interviewer I'd expect adherence to this model.

• I don't know what were the requirements for displayBuffer(). As implemented, it may be used as a debugging aid, but nothing more.

• push() shall not call displayBuffer().