...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
The following paragraphs describe issues that had to be considered during the implementation of the circular_buffer:
The thread-safety of the circular_buffer
is the same as the thread-safety of containers in most STL implementations.
This means the circular_buffer
is not fully thread-safe. The thread-safety is guaranteed only in the sense
that simultaneous accesses to distinct instances of the circular_buffer
are safe, and simultaneous read accesses to a shared circular_buffer
are safe.
If multiple threads access a single circular_buffer
,
and at least one of the threads may potentially write, then the user is responsible
for ensuring mutual exclusion between the threads during the container accesses.
The mutual exclusion between the threads can be achieved by wrapping operations
of the underlying circular_buffer
with a lock acquisition and release. (See the Bounded Buffer example code at
circular_buffer_bound_example.cpp)
Overwrite operation occurs when an element is inserted into a full circular_buffer
- the old element
is being overwritten by the new one. There was a discussion what exactly "overwriting
of an element" means during the formal review. It may be either a destruction
of the original element and a consequent inplace construction of a new element
or it may be an assignment of a new element into an old one. The circular_buffer
implements assignment
because it is more effective.
From the point of business logic of a stored element, the destruction/construction operation and assignment usually mean the same. However, in very rare cases (if in any) they may differ. If there is a requirement for elements to be destructed/constructed instead of being assigned, consider implementing a wrapper of the element which would implement the assign operator, and store the wrappers instead. It is necessary to note that storing such wrappers has a drawback. The destruction/construction will be invoked on every assignment of the wrapper - not only when a wrapper is being overwritten (when the buffer is full) but also when the stored wrappers are being shifted (e.g. as a result of insertion into the middle of container).
There are several options how to cope if a data source produces more data than can fit in the fixed-sized buffer:
It is apparent that the circular_buffer
implements the third option. But it may be less apparent it does not implement
any other option - especially the first two. One can get an impression that
the circular_buffer
should
implement first three options and offer a mechanism of choosing among them.
This impression is wrong.
The circular_buffer
was
designed and optimized to be circular (which means overwriting the oldest data
when full). If such a controlling mechanism had been enabled, it would just
complicate the matters and the usage of the circular_buffer
would be probably less straightforward.
Moreover, the first two options (and the fourth option as well) do not require
the buffer to be circular at all. If there is a need for the first or second
option, consider implementing an adaptor of e.g. std::vector. In this case
the circular_buffer
is
not suitable for adapting, because, contrary to std::vector, it bears an overhead
for its circular behaviour.
When reading or removing an element from an empty buffer, the buffer should
be able to notify the data consumer (e.g. by throwing underflow exception)
that there are no elements stored in it. The circular_buffer
does not implement such a behaviour for two reasons:
It is considered to be a bug to read or remove an element (e.g. by calling
front()
or
pop_back()
)
from an empty std container and from an empty circular_buffer
as well. The data consumer has to test if the container is not empty before
reading/removing from it by testing empty()
.
However, when reading from the circular_buffer
,
there is an option to rely on the at()
method which throws an exception when the index is out of range.
An iterator is usually considered to be invalidated if an element, the iterator
pointed to, had been removed or overwritten by an another element. This definition
is enforced by the Debug Support and is documented for every method. However,
some applications utilizing circular_buffer
may require less strict definition: an iterator is invalid only if it points
to an uninitialized memory.
Consider following example:
#define BOOST_CB_ENABLE_DEBUG 0 // The Debug Support has to be disabled, otherwise the code produces a runtime error. #include <boost/circular_buffer.hpp> #include <boost/assert.hpp> #include <assert.h> int main(int /*argc*/, char* /*argv*/[]) { boost::circular_buffer<int> cb(3); cb.push_back(1); cb.push_back(2); cb.push_back(3); boost::circular_buffer<int>::iterator it = cb.begin(); assert(*it == 1); cb.push_back(4); assert(*it == 4); // The iterator still points to the initialized memory. return 0; }
The iterator does not point to the original element any more (and is considered
to be invalid from the "strict" point of view) but it still points
to the same valid place in the memory. This "soft" definition of
iterator invalidation is supported by the circular_buffer
but should be considered as an implementation detail rather than a full-fledged
feature. The rules when the iterator is still valid can be inferred from the
code in soft_iterator_invalidation.cpp.
Since Boost 1.54.0 support for move semantics was implemented using the Boost.Move library. If rvalue references
are available circular_buffer
will use them, but if not it uses a close, but imperfect emulation. On such
compilers:
emplace
,
or if they support Boost.Move, moved into place.
circular_buffer
will use
rvalues and move emulations for value types only if move constructor and move
assignment operator of the value type do not throw; or if the value type has
no copy constructor.
Some methods won't use move constructor for the value type at all, if the constructor
throws. This is required for data consistency and avoidance of situations,
when aftrer an exception circular_buffer
contains moved away objects along with the good ones.
See documentation for is_copy_constructible
, is_nothrow_move_assignable
and is_nothrow_move_constructible
type
triats. There you'll find information about how to make constructor of class
noexcept and how to make a non-copyable class in C++03 and C++98.
Performance of circular_buffer
will greatly improve if value type has noexcept
move constructor and noexcept move assignment.
Reference documentation of the circular_buffer
contains notes like "Throws: See Exceptions of move_if_noexcept(T&)
".
That note means the following: move_if_noexcept(T&
value)
does not throws exceptions at all, but it returns value
as rvalue reference only if class T
have noexcept move constructor and noexcept move assignment operator; or if
it has no copy constructor. Otherwise move_if_noexcept(T&
value)
returns value
as const reference.
This leads us to the following situation:
value
has a noexcept
move constructor and noexcept move assignment operator, then no exceptions
will be thrown at all.
value
has a throwing
move constructor and some copy constructor, then method may throw exceptions
of copy constructor.
value
has no copy constructor,
then method may throw exceptions of move constructor.
move_if_noexcept(T&)
uses
Boost.Move, is_copy_constructible
, is_nothrow_move_assignable
and is_nothrow_move_constructible
type
triats.
The circular_buffer
should
not be used for storing pointers to dynamically allocated objects. When a circular
buffer becomes full, further insertion will overwrite the stored pointers -
resulting in a memory leak. One recommend
alternative is the use of smart pointers, for example Boost
Smart pointers.
Caution | |
---|---|
Any container of |
Tip | |
---|---|
Never create a circular buffer of |
While internals of a circular_buffer
are circular, iterators are not. Iterators
of a circular_buffer
are
only valid for the range \[begin(), end()\]
,
so for example: iterators (begin() - 1)
and (end() +
1)
are
both invalid.
In order to help a programmer to avoid and find common bugs, the circular_buffer
can be enabled to
provide a kind of debug support.
When the debugging functionality is enabled, the circular_buffer
maintains a list of valid iterators. As soon as any element gets destroyed
all iterators pointing to this element are removed from this list and explicitly
invalidated (an invalidation flag is set). The debug support also consists
of many assertions (BOOST_ASSERT
macros) which ensure the circular_buffer
and its iterators are used in the correct manner at runtime. In case an invalid
iterator is used, the assertion will report an error. The connection of explicit
iterator invalidation and assertions makes a very robust debug technique which
catches most of the errors.
Moreover, the uninitialized memory allocated by circular_buffer
is filled with the value 0xcc
in
the debug mode. When debugging the code, this can help the programmer to recognize
the initialized memory from the uninitialized. For details refer the source
code circular_buffer/debug.hpp.
Caution | |
---|---|
Since the debugging code makes |
The debug support is disabled by default. To enable it, one has to define
BOOST_CB_ENABLE_DEBUG
macro
with the value of 1 while compiling the code using circular_buffer
.
The circular_buffer
is
compatible with the Boost.Interprocess
library used for interprocess communication. Considering that the circular_buffer's
debug support relies on 'raw' pointers (which is not permited by the Interprocess
library) the code has to compiled with debug support disabled (i.e. with BOOST_CB_ENABLE_DEBUG
macro not defined or
defined to 0). Not doing that will cause the compilation to fail.