STL-подобный Java Red-black tree/TreeSet/Map и связанные списки с безотказными/безопасными итераторами

Question

Я ищу библиотеку с красно-черным деревом и реализацией Linked List, предлагающую итераторы, которые не поддаются быстрой , Я хотел бы иметь такую ​​же функциональность, как и я в C++ с использованием STL и что:

• вставки в дереве/списке не отменяет никаких итераторы
• удаление аннулирует только итератор, указывающий на элемент бытия удален
• можно каким-то образом сохранить «позицию» итератора и ссылки на значение она, указывая на

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

• получение соседнего элемента в связанном списке/красно-черном дереве до некоторого сохраненного значения в O (1) не
• пакетных вставок/абсорбция (без ограничения, такие, как один удаления за приращение позиции)
• разделительный список в O (1) через положение итератора
• более эффективные удаления при сохранении позиции итератора (например, путем сохранения итераторов в позиции в связанном списке, удаление O (1), а не O (N))

Мне также понравилась бы эта библиотека/исходный код/​​реализация, чтобы иметь некоторую лицензию, совместимую с Apache/GPL, и она достаточно расширяема (поэтому я могу внести свои изменения для реализации некоторых операций, таких как примеры из приведенных выше примеров).

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

Answer 1

Это довольно легко реализовать. Итератора должен сделать три вещи:

1. Только хранить две ссылки, одна на «текущий» элемент и один к внешнему объекту контейнера (сгусток хранить ссылку корневой (дерево) или головку/хвосты (список)).

2. Уметь определять, является ли упомянутый элемент действительным (легко, если родительский указатель имеет значение null (дерево) или prev/next указатели являются нулевыми (список), то это лучше будет корнем дерева или головой/хвостом списка). Бросьте что-нибудь, когда какие-либо операции будут предприняты на недействительном итераторе.

3. Уметь находить предыдущий/следующий элемент.

Есть несколько подводных камней: для списка, это будет боль, чтобы поддержать NEXTINDEX в java.util.ListIterator() и PREVINDEX() эффективно, и, конечно же, теперь у вас есть проблемы с одновременными изменениями! Вот пример того, как все может испортиться:

while (it.hasNext()) { 
    potentially_delete_the_last_element() 
    it.next() // oops, may throw NoSuchElementException. 
} 

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