[boost] Re: Review Request: cyclic_buffer

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2003-06-09 20:09:54

In article <3EE4BB8A.1D8AB0E2_at_[hidden]>, Alisdair Meredith
<alisdair.meredith_at_[hidden]> wrote:

| "The one true circular buffer template" is a nigh impossible goal,
| because it means so many things to different people.
<snip>
| I would certainly like the documentation to explain the tradeoffs made
| in the implementation, and why this particular variation was chosen as
| most appropriate for the general case.

Indeed!  Excellent post!

Perhaps container adaptors could be applied to a sufficiently
generalized circular buffer.

What is the one true queue?  There isn't one.  It is best a container
adaptor (policy based if you prefer).  I suspect that a more general
circular buffer, restricted by various adaptors, might serve more uses
with less code.

The circular buffer I've needed (and coded) fits none of aforementioned
descriptions.  But it is a circular buffer nonetheless.

For my money, the general circular buffer is one that exists in a
contiguous array, but with an arbitrary begin and end within that
array, capable of wrapping around the end of the physical memory:

+---+---+---+---+---+---+---+---+---+---+
| 4 | 5 |   |   |   |   | 0 | 1 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+---+
          ^               ^
          |               |
         end            begin

Constant time push/pop_front, constant time push/pop_back.  When begin
and end collide, reallocation automatically happens vector-like.

This data structure can be efficiently coded with a 4-word data
structure.  For example:  data_ptr, capacity, size, begin_ptr  (there
are other variations that also only take 4 words).

>From this you can write adaptors to constrain capacity, have push_back
overwrite front(), throw an exception on size() exceeding capacity(),
or whatever else you need to do.

You can't adapt any other std::container to do this job because vector
is the only one with capacity, but vector doesn't have a constant time
push/pop_front.  But I believe you can adapt the above described
container to meet the needs of other "circular buffer" requirements.  
For example:

template <class T, class Container = general_cyclic_buffer<T> >
class my_cyclic_buffer
{
public:
   // typedefs ...

   my_cyclic_buffer(size_type cap) {c.reserve(cap);}

   reference operator[](size_type n) {return c[n];}
   // etc.

   void push_back(const value_type& x)
   {
      if (capacity() != 0)
      {
         if (c.size() == c.capacity())
            c.pop_front();
         c.push_back(x);
      }
   }

   change_capacity(size_type new_cap)
   {
      if (new_cap > c.capacity())
         c.reserve(new_cap);
      else if (new_cap < c.capacity())
      {
         c.erase(c.begin(), c.begin() + c.size() - new_cap);
         Container tmp(c);  // assumes tmp.capacity() == c.size()
         c.swap(tmp);
      }
   }
   // etc.
   
private:
   Container c;
};

-- 
Howard Hinnant
Metrowerks