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 <[EMAIL PROTECTED]>, Alisdair Meredith
> <[EMAIL PROTECTED]> 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 | [EMAIL PROTECTED]
Whitestein Technologies | www.whitestein.com
Panenska 28 | SK-81103 Bratislava | Slovak Republic
Tel +421(2)5930-0734 | Fax +421(2)5443-5512
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
