У меня есть рабочий класс, и я могу отправить рабочие места работнику.Работник сохраняет эти задания и запускает их последовательно в порядке приоритета (приоритет может быть любым без знака int в основном).В этом случае std :: priority_queue или даже std :: set / map могут использоваться для хранения заданий, упорядоченных по приоритету, и тогда работник сможет извлечь их в порядке O (1).Добавление заданий будет O (log N).
Теперь у меня есть требование изменить приоритет любого отправленного задания.В случае std :: set / map мне нужно удалить и добавить задание с другим приоритетом.Это будет O (log N) и, кроме того, с помощью set / map он перераспределяет узлы внутри системы (хотя этого можно было бы избежать с помощью C ++ 17).Что делает это необычным, так это то, что в моем случае я буду обновлять приоритеты работы гораздо чаще, чем планировать или выполнять их.По сути, я мог бы запланировать задание один раз, и прежде чем оно будет выполнено, я могу закончить обновление его приоритета тысячи раз.Фактически, приоритеты каждой работы будут меняться примерно 10-20 раз в секунду.В моем случае достаточно безопасно предположить, что в очереди у меня будет не более 10 тысяч заданий.В начале моего процесса я ожидаю, что он всегда будет расти примерно до 10 тыс. Заданий, и, поскольку эти задания удаляются, очередь должна в конечном итоге все время оставаться почти пустой, и иногда будет добавляться 10-50 новых заданий, но не должно растиболее 1000 рабочих мест.Рабочие места будут удалены со скоростью несколько рабочих мест в секунду.Из-за моего странного требования этого частого обновления приоритетов std :: priority_queue или набор не кажутся подходящими.Простой std :: list кажется лучшим выбором: изменение приоритета или обновление / удаление - это O (1), а когда мне нужно удалить задания, это O (N), чтобы просмотреть весь список, чтобы найти элемент с наивысшим приоритетом, что должно происходить режечем изменение приоритетов.
Еще одно наблюдение, что, хотя приоритеты работы часто меняются, эти изменения не обязательно приводят к изменению порядка, например, я мог бы просто обновить ключевой элемент моего набора (отбрасывая константность или создавая ключизменяемый?), если это изменение все еще сохранит этот измененный элемент между левым и правым узлами.Что бы вы предложили для такой приоритетной очереди?Все буст-контейнеры или пользовательские структуры данных в порядке.
В случае набора / карты я использую приоритет в качестве ключа.Чтобы сделать ключи уникальными в моем случае, каждый ключ на самом деле состоит из двух целых чисел: порядкового номера задания (полученного из atomic int, который я увеличиваю для каждого нового запроса) и фактического номера приоритета.Таким образом, если я добавлю несколько заданий с одинаковым приоритетом, они будут выполнены в том порядке, в котором они были запланированы, так как порядковые номера сохранят их в порядке.