Java: структура данных копирования при записи?

Question

Есть ли в Java что-то, что реализует что-то вроде следующего

interface MSet<T> extends Iterable<T> {
    /**
     * return a new set which consists of this set plus a new element.
     * This set is not changed.
     */
    MSet<T> add(T t);

    /**
     * return a new set which consists of this set minus a designated element.
     * This set is not changed.
     */
    MSet<T> remove(T t);
}

edit: я хочу что-то вроде CopyOnWriteArraySet, за исключением того, что класс является изменяемым, и я хочу что-то неизменное, позволяющее создавать новый набор Причина этого в том, что мне нужно раздать ссылки на старый набор и оставить их неизменными.

edit 2: как Scala реализует scala.collection.immutable.Set ? Мне нужно такое поведение, просто я не хочу впитывать всю Scala только для этого.

Answer 1

Используйте библиотеку Google Collections Immutable* для всех ваших постоянных потребностей в коллекции. Я полагаю, вам понадобится легкий обернутый класс - который можно очень легко сделать с помощью Forwarding* (также в GC) - который порождает новые неизменяемые (или изменяемые, что угодно) операции добавления / удаления. Наконец, если вашим модификациям не нужно самим создавать новые модификации, вы можете реализовать эти операции, используя различные опции в библиотеках вспомогательных статических коллекций в GC (Iterables, Lists, Sets и т.д.), чтобы получить представления (переустановки). : объединение, пересечение, фильтр).

edit: однако, Google-код сейчас очень медленный - возможно, придется немного подождать, чтобы проверить это.

Answer 2

В Java существуют структуры копирования при записи, например, CopyOnWriteArrayList , однако API немного отличается от предложенного вами; вместо того, чтобы возвращать новый объект, он имеет тот же API, что и другие коллекции, но просто создает отдельную копию массива внутри. '

Нет готового типа с API, который вы хотите; однако, это должно быть довольно тривиально для реализации; просто продублируйте коллекцию, выполните мутацию с дубликатом и верните ее.

Answer 3

CopyOnWriteArraySet аналогично. Однако копирование является внутренним, поэтому оно не возвращает ссылку на новый объект.