Реализация MinMax PriorityQueue с minValue и maxValue в O (1)

Question

Я реализую очередь MinMax Priority Queue на std :: multimap с возможностью иметь несколько значений на ключе, и у меня уже есть функции minKey и maxKey, написанные в O (1) временная сложность (с использованием begin() и end()).

Теперь у меня есть проблема с реализацией minValue и maxValue. Одним из очевидных решений было бы создание структуры данных (например, с помощью std :: set) с помощью только значений этого pqueue и доступа к min и max в O (1).

Очевидно, что недостатком этого решения будет дублированный объем памяти, который я, конечно, не хочу.

Я думаю о решении с указателями на minValue и maxValue соответственно. Вставка в PQ будет простой, просто сравните с этими указателями ... теперь, что насчет удаления?

Вставка: Я могу иметь несколько значений на определенном ключевом

Удаление: Стирает любое значение из определенного ключа (если ключ не существует, генерируется исключение).

Есть ли у вас какие-либо предложения о том, как реализовать minValue и maxValue в O (1) сложности времени?

Заранее спасибо

Answer 1

Давайте резюмировать то, что вы хотите. Вы хотите реализовать двойную очередь приоритетов для пар ключ-значение, которые должны сортироваться в соответствии с двумя различными функциями сравнения. Один, который сравнивает ключевую часть пары и сравнивает значение-часть.

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

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

Если вы чертовски настроены в своем дизайне с несколькими сравнениями, то то, что вы могли бы использовать для реализации очереди, - это контейнер с несколькими индексами. Boost имеет библиотеку таких контейнеров.