|
|
Boost : |
From: Jan Gaspar (jga_at_[hidden])
Date: 2003-04-10 10:06:35
Hi all!
I have refactored my implelentation of the cyclic buffer. Its underlaying container is now vector
(previosly it was deque). There is still one problem - iterator invalidation. If you add or remove an
element from the end of the buffer, the iterators becomes invalidated.
Jan
-- Jan Gaspar | jga_at_[hidden] Whitestein Technologies | www.whitestein.com Panenska 28 | SK-81103 Bratislava | Slovak Republic Tel +421(2)5930-0721 | Fax +421(2)5443-5512
/*
Copyright (c) 2003
Jan Gaspar, Whitestein Technologies
This material is provided "as is", with absolutely no warranty expressed
or implied. Any use is at your own risk.
Permission to use or copy this software for any purpose is hereby granted
without fee, provided the above notices are retained on all copies.
Permission to modify the code and to distribute modified code is granted,
provided the above notices are retained, and a notice that the code was
modified is included with the above copyright notice.
*/
/*!
\file cyclic_buffer.hpp
This file contains an implementation of the cyclic buffer.
*/
#ifndef BOOST_CYCLIC_BUFFER_HPP
#define BOOST_CYCLIC_BUFFER_HPP
#include <boost/config.hpp>
#include <boost/assert.hpp>
#include <boost/concept_check.hpp>
#include <vector>
#include <algorithm>
namespace boost {
// Helper defines
#define CB_CONTAINER std::vector
#if !defined(BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS)
#define CB_DEFAULT_ALLOCATOR(T) typename CB_CONTAINER<T>::allocator_type
#else // #if !defined(BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS)
#define CB_DEFAULT_ALLOCATOR(T) CB_CONTAINER<T>::allocator_type
#endif // #if !defined(BOOST_NO_DEPENDENT_TYPES_IN_TEMPLATE_VALUE_PARAMETERS)
/*!
\struct cb_iterator
\brief An iterator for the cyclic buffer.
\param Container Cyclic buffer's undelying container type.
\param Ref Reference type to the element stored in the container.
\param Ptr Pointer type to the element stored in the container.
\author Jan Gaspar, <A HREF="mailto:jga_at_[hidden]">jga_at_[hidden]</A>
\version 2.0
\date 2003
*/
template <class Container, class Ref, class Ptr>
struct cb_iterator {
// Basic types
//! Iterator category.
typedef std::random_access_iterator_tag iterator_category;
//! The type of the element stored in the container.
typedef typename Container::value_type value_type;
//! Pointer to the element.
typedef Ptr pointer;
//! Reference to the element.
typedef Ref reference;
//! An unsigned integral type.
typedef typename Container::size_type size_type;
//! A signed integral type.
typedef typename Container::difference_type difference_type;
// Helper types
//! Non-const iterator
typedef cb_iterator<Container, value_type&, value_type*> NonconstSelf;
//! Container iterator.
typedef typename Container::iterator InternalIterator;
// Member variables
//! A container where the iterator points to.
Container* m_buffer;
//! An internal iterator.
InternalIterator m_iterator;
//! An iterator pointing to the "virtual begining" of the cyclic buffer.
const InternalIterator* m_begin;
//! Does the iterator point to the end of the container ?
bool m_isEnd;
// Construction & assignment
// Default copy constructor.
//! Default constructor
cb_iterator() : m_buffer(0), m_begin(0), m_isEnd(false) {}
//! Copy constructor (used for converting from a non-const to a const iterator).
cb_iterator(const NonconstSelf& it)
: m_buffer(it.m_buffer), m_iterator(it.m_iterator), m_begin(it.m_begin), m_isEnd(it.m_isEnd) {}
//! Internal constructor.
/*!
This constructor is not intended to be used directly.
*/
cb_iterator(const Container* buffer, const InternalIterator& it, const InternalIterator& begin, bool isEnd)
: m_buffer(const_cast<Container*>(buffer)), m_iterator(it), m_begin(&begin), m_isEnd(isEnd) {}
// Default assign operator.
// Random access iterator methods
//! Dereferencing operator.
reference operator * () const { return *m_iterator; }
//! Dereferencing operator.
pointer operator -> () const { return &(operator*()); }
//! Difference operator.
difference_type operator - (const cb_iterator& it) const {
if (it < *this && it.m_iterator >= m_iterator)
return (m_iterator - m_buffer->begin()) + (m_buffer->end() - it.m_iterator);
if (it > *this && it.m_iterator <= m_iterator)
return (m_buffer->begin() - it.m_iterator) + (m_iterator - m_buffer->end());
return m_iterator - it.m_iterator;
}
//! Increment operator (prefix).
cb_iterator& operator ++ () {
if (++m_iterator == m_buffer->end())
m_iterator = m_buffer->begin();
m_isEnd = (m_iterator == *m_begin);
return *this;
}
//! Increment operator (postfix).
cb_iterator operator ++ (int) {
cb_iterator tmp = *this;
++*this;
return tmp;
}
//! Decrement operator (prefix).
cb_iterator& operator -- () {
if (m_iterator == m_buffer->begin())
m_iterator = m_buffer->end();
--m_iterator;
m_isEnd = false;
return *this;
}
//! Decrement operator (postfix).
cb_iterator operator -- (int) {
cb_iterator tmp = *this;
--*this;
return tmp;
}
//! Iterator addition.
cb_iterator& operator += (difference_type n) {
if (n > 0) {
n %= m_buffer->size();
difference_type diff = m_buffer->end() - m_iterator;
if (n >= diff)
m_iterator = m_buffer->begin() + n - diff;
else
m_iterator += n;
m_isEnd = (m_iterator == *m_begin);
}
else if (n < 0)
*this -= -n;
return *this;
}
//! Iterator addition.
cb_iterator operator + (difference_type n) const {
cb_iterator tmp = *this;
return tmp += n;
}
//! Iterator subtraction.
cb_iterator& operator -= (difference_type n) {
if (n > 0) {
n %= m_buffer->size();
difference_type diff = m_iterator - m_buffer->begin();
if (n > diff)
m_iterator = m_buffer->end() - n + diff;
else
m_iterator -= n;
m_isEnd = false;
}
else if (n < 0)
*this += -n;
return *this;
}
//! Iterator subtraction.
cb_iterator operator - (difference_type n) const {
cb_iterator tmp = *this;
return tmp -= n;
}
//! Element access operator.
reference operator [] (difference_type n) const { return *(*this + n); }
// Equality & comparison
//! Equality.
bool operator == (const cb_iterator& it) const {
return m_iterator == it.m_iterator
&& m_isEnd == it.m_isEnd;
}
//! Inequality.
bool operator != (const cb_iterator& it) const { return !(*this == it); }
//! Less.
bool operator < (const cb_iterator& it) const {
switch (sign(m_iterator - *m_begin)) {
case -1:
switch (sign(it.m_iterator - *m_begin)) {
case -1: return m_iterator < it.m_iterator;
case 0: return it.m_isEnd;
case 1: return false;
default:
BOOST_ASSERT(!"cb_iterator::operator < ");
}
break;
case 0:
switch (sign(it.m_iterator - *m_begin)) {
case -1: return !m_isEnd;
case 0: return !m_isEnd && it.m_isEnd;
case 1: return !m_isEnd;
default:
BOOST_ASSERT(!"cb_iterator::operator < ");
}
break;
case 1:
switch (sign(it.m_iterator - *m_begin)) {
case -1: return true;
case 0: return it.m_isEnd;
case 1: return m_iterator < it.m_iterator;
default:
BOOST_ASSERT(!"cb_iterator::operator < ");
}
break;
default:
BOOST_ASSERT(!"cb_iterator::operator < ");
}
return false;
}
//! Greater.
bool operator > (const cb_iterator& it) const { return it < *this; }
//! Less or equal.
bool operator <= (const cb_iterator& it) const { return !(it < *this); }
//! Greater or equal.
bool operator >= (const cb_iterator& it) const { return !(*this < it); }
// Helpers
//! Sign.
/*!
\return 1 if n is positive
\return 0 if n is zero
\return -1 if n is negative
*/
static difference_type sign(difference_type n) { return n < 0 ? -1 : (n > 0 ? 1 : 0); }
};
template <class Container, class Ref, class Ptr>
inline cb_iterator<Container, Ref, Ptr>
operator + (typename Container::difference_type n, const cb_iterator<Container, Ref, Ptr>& it) {
return it + n;
}
#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
template <class Container, class Ref, class Ptr>
inline std::random_access_iterator_tag
iterator_category(const cb_iterator<Container, Ref, Ptr>&) {
return std::random_access_iterator_tag();
}
template <class Container, class Ref, class Ptr>
inline typename Container::value_type*
value_type(const cb_iterator<Container, Ref, Ptr>&) { return 0; }
template <class Container, class Ref, class Ptr>
inline typename Container::difference_type*
distance_type(const cb_iterator<Container, Ref, Ptr>&) { return 0; }
#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
/*!
\class cyclic_buffer
\brief Cyclic buffer - a STL compliant container.
\param T Type of the elements stored in the cyclic buffer.
\param Alloc An Allocator.
\author Jan Gaspar, <A HREF="mailto:jga_at_[hidden]">jga_at_[hidden]</A>
\version 2.0
\date 2003
For more information how to use the cyclic buffer see
<A HREF="../cyclic_buffer_howto.html">Cyclic Buffer HOWTO</A>.
*/
template <class T, class Alloc = CB_DEFAULT_ALLOCATOR(T)>
class cyclic_buffer {
// Requirements
BOOST_CLASS_REQUIRE(T, boost, AssignableConcept);
private:
// Internal types
//! Internal container type.
typedef CB_CONTAINER<T, Alloc> Container;
//! Container iterator.
typedef typename Container::iterator InternalIterator;
public:
// Basic types
//! The type of the element stored in the cyclic buffer.
typedef typename Container::value_type value_type;
//! Pointer to the element.
typedef typename Container::value_type* pointer;
//! Const pointer to the element.
typedef typename Container::value_type const* const_pointer;
//! Reference to the element.
typedef typename Container::reference reference;
//! Const reference to the element.
typedef typename Container::const_reference const_reference;
//! An unsigned integral type.
typedef typename Container::size_type size_type;
//! A signed integral type.
typedef typename Container::difference_type difference_type;
//! The type of an allocator used in the cyclic buffer.
typedef typename Container::allocator_type allocator_type;
//! Get the allocator.
/*!
\return Allocator
*/
allocator_type get_allocator() const { return m_buffer.get_allocator(); }
public:
// Iterators
//! Const iterator used to iterate through a cyclic buffer.
typedef cb_iterator<Container, const T&, const T*> const_iterator;
//! Iterator used to iterate through a cyclic buffer.
typedef cb_iterator<Container, T&, T*> iterator;
#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
//! Const iterator used to iterate backwards through a cyclic buffer.
typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
//! Iterator used to iterate backwards through a cyclic buffer.
typedef std::reverse_iterator<iterator> reverse_iterator;
#else // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
//! Const iterator used to iterate backwards through a cyclic buffer.
typedef std::reverse_iterator<const_iterator, value_type, const_reference, difference_type> const_reverse_iterator;
//! Iterator used to iterate backwards through a cyclic buffer.
typedef std::reverse_iterator<iterator, value_type, reference, difference_type> reverse_iterator;
#endif // BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION
private:
// Member variables
//! The internal buffer used for storing elements in the cyclic buffer.
Container m_buffer;
//! "The beginning" of the cyclic buffer.
InternalIterator m_begin;
//! Capacity
size_type m_capacity;
public:
// Basic accessors
//! Returns an iterator pointing to the beginning of the cyclic buffer.
iterator begin() { return iterator(&m_buffer, m_begin, m_begin, m_buffer.empty()); }
//! Returns an iterator pointing to the end of the cyclic buffer.
iterator end() { return iterator(&m_buffer, m_begin, m_begin, true); }
//! Returns a const iterator pointing to the beginning of the cyclic buffer.
const_iterator begin() const { return const_iterator(&m_buffer, m_begin, m_begin, m_buffer.empty()); }
//! Returns a const iterator pointing to the end of the cyclic buffer.
const_iterator end() const { return const_iterator(&m_buffer, m_begin, m_begin, true); }
//! Returns a reverse iterator pointing to the beginning of the reversed cyclic buffer.
reverse_iterator rbegin() { return reverse_iterator(end()); }
//! Returns a reverse iterator pointing to the end of the reversed cyclic buffer.
reverse_iterator rend() { return reverse_iterator(begin()); }
//! Returns a const reverse iterator pointing to the beginning of the reversed cyclic buffer.
const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
//! Returns a const reverse iterator pointing to the end of the reversed cyclic buffer.
const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
//! Returns an element at the index position.
reference operator [] (difference_type index) { return *(begin() + index); }
//! Returns an element at the index position.
const_reference operator [] (difference_type index) const { return *(begin() + index); }
#ifndef BOOST_NO_EXCEPTIONS
//! Returns an element at the index position.
/*!
Throws an exception when the position is invalid.
*/
reference at(size_type index) {
size_type diff = m_buffer.end() - m_begin;
return m_buffer.at(index > diff ? index - diff : m_begin - m_buffer.begin() + index);
}
//! Returns an element at the index position.
/*!
Throws an exception when the position is invalid.
*/
const_reference at(size_type index) const {
size_type diff = m_buffer.end() - m_begin;
return m_buffer.at(index > diff ? index - diff : m_begin - m_buffer.begin() + index);
}
#endif // BOOST_NO_EXCEPTIONS
//! Returns the first element.
reference front() { return *begin(); }
//! Returns the last element.
reference back() { return *--end(); }
//! Returns the first element.
const_reference front() const { return *begin(); }
//! Returns the last element.
const_reference back() const { return *--end(); }
//! Returns the number of elements stored in the cyclic buffer.
size_type size() const { return m_buffer.size(); }
//! Returns the largest possible capacity of the cyclic buffer.
size_type max_size() const { return m_buffer.max_size(); }
//! Returns the size of the cyclic buffer.
size_type capacity() const { return m_capacity; }
//! True if there are no elements stored in the cyclic buffer.
bool empty() const { return m_buffer.empty(); }
//! True if the number of elements stored in the cyclic buffer equals capacity of the cyclic buffer.
bool full() const { return size() == capacity(); }
//! Changes the capacity of the cyclic buffer.
/*!
If the current number of elements stored in the cyclic
buffer is bigger than the desired new capacity then the
first ["current number of elements" - "new capacity"]
elements will be removed.
*/
void change_capacity(size_type newCapacity) {
if (newCapacity == capacity())
return;
if (newCapacity > capacity()) {
size_type diff = m_begin - m_buffer.begin();
m_buffer.reserve(newCapacity);
m_begin = m_buffer.begin() + diff;
}
else {
Container tmp(get_allocator());
tmp.reserve(newCapacity);
std::copy(newCapacity < size() ? begin() + (size() - newCapacity) : begin(),
end(),
std::back_inserter(tmp));
m_buffer.swap(tmp);
m_begin = m_buffer.begin();
}
m_capacity = newCapacity;
}
//! Changes the size of the cyclic buffer.
/*!
If the new size is greater than the current size, the rest
of the cyclic buffer is filled with copies of <TT>item</TT>.
The resulting size will not be greater than the capacity.
(If you want to get the size greater than current capacity
you have to <TT>change_capacity</TT> first.
*/
void resize(size_type newSize, const T& item = T()) {
if (newSize > size())
insert(end(), newSize - size(), item);
else
erase(end() - (size() - newSize), end());
}
public:
// Construction/Destruction
//! Creates an empty cyclic buffer.
explicit cyclic_buffer(
size_type capacity,
const allocator_type& a = allocator_type())
: m_buffer(a), m_capacity(capacity) {
m_buffer.reserve(capacity);
m_begin = m_buffer.begin();
}
//! Creates a full cyclic buffer with given capacity and filled with copies of item.
cyclic_buffer(
size_type capacity,
const T& item,
const allocator_type& a = allocator_type())
: m_buffer(capacity, item, a), m_begin(m_buffer.begin()), m_capacity(capacity) { }
//! Copy constructor.
cyclic_buffer(const cyclic_buffer<T, Alloc>& cb)
: m_buffer(cb.m_buffer)
, m_begin(m_buffer.begin() + (cb.m_begin - cb.m_buffer.begin()))
, m_capacity(cb.capacity()) {}
#ifndef BOOST_NO_MEMBER_TEMPLATES
//! Creates a cyclic buffer with a copy of a range.
template <class InputIterator> cyclic_buffer(
size_type capacity,
InputIterator first,
InputIterator last,
const allocator_type& a = allocator_type())
: m_buffer(a), m_capacity(capacity) {
m_buffer.reserve(capacity);
m_begin = m_buffer.begin();
std::copy(first, last, std::back_inserter(*this));
}
#else // BOOST_NO_MEMBER_TEMPLATES
//! Creates a cyclic buffer with a copy of a range.
cyclic_buffer(
size_type capacity,
const value_type* first,
const value_type* last,
const allocator_type& a = allocator_type())
: m_buffer(a), m_capacity(capacity) {
m_buffer.reserve(capacity);
m_begin = m_buffer.begin();
std::copy(first, last, std::back_inserter(*this));
}
//! Creates a cyclic buffer with a copy of a range.
cyclic_buffer(
size_type capacity,
const_iterator first,
const_iterator last,
const allocator_type& a = allocator_type())
: m_buffer(a), m_capacity(capacity) {
m_buffer.reserve(capacity);
m_begin = m_buffer.begin();
std::copy(first, last, std::back_inserter(*this));
}
#endif // BOOST_NO_MEMBER_TEMPLATES
//! Default destructor.
public:
// Assign methods
//! The default assign operator.
cyclic_buffer<T, Alloc>& operator = (const cyclic_buffer<T, Alloc>& cb) {
if (this == &cb)
return *this;
m_buffer = cb.m_buffer;
m_begin = m_buffer.begin() + (cb.m_begin - cb.m_buffer.begin());
m_capacity = cb.capacity();
return *this;
}
//! Assigns n items into cyclic buffer.
void assign(size_type n, const T& item) {
m_buffer.assign(n < capacity() ? n : capacity(), item);
m_begin = m_buffer.begin();
}
#ifndef BOOST_NO_MEMBER_TEMPLATES
//! Assigns a copy of range.
template <class InputIterator>
void assign(InputIterator first, InputIterator last) {
clear();
std::copy(first, last, std::back_inserter(*this));
}
#endif // BOOST_NO_MEMBER_TEMPLATES
//! Swaps the contents of two cyclic buffers.
void swap(cyclic_buffer& cb) {
if (this == &cb)
return;
InternalIterator cbBegin = cb.m_begin;
cb.m_begin = m_begin;
m_begin = cbBegin;
size_type cbCapacity = cb.m_capacity;
cb.m_capacity = m_capacity;
m_capacity = cbCapacity;
m_buffer.swap(cb.m_buffer);
}
public:
// push and pop
//! Inserts a new element at the end.
/*!
If the cyclic buffer is full, the first element will be removed.
\note For information about iterator invalidation see
<A HREF="../cyclic_buffer_howto.html#invalidation">Cyclic Buffer HOWTO</A>.
*/
void push_back(const value_type& item) { insert(end(), item); }
//! Inserts a new element with the default value at the end.
/*!
If the cyclic buffer is full, the first element will be removed.
\note For information about iterator invalidation see
<A HREF="../cyclic_buffer_howto.html#invalidation">Cyclic Buffer HOWTO</A>.
*/
void push_back() { push_back(value_type()); }
//! Removes the last element.
/*!
\note For information about iterator invalidation see
<A HREF="../cyclic_buffer_howto.html#invalidation">Cyclic Buffer HOWTO</A>.
*/
void pop_back() { erase(--end()); }
public:
// Insert
//! Inserts an item before the given position.
/*!
\return iterator to the inserted element
If the cyclic buffer is full, the first element will be removed.
\note For information about iterator invalidation see
<A HREF="../cyclic_buffer_howto.html#invalidation">Cyclic Buffer HOWTO</A>.
*/
iterator insert(iterator position, const value_type& item) {
if (full()) {
if (position == begin())
return end();
if (!position.m_isEnd) {
iterator src = --end();
iterator dest = begin();
while (dest != position)
*dest-- = *src--;
}
*position = item;
if (++m_begin == m_buffer.end())
m_begin = m_buffer.begin();
return iterator(&m_buffer, position.m_iterator, m_begin, false);
}
bool wasEmpty = empty();
InternalIterator it = m_buffer.insert(position.m_iterator, item);
switch (cyclic_buffer<T, Alloc>::iterator::sign(m_begin - position.m_iterator)) {
case 0:
m_begin = it;
if (position.m_isEnd && !wasEmpty)
++m_begin;
break;
case 1: ++m_begin; //< m_begin += it - position.m_iterator + 1;
case -1: m_begin += it - position.m_iterator;
break;
default:
BOOST_ASSERT(!"cyclic_buffer::insert");
}
return iterator(&m_buffer, it, m_begin, false);
}
//! Inserts a new element with the default value before the given position.
/*!
\return iterator to the inserted element
If the cyclic buffer is full, the first element will be removed.
\note For information about iterator invalidation see
<A HREF="../cyclic_buffer_howto.html#invalidation">Cyclic Buffer HOWTO</A>.
*/
iterator insert(iterator position) { return insert(position, value_type()); }
//! Inserts n copies of the item before the given position.
/*!
If the insertion would result in exceeding the capacity
of the cyclic buffer, then the necessary number of elements
from the beginning of the cyclic buffer will be removed.
\note For information about iterator invalidation see
<A HREF="../cyclic_buffer_howto.html#invalidation">Cyclic Buffer HOWTO</A>.
*/
void insert(iterator position, size_type n, const value_type& item) {
if (n > capacity())
n = capacity();
for (; n > 0; --n)
position = insert(position, item);
}
#ifndef BOOST_NO_MEMBER_TEMPLATES
//! Inserts the range [first, last) before the given position.
/*!
If the insertion would result in exceeding the capacity
of the cyclic buffer, then the necessary number of elements
from the beginning of the cyclic buffer will be removed.
\note For information about iterator invalidation see
<A HREF="../cyclic_buffer_howto.html#invalidation">Cyclic Buffer HOWTO</A>.
*/
template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last) {
std::copy(first, last, std::inserter(*this, position));
}
#else // BOOST_NO_MEMBER_TEMPLATES
//! Inserts the range [first, last) before the given position.
/*!
If the insertion would result in exceeding the capacity
of the cyclic buffer, then the necessary number of elements
from the beginning of the cyclic buffer will be removed.
\note For information about iterator invalidation see
<A HREF="../cyclic_buffer_howto.html#invalidation">Cyclic Buffer HOWTO</A>.
*/
void insert(iterator position, const value_type* first, const value_type* last) {
std::copy(first, last, std::inserter(*this, position));
}
//! Inserts the range [first, last) before the given position.
/*!
If the insertion would result in exceeding the capacity
of the cyclic buffer, then the necessary number of elements
from the beginning of the cyclic buffer will be removed.
\note For information about iterator invalidation see
<A HREF="../cyclic_buffer_howto.html#invalidation">Cyclic Buffer HOWTO</A>.
*/
void insert(iterator position, const_iterator first, const_iterator last) {
std::copy(first, last, std::inserter(*this, position));
}
#endif // BOOST_NO_MEMBER_TEMPLATES
public:
// Erase
//! Erases the element at the given position.
/*!
\return iterator to the first element remaining beyond the removed
element or end() if no such element exists
\note For information about iterator invalidation see
<A HREF="../cyclic_buffer_howto.html#invalidation">Cyclic Buffer HOWTO</A>.
*/
iterator erase(iterator position) {
InternalIterator it = m_buffer.erase(position.m_iterator);
m_begin += it - position.m_iterator;
if (m_begin > position.m_iterator)
--m_begin;
return iterator(&m_buffer, it, m_begin, m_buffer.empty());
}
//! Erases the range [first, last).
/*!
\return iterator to the first element remaining beyond the removed
element or end() if no such element exists
\note For information about iterator invalidation see
<A HREF="../cyclic_buffer_howto.html#invalidation">Cyclic Buffer HOWTO</A>.
*/
iterator erase(iterator first, iterator last) {
if (first == last)
return first;
if (first.m_iterator < last.m_iterator) {
InternalIterator it = m_buffer.erase(first.m_iterator, last.m_iterator);
return iterator(&m_buffer, it, m_begin, m_buffer.empty());
}
m_begin -= last.m_iterator - m_buffer.begin();
m_buffer.erase(m_buffer.begin(), last.m_iterator);
InternalIterator it = m_buffer.erase(first.m_iterator, m_buffer.end());
return iterator(&m_buffer, it, m_begin, m_buffer.empty());
}
//! Erases all of the elements.
void clear() {
m_buffer.clear();
m_begin = m_buffer.begin();
}
};
// Nonmember functions
#ifndef BOOST_NO_MEMBER_TEMPLATES
//! Tests two cyclic buffers for equality.
template <class T, class Alloc>
inline bool operator == (const cyclic_buffer<T, Alloc>& lhs,
const cyclic_buffer<T, Alloc>& rhs) {
return CB_CONTAINER<T, Alloc>(lhs.begin(), lhs.end(), lhs.get_allocator())
== CB_CONTAINER<T, Alloc>(rhs.begin(), rhs.end(), rhs.get_allocator());
}
//! Lexicographical comparison.
template <class T, class Alloc>
inline bool operator < (const cyclic_buffer<T, Alloc>& lhs,
const cyclic_buffer<T, Alloc>& rhs) {
return CB_CONTAINER<T, Alloc>(lhs.begin(), lhs.end(), lhs.get_allocator())
< CB_CONTAINER<T, Alloc>(rhs.begin(), rhs.end(), rhs.get_allocator());
}
#else // BOOST_NO_MEMBER_TEMPLATES
//! Tests two cyclic buffers for equality.
template <class T, class Alloc>
inline bool operator == (const cyclic_buffer<T, Alloc>& lhs,
const cyclic_buffer<T, Alloc>& rhs) {
CB_CONTAINER<T, Alloc> tmpLhs(lhs.get_allocator());
CB_CONTAINER<T, Alloc> tmpRhs(rhs.get_allocator());
tmpLhs.reserve(lhs.size());
tmpRhs.reserve(rhs.size());
std::copy(lhs.begin(), lhs.end(), std::back_inserter(tmpLhs));
std::copy(rhs.begin(), rhs.end(), std::back_inserter(tmpRhs));
return tmpLhs == tmpRhs;
}
//! Lexicographical comparison.
template <class T, class Alloc>
inline bool operator < (const cyclic_buffer<T, Alloc>& lhs,
const cyclic_buffer<T, Alloc>& rhs) {
CB_CONTAINER<T, Alloc> tmpLhs(lhs.get_allocator());
CB_CONTAINER<T, Alloc> tmpRhs(rhs.get_allocator());
tmpLhs.reserve(lhs.size());
tmpRhs.reserve(rhs.size());
std::copy(lhs.begin(), lhs.end(), std::back_inserter(tmpLhs));
std::copy(rhs.begin(), rhs.end(), std::back_inserter(tmpRhs));
return tmpLhs < tmpRhs;
}
#endif // BOOST_NO_MEMBER_TEMPLATES
#ifndef BOOST_NO_FUNCTION_TEMPLATE_ORDERING
//! Tests two cyclic buffers for non-equality.
template <class T, class Alloc>
inline bool operator != (const cyclic_buffer<T, Alloc>& lhs,
const cyclic_buffer<T, Alloc>& rhs) {
return !(lhs == rhs);
}
//! Lexicographical comparison.
template <class T, class Alloc>
inline bool operator > (const cyclic_buffer<T, Alloc>& lhs,
const cyclic_buffer<T, Alloc>& rhs) {
return rhs < lhs;
}
//! Lexicographical comparison.
template <class T, class Alloc>
inline bool operator <= (const cyclic_buffer<T, Alloc>& lhs,
const cyclic_buffer<T, Alloc>& rhs) {
return !(rhs < lhs);
}
//! Lexicographical comparison.
template <class T, class Alloc>
inline bool operator >= (const cyclic_buffer<T, Alloc>& lhs,
const cyclic_buffer<T, Alloc>& rhs) {
return !(lhs < rhs);
}
//! Swaps the contents of two cyclic buffers.
template <class T, class Alloc>
inline void swap(cyclic_buffer<T, Alloc>& lhs, cyclic_buffer<T, Alloc>& rhs) {
lhs.swap(rhs);
}
#endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING
}; // namespace boost
#endif // BOOST_CYCLIC_BUFFER_HPP
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk