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