C ++ boost - есть ли контейнер, работающий как очередь с прямым доступом к ключу?

Question

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

Если такого контейнера нет, как вы думаете, это можно реализовать с помощью очереди и карты?

Answer 1

Boost multi-index предоставляет этот тип контейнера.

Чтобы реализовать это самостоятельно, я бы, вероятно, выбрал map, значения которого состоят из узла связанного списка плюс полезная нагрузка. Узел списка может быть свернут вручную или может быть Boost intrusive .

Обратите внимание, что главное в адаптере queue - скрыть большую часть интерфейса Sequence, но вы хотите возиться с деталями, которые он скрывает. Поэтому я думаю, что вы должны стремиться воспроизвести интерфейс queue (слегка измененный с вашей измененной семантикой для push), а не использовать его на самом деле.

Answer 2

Очевидно, что вы можете сделать это просто с помощью контейнера, похожего на очередь, но вам придется тратить O(n) время на каждую вставку, чтобы определить, присутствует ли элемент уже. Если вы реализуете свою очередь на основе чего-то вроде std::vector, вы можете использовать бинарный поиск и в основном ускорить вставку до O(log n) (для этого все равно потребуется O(n) операций, когда перераспределение памяти выполнено).

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

---

Во втором сценарии вы можете захотеть хранить ваши элементы дважды в разных контейнерах - исходная очередь и что-то вроде карты (или иногда hashmap может работать лучше). Карта используется только для определения того, присутствует ли элемент в контейнере или нет - и если ДА, вам придется обновить его в своей очереди.

По сути, это дает нам O(1) сложность для поиска по хэш-карте (в реальном мире это может стать уродливее из-за коллизий - хеш-карты не очень хороши для определения существования элемента) и O(1) время вставки для случая, когда обновление не требуется и требуется O(n) время вставки для обновления дела.

Исходя из процента фактических операций обновления, фактическая производительность вставки может варьироваться от O(1) до O(n), но эта схема определенно превзойдет первую, если количество обновлений достаточно мало.

Тем не менее, вы должны вставить свои элементы в два контейнера одновременно, и то же самое должно быть сделано, если элемент удален, и я бы дважды подумал: «Мне действительно нужно это повышение производительности?».

Answer 3

Я вижу простой способ сделать это с помощью очереди и, возможно, карты.

Определите своего рода оператор == для ваших элементов.

Затем просто создайте очередь и ищите свой элемент каждый раз, когда вы хотите вставить его.

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