Вариант очереди приоритетов

Question

Мне нужна некоторая приоритетная очередь для хранения пар <key, value>. Значения уникальны, но ключей нет. Я буду выполнять следующие операции (наиболее часто встречающиеся в первую очередь):

1. случайный ввод;
2. извлечение (и удаление) всех элементов с наименьшим ключом.
3. случайное удаление (по значению);

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

На данный момент я использую unsorted std::list. Вставка выполняется простым нажатием новых элементов на спину (O (1)). Операция 2 сортирует список с list::sort (O (N * logN)) перед выполнением фактического поиска. Удаление, однако, это O (n), что немного дорого.

Любая идея лучшей структуры данных?

Answer 1

Итак, я проверил множество вариантов и в итоге получил что-то, основанное на идее Matthieu M..В настоящее время я использую std::map<key_type, std::list<value_type> >, где value_type содержит std::list<value_type>::iterator для себя, что полезно для удаления.

Снятие необходимо проверить, если вектор пуст, что подразумевает запрос map и, возможно, звонок по номеру erase. В худшем случае сложность заключается в том, когда ключи различны, O(logN) для вставки, O(1) для извлечения и O(logN) для снятия. У меня очень хорошие экспериментальные результаты по сравнению с другими альтернативами на моей тестовой машине.

Использование std::vector менее эффективно как с точки зрения теоретической сложности (O (N) в худшем случае для удаления, когда ключи идентичны), так и для экспериментов, которые я выполнял.

Answer 2

Если вы используете Visual Studio, у них есть hash_multimap. Я также должен добавить, что Boost имеет неупорядоченный мультимаг, here. Если вам нужна заказанная мультимарма, STL multimap или заказанный множитель STL multiset

Answer 3

Можете ли вы отменить заказ коллекции, т. Е. Сохранить их в <value, key>?

Тогда вы могли бы просто использовать std::map имея O(logn) время для вставки O(n) для удаления (пересекающего всю коллекция) и O(logn) для случайного удаления значения (которое было бы ключом указанной карты).

Если бы вы могли найти map реализации, основанный на хэши вместо деревьев (как std::map) времена было бы еще лучше: O(1), O(n), O(1).

Answer 4

std :: multimap похоже, что вы ищите.

Он сохранит ваши объекты, упорядоченные по ключу, позволит вам получить наименьшее/максимальное значение ключа (begin(), rbegin()) и весь объект с заданным ключом (equal_range, lower_bound, upper_bound).

(EDIT: если у вас есть только несколько пунктов, скажем, менее 30, вы должны также проверить работу только с помощью Deque или вектора)

Answer 5

Если я хорошо понял, вы цель производительности иметь быстрые (1) и (3) и (2) не так важны. В этом случае и учитывая, что значения уникальны, почему бы просто не получить std::set<value> и выполнить последовательный поиск (2)? У вас будет O (log n) для (1) и (3) и O (n) для (2). Еще лучше, если ваш STL имеет std::hash_set, вы должны быть близки к O (1) для (1) и (3).

Если вам нужно что-то лучше, чем O (n) для (2), альтернативой может быть набор приоритетных очередей.

Answer 6

Когда вам нужно сделать заказ, используйте заказанный контейнер. Нет смысла оплачивать стоимость сортировки позже.

Ваше текущее решение:

• Вставка O(1)
• индексирование O(N log N)
• Удаление O(N) (который так же хорошо, как вы можете получить без сохранения другого индекса там)

Просто используя a std::multi_map, вы могли бы:

• Вставка O(log N)
• индексирование O(log N) < - гораздо лучше, не так ли? Нам нужно найти конец диапазона
• Удаление O(N)

Теперь, вы могли бы сделать немного лучше с std::map< key, std::vector<value> >:

• Вставка O(log M) где M является число различных ключей
• Возвращение O(1) (begin ожидается на постоянной основе)
• Снятие O(N)

Вы не можете надавить на случайное удаление ... если только вы не захотите сохранить там еще один индекс. Например:

typedef std::vector<value_type> data_value_t; 
typedef std::map<key_type, data_value_t> data_t; 

typedef std::pair<data_t::iterator,size_t> index_value_t; 
    // where iterator gives you the right vector and size_t is an index in it 

typedef std::unordered_map<value_type, index_value_t> index_t; 

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

• Вставка O(log M) -> сложность вставки в хэш-карта является O(1)
• индексирование O(N/M) -> нужно отменить индексных все значения в векторе, там в среднем
• удаление O(N/M)N/M -> нахождение в хэш-карте O(1), разыменования O(1), удаление из вектора O(N/M), потому что нам нужно перенести примерно половину содержимого вектора. Использование list даст O(1) ... но может быть не быстрее (зависит от количества элементов из-за недостатка памяти).

Также учтите, что сложность хэш-карты является амортизированной. Запустите перераспределение, потому что вы перегрузили коэффициент загрузки, и эта конкретная вставка займет очень много времени.

Я бы пошёл с std::map<key_type, std::vector<value_type> > вместо вас. Это лучший удар для доллара.