Boost logo

Boost :

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.
| 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
   // 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())

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

Howard Hinnant

Boost list run by bdawes at, gregod at, cpdaniel at, john at