Список без дубликатов или упорядоченного набора

Есть ли библиотека, которая предоставляет структуру данных, которая сохраняет порядок элементов и не содержит дубликатов? И существует ли собственное имя для такой структуры данных?

Я ожидаю, что он будет вести себя как список с nub, применяемый после каждой операции на нем. Конечно, я не ожидаю, что это будет реализовано как неэффективно.

Ответы

Ответ 1

Здесь одно решение:

Используйте fingertree с моноидом Set в качестве вашей меры. Затем на вставках сначала проверьте членство, используя measure вашего полного пальца. Это дает вам O(log(n)) cons и snoc, O(1) удаляет.

Здесь другое решение:

Соедините обычный список с нормальным Set и получите в основном тот же эффект. Вы получаете более высокие константы, но O(log(n)) удаляет.

Вот вопрос: что вы хотите, чтобы вставить дубликат? Следует ли сохранить существующую позицию? Новая позиция? Приоритетные очереди могут быть близки к тому, что вы хотите, в зависимости.