Есть ли библиотека, которая предоставляет структуру данных, которая сохраняет порядок элементов и не содержит дубликатов? И существует ли собственное имя для такой структуры данных?
Я ожидаю, что он будет вести себя как список с nub, применяемый после каждой операции на нем. Конечно, я не ожидаю, что это будет реализовано как неэффективно.
Здесь одно решение:
Используйте fingertree с моноидом Set в качестве вашей меры. Затем на вставках сначала проверьте членство, используя measure вашего полного пальца. Это дает вам O(log(n)) cons и snoc, O(1) удаляет.
Здесь другое решение:
Соедините обычный список с нормальным Set и получите в основном тот же эффект. Вы получаете более высокие константы, но O(log(n)) удаляет.
Вот вопрос: что вы хотите, чтобы вставить дубликат? Следует ли сохранить существующую позицию? Новая позиция? Приоритетные очереди могут быть близки к тому, что вы хотите, в зависимости.