Re: [boost] Re: Review Request: cyclic_buffer

From: Jan Gaspar (jga_at_[hidden])
Date: 2003-06-10 04:20:34

Hi Howard!

I like your idea. But (referring to the Nigel Stewart's posting) what would you
propose for the insert? Should I not provide it?

Jan

Howard Hinnant wrote:

> 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
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

--
Jan Gaspar | jga_at_[hidden]
Whitestein Technologies | www.whitestein.com
Panenska 28 | SK-81103 Bratislava | Slovak Republic
Tel [phone] | Fax [phone]