Qual è un modo efficiente ed elegante per aggiungere un singolo elemento a un set immutabile?

Question

Ho un set immutabile (cast come Set<Integer>) che potenzialmente contiene molti elementi. Ho bisogno di una collezione che contenga gli elementi di quella serie più un elemento aggiuntivo. Ho un codice kludgy per copiare il set, quindi aggiungo l'elemento, ma sto cercando The Right Way che mantenga le cose il più efficienti possibile.

Ho Guava disponibile, anche se non ne ho bisogno.

Answer 1

Non sei sicuro di prestazioni, ma è possibile utilizzare di ImmutableSet.Builder Guava:

import com.google.common.collect.ImmutableSet 

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

Naturalmente si può anche scrivere da soli un metodo di supporto per questo:

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

Se il Set è immutabile, non vedo alcun modo per farlo tranne copiare il Set, e quindi aggiungere il nuovo elemento. Ricorda, copiare un set è facile come passare il set base alla funzione costruttore quando si crea il nuovo set.

Answer 3

Sto vivendo una dissonanza cognitiva quando leggo "immutabile" e "aggiungi" nella stessa frase. È possibile aggiungere un nuovo elemento alla fine di una copia mutabile dei valori immutabili, ma non è possibile modificare il set immutabile. Non so nulla di elegante.

Answer 4

Sono disponibili tre opzioni.

• Utilizzare un set mutabile.
• Verificare che l'elemento non sia già presente, se non creare una copia del set e aggiungere un elemento.
• Creare un set di wrapper che include il set precedente e l'elemento.

A volte uno BitSet è una scelta migliore di Set<Integer> in base alla distribuzione dei valori.

Answer 5

Si potrebbe considerare Sets.union(). La costruzione sarebbe più veloce, ma usare più lentamente.

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 6

Quando si desidera migliorare le prestazioni di una copia completa, e si dispone di un ordinamento sugli elementi, è possibile utilizzare un involucro effettivamente immutabile attorno a uno B+ tree per ottenere buone prestazioni dell'insieme incrementale.

L'aggiunta di un elemento a un albero B + richiede il tempo O (log (n)) e l'allocazione incrementale, non O (n) come si ottiene con ImmutableSet.builder().addAll(...).add(...).build(). Ciò significa che la creazione di un set da n aggiunte incrementali è O (n * log (n)), non O (sqr (n)).

Questo answer ha un puntatore a una libreria jdbm, quindi potrebbe valere la pena guardare jdbm:jdbm.