Constant time push/pop_front, constant time push/pop_back. When begin and end collide, reallocation automatically happens vector-like.
Another point to consider:
Constant time push/pop can not be combined with std::vector
automatic re-allocation due to the linear cost of copying
into the realloc'd buffer. Given that circular buffers
are often used in the context of real-time applications,
it seems to be consistant that push/pop from each end
should be truely constant time, and as a consequence the
the capacity is never implicitly changed unless explicitly
requested via reserve() or resize().So as a proposed design criteria:
circular_buffer
- provides guaranteed O(1) push/pop
- provides O(n) arbitrary insertion
- provides O(n) manual capacity and size managementin contrast to vector
- provides (amortized) O(1) push_back/pop_back
O(n) in reallocation case
- provides O(n) arbitrary insertion
- provides O(n) manual capacity and size management
(The implication for real-time uses of circular_buffer is that
only push and pop are allowed in time-critical code.) This I think is a resounding case against re-allocation,
and reflected in the broader understanding of what circular
buffers are commonly used for. A re-allocating circular_buffer should therefore only be
an adaptor or variant, but can not provide "proper" O(1)
push/pop, so is missing this critical feature of a "true"
circular_buffer._______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
