STL-подобная Java Красно-черное дерево / TreeSet / Карта и связанные списки с небыстрым / безопасным итератором

Question

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

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

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

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

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

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

Answer 1

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

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

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

3. Уметь найти элемент prev / next.

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

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

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