On 04/17/2015 12:12 PM, Berkay Elbir wrote:
Hello All,
I want to ask a question to you to be certain. Is void qsort() function
obsolete? Should we use std::sort instead of this function? Because I
have a priority list and need to sort it.
Slightly off-topic: Don't implement a priority queue this way. Unless
you have a system where you get a bunch of those and can sort them once,
and handle all of them. If this isn't the case, you are going to have
inserts and removes mixed. Then you will continually sort something
that's already sorted.
I have an old implementation of a priority queue you can use instead.
It's an implementation of a binary heap algorithm. It's optimized for
the case where there are just a few items in the queue and very rarely
it will get a burst of more. If your case doesn't match this, you could
probably remove the resize to minimum. You can instantiate it with
anything that implements operator<.
I hope it helps.
Bo Thorsen,
Director, Viking Software.
--
Viking Software
Qt and C++ developers for hire
http://www.vikingsoft.eu
#ifndef VSTOOLS_PRIORITYQUEUE_H
#define VSTOOLS_PRIORITYQUEUE_H
#include <QList>
class PriorityQueueTest;
namespace VSTools {
template <typename T> class PriorityQueue {
public:
enum { MinimumSpace = 8 };
PriorityQueue() : mReserved(0), mCount(0), mEntries(0) {
}
~PriorityQueue() {
delete[] mEntries;
}
void enqueue(T item) {
if (mCount < 2 && mReserved != MinimumSpace) {
// Our list was (almost) empty, resize it to 8 so we have some room. This also prunes the list if it used to be bigger
resize(MinimumSpace);
} else if (mCount == mReserved) {
// We need more space
resize(mReserved * 4);
}
// Insert this at the end of the tree
int i = mCount;
int parent = (i - 1) / 2;
mEntries[mCount++] = item;
// Test that the tree is still in order
while (parent >= 0 && i > 0 && mEntries[i] < mEntries[parent]) {
swap(parent, i);
// Go up the tree and retest
i = parent;
parent = (i - 1) / 2;
}
}
T dequeue() {
Q_ASSERT(!isEmpty());
if (mCount == 1) {
// Small optimization
mCount = 0;
return mEntries[0];
}
// Take the first and move the last to the top
T item = mEntries[0];
mEntries[0] = mEntries[--mCount];
// Sink the top down
int i = 0;
while (true) {
int swapWith = 2 * i + 1;
if (swapWith >= mCount) {
// We're at the end
break;
}
if (swapWith < mCount - 1 && mEntries[swapWith + 1] < mEntries[swapWith]) {
// Use the right entry instead
++swapWith;
}
if (mEntries[swapWith] < mEntries[i]) {
swap(swapWith, i);
i = swapWith;
} else {
// Done, we found the right place in the tree
break;
}
}
return item;
}
const T& peek() const {
Q_ASSERT(!isEmpty());
return mEntries[0];
}
inline int count() const { return mCount; }
/// Returns true, if this queue is empty
inline bool isEmpty() const { return mCount == 0; }
void clear() {
mCount = 0;
if (mReserved > MinimumSpace) {
resize(MinimumSpace);
}
}
private:
Q_DISABLE_COPY(PriorityQueue)
void resize(unsigned int reserved) {
mReserved = reserved;
T* oldEntries = mEntries;
mEntries = new T[reserved];
// Copy over the old entries
for (int i=0; i<mCount; ++i) {
mEntries[i] = oldEntries[i];
}
delete[] oldEntries;
}
inline void swap(int i, int j) {
T temp = mEntries[i];
mEntries[i] = mEntries[j];
mEntries[j] = temp;
}
int mReserved;
int mCount;
T* mEntries;
};
}
#endif // PRIORITYQUEUE_H
_______________________________________________
Interest mailing list
Interest@qt-project.org
http://lists.qt-project.org/mailman/listinfo/interest
