Re: [boost] Re: Review Request: cyclic_buffer

From: Howard Hinnant (hinnant_at_[hidden])
Date: 2003-06-10 09:13:03

For the general container I propose that insert reallocates if size() 
would exceed capacity (invalidating all iterators, pointers and 
references).  And if size() does not exceed capacity, all iterators, 
pointers and references are still invalidated, unless the insert 
happens at one end or the other, in which case no pointers or 
references are invalidated (iterators still are invalidated).  I would 
expect a quality implementation to minimize the number of elements that 
need to be shifted.

insert in general should have the basic exception safety guarantee.  
But when inserting only one element at either end, the strong guarantee 
is in place.  Also if the value_type's copy constructor and assignment 
operator do not throw, then the strong guarantee is in place.

For any given adaptor, I think you could restrict or eliminate insert 
as appropriate for that model.

-Howard

On Tuesday, June 10, 2003, at 05:20  AM, Jan Gaspar wrote:

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