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

Question

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

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

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

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

Есть идеи о лучшей структуре данных?

Answer 1

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

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

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

Просто используя std::multi_map вы можете получить:

• Вставка O(log N)
• Извлечение O(log N) <- намного лучше, не так ли? Нам нужно найти конец диапазона </li>
• Снятие 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)
• Retrieval O(N/M) -> необходимо проиндексировать все значения в векторе, в среднем N/M
• Удаление O(N/M) -> поиск в хэш-карте O(1), разыменование O(1), удаление из вектора O(N/M), потому что нам нужно сместить примерно половину содержимого вектора. Использование list даст O(1) ... но может быть не быстрее (зависит от количества элементов из-за компромисса памяти).

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

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

Answer 2

Можете ли вы отменить порядок сбора, т.е. сохранить их в <value, key> порядке?

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

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

Answer 3

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

Answer 4

Хорошо, поэтому я протестировал множество вариантов и в итоге получил что-то, основанное на идее Матье М. . В настоящее время я использую 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 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

std :: multimap - это то, что вы ищете.

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

(РЕДАКТИРОВАТЬ: если у вас есть всего несколько элементов, скажем, менее 30, вы также должны проверить производительность, просто используя деку или вектор)