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