Как сообщить std:: priority_queue обновить его порядок?

Ответ 1

Это немного хакерский, но ничего незаконного в этом нет, и он выполняет свою работу.

std::make_heap(const_cast<city**>(&cities.top()),
               const_cast<city**>(&cities.top()) + cities.size(),
               Compare());

Обновление

Не используйте этот хак, если:

• Основной контейнер не vector.
• Функтор Compare имеет поведение, которое приведет к тому, что внешняя копия будет упорядочена иначе, чем копия Compare, хранящаяся внутри priority_queue.
• Вы не полностью понимаете, что означают эти предупреждения.

Вы всегда можете написать собственный контейнерный адаптер, который обертывает алгоритмы кучи. priority_queue - не что иное, как простая оболочка вокруг make/push/pop_heap.

Ответ 2

На основе http://www.sgi.com/tech/stl/priority_queue.html не похоже, что есть способ сделать это, без опорожнения и повторной установки.

Если вы хотите отойти от priority_queue (но все еще хотите кучу), вы можете использовать вектор вместе с make_heap, push_heap и pop_heap. См. Раздел "Примечания" на странице priority_queue.

Ответ 3

Если вам нужно сохранить упорядоченную коллекцию, вы можете рассмотреть следующее решение: Используйте std::set, а для обновления значений удалите элемент, обновите его значение и поместите его обратно в набор. Это даст вам сложность O (log n) для обновления одного элемента, что лучше всего подходит для обычной структуры кучи (если у вас есть доступ к своим внутренним элементам для массового обслуживания с помощью процедур sift-up sift-down). Единственным недостатком std::set будет время для инициализации набора с n элементами. (O (n log n) вместо O (n)).

Ответ 4

Это старый вопрос, но я не был полностью удовлетворен ни одним из ответов, когда хотел сделать это сам. Нет необходимости в каких-либо хаках. std::priority_queue содержит все механизмы, чтобы сделать это юридически и идиоматично.

std::priority_queue имеет два очень полезных элемента данных, c (базовый контейнер) и comp (предикат сравнения).

Также полезно, что в стандарте указано, что тип шаблона Container должен быть моделью SequenceContainer, итераторы - это модели RandomAccessIterator.

Это полезно, потому что тип аргумента Iter std::make_heap имеет те же требования к модели RandomAccessIterator.

Это длинный способ сказать, что std::priority_queue является оберткой вокруг кучи и поэтому std::make_heap(std::begin(c), std::end(c), comp) должен быть допустимым выражением.

"Плохая" новость заключается в том, что c и comp защищены. Это хорошая новость по двум причинам:

• Вы не можете случайно уничтожить кучу.

• Если вы вышли из std::priority_queue, вы можете намеренно модифицировать кучу.

Итак, трюк заключается в том, чтобы вывести свою очередь приоритетов из std::priority_queue, в функцию-член, как угодно, изменить внутреннюю кучу c, а затем вызвать std::make_heap(std::begin(c), std::end(c), comp);, чтобы вернуть ее в действительную кучу.

Не так ли, как правило, плохая идея наследовать от контейнеров STL

Ну да, но...

Есть две причины, по которым это может быть плохой идеей для молодых и/или неосторожных. Отсутствие полиморфных деструкторов и риск нарезки.

• Полиморфные деструкторы

Фактически нет разумного случая использования для хранения контейнера std через указатель на его базовый класс. Контейнеры легкие (когда в них нет ничего) и дешево передвигаются. Вы можете думать о случаях использования, но я могу гарантировать, что все, что вы намеревались сделать, может быть сделано лучше, инкапсулируя контейнер в другой объект, выделенный для кучи. В хорошо продуманном коде это никогда не должно вызывать беспокойства. В любом случае, наследование в частном порядке из класса шаблона priority_queue устраняет этот риск.

2. Нарезка

Конечно, существует риск среза, когда мы передаем унаследованные объекты. Ответ здесь заключается в том, чтобы наследовать в частном порядке из базового класса priority_queue, а затем использовать using в производном классе для экспорта только частей интерфейса базового класса, которые мы хотим предоставить.

Приведенный ниже пример обновлен, чтобы показать это.

Ниже приведен пример из реального проекта.

Требования: Сохраняйте очередь тем, на которые клиент должен быть уведомлен об изменениях. Закажите очередь по метке времени, когда это сообщение было извещено. Не допускайте дублирования имен тем.

Вот рабочая демонстрация:

#include <queue>
#include <string>
#include <chrono>
#include <cassert>
#include <iostream>

using topic_type = std::string;
using timestamp_clock = std::chrono::system_clock;
using timestamp_type = timestamp_clock::time_point;

struct notification {
    topic_type topic;
    timestamp_type timestamp;
};

bool topic_equals(const notification& l, const topic_type& r) {
    return l.topic == r;
}
bool topic_equals(const topic_type& l, const notification& r) {
    return l == r.topic;
}

bool age_after(const notification& l , const notification& r) {
    return l.timestamp > r.timestamp;
}

bool age_after(const notification& l , const timestamp_type& r) {
    return l.timestamp > r;
}

bool age_after(const timestamp_type& l , const notification& r) {
    return l > r.timestamp;
}

struct greater_age
{
    template<class T, class U>
    bool operator()(const T& l, const U& r) const {
        return age_after(l, r);
    }
};

template<class T>
struct pending_queue_traits;

template<>
struct pending_queue_traits<notification>
{
    using container_type = std::vector<notification>;
    using predicate_type = greater_age;
    using type = std::priority_queue<notification, container_type, predicate_type>;
};

class pending_notification_queue
: private pending_queue_traits<notification>::type
{
    using traits_type = pending_queue_traits<notification>;
    using base_class = traits_type::type;

public:


    // export the constructor
    using base_class::base_class;

    // and any other members our clients will need
    using base_class::top;
    using base_class::pop;
    using base_class::size;

    bool conditional_add(topic_type topic, timestamp_type timestamp = timestamp_clock::now())
    {
        auto same_topic = [&topic](auto& x) { return topic_equals(topic, x); };
        auto i = std::find_if(std::begin(c), std::end(c), same_topic);
        if (i == std::end(c)) {
            this->push(notification{std::move(topic), std::move(timestamp)});
            return true;
        }
        else {
            if (timestamp < i->timestamp) {
                i->timestamp = std::move(timestamp);
                reorder();
                return true;
            }
        }
        return false;
    }

private:
    void reorder() {
        std::make_heap(std::begin(c), std::end(c), comp);
    }
};

// attempt to steal only the base class...
void try_to_slice(pending_queue_traits<notification>::type naughty_slice)
{
    // danger lurks here
}
int main()
{
    using namespace std::literals;

    auto pn = pending_notification_queue();

    auto now = timestamp_clock::now();
    pn.conditional_add("bar.baz", now);
    pn.conditional_add("foo.bar", now + 5ms);
    pn.conditional_add("foo.bar", now + 10ms);
    pn.conditional_add("foo.bar", now - 10ms);

    // assert that there are only 2 notifications
    assert(pn.size() == 2);
    assert(pn.top().topic == "foo.bar");
    pn.pop();
    assert(pn.top().topic == "bar.baz");
    pn.pop();

    // try to slice the container. these expressions won't compile.
//    try_to_slice(pn);
//    try_to_slice(std::move(pn));

}

Ответ 5

Контейнеры stl не предоставляют максимально быстро обновляемые очереди с приоритетами.

@Richard Hodges: make_heap требует сложности O (n), а функция push_heap не сообщает вам, где хранился предоставленный элемент, что делает невозможным быстрое обновление одного элемента (для его поиска требуется O (n)).

Я реализовал высокопроизводительную обновляемую очередь с приоритетами (обновление стоит O (log n), в два раза быстрее, чем использование std::set) и сделал ее доступной на github.

Вот как вы обычно используете это:

better_priority_queue::updatable_priority_queue<int,int> pQ;
pQ.push(0, 30);   // or pQ.set(0, 30)
pQ.push(1, 20);
pQ.push(2, 10);

pQ.update(2, 25); // or pQ.set(2, 25)

while(!pQ.empty())
    std::cout << pQ.pop_value().key << ' ';

// Outputs: 0 2 1