Here is an open source dynamic Queue I wrote for anyone who is interested

[Critkeeper]

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:

Code: [Select]

#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



[Critkeeper]

Right now I have an outstanding bug that I can't figure out how to fix.

Compile and run this code, with the class provided above:

Code: [Select]


#include "Queue.h"
#include <queue>
#include "Chrono"

using namespace std;

int main()
{
    Queue<int> q = Queue<int>();
    std::queue<int> stdq = std::queue<int>();


    for( int i = 0; i < 123; ++i )
    {
        q.push( i );
        stdq.push( i );
    }

    auto start = std::chrono::high_resolution_clock::now();
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);

    start = std::chrono::high_resolution_clock::now();
    for( int i = 0; i < 1234; ++i )
    {
        cout << stdq.front() << endl;
        stdq.push( stdq.front() );
        stdq.pop();
    }
    end = std::chrono::high_resolution_clock::now();
    elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    cout << "std::queue: " << elapsed.count() << endl;

/*
    start = std::chrono::high_resolution_clock::now();
    for( int i = 0; i < 1234; ++i )
    {
        cout << q.front() << endl;
        q.push( q.front() );
        q.pop();
    }
    end = std::chrono::high_resolution_clock::now();
    elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    cout << "Queue: " << elapsed.count() << endl;
*/
    return 0;
}


If you run it as is, it will work fine. If you uncomment the block that is commented, it will crash.

What is odd about that crash is that it doesn't happen immediately. The Queue object will cycle the same way as std::queue and spit out the correct values many many times before it fails.


EDIT:

Special thanks to Alfie275 for helping me find the bug! I modified the source in the original post to reflect the changes.

[Nexus]

Several semantic issues:

• The std::move() algorithm into an empty std::vector leads to undefined behavior. Reserving is not resizing!
  
• There are unnecessary copies in front(), back() and push().
  
• You should use std::size_t for container sizes.
  
• The constructor should be explicit.
• You disregard const-correctness.
• You hide logic errors by doing nothing in pop() when the queue is empty. Never do that, it leads to nasty bugs.
  
• The emplace() and push() functions duplicate code and look overly complicated. Why do you do std::vector's job of reserving space, with a questionable strategy of doubling the capacity? These containers do their job well, you're most probably degrading performance by trying to do better.

And less severe points:

• return at the end of a void function is pointless.
  
• You're using a very uncommon line-breaking style for return types.
• QUEUE_H is quite a generic macro, I'm sure you're not the only one definining it.
  

Are you sure reinventing circular buffers is a good idea? Boost provides a working implementation, and there are certainly tons of other libraries that do so, too. If you really build containers, then do it in a straightforward way (just a thin layer over existing STL containers with the simplest possible implementation) and cover the operations with unit tests to catch the most bugs.

What you're underestimating is exception safety. You should be clear about the guarantees (basic, strong, nothrow) your operations provide, and this is non-trivial to implement correctly. Even more when you consider special cases like throwing copy or move constructors. You may say that this is irrelevant, and it may be to you. However, a container is a generic data structure, and since you're sharing it, you don't know how it will be used. Not providing exception safety is also an option, but you should state this.

[Critkeeper]

Thankyou for the feedback nexus, I will implement your suggestions.

[Nexus]

You're welcome.

Oh, and I forgot: General Discussions is the wrong subforum for that, it's definitely not a general discussion about the library
There's actually no really good subforum for it (this forum is all about SFML, and your post has nothing to do with it), but Wiki or Projects would be the best fit in the future.

[Hapax]

Does this just do the same as std::queue (or std::deque) or does it have something extra special?

@Nexus I always learn so much when you post things people can do better

[Klaim]

std::queue is a thin wrapper over a container and unfortunately it is not useful as a queue most of the time.
std::deque works but have specific performance characteristics which might not fit your use case (aka: it's not a vector inside). Also it's not a circular buffer, you would still have to augment it's behaviour by wrapping it.

Other than boost, there was some proposal to add actually useful (non-concurrent) queue types in the C++ standard in the last year, but I don't remember if it was well received or not.

[therocode]

How come you say that std::queue is not useful as a queue?

[ChronicRat]

std::queue is a thin wrapper over a container and unfortunately it is not useful as a queue most of the time.

Hm, I use std::queue as queue two years already. And I can't imagine another way to use std::queue except queue. =)

[Nexus]

I think most people who say std::queue is not useful criticize the lack of operations such as iteration. The whole point of container adapters however is to reduce the API of an underlying container, so that is entirely by design.

People who need more can easily use std::deque directly.