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<typename T>
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 <= m_startIndex) {
int cnt = 0;
for (int i = m_startIndex; i < m_capacity; i++) {
newBuffer[cnt++] = m_buffer[i];
}
for (int i = 0; i < m_endIndex; i++) {
newBuffer[cnt++] = m_buffer[i];
}
} else {
int cnt = 0;
for (int i = m_startIndex; i < m_endIndex; i++) {
newBuffer[cnt++] = m_buffer[i];
}
}
delete[] m_buffer;
m_buffer = newBuffer;
m_startIndex = 0;
m_endIndex = m_size;
m_capacity = newCapacity;
}
void init_queue(int capacity) {
m_capacity = capacity;
m_size = 0;
m_startIndex = 0;
m_endIndex = 0;
m_buffer = new T[capacity];
}
public:
Queue() {
init_queue(32);
}
Queue(int capacity) {
init_queue(capacity);
}
void push(T element) {
if (m_endIndex == m_startIndex && m_size > 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 <queue>
#include "queue.h"
#include <iostream>
#include <list>
#include <cstdlib>
#include <ctime>
using namespace std;
Queue<int> q;
// queue<int> q;
int main() {
srand(time(0));
for (int i = 0; i < 100000000; i++) {
if (q.size() > 10000000) {
q.pop();
} else if (q.size() == 0) {
q.push(i);
} else if (random() % 2 == 0) {
q.push(i);
} else {
q.pop();
}
}
while (q.size() > 0) {
q.pop();
}
return 0;
}
You can see that in the test code I have both queue types in there (just comment one line and uncomment the other). This program perform 100 milion operation of push/pop on the queue while making sure the queue doesn't go over 10 million in size.
Using the queue implementation above I get this time:
real 0m3.859s
user 0m3.827s
sys 0m0.015s
And these are times using the std queue:
real 0m6.077s
user 0m6.055s
sys 0m0.011s
(Benchmarks done on a mid-2012 Macbook Air).
After studying the std queue implementation I managed to note these differences:
- std::queue uses std::deque as a container by default (using std::list gives even worse results). The std::queue only calls the pop_front and the push_back methods of the deque. All the logic is in the deque.
- std::deque creates chunks of fixed size which he uses to allocate the data and manages them accordingly (first chunk expands in reverse and the last chunk expands normally).
- Given that std::deque creates these chunks memory fragmentation could also become an issue.
- std::queue doesn't do any memory movements, just allocations of new chunks, while my queue will move the memory around when it needs to expand the queue (log(N) times where N is the maximum size of the queue).
