Понадобилась мне недавно очередь с приоритетами, заглянул в Tulip не нашел, а так как на стандартную библиотеку в этом проекте использовать нехочется, решил написать это детище сам. Смотрим далее что получилось. Может кому и пригодиться.
Для начала, мне очень нравится интерфейс std::priority_queue и конечный вариант будет весьма похож на нее (только без поддержки итераторов, т.к. лень, сейчас не нужны).
Посмотрев на реализацию stl и Qt родил последовательно три вот таких класса:
1. Ни что иное как QQueue с расширенной функциональностью. Реализация через наследование от QList-а с добавлением определять функцию сортировки. Т.к. используется qSort то получем соответствующее ограничение: либо используем стандартные для Qt функции qLess и qGreater, либо с больной головой сами пытаемся реализовать соответствующие функторы. Все очень просто, но зато дешево и сердито.
template <typename T, typename LessThan=qLess<typename T> >
class QPriorityQueue : public QList<T>{
LessThan comp;
public:
inline QPriorityQueue(): comp() {}
inline ~QPriorityQueue() {}
inline void enqueue(const T &t) { QList<T>::append(t); qSort(QList<T>::begin(), QList<T>::end(), comp);}
inline T dequeue() { return QList<T>::takeFirst(); }
inline T &head() { return QList<T>::first(); }
inline const T &head() const { return QList<T>::first(); }
};
2. Больше похоже на stl, так как хочется, все таки, отвязаться от QList-а, в смысле наследования. Этакий промежуточный вариант но тоже может быть полезен, так как в отличие от следующего случая имеет более простой интерфейс.
template <typename T, typename LessThan=qLess<typename T> >
class QPriorityQueue{
QList<T> cont;
LessThan comp;
public:
inline QPriorityQueue(): comp() {}
inline QPriorityQueue(const QList &_cont): cont(_cont), comp() {}
inline ~QPriorityQueue() {}
inline void enqueue(const T &t) { cont.append(t); qSort(cont.begin(), cont.end(), comp);}
inline T dequeue() { return cont.takeFirst(); }
inline T &head() { return cont.first(); }
inline const T &head() const { return cont.first(); }
};
3. Ну и наконец почти QSTL 8-). Избавляемся от QList-а вовсе, и имем возможность использовать другие контейнеры (например QVector), и добавляем, так не хватающей нам, привычной функциональности из std::priority_queue.
template <typename T, typename Cont=QList<T>, typename LessThan=qLess<typename T> >
class QPriorityQueue{
Cont cont;
LessThan comp;
public:
inline QPriorityQueue(): comp() {}
inline QPriorityQueue(const Cont &_cont): cont(_cont), comp() {}
inline ~QPriorityQueue() {}
inline void enqueue(const T &t) { cont.push_back(t); qSort(cont.begin(), cont.end(), comp);}
inline T dequeue() { T t = cont.front(); cont.pop_front(); return t; }
inline T &head() { return cont.front(); }
inline void clear() { return cont.clear(); }
inline void size() { return cont.size(); }
inline bool empty() { return cont.empty(); }
inline T &top() { return cont.front(); }
inline const T &head() const { return cont.first(); }
};
Вот собственно и все. Хотелось бы услышать мнения, предпочтения, рекомендации.
P.S. Контейнеры конечно же должны поддерживать соответствующие интерфейсы, а объекты помещаемые в очередь иметь реализацию оператора <.
P.S. Тут есть еще вопрос по контейнерам Qt, как у них с многопоточностью? Интерисует режим когда есть пара потоков, и один поток только забирает данные из контейнера, а другой только кладет. Возникнут ли здесь проблемы если не использовать примитвов межпоточной синхронизации при обращении к функциям контейнера.
