priority_queue с динамическими приоритетами

Сколько дискретных значений приоритета вы хотите реализовать? Если их количество невелико (скажем, 256 уровней), то вместо одной приоритетной очереди имеет смысл иметь 256 простых очередей (так в некоторых ОС реализованы планировщики приоритетных процессов). Изначально ваши события, отправленные с приоритетом 1, помещаются в очередь №1. Затем кто-то отправляет событие prio=25, и оно помещается в очередь №25. Читатель считывает событие из самой высокой непустой очереди (в данном случае № 25), а события во всех непустых очередях до 25 перемещаются вверх по слоту (вся очередь № 1 перемещается в очередь № 2 и т. д.). . Я почти уверен, что все это можно сделать за O(k) (где k — количество уровней приоритета), либо с помощью std::move, либо с помощью std::swap, либо с помощью list::splice.

Перемещение очереди № 1 в позицию, ранее занятую очередью № 2, должно быть O (1) с перемещением или обменом, и если остаток очереди prio = 25 не пуст, то перемещение всех элементов вверх из очереди № 24 в очередь № 25. равно O(1), если используются очереди std::list и list::splice().

std::priority_queue не имеет возможности реорганизовать себя, если ваши критерии сортировки изменятся. Вам придется управлять им самостоятельно.

Я бы предложил просто использовать std::vector и один из двух подходов для его обслуживания.

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

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

Если вам нужно изменить приоритеты, вы не можете использовать priority_queue, потому что нет интерфейса для доступа ко всем элементам. Лучше с std::vector и std::make_heap.

Структура ACE, вероятно, предоставляет что-то, что могло бы вам помочь. См. классы ACE_Dynamic_Message_Queue и ACE_Laxity_Message_Strategy. Я еще не работал с этими классами, поэтому не могу привести пример. Но идея такова:

• У вас есть очередь сообщений, совместно используемая двумя потоками
• В потоке производителя вы заполняете очередь сообщений
• Очередь сообщений будет вставлять новые сообщения в нужное место в соответствии со стратегией.
• В потоке получателя вы только что прочитали самый верхний элемент из очереди.

Прежде всего, некоторые комментарии к вашему коду:

1. Вы не можете гарантировать, что оператор ‹ будет вызываться только один раз для каждого объекта при каждом удалении (его можно вызывать как вверху, так и при извлечении, или при нажатии, или...).
2. Вы повышаете приоритет локальной копии в операторской функции, а не копии в очереди
3. Здесь нет необходимости использовать дружественные функции для объявления оператора‹.

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

В основном он копирует размер и пустую обычную очередь и создает 2 новых метода для вставки и получения запросов (push, pop и top отключены). Вставьте только вызовы push, получите вызовы как top, pop и обновите все приоритеты, используя вызов for_each в локальном контейнере. Наконец, предоставляется небольшая программа, показывающая функциональность.

Кроме того, он основан на управлении кучей в pop и push. Насколько я знаю, это будет работать правильно из-за линейного изменения каждого элемента, порядок не меняется между нажатиями;).

#include <algorithm>
#include <queue>
#include <iostream>

class Query
{
public:
    Query( std::string p_stQuery, double priority = 1.0) : stQuery( p_stQuery ) , fPriority(priority), fStartPriority(priority) {};
    std::string getQuery() const
    {
        return stQuery;
    };
    void conditionalIncrease( const Query& otherQuery )
    {
        if (fStartPriority < otherQuery.fStartPriority) fPriority += INCREASE_RATE;
    }

    bool operator < ( const Query& rhs )  const
    {
        return fPriority < rhs.fPriority;
    }

    double getPriority() const
    {
        return fPriority;
    }
private:
    static const double INCREASE_RATE = 0.2;
    double fPriority; // current priority
    double fStartPriority; // initialised priority
    std::string stQuery;
};

class QueryIncreaser
{
private:
    Query base;
public:
    QueryIncreaser(const Query& q) : base(q) {}
    void operator() (Query& q)
    {
        q.conditionalIncrease(base);
    }
};

class QueryQueue : private std::priority_queue<Query>
{
public:
    void insertQuery(const Query& q)
    {
        push(q);
    }
    Query getQuery()
    {
        Query q = top();
        pop();
        QueryIncreaser comp(q);
        for_each(c.begin(), c.end(), comp);
        return q;
    }
    bool empty() const
    {
        return std::priority_queue<Query>::empty();
    }
    size_t size() const
    {
        return std::priority_queue<Query>::size();
    }
};

int main ()
{
    Query a("hello"), b("world",2.);
    QueryQueue myQueue;
    myQueue.insertQuery(a);
    myQueue.insertQuery(b);
    while (!myQueue.empty())
    {
        std::cout << myQueue.getQuery().getPriority() << std::endl;
    }
    return 0;
}

Я бы пошел с std::deque и собрал все остальное самостоятельно (если вы просто используете C++ без внешних библиотек, которые могут помочь). Проблема с другими предложениями make_heap (которые использует std::priority_queue) заключается в том, что они нестабильны. Отсутствие стабильности в данном случае означает, что упорядочение не гарантируется в пределах приоритета и возможно голодание.