Реализация очереди приоритетов, которая может быть повторена в C ++ - PullRequest
Новая
       23

Реализация очереди приоритетов, которая может быть повторена в C ++

5 голосов
/ 12 декабря 2010

Мне нужно реализовать приоритетную очередь для проекта, но STL priority_queue не указывается, поскольку нам нужно перебирать все элементы и удалять их случайным образом.

Мы думаем об использовании STL set для этого, оборачивая его в класс, чтобы сделать его ADT.

Есть ли более разумное решение для этого?

Как мы можем сделать так, чтобы некоторые публичные функции-члены set могли использоваться публично? Нас интересуют итераторы и т. Д.

Видимо, вывод STL неразумен из-за отсутствия виртуальных деструкторов: /

Новый код: 

#ifndef PRIORITYQUEUE_H_
#define PRIORITYQUEUE_H_

#include <set>

template<typename T, template<typename X> class impl_type = std::set>
class PriorityQueue {
    typedef impl_type<T> set_type;
    typedef typename set_type::iterator iterator;
public:
    void push(const T& x) {
        insert(x);

    }

    void pop() {
        erase(begin());
    }

    const T& top() const {
        return *begin();
    }
};

#endif /* PRIORITYQUEUE_H_ */

Итак, у нас сейчас есть это. Компилятор не жалуется на вставку, но он жалуется на erase(begin()) и return *begin():

there are no arguments to 'begin' that depend on a template parameter, so a declaration of 'begin' must be available

Почему это?

Ответы [ 4 ]

3 голосов
/ 12 декабря 2010

Вы должны иметь возможность реализовать собственную очередь приоритетов, используя std::vector, std::make_heap, std::push_heap и std::pop_heap. Разве не так std::priority_queue реализован? Вам просто нужно будет снова вызвать std::make_heap, чтобы исправить структуру данных при удалении случайного элемента.

Вам нужно перебирать элементы по порядку? Есть алгоритм std::sort_heap, чтобы упорядочить базовый std::vector.

2 голосов
/ 12 декабря 2010

Набор STL должен использоваться для создания того, что вы хотите, хотя я должен отметить, что список требований выглядит немного странно. Вы можете просто определить новый тип. 

template<typename T, template<typename X> class impl_type = std::set> class prio_queue {
    typedef impl_type<T> set_type;
    typedef typename set_type::iterator iterator;
    // etc
public:
    // Forward the set's members
    T& top() {
        return *begin();
    }
    // etc
};
2 голосов
/ 12 декабря 2010

Вам действительно нужна очередь с приоритетами?

Вам нужно перебрать все элементы и удалить случайным образом -> связанный список

Если вам нужно сохранить список отсортированным, отсортируйте его в началеи затем при вставке нового элемента используйте сортировку вставки (вставьте новый элемент в нужное место).

1 голос
/ 12 декабря 2010

Я бы следовал примеру, установленному некоторыми другими адаптерами контейнеров в стандартной библиотеке, используя композицию, и сделал бы тип базового контейнера параметром шаблона. Хотя, поскольку это школьный проект, он может быть слишком гибким. Вы можете начать с использования композиции с одним из существующих контейнеров и построить его оттуда, если это необходимо.

...