HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppMinor

C++ Queue Implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
implementationqueuestackoverflow

Problem

so I wrote a queue implementation in c++ and even though I know the code probably isn't as robust as it should be and probably doesn't perform all the checks it should, I'd like to know mostly if there is any functionality difference between my implementation and the one in STL.

My implementation idea is to use a circular queue, when I reach the end of the queue I start using the elements at the beginning of the range (that were removed through the pop method).

When I don't have any more space to allocate a new element I reallocate a new buffer and move everything to the new buffer in order (this could probably be done faster using 2 memmoves).

The reason I post this here is because this queue implementation seems to be aproximately 50% faster than the one in std. Here is my code:

template
class Queue
{
private:
    int m_capacity;
    int m_size;
    int m_startIndex;
    int m_endIndex;
    T* m_buffer;

    void expand_queue() {
        int newCapacity = m_capacity * 2;
        T* newBuffer = new T[newCapacity];
        if (m_endIndex  0) {
            // expand queue
            expand_queue();
        }

        m_buffer[m_endIndex] = element;
        m_endIndex = (m_endIndex + 1) % m_capacity;
        m_size++;
    }

    void pop() {
        if (m_size == 0) {
            return;
        }

        m_startIndex = (m_startIndex + 1) % m_capacity;
        m_size--;
    }

    T front() {
        if (m_size == 0) {
            throw;
        }

        return m_buffer[m_startIndex];
    }

    T back() {
        if (m_size == 0) {
            throw;
        }

        if (m_endIndex == 0) {
            return m_buffer[m_capacity - 1];
        } else {
            return m_buffer[m_endIndex - 1];
        }
    }

    int size() {
        return m_size;
    }
};


And here is the code I used to test this:

```
#include
#include "queue.h"
#include
#include
#include
#include

using namespace std;

Queue q;
// queue q;

int main() {
srand(time(0)

Solution

Please use std::vector instead of T* because you clearly don't know what you are doing (missing operator=, copy-constructor, etc). Better, make the underlying container a template parameter.

The std::queue is probably slower because it may free some memory when doing all these pop() while yours doest release anything.

About this:

if (m_size == 0) {
        throw;
    }


what do you think you are throwing ? Please throw a proper exception (see http://en.cppreference.com/w/cpp/header/stdexcept for example).

Code Snippets

if (m_size == 0) {
        throw;
    }

Context

StackExchange Code Review Q#135680, answer score: 2

Revisions (0)

No revisions yet.