In this part, we'll get
back to some basics. In a brief intermission from iterators, we'll add the complement to
front(),
back(), which returns a reference to the last item in the buffer. We provide a
const and a non-
const version:
// In declaration
reference back();
const_reference back() const;
template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::back()
{
assert(m_front);
return *wrap(m_back-1);
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::back() const
{
assert(m_front);
return *wrap(m_back-1);
}
To make this work, we need to make
wrap cope with pointers that stray below
m_buffer:
value_type *wrap(value_type *ptr) const
{
assert(ptr < m_buffer + m_capacity*2);
assert(ptr > m_buffer - m_capacity);
if (ptr >= m_buffer+m_capacity)
return ptr-m_capacity;
else if (ptr < m_buffer)
return ptr+m_capacity;
else
return ptr;
}
As ever, I'll add some tests that exercise the code, and reproduce the entire thing below for your cut-n-paste pleasure...
#include <algorithm>
#include <cassert>
#include <stdexcept>
template <typename T, typename A = std::allocator<T> >
class circular_buffer
{
public:
typedef T value_type;
typedef A allocator_type;
typedef typename allocator_type::size_type size_type;
typedef typename allocator_type::difference_type difference_type;
typedef typename allocator_type::reference reference;
typedef typename allocator_type::const_reference const_reference;
typedef typename allocator_type::pointer pointer;
typedef typename allocator_type::const_pointer const_pointer;
class iterator;
explicit circular_buffer(size_type capacity,
const allocator_type &a = allocator_type());
~circular_buffer();
allocator_type get_allocator() const;
size_type size() const;
size_type max_size() const;
bool empty() const;
size_type capacity() const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;
reference operator[](size_type n);
const_reference operator[](size_type n) const;
reference at(size_type n);
const_reference at(size_type n) const;
iterator begin();
iterator end();
bool push_back(const value_type &);
void pop_front();
void clear();
private:
size_type m_capacity;
allocator_type m_allocator;
pointer m_buffer;
pointer m_front;
pointer m_back; // points to next unused item
typedef circular_buffer<T> class_type;
circular_buffer(const class_type &);
class_type &operator=(const class_type &);
value_type *wrap(value_type *ptr) const
{
assert(ptr < m_buffer + m_capacity*2);
assert(ptr > m_buffer - m_capacity);
if (ptr >= m_buffer+m_capacity)
return ptr-m_capacity;
else if (ptr < m_buffer)
return ptr+m_capacity;
else
return ptr;
}
};
template <typename T, typename A>
inline
circular_buffer<T,A>::circular_buffer
(size_type capacity, const allocator_type &allocator)
: m_capacity(capacity),
m_allocator(allocator),
m_buffer(m_allocator.allocate(capacity)),
m_front(0),
m_back(m_buffer)
{
assert(capacity > 0);
}
template <typename T, typename A>
inline
circular_buffer<T,A>::~circular_buffer()
{
clear(); // deallocates all objects
m_allocator.deallocate(m_buffer, m_capacity);
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::allocator_type
circular_buffer<T,A>::get_allocator() const
{
return m_allocator;
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::capacity() const
{
return m_capacity;
}
template <typename T, typename A>
inline
bool circular_buffer<T,A>::empty() const
{
return !m_front;
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::size() const
{
return !m_front ? 0
: (m_back > m_front ? m_back : m_back+m_capacity) - m_front;
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::size_type circular_buffer<T,A>::max_size() const
{
return m_allocator.max_size();
}
template <typename T, typename A>
inline
bool circular_buffer<T,A>::push_back(const value_type &value)
{
if (m_front && m_front == m_back)
m_allocator.destroy(m_back);
m_allocator.construct(m_back, value);
value_type *const next = wrap(m_back+1);
if (!m_front)
{
// first entry in the buffer
m_front = m_back;
m_back = next;
return true;
}
else if (m_front == m_back)
{
// buffer is full already, throw something away
m_front = m_back = next;
return false;
}
else
{
m_back = next;
return true;
}
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::front()
{
assert(m_front);
return *m_front;
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::front() const
{
assert(m_front);
return *m_front;
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::back()
{
assert(m_front);
return *wrap(m_back-1);
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::back() const
{
assert(m_front);
return *wrap(m_back-1);
}
template <typename T, typename A>
inline
void circular_buffer<T,A>::pop_front()
{
assert(m_front);
m_allocator.destroy(m_front);
value_type *const next = wrap(m_front+1);
if (next == m_back)
m_front = 0;
else
m_front = next;
}
template <typename T, typename A>
inline
void circular_buffer<T,A>::clear()
{
if (m_front)
{
do
{
m_allocator.destroy(m_front);
m_front = wrap(m_front+1);
}
while (m_front != m_back);
}
m_front = 0;
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::operator[]
(size_type n)
{
return *wrap(m_front+n);
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::operator[]
(size_type n) const
{
return *wrap(m_front+n);
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::reference circular_buffer<T,A>::at(size_type n)
{
if (n >= size()) throw std::out_of_range("Parameter out of range");
return (*this)[n];
}
template <typename T, typename A>
inline
typename circular_buffer<T,A>::const_reference circular_buffer<T,A>::at
(size_type n) const
{
if (n >= size()) throw std::out_of_range("Parameter out of range");
return (*this)[n];
}
template <typename T, typename A>
class circular_buffer<T,A>::iterator
: public std::iterator<std::random_access_iterator_tag,
value_type,
size_type,
pointer,
reference>
{
public:
typedef circular_buffer<T> parent_type;
typedef typename parent_type::iterator self_type;
iterator(parent_type &parent, size_type index)
: parent(parent), index(index) {}
self_type &operator++()
{
++index;
return *this;
}
self_type operator++(int) // postincrement
{
self_type old(*this);
operator++();
return old;
}
self_type &operator--()
{
--index;
return *this;
}
self_type operator--(int) // postdecrement
{
self_type old(*this);
operator--();
return old;
}
reference operator*() { return parent[index]; }
pointer operator->() { return &(parent[index]); }
bool operator==(const self_type &other) const
{ return &parent == &other.parent && index == other.index; }
bool operator!=(const self_type &other) const
{ return !(other == *this); }
private:
parent_type &parent;
size_type index;
};
template <typename T, typename A>
typename circular_buffer<T,A>::iterator circular_buffer<T,A>::begin()
{
return iterator(*this, 0);
}
template <typename T, typename A>
typename circular_buffer<T,A>::iterator circular_buffer<T,A>::end()
{
return iterator(*this, size());
}
namespace tests
{
void pushing_and_popping()
{
circular_buffer<int> cb(5);
assert(cb.size() == 0);
assert(cb.capacity() == 5);
assert(cb.empty());
assert(cb.max_size() > 0);
assert(cb.push_back(1));
assert(cb.size() == 1);
assert(cb.capacity() == 5);
assert(!cb.empty());
assert(cb.front() == 1);
assert(cb.back() == 1);
assert(cb.push_back(2));
assert(cb.size() == 2);
assert(cb.capacity() == 5);
assert(!cb.empty());
assert(cb.front() == 1);
assert(cb.back() == 2);
assert(cb.push_back(3));
assert(cb.push_back(4));
assert(cb.push_back(5));
assert(cb.size() == 5);
assert(cb.capacity() == 5);
assert(!cb.empty());
assert(cb.front() == 1);
assert(cb.back() == 5);
assert(!cb.push_back(6));
assert(cb.size() == 5);
assert(cb.capacity() == 5);
assert(!cb.empty());
assert(cb.front() == 2);
assert(cb.back() == 6);
cb.pop_front();
assert(cb.size() == 4);
assert(cb.capacity() == 5);
assert(!cb.empty());
assert(cb.front() == 3);
assert(cb.back() == 6);
cb.pop_front();
assert(cb.size() == 3);
assert(cb.front() == 4);
assert(cb.back() == 6);
cb.pop_front();
assert(cb.size() == 2);
assert(cb.front() == 5);
assert(cb.back() == 6);
cb.pop_front();
assert(cb.size() == 1);
assert(cb.front() == 6);
assert(cb.back() == 6);
cb.pop_front();
assert(cb.size() == 0);
assert(cb.capacity() == 5);
assert(cb.empty());
// empty again
assert(cb.push_back(7));
assert(cb.size() == 1);
assert(cb.capacity() == 5);
assert(!cb.empty());
assert(cb.front() == 7);
assert(cb.back() == 7);
assert(cb.push_back(8));
assert(cb.push_back(9));
assert(cb.size() == 3);
assert(!cb.empty());
assert(cb.front() == 7);
assert(cb.back() == 9);
cb.clear();
assert(cb.size() == 0);
assert(cb.capacity() == 5);
assert(cb.empty());
}
void indexing()
{
circular_buffer<int> cb(5);
// A helper - like asssert, but checks for an exception
#define assert_throws(a,b) \
{\
try { a; throw "Failed to throw"; } \
catch (const b&) { /*OK*/ } \
catch (...) { throw "Threw wrong thing"; } \
}
// We loop round this test several times so our data wraps around the
// internal m_buffer array a few times.
for (size_t n = 0; n < 10; ++n)
{
assert(cb.empty());
const circular_buffer<int> &const_cb(cb);
assert_throws(cb.at(0), std::out_of_range);
assert_throws(cb.at(1), std::out_of_range);
assert_throws(const_cb.at(0), std::out_of_range);
assert_throws(const_cb.at(0), std::out_of_range);
// we could check that operator[] explodes, but there's little point!
assert(cb.push_back(0));
assert(cb.push_back(1));
assert(cb.push_back(2));
assert(cb.at(0) == 0); assert(const_cb.at(0) == 0);
assert(cb.at(1) == 1); assert(const_cb.at(1) == 1);
assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
assert(cb[0] == 0); assert(const_cb[0] == 0);
assert(cb[1] == 1); assert(const_cb[1] == 1);
assert(cb[2] == 2); assert(const_cb[2] == 2);
assert(cb.front() == 0);
cb[0] = 3;
assert(cb.front() == 3);
assert(cb.at(0) == 3); assert(const_cb.at(0) == 3);
assert(cb.at(1) == 1); assert(const_cb.at(1) == 1);
assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
assert(cb[0] == 3); assert(const_cb[0] == 3);
assert(cb[1] == 1); assert(const_cb[1] == 1);
assert(cb[2] == 2); assert(const_cb[2] == 2);
cb[1] = 4;
assert(cb.at(0) == 3); assert(const_cb.at(0) == 3);
assert(cb.at(1) == 4); assert(const_cb.at(1) == 4);
assert(cb.at(2) == 2); assert(const_cb.at(2) == 2);
assert(cb[0] == 3); assert(const_cb[0] == 3);
assert(cb[1] == 4); assert(const_cb[1] == 4);
assert(cb[2] == 2); assert(const_cb[2] == 2);
cb.pop_front();
assert(cb[0] == 4); assert(const_cb[0] == 4);
assert(cb[1] == 2); assert(const_cb[1] == 2);
cb.pop_front();
assert(cb[0] == 2); assert(const_cb[0] == 2);
cb.pop_front();
}
}
}
int main()
{
tests::pushing_and_popping();
tests::indexing();
return 0;
}
4 comments:
Various different shades of green on a green background... interesting colour scheme you have :)
Oooh, that implementation of wrap() is a bit worrying. I'm pretty sure that C++ doesn't guarantee that that sort of arithmetic will work with pointers outside the actual allocated object. For the ptr<m_buffer case to fail you probably have to be on some sort of segmented or Win16 architecture; but the ptr>=m_buffer+m_capacity one can fail even on a sane 32-bit architecture if m_buffer ends up near the very top of memory. (C++ guarantees this to work for m_buffer+m_capacity, but not for anything beyond there.)
To implement wrap() without invoking undefined behaviour, you probably need to implement it as something like
value_type *wrap(value_type *ptr, difference_type offset)
{
size_type pos = ptr - m_buffer;
assert(pos < m_capacity);
if (offset >= 0)
{
assert(offset<m_capacity);
pos += offset;
}
else
{
// Care with promotion to unsigned!
assert(-offset<m_capacity);
pos += (m_capacity+offset);
}
if (pos > m_capacity)
pos -= m_capacity;
return m_buffer + pos;
}
and call it with wrap(m_back, -1) or whatever, but of course that's rather more expensive, as calculating pos requires a division. You could avoid the division by working in char*s, but at the expense of much uglier code...
Hi Peter. Yes, you have a very valid point.
I think a nicer solution here would be something like:
pointer increment(pointer ptr, size_type by) const
{
assert(ptr >= m_buffer);
assert(ptr < m_buffer+m_capacity);
const size_type index = ptr-m_buffer;
assert(index < m_capacity);
if (index+by >= m_capacity)
return ptr+by-m_capacity;
else
return ptr+by;
}
pointer decrement(pointer ptr, size_type by) const
{
assert(ptr >= m_buffer);
assert(ptr < m_buffer+m_capacity);
const size_type index = ptr-m_buffer;
assert(index < m_capacity);
if (index >= by)
return ptr-by;
else
return ptr+(m_capacity-by);
}
It still has the pointer arithmetic issue you mention, but it reads a little better, and avoids some unnecessary if statements.
Can you please explain why I get an error when trying to use an iterator?
I am trying to retrieve the entries from the circular buffer from the oldest entry to the youngest.
In your test file, I tried to add the following (using Visual Studio 2010) just to test iterators:
circular_buffer<int>::iterator iter;
int n(0);
for (iter = cb.begin(); iter != cb.end(); iter++) {
n++;
}
On the definition of 'iter', I get the following error:
error C2512: 'circular_buffer::iterator' : no appropriate default constructor available
In the "for" statement, "iter = cb.begin()", I get the error:
error C2582: 'operator =' function is unavailable in 'circular_buffer::iterator'
Many thanks
Post a Comment