22
« on: May 22, 2015, 07:59:43 pm »
I'm putting it in the public domain.
I tested it so it should be bug free, but having more than one person test it is always one of the fantastic benefits of sharing code with a community.
Its just a circular buffer that uses a std::vector as a back end. When the buffer becomes full it requests that the vector allocate more space and then it copies itself into the vector. The copying is almost trivial but not quite, because circular buffers that are completely full have no empty elements, and yet extending the size of a circular buffer mandates that the new container will have empty elements. Deciding where to put these empty elements in order to preserve the qualities of a circular queue is an easy problem, but nevertheless here is my solution:
#ifndef QUEUE_H
#define QUEUE_H
#include <vector>
#include <algorithm>
/**
@brief A queue based on an underlying dynamic circular array buffer
*/
template< typename T, typename Alloc = std::allocator<T> >
class
Queue
{
public:
Queue( unsigned int initialCapacity = 0);
bool
empty();
unsigned int
size();
unsigned int
capacity();
T
front();
T
back();
void
push( T );
void
pop();
template <class... Args>
void
emplace (Args&&... args);
void
swap( Queue& );
protected:
private:
std::vector< T, Alloc >
buffer;
unsigned int
frontIndex;
unsigned int
backIndex;
unsigned int
numberOfElements;
};
template< typename T, typename Alloc >
Queue< T, Alloc >::
Queue( unsigned int initialCapacity )
: buffer( initialCapacity > 0 ? initialCapacity : 16 )
, frontIndex(0)
, backIndex(0)
, numberOfElements(0)
{
}
template< typename T, typename Alloc >
void
Queue< T, Alloc >::
swap(Queue& q)
{
buffer.swap( q.buffer );
}
template< typename T, typename Alloc >
template <class... Args>
void
Queue< T, Alloc >::
emplace( Args&& ... args )
{
if( numberOfElements == buffer.capacity() )
{
std::vector< T, Alloc > v;
v.reserve( 2*buffer.capacity() );
std::move( buffer.begin(), buffer.begin() + frontIndex + 1, v.begin() );
if( frontIndex != numberOfElements )
{
std::move_backward( buffer.begin() + backIndex, buffer.end(), v.end() );
backIndex += v.capacity() - buffer.capacity();
}
v.swap( buffer );
}
if( frontIndex == buffer.capacity() )
frontIndex = 0;
buffer.emplace( frontIndex, args ... );
// incrementing front index of circular buffer should not require setting it to 0
// if additional space was successfully allocated; otherwise bad_alloc exception.
++frontIndex;
++numberOfElements;
return;
}
template< typename T, typename Alloc >
void
Queue< T, Alloc >::
pop()
{
if( numberOfElements == 0 )
return;
if( backIndex == buffer.capacity() - 1 )
backIndex = 0;
else
++backIndex;
--numberOfElements;
return;
}
template< typename T, typename Alloc >
void
Queue< T, Alloc >::
push( T x )
{
if( numberOfElements == buffer.capacity() )
{
std::vector< T, Alloc > v;
v.reserve( 2*buffer.capacity() );
std::move( buffer.begin(), buffer.begin() + frontIndex + 1, v.begin() );
if( frontIndex != numberOfElements )
{
std::move_backward( buffer.begin() + backIndex, buffer.end(), v.end() );
backIndex += v.capacity() - buffer.capacity();
}
v.swap( buffer );
}
if( frontIndex == buffer.capacity() )
frontIndex = 0;
buffer[frontIndex] = x;
// incrementing front index of circular buffer should not require setting it to 0
// if additional space was successfully allocated; otherwise bad_alloc exception.
++frontIndex;
++numberOfElements;
return;
}
template< typename T, typename Alloc >
T
Queue< T, Alloc >::
back()
{
return buffer[frontIndex];
}
template< typename T, typename Alloc >
T
Queue< T, Alloc >::
front()
{
return buffer[backIndex];
}
template< typename T, typename Alloc >
bool
Queue< T, Alloc >::
empty()
{
return numberOfElements == 0;
}
template< typename T, typename Alloc >
unsigned int
Queue< T, Alloc >::
size()
{
return numberOfElements;
}
template< typename T, typename Alloc >
unsigned int
Queue< T, Alloc >::
capacity()
{
return buffer.capacity();
}
#endif // QUEUE_H
Show Posts