CODEWITHSUNDEEP
javaguava
Max
Max

Reputation: 11607

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

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.

Upvotes: 46

Views: 36345

Answers (7)

bric3
bric3

Reputation: 42223

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())

Upvotes: 23

Mike Samuel
Mike Samuel

Reputation: 120516

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.

Upvotes: 1

Darren Gilroy
Darren Gilroy

Reputation: 2121

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)

Upvotes: 8

Niklas B.
Niklas B.

Reputation: 95318

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);

Upvotes: 45

Peter Lawrey
Peter Lawrey

Reputation: 533530

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.

Upvotes: 4

duffymo
duffymo

Reputation: 308813

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.

Upvotes: -3

hvgotcodes
hvgotcodes

Reputation: 120198

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.

Upvotes: 2

Related Questions