What is an efficient and elegant way to add a single element to an immutable set?

Question

I have an immutable set (cast as a Set<Integer>) that potentially contains many elements. I need a Collection that contains the elements from that set plus one additional element. I have kludgy code in place to copy the set, then append the element, but I'm looking for The Right Way that keeps things as efficient as possible.

I have Guava available, though I do not require its use.

Answer 1

Not sure about performance, but you can use Guava's ImmutableSet.Builder:

import com.google.common.collect.ImmutableSet

// ...
Set<Integer> newSet = new ImmutableSet.Builder<Integer>()
                                .addAll(oldSet)
                                .add(3)
                                .build();

Of course you can also write yourself a helper method for that:

public static <T> Set<T> setWith(Set<T> old, T item) {
  return new ImmutableSet.Builder<T>().addAll(old).add(item).build();
}

// ...
Set<Integer> newSet = setWith(oldSet, 3);

Answer 2

Using Java 8 you can also use streams for that effect

Stream.concat(oldSet.stream(),
              Stream.of(singleElement))
      .collect(Collectors.toSet())

By the way since JDK 10, the Collectors also allow to accumulate to immutable types (the same as the ones created by the static factories like Set.of()) :

Stream.concat(oldSet.stream(),
              Stream.of(singleElement))
      .collect(Collectors.toUnmodifiableSet())

Answer 3

You might consider Sets.union(). Construction would be faster, but use slower.

public static <T> Set<T> setWith(Set<T> old, T item) {
  return Sets.union(old, Collections.singleton(item);
}

(com.google.common.collect.Sets & java.util.Collections)

Answer 4

If the Set is immutable, I don't see any way to do it other than copy the Set, and then add your new element. Remember, copying a set is as easy as passing the base set to the constructor function when creating the new set.

Answer 5

You have three options.

• Use a mutable set.
• Check the element isn't already present, if not create a copy of the set and add an element.
• Create a wrapper set which includes the previous set and the element.

Sometimes a BitSet is a better choice than Set<Integer> depending on the distribution of your values.

Answer 6

When you want better performance than a full copy, and you have an ordering over elements, you can use an effectively immutable wrapper around a B+ tree to get good incremental set performance.

Adding an item to a B+ tree requires O(log(n)) time and incremental allocation, not O(n) as you get with ImmutableSet.builder().addAll(...).add(...).build(). This means that building a set from n incremental adds is O(n*log(n)), not O(sqr(n)).

This answer has a pointer to a jdbm library so it might be worth looking at jdbm:jdbm.

Answer 7

I'm experiencing cognitive dissonance when I read "immutable" and "add to" in the same sentence. You can add a new element to the end of a mutable copy of the immutable values, but you can't modify the immutable set. I don't know of anything elegant.