Упорядоченная структура данных, позволяющая эффективно удалять дубликаты

Question

Мне нужна структура данных, которая

• Должен быть заказан (добавление элементов a, b and c к пустой структуре приведет к тому, что они будут в позициях 0, 1 and 2).
• Позволяет добавлять повторяющиеся предметы. Это, я могу иметь список с a, b, c, a, b.
• Позволяет удалить все вхождения данного элемента (если я сделаю что-то вроде delete(1), он удалит все вхождения 1 в структуре). Если у меня есть элементы a, b, c, d, c, e и удалить элемент c, я должен получить a, b, d, e.
• Мне просто нужно получить доступ к элементам двумя способами. Во-первых, при удалении данного запаха (см. Пункт выше), а во-вторых, когда я преобразую данные, которые у меня есть в этой структуре, в список.

Я не могу действительно выбрать, какая здесь самая лучшая структура данных. Сначала я думал о чем-то вроде List (проблема заключается в операции O(n) при удалении элементов), но, может быть, я что-то упустил? Как насчет деревьев / куч? Hashtables / карты

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

Спасибо

Answer 1

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

Что-то вроде двусвязного списка с дополнительным nextEqualItemPtr в нем и HashMap, указывающим на первый из каждого элемента.

Затем вы можете быстро найти первый «b» для удаления и следовать всем nextEqualItemPtrs, чтобы удалить их всех (двойные ссылки, так что легко сохранить список в целости). Накладные расходы на самом деле держать карту в актуальном состоянии. Список nextEqualItemPtr нового элемента может просто указывать на узел, возвращаемый map.put (key) .nextEqualItemPtr

Сначала я определенно использовал бы что-то простое и включал бы такие вещи, только если / когда это слишком медленно.

Answer 2

Bag интерфейс Apache Collections ( homepage ) должен соответствовать вашим требованиям. Он имеет много реализаций, так что, возможно, он также отслеживает порядок вставки (ваша первая точка).

И имеет:

• removeAll
• remove(count)

Это также довольно быстро по сравнению с использованием обычных LinkedList или ArrayList, но я не уверен насчет вставленных индексов элементов.

Это описывается как

Интерфейс мешка для коллекций, имеющих количество копий каждого объекта