Nugget
|
#include <ring_buffer.h>
Public Types | |
typedef ring_buffer< T, Container, Allocator > | this_type |
typedef Container | container_type |
typedef Allocator | allocator_type |
typedef Container::value_type | value_type |
typedef Container::reference | reference |
typedef Container::const_reference | const_reference |
typedef Container::size_type | size_type |
typedef Container::difference_type | difference_type |
typedef Container::iterator | container_iterator |
typedef Container::const_iterator | container_const_iterator |
typedef ring_buffer_iterator< T, T *, T &, Container > | iterator |
typedef ring_buffer_iterator< T, const T *, const T &, Container > | const_iterator |
typedef eastl::reverse_iterator< iterator > | reverse_iterator |
typedef eastl::reverse_iterator< const_iterator > | const_reverse_iterator |
Public Member Functions | |
ring_buffer (size_type cap=0) | |
ring_buffer (size_type cap, const allocator_type &allocator) | |
ring_buffer (const Container &x) | |
ring_buffer (const allocator_type &allocator) | |
ring_buffer (const this_type &x) | |
ring_buffer (this_type &&x) | |
ring_buffer (this_type &&x, const allocator_type &allocator) | |
ring_buffer (std::initializer_list< value_type > ilist, const allocator_type &allocator=EASTL_RING_BUFFER_DEFAULT_ALLOCATOR) | |
this_type & | operator= (const this_type &x) |
this_type & | operator= (std::initializer_list< value_type > ilist) |
this_type & | operator= (this_type &&x) |
template<typename InputIterator > | |
void | assign (InputIterator first, InputIterator last) |
void | swap (this_type &x) |
iterator | begin () EA_NOEXCEPT |
const_iterator | begin () const EA_NOEXCEPT |
const_iterator | cbegin () const EA_NOEXCEPT |
iterator | end () EA_NOEXCEPT |
const_iterator | end () const EA_NOEXCEPT |
const_iterator | cend () const EA_NOEXCEPT |
reverse_iterator | rbegin () EA_NOEXCEPT |
const_reverse_iterator | rbegin () const EA_NOEXCEPT |
const_reverse_iterator | crbegin () const EA_NOEXCEPT |
reverse_iterator | rend () EA_NOEXCEPT |
const_reverse_iterator | rend () const EA_NOEXCEPT |
const_reverse_iterator | crend () const EA_NOEXCEPT |
bool | empty () const EA_NOEXCEPT |
bool | full () const EA_NOEXCEPT |
size_type | size () const EA_NOEXCEPT |
size_type | capacity () const EA_NOEXCEPT |
void | resize (size_type n) |
void | set_capacity (size_type n) |
void | reserve (size_type n) |
reference | front () |
const_reference | front () const |
reference | back () |
const_reference | back () const |
void | push_back (const value_type &value) |
reference | push_back () |
void | push_front (const value_type &value) |
reference | push_front () |
void | pop_back () |
void | pop_front () |
reference | operator[] (size_type n) |
const_reference | operator[] (size_type n) const |
iterator | insert (const_iterator position, const value_type &value) |
void | insert (const_iterator position, size_type n, const value_type &value) |
void | insert (const_iterator position, std::initializer_list< value_type > ilist) |
template<typename InputIterator > | |
void | insert (const_iterator position, InputIterator first, InputIterator last) |
iterator | erase (const_iterator position) |
iterator | erase (const_iterator first, const_iterator last) |
reverse_iterator | erase (const_reverse_iterator position) |
reverse_iterator | erase (const_reverse_iterator first, const_reverse_iterator last) |
void | clear () |
container_type & | get_container () |
const container_type & | get_container () const |
bool | validate () const |
int | validate_iterator (const_iterator i) const |
Public Attributes | |
Container | c |
Protected Attributes | |
container_iterator | mBegin |
container_iterator | mEnd |
size_type | mSize |
Implements a ring buffer via a given container type, which would typically be a vector or array, though any container which supports bidirectional iteration would work.
A ring buffer is a FIFO (first-in, first-out) container which acts much like a queue. The difference is that a ring buffer is implemented via chasing pointers around a container and moving the read and write positions forward (and possibly wrapping around) as the container is read and written via pop_front and push_back.
The benefit of a ring buffer is that memory allocations don't occur and new elements are neither added nor removed from the container. Elements in the container are simply assigned values in circles around the container.
ring_buffer is different from other containers – including adapter containers – in how iteration is done. Iteration of a ring buffer starts at the current begin position, proceeds to the end of the underlying container, and continues at the begin of the underlying container until the ring buffer's current end position. Thus a ring_buffer does indeed have a begin and an end, though the values of begin and end chase each other around the container. An empty ring_buffer is one in which end == begin, and a full ring_buffer is one in which end + 1 == begin.
Example of a ring buffer layout, where + indicates queued items: ++++++++++-----------------------------—+++++++++ ^ ^ end begin
^ begin / end
Full ring buffer. Note that one item is necessarily unused; it is analagous to a '\0' at the end of a C string: +++++++++++++++++++++++++++++++++++++++++-+++++++++ ^^ end begin
A push_back operation on a ring buffer assigns the new value to end.
If there is no more space in the buffer, this will result in begin being overwritten and the begin position being moved foward one position. The user can use the full() function to detect this condition. Note that elements in a ring buffer are not created or destroyed as their are added and removed; they are merely assigned. Only on container construction and destruction are any elements created and destroyed.
The ring buffer can be used in either direction. By this we mean that you can use push_back to add items and pop_front to remove them; or you can use push_front to add items and pop_back to remove them. You aren't limited to these operations; you can push or pop from either side arbitrarily and you can insert or erase anywhere in the container.
The ring buffer requires the user to specify a Container type, which by default is vector. However, any container with bidirectional iterators will work, such as list, deque, string or any of the fixed_* versions of these containers, such as fixed_string. Since ring buffer works via copying elements instead of allocating and freeing nodes, inserting in the middle of a ring buffer based on list (instead of vector) is no more efficient.
To use the ring buffer, its container must be resized to the desired ring buffer size. Changing the size of a ring buffer may cause ring buffer iterators to invalidate.
An alternative to using a ring buffer is to use a list with a user-created node pool and custom allocator. There are various tradeoffs that result from this.
Example usage: ring_buffer< int, list<int> > rb(100); rb.push_back(1);
Example usage: // Example of creating an on-screen debug log that shows 16 // strings at a time and scrolls older strings away.
// Create ring buffer of 16 strings. ring_buffer< string, vector<string> > debugLogText(16);
// Reserve 128 chars for each line. This can make it so that no // runtime memory allocations occur. for(vector<string>::iterator it = debugLogText.get_container().begin(), itEnd = debugLogText.get_container().end(); it != itEnd; ++it) { (*it).reserve(128); }
// Add a new string, using push_front() and front() instead of // push_front(str) in order to avoid creating a temporary str. debugLogText.push_front(); debugLogText.front() = "Player fired weapon";
ring_buffer< T, Container, Allocator >::reference eastl::ring_buffer< T, Container, Allocator >::push_back |
A push_back operation on a ring buffer assigns the new value to end.
If there is no more space in the buffer, this will result in begin being overwritten and the begin position being moved foward one position.
void eastl::ring_buffer< T, Container, Allocator >::push_back | ( | const value_type & | value | ) |
A push_back operation on a ring buffer assigns the new value to end.
If there is no more space in the buffer, this will result in begin being overwritten and the begin position being moved foward one position.