C++: An STL-like circular buffer (Part 8)

The circular_buffer is looking in pretty good shape now. We've squashed bugs and introduced an allocator. And, to be fair, we could stop here and have a perfectly usable class.

However, let's add some more methods to the container to learn a bit more about writing STL-like containers. The story can't end here after all, there's been no dramatic climax.

operator[] and at

These two methods aren't strictly required of a circular buffer. Section 23.1.1 of the standard claims these operations are only provided when they take constant time. We can achieve constant time indexing with our class, so let's write them.

    // In declaration
   reference       operator[](size_type n);
   const_reference operator[](size_type n) const;
   reference       at(size_type n);
   const_reference at(size_type n) const;

at() is an index operator that performs bounds checking, throwing a std::out_of_range error if the index is invalid. operator[] itself need perform no bounds checking. Given our wrap() method, the implementations are simple:

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::operator[]
   (size_type n)
{
   return *wrap(m_front+n);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::operator[]
   (size_type n) const
{
   return *wrap(m_front+n);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::at(size_type n)
{
   if (n >= size()) throw std::out_of_range("Parameter out of range");
   return (*this)[n];
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::at
    (size_type n) const
{
   if (n >= size()) throw std::out_of_range("Parameter out of range");
   return (*this)[n];
}

We implement at() in terms of operator[]. To use std::out_of_range, you'll need to include <stdexcept>

We should write some more tests for test these new methods. In showing you this, I'll reproduce the entire class so far.

#include <algorithm>
#include <stdexcept>

template <typename T, typename A = std::allocator<T> >
class circular_buffer
{
public:
   typedef T                                            value_type;
   typedef A                                            allocator_type;
   typedef typename allocator_type::size_type           size_type;
   typedef typename allocator_type::difference_type     difference_type;
   typedef typename allocator_type::reference           reference;
   typedef typename allocator_type::const_reference     const_reference;
   typedef typename allocator_type::pointer             pointer;
   typedef typename allocator_type::const_pointer       const_pointer;

   explicit circular_buffer(size_type capacity,
                            const allocator_type &a = allocator_type());
   ~circular_buffer();
   allocator_type get_allocator() const;

   size_type size() const;
   size_type max_size() const;
   bool      empty() const;

   size_type capacity() const;

   reference       front();
   const_reference front() const;

   bool push_back(const value_type &);
   void pop_front();
   void clear();

   reference       operator[](size_type n);
   const_reference operator[](size_type n) const;
   reference       at(size_type n);
   const_reference at(size_type n) const;

private:
   size_type       m_capacity;
   allocator_type  m_allocator;
   pointer         m_buffer;
   pointer         m_front;
   pointer         m_back; // points to next unused item

   typedef circular_buffer<T> class_type;

   circular_buffer(const class_type &);
   class_type &operator=(const class_type &);

   value_type *wrap(value_type *ptr) const
   {
       assert(ptr < m_buffer + m_capacity*2);
       if (ptr >= m_buffer+m_capacity)
           return ptr-m_capacity;
       else
           return ptr;
   }
};

template <typename T, typename A>
inline
circular_buffer<T,A>::circular_buffer
    (size_type capacity, const allocator_type &allocator)
: m_capacity(capacity),
 m_allocator(allocator),
 m_buffer(m_allocator.allocate(capacity)),
 m_front(0),
 m_back(m_buffer)
{
   assert(capacity > 0);
}

template <typename T, typename A>
inline
circular_buffer<T,A>::~circular_buffer()
{
   clear(); // deallocates all objects
   m_allocator.deallocate(m_buffer, m_capacity);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::allocator_type
circular_buffer<T,A>::get_allocator() const
{
   return m_allocator;
}


template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::capacity() const
{
   return m_capacity;
}

template <typename T, typename A>
inline
bool circular_buffer<T,A>::empty() const
{
   return !m_front;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::size() const
{
   return !m_front ? 0
                   : (m_back > m_front ? m_back : m_back+m_capacity) - m_front;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::max_size() const
{
   return m_allocator.max_size();
}

template <typename T, typename A>
inline
bool circular_buffer<T,A>::push_back(const value_type &value)
{
   if (m_front && m_front == m_back)
       m_allocator.destroy(m_back);

   m_allocator.construct(m_back, value);

   value_type *const next = wrap(m_back+1);
   if (!m_front)
   {
       // first entry in the buffer
       m_front = m_back;
       m_back = next;
       return true;
   }
   else if (m_front == m_back)
   {
       // buffer is full already, throw something away
       m_front = m_back = next;
       return false;
   }
   else
   {
       m_back = next;
       return true;
   }
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::front()
{
   assert(m_front);
   return *m_front;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::front() const
{
   assert(m_front);
   return *m_front;
}

template <typename T, typename A>
inline
void circular_buffer<T,A>::pop_front()
{
   assert(m_front);

   m_allocator.destroy(m_front);
   value_type *const next = wrap(m_front+1);
   if (next == m_back)
       m_front = 0;
   else
       m_front = next;
}

template <typename T, typename A>
inline
void circular_buffer<T,A>::clear()
{
   if (m_front)
   {
       do
       {
           m_allocator.destroy(m_front);
           m_front = wrap(m_front+1);
       }
       while (m_front != m_back);
   }
   m_front = 0;
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::operator[]
   (size_type n)
{
   return *wrap(m_front+n);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::operator[]
   (size_type n) const
{
   return *wrap(m_front+n);
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::at(size_type n)
{
   if (n >= size()) throw std::out_of_range("Parameter out of range");
   return (*this)[n];
}

template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::at
    (size_type n) const
{
   if (n >= size()) throw std::out_of_range("Parameter out of range");
   return (*this)[n];
}

namespace tests
{
   void pushing_and_popping()
   {
       circular_buffer<int> cb(5);

       assert(cb.size() == 0);
       assert(cb.capacity() == 5);
       assert(cb.empty());
       assert(cb.max_size() > 0);

       assert(cb.push_back(1));
       assert(cb.size() == 1);
       assert(cb.capacity() == 5);
       assert(!cb.empty());
       assert(cb.front() == 1);

       assert(cb.push_back(2));
       assert(cb.size() == 2);
       assert(cb.capacity() == 5);
       assert(!cb.empty());
       assert(cb.front() == 1);

       assert(cb.push_back(3));
       assert(cb.push_back(4));
       assert(cb.push_back(5));
       assert(cb.size() == 5);
       assert(cb.capacity() == 5);
       assert(!cb.empty());
       assert(cb.front() == 1);

       assert(!cb.push_back(6));
       assert(cb.size() == 5);
       assert(cb.capacity() == 5);
       assert(!cb.empty());
       assert(cb.front() == 2);

       cb.pop_front();
       assert(cb.size() == 4);
       assert(cb.capacity() == 5);
       assert(!cb.empty());
       assert(cb.front() == 3);

       cb.pop_front();
       assert(cb.size() == 3);
       assert(cb.front() == 4);

       cb.pop_front();
       assert(cb.size() == 2);
       assert(cb.front() == 5);

       cb.pop_front();
       assert(cb.size() == 1);
       assert(cb.front() == 6);

       cb.pop_front();
       assert(cb.size() == 0);
       assert(cb.capacity() == 5);
       assert(cb.empty());

       // empty again

       assert(cb.push_back(7));
       assert(cb.size() == 1);
       assert(cb.capacity() == 5);
       assert(!cb.empty());
       assert(cb.front() == 7);

       assert(cb.push_back(8));
       assert(cb.push_back(9));
       assert(cb.size() == 3);
       assert(!cb.empty());
       assert(cb.front() == 7);

       cb.clear();
       assert(cb.size() == 0);
       assert(cb.capacity() == 5);
       assert(cb.empty());
   }

   void indexing()
   {
       circular_buffer<int> cb(5);

       // A helper - like asssert, but checks for an exception
        #define assert_throws(a,b) \
        {\
            try { a; throw "Failed to throw"; } \
            catch (const b&) { /*OK*/ } \
            catch (...) { throw "Threw wrong thing"; } \
        }

       // We loop round this test several times so our data wraps around the
       // internal m_buffer array a few times.
       for (size_t n = 0; n < 10; ++n)
       {
           assert(cb.empty());

           const circular_buffer<int> &const_cb(cb);

           assert_throws(cb.at(0), std::out_of_range);
           assert_throws(cb.at(1), std::out_of_range);
           assert_throws(const_cb.at(0), std::out_of_range);
           assert_throws(const_cb.at(0), std::out_of_range);
           // we could check that operator[] explodes, but there's little point!

           assert(cb.push_back(0));
           assert(cb.push_back(1));
           assert(cb.push_back(2));
           assert(cb.at(0) == 0); assert(const_cb.at(0) == 0);
           assert(cb.at(1) == 1); assert(const_cb.at(1) == 1);
           assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
           assert(cb[0] == 0);    assert(const_cb[0] == 0);
           assert(cb[1] == 1);    assert(const_cb[1] == 1);
           assert(cb[2] == 2);    assert(const_cb[2] == 2);

           assert(cb.front() == 0);
           cb[0] = 3;
           assert(cb.front() == 3);
           assert(cb.at(0) == 3); assert(const_cb.at(0) == 3);
           assert(cb.at(1) == 1); assert(const_cb.at(1) == 1);
           assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
           assert(cb[0] == 3);    assert(const_cb[0] == 3);
           assert(cb[1] == 1);    assert(const_cb[1] == 1);
           assert(cb[2] == 2);    assert(const_cb[2] == 2);

           cb[1] = 4;
           assert(cb.at(0) == 3); assert(const_cb.at(0) == 3);
           assert(cb.at(1) == 4); assert(const_cb.at(1) == 4);
           assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
           assert(cb[0] == 3);    assert(const_cb[0] == 3);
           assert(cb[1] == 4);    assert(const_cb[1] == 4);
           assert(cb[2] == 2);    assert(const_cb[2] == 2);

           cb.pop_front();
           assert(cb[0] == 4);    assert(const_cb[0] == 4);
           assert(cb[1] == 2);    assert(const_cb[1] == 2);

           cb.pop_front();
           assert(cb[0] == 2);    assert(const_cb[0] == 2);

           cb.pop_front();
       }

   }
}

int main()
{
   tests::pushing_and_popping();
   tests::indexing();
   return 0;
}