Templated Circular Buffer Container
circular_buffer<T, Alloc>
Templated Circular Buffer Containercircular_buffer<T, Alloc> |
|
|
||
|
In general the term circular buffer refers to an area in memory which is used to store incoming data. When the buffer is filled, new data is written starting at the beginning of the buffer and overwriting the old. (Also see the Figure.)
The circular_buffer is a STL compliant container. It is a kind of sequence similar to std::list or std::deque. It supports random access iterators, constant
time insert and erase operations at the beginning or the end of the buffer and interoperability with
std algorithms. The circular_buffer is especially designed to provide fixed capacity
storage. When its capacity is exhausted, newly inserted elements will cause elements either at the beginning or
end of the buffer (depending on what insert operation is used) to be overwritten.
The circular_buffer only allocates memory when created, when the capacity is adjusted explicitly, or
as necessary to accommodate resizing or assign operations. On the other hand, there is also a circular_buffer_space_optimized available. It is an adaptor of the
circular_buffer which does not allocate memory at once when created, rather it allocates memory as
needed.
A brief example using the circular_buffer:
#include <boost/circular_buffer.hpp>
int main(int /*argc*/, char* /*argv*/[]) {
// Create a circular buffer with a capacity for 3 integers.
boost::circular_buffer<int> cb(3);
// Insert some elements into the buffer.
cb.push_back(1);
cb.push_back(2);
cb.push_back(3);
int a = cb[0]; // a == 1
int b = cb[1]; // b == 2
int c = cb[2]; // c == 3
// The buffer is full now, pushing subsequent
// elements will overwrite the front-most elements.
cb.push_back(4); // Overwrite 1 with 4.
cb.push_back(5); // Overwrite 2 with 5.
// The buffer now contains 3, 4 and 5.
a = cb[0]; // a == 3
b = cb[1]; // b == 4
c = cb[2]; // c == 5
// Elements can be popped from either the front or the back.
cb.pop_back(); // 5 is removed.
cb.pop_front(); // 3 is removed.
int d = cb[0]; // d == 4
return 0;
}
namespace boost {
template <class T, class Alloc>
class circular_buffer
{
public:
typedef typename Alloc::value_type value_type;
typedef typename Alloc::pointer pointer;
typedef typename Alloc::const_pointer const_pointer;
typedef typename Alloc::reference reference;
typedef typename Alloc::const_reference const_reference;
typedef typename Alloc::difference_type difference_type;
typedef typename Alloc::size_type size_type;
typedef Alloc allocator_type;
typedef implementation-defined const_iterator;
typedef implementation-defined iterator;
typedef boost::reverse_iterator<const_iterator> const_reverse_iterator;
typedef boost::reverse_iterator<iterator> reverse_iterator;
typedef std::pair<pointer, size_type> array_range;
typedef std::pair<const_pointer, size_type> const_array_range;
typedef size_type capacity_type;
explicit circular_buffer(const allocator_type& alloc = allocator_type());
explicit circular_buffer(capacity_type buffer_capacity, const allocator_type& alloc = allocator_type());
circular_buffer(size_type n, const_reference item, const allocator_type& alloc = allocator_type());
circular_buffer(capacity_type buffer_capacity, size_type n, const_reference item, const allocator_type& alloc = allocator_type());
circular_buffer(const circular_buffer<T, Alloc>& cb);
template <class InputIterator>
circular_buffer(InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
template <class InputIterator>
circular_buffer(capacity_type buffer_capacity, InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
~circular_buffer();
allocator_type get_allocator() const;
allocator_type& get_allocator();
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;
reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;
reference operator[](size_type index);
const_reference operator[](size_type index) const;
reference at(size_type index);
const_reference at(size_type index) const;
reference front();
reference back();
const_reference front() const;
const_reference back() const;
array_range array_one();
array_range array_two();
const_array_range array_one() const;
const_array_range array_two() const;
pointer linearize();
bool is_linearized() const;
void rotate(const_iterator new_begin);
size_type size() const;
size_type max_size() const;
bool empty() const;
bool full() const;
size_type reserve() const;
capacity_type capacity() const;
void set_capacity(capacity_type new_capacity);
void resize(size_type new_size, const_reference item = value_type());
void rset_capacity(capacity_type new_capacity);
void rresize(size_type new_size, const_reference item = value_type());
circular_buffer<T, Alloc>& operator=(const circular_buffer<T, Alloc>& cb);
void assign(size_type n, const_reference item);
void assign(capacity_type buffer_capacity, size_type n, const_reference item);
template <class InputIterator>
void assign(InputIterator first, InputIterator last);
template <class InputIterator>
void assign(capacity_type buffer_capacity, InputIterator first, InputIterator last);
void swap(circular_buffer<T, Alloc>& cb);
void push_back(const_reference item = value_type());
void push_front(const_reference item = value_type());
void pop_back();
void pop_front();
iterator insert(iterator pos, const_reference item = value_type());
void insert(iterator pos, size_type n, const_reference item);
template <class InputIterator>
void insert(iterator pos, InputIterator first, InputIterator last);
iterator rinsert(iterator pos, const_reference item = value_type());
void rinsert(iterator pos, size_type n, const_reference item);
template <class InputIterator>
void rinsert(iterator pos, InputIterator first, InputIterator last);
iterator erase(iterator pos);
iterator erase(iterator first, iterator last);
iterator rerase(iterator pos);
iterator rerase(iterator first, iterator last);
void erase_begin(size_type n);
void erase_end(size_type n);
void clear();
};
template <class T, class Alloc>
bool operator==(const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs);
template <class T, class Alloc>
bool operator<(const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs);
template <class T, class Alloc>
bool operator!=(const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs);
template <class T, class Alloc>
bool operator>(const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs);
template <class T, class Alloc>
bool operator<=(const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs);
template <class T, class Alloc>
bool operator>=(const circular_buffer<T, Alloc>& lhs, const circular_buffer<T, Alloc>& rhs);
template <class T, class Alloc>
void swap(circular_buffer<T, Alloc>& lhs, circular_buffer<T, Alloc>& rhs);
} // namespace boost
|
The basic motivation behind the circular_buffer was to create a container which would work
seamlessly with STL. Additionally, the design of the circular_buffer was guided by the following
principles:
circular_buffer_space_optimized is such an example of the adaptor.)
In order to achieve maximum efficiency, the circular_buffer stores its elements in a contiguous
region of memory, which then enables:
Possible applications of the circular_buffer include:
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 thread-safe. The thread-safety is
guarantied 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.)
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 with the case 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, in
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:
std container implements it this way.
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. 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_DISABLE_DEBUG // The Debug Support has to be disabled, otherwise the code produces a runtime error.
#include <boost/circular_buffer.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.
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 [1]. (Any
container of std::auto_ptr is considered particularly hazardous. [2] )
While internals of a circular_buffer are circular, iterators are not. Iterators of a
circular_buffer are only valid for the range [begin(), end()]. E.g. iterators
(begin() - 1) and (end() + 1) are invalid.
In order to help a programmer to avoid and find common bugs, the circular_buffer contains a kind of
debug support.
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. This can help the programmer when debugging the code to recognize the
initialized memory from the uninitialized. For details refer the source code.
The debug support is enabled only in the debug mode (when the NDEBUG is not defined). It can also be
explicitly disabled (only for circular_buffer) by defining BOOST_CB_DISABLE_DEBUG
macro.
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 -DBOOST_CB_DISABLE_DEBUG or -DNDEBUG (which disables the
Debug Support). Not doing that will cause the compilation to fail.
The following example includes various usage of the circular_buffer.
#include <boost/circular_buffer.hpp>
#include <numeric>
#include <assert.h>
int main(int /*argc*/, char* /*argv*/[])
{
// create a circular buffer of capacity 3
boost::circular_buffer<int> cb(3);
// insert some elements into the circular buffer
cb.push_back(1);
cb.push_back(2);
// assertions
assert(cb[0] == 1);
assert(cb[1] == 2);
assert(!cb.full());
assert(cb.size() == 2);
assert(cb.capacity() == 3);
// insert some other elements
cb.push_back(3);
cb.push_back(4);
// evaluate the sum
int sum = std::accumulate(cb.begin(), cb.end(), 0);
// assertions
assert(cb[0] == 2);
assert(cb[1] == 3);
assert(cb[2] == 4);
assert(*cb.begin() == 2);
assert(cb.front() == 2);
assert(cb.back() == 4);
assert(sum == 9);
assert(cb.full());
assert(cb.size() == 3);
assert(cb.capacity() == 3);
return 0;
}
The circular_buffer has a capacity of three int. Therefore, the size of the buffer will
not exceed three. The std::accumulate
algorithm evaluates the sum of the stored elements. The semantics of the circular_buffer can be
inferred from the assertions.
The bounded buffer is normally used in a producer-consumer mode when producer threads produce items and store them in the container and consumer threads remove these items and process them. The bounded buffer has to guarantee that producers do not insert items into the container when the container is full, that consumers do not try to remove items when the container is empty, and that each produced item is consumed by exactly one consumer.
The example below shows how the circular_buffer can be utilized as an underlying container of the
bounded buffer.
#include <boost/circular_buffer.hpp>
#include <boost/thread/mutex.hpp>
#include <boost/thread/condition.hpp>
#include <boost/thread/thread.hpp>
#include <boost/call_traits.hpp>
#include <boost/progress.hpp>
#include <boost/bind.hpp>
template <class T>
class bounded_buffer {
public:
typedef boost::circular_buffer<T> container_type;
typedef typename container_type::size_type size_type;
typedef typename container_type::value_type value_type;
typedef typename boost::call_traits<value_type>::param_type param_type;
explicit bounded_buffer(size_type capacity) : m_unread(0), m_container(capacity) {}
void push_front(boost::call_traits<value_type>::param_type item) {
// param_type represents the "best" way to pass a parameter of type value_type to a method
boost::mutex::scoped_lock lock(m_mutex);
m_not_full.wait(lock, boost::bind(&bounded_buffer<value_type>::is_not_full, this));
m_container.push_front(item);
++m_unread;
lock.unlock();
m_not_empty.notify_one();
}
void pop_back(value_type* pItem) {
boost::mutex::scoped_lock lock(m_mutex);
m_not_empty.wait(lock, boost::bind(&bounded_buffer<value_type>::is_not_empty, this));
*pItem = m_container[--m_unread];
lock.unlock();
m_not_full.notify_one();
}
private:
bounded_buffer(const bounded_buffer&); // Disabled copy constructor
bounded_buffer& operator = (const bounded_buffer&); // Disabled assign operator
bool is_not_empty() const { return m_unread > 0; }
bool is_not_full() const { return m_unread < m_container.capacity(); }
size_type m_unread;
container_type m_container;
boost::mutex m_mutex;
boost::condition m_not_empty;
boost::condition m_not_full;
};
The bounded_buffer relies on Boost Threads and Boost Bind libraries and Boost call_traits
utility.
The push_front() method is called by the producer thread in order to insert a new item into the
buffer. The method locks the mutex and waits until there is a space for the new item. (The mutex is unlocked
during the waiting stage and has to be regained when the condition is met.) If there is a space in the buffer
available, the execution continues and the method inserts the item at the end of the
circular_buffer. Then it increments the number of unread items and unlocks the mutex (in case an
exception is thrown before the mutex is unlocked, the mutex is unlocked automatically by the destructor of the
scoped_lock). At last the method notifies one of the consumer threads waiting for a new item to be
inserted into the buffer.
The pop_back() method is called by the consumer thread in order to read the next item from the
buffer. The method locks the mutex and waits until there is an unread item in the buffer. If there is at least
one unread item, the method decrements the number of unread items and reads the next item from the
circular_buffer. Then it unlocks the mutex and notifies one of the producer threads waiting for the
buffer to free a space for the next item.
The pop_back() method does not remove the item but the item is left in the
circular_buffer which then replaces it with a new one (inserted by a producer) when the
circular_buffer is full. This technique is more effective than removing the item explicitly by
calling the pop_back() method of the circular_buffer. This claim is based on the
assumption that an assignment (replacement) of a new item into an old one is more effective than a destruction
(removal) of an old item and a consequent inplace construction (insertion) of a new item.
For comparison of bounded buffers based on different containers compile and run bounded_buffer_comparison.cpp. The test should reveal the bounded
buffer based on the circular_buffer is most effective closely followed by the
std::deque based bounded buffer. (In reality the result may differ sometimes because the test is
always affected by external factors such as immediate CPU load.)
The circular_buffer is defined in the file boost/circular_buffer.hpp. There is also a forward declaration
for the circular_buffer in the header file boost/circular_buffer_fwd.hpp.
Random Access Container, Front Insertion Sequence and Back Insertion Sequence.
| Parameter | Description | Default |
|---|---|---|
T
|
The type of the elements stored in the circular_buffer.
|
|
Alloc
|
The allocator type used for all internal memory management.
|
std::allocator<T>
|
| Type | Description |
|---|---|
value_type
|
The type of elements stored in the circular_buffer.
|
pointer
|
A pointer to an element. |
const_pointer
|
A const pointer to the element. |
reference
|
A reference to an element. |
const_reference
|
A const reference to an element. |
difference_type
|
The distance type. (A signed integral type used to represent the distance between two iterators.) |
size_type
|
The size type. (An unsigned integral type that can represent any non-negative value of the container's distance type.) |
allocator_type
|
The type of an allocator used in the circular_buffer.
|
const_iterator
|
A const (random access) iterator used to iterate through the circular_buffer.
|
iterator
|
A (random access) iterator used to iterate through the circular_buffer.
|
const_reverse_iterator
|
A const iterator used to iterate backwards through a circular_buffer.
|
reverse_iterator
|
An iterator used to iterate backwards through a circular_buffer.
|
array_range
|
An array range. (A typedef for the std::pair where its first element is a pointer to
a beginning of an array and its second element represents a size of the array.)
|
const_array_range
|
A range of a const array. (A typedef for the std::pair where its first element is a pointer to
a beginning of a const array and its second element represents a size of the const array.)
|
capacity_type
|
The capacity type. (Same as size_type - defined for consistency with the circular_buffer_space_optimized.)
|
explicit
circular_buffer(const allocator_type& alloc =
allocator_type());Create an empty circular_buffer with zero capacity.
|
explicit
circular_buffer(capacity_type buffer_capacity,
const allocator_type&
alloc = allocator_type());Create an empty circular_buffer with the specified capacity.
|
circular_buffer(size_type n, const_reference item, const
allocator_type& alloc =
allocator_type());Create a full circular_buffer with the specified capacity and filled with n
copies of item.
|
circular_buffer(capacity_type buffer_capacity,
size_type n, const_reference item, const
allocator_type& alloc =
allocator_type());Create a circular_buffer with the specified capacity and filled with n copies of
item.
|
circular_buffer(const
circular_buffer<T,Alloc>& cb);The copy constructor.
Creates a copy of the specified
|
template <class
InputIterator>Create a full circular_buffer filled with a copy of the range.
|
template <class
InputIterator>Create a circular_buffer with the specified capacity and filled with a copy of the range.
|
~circular_buffer();The destructor.
Destroys the
|
allocator_type get_allocator()
const;Get the allocator.
|
allocator_type&
get_allocator();Get the allocator reference.
|
iterator begin();Get the iterator pointing to the beginning of the circular_buffer.
|
iterator end();Get the iterator pointing to the end of the circular_buffer.
|
const_iterator begin()
const;Get the const iterator pointing to the beginning of the circular_buffer.
|
const_iterator end()
const;Get the const iterator pointing to the end of the circular_buffer.
|
reverse_iterator
rbegin();Get the iterator pointing to the beginning of the "reversed" circular_buffer.
|
reverse_iterator
rend();Get the iterator pointing to the end of the "reversed" circular_buffer.
|
const_reverse_iterator rbegin()
const;Get the const iterator pointing to the beginning of the "reversed" circular_buffer.
|
const_reverse_iterator rend()
const;Get the const iterator pointing to the end of the "reversed" circular_buffer.
|
reference operator[](size_type index);Get the element at the index position.
|
const_reference operator[](size_type index)
const;Get the element at the index position.
|
reference at(size_type index);Get the element at the index position.
|
const_reference at(size_type index)
const;Get the element at the index position.
|
reference front();Get the first element.
|
reference back();Get the last element.
|
const_reference front()
const;Get the first element.
|
const_reference back()
const;Get the last element.
|
array_range
array_one();Get the first continuous array of the internal buffer.
This method in combination with
|
array_range
array_two();Get the second continuous array of the internal buffer.
This method in combination with
|
const_array_range array_one()
const;Get the first continuous array of the internal buffer.
This method in combination with
|
const_array_range array_two()
const;Get the second continuous array of the internal buffer.
This method in combination with
|
pointer linearize();Linearize the internal buffer into a continuous array. This method can be useful when passing the stored data into a legacy C API as an array.
|
bool is_linearized()
const;Is the circular_buffer linearized?
|
void rotate(const_iterator
new_begin);Rotate elements in the circular_buffer.
A more effective implementation of
|
size_type size()
const;Get the number of elements currently stored in the circular_buffer.
|
size_type max_size()
const;Get the largest possible size or capacity of the circular_buffer. (It depends on allocator's
max_size()).
|
bool empty()
const;Is the circular_buffer empty?
|
bool full()
const;Is the circular_buffer full?
|
size_type reserve()
const;Get the maximum number of elements which can be inserted into the circular_buffer without
overwriting any of already stored elements.
|
capacity_type capacity()
const;Get the capacity of the circular_buffer.
|
void set_capacity(capacity_type
new_capacity);Change the capacity of the circular_buffer.
|
void resize(size_type new_size, const_reference item =
value_type());Change the size of the circular_buffer.
|
void rset_capacity(capacity_type
new_capacity);Change the capacity of the circular_buffer.
|
void rresize(size_type new_size, const_reference item =
value_type());Change the size of the circular_buffer.
|
circular_buffer<T,Alloc>&
operator=(const circular_buffer<T,Alloc>& cb);The assign operator.
Makes this
|
void assign(size_type n, const_reference
item);Assign n items into the circular_buffer.
The content of the
|
void assign(capacity_type buffer_capacity,
size_type n, const_reference
item);Assign n items into the circular_buffer specifying the capacity.
The capacity of the
|
template <class
InputIterator>Assign a copy of the range into the circular_buffer.
The content of the
|
template <class
InputIterator>Assign a copy of the range into the circular_buffer specifying the capacity.
The capacity of the
|
void
swap(circular_buffer<T,Alloc>& cb);Swap the contents of two circular_buffers.
|
void push_back(const_reference item =
value_type());Insert a new element at the end of the circular_buffer.
|
void push_front(const_reference item =
value_type());Insert a new element at the beginning of the circular_buffer.
|
void
pop_back();Remove the last element from the circular_buffer.
|
void
pop_front();Remove the first element from the circular_buffer.
|
iterator insert(iterator pos, const_reference item =
value_type());Insert an element at the specified position.
|
void insert(iterator pos, size_type n, const_reference
item);Insert n copies of the item at the specified position.
|
template <class
InputIterator>Insert the range [first, last) at the specified position.
|
iterator rinsert(iterator pos, const_reference item =
value_type());Insert an element before the specified position.
|
void rinsert(iterator pos, size_type n, const_reference
item);Insert n copies of the item before the specified position.
|
template <class
InputIterator>Insert the range [first, last) before the specified position.
|
iterator erase(iterator pos);Remove an element at the specified position.
|
iterator erase(iterator first, iterator last);Erase the range [first, last).
|
iterator rerase(iterator pos);Remove an element at the specified position.
|
iterator rerase(iterator first, iterator last);Erase the range [first, last).
|
void erase_begin(size_type n);Remove first n elements (with constant complexity for scalar types).
|
void erase_end(size_type n);Remove last n elements (with constant complexity for scalar types).
|
void
clear();Remove all stored elements from the circular_buffer.
|
template <class T, class Alloc>Compare two circular_buffers element-by-element to determine if they are equal.
|
template <class T, class Alloc>Compare two circular_buffers element-by-element to determine if the left one is lesser than
the right one.
|
template <class T, class Alloc>Compare two circular_buffers element-by-element to determine if they are non-equal.
|
template <class T, class Alloc>Compare two circular_buffers element-by-element to determine if the left one is greater than
the right one.
|
template <class T, class Alloc>Compare two circular_buffers element-by-element to determine if the left one is lesser or
equal to the right one.
|
template <class T, class Alloc>Compare two circular_buffers element-by-element to determine if the left one is greater or
equal to the right one.
|
template <class T, class Alloc>Swap the contents of two circular_buffers.
|
A good implementation of smart pointers is included in Boost.
Never create a circular buffer of std::auto_ptr. Refer to Scott Meyers ' excellent book Effective STL for a detailed discussion.
(Meyers S., Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library.
Addison-Wesley, 2001.)
boost::circular_buffer_space_optimized, std::vector, std::list, std::deque
The circular_buffer has a short history. Its first version was a std::deque adaptor.
This container was not very effective because of many reallocations when inserting/removing an element. Thomas
Wenish did a review of this version and motivated me to create a circular buffer which allocates memory at once
when created.
The second version adapted std::vector but it has been abandoned soon because of limited control
over iterator invalidation.
The current version is a full-fledged STL compliant container. Pavel Vozenilek did a thorough review of this version and came with many good ideas and improvements. Also, I would like to thank Howard Hinnant, Nigel Stewart and everyone who participated at the formal review for valuable comments and ideas.
erase_begin(size_type) and erase_end(size_type) with constant
complexity for such types of stored elements which do not need an explicit destruction e.g. int
or double.
clear() method and the destructor so their
complexity is now constant for such types of stored elements which do not require an explicit destruction
(the complexity for other types remains linear).
is_linearized() and rotate(const_iterator).
circular_buffer.hpp #includes absolute.circular_buffer(const allocator_type&) constructor. Since this
version the constructor does not allocate any memory and both capacity and size are set to zero.
std::bad_alloc.Copyright © 2003-2008 Jan Gaspar
Use, modification, and distribution is subject to the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)