Dipende dall'implementazione che ne fanno i compilatori. Su wikipedia c'è scritto che potrebbero usare una bitmask (quindi tutte le operazioni hanno complessità Theta(1)).
In Java, ad esempio, ne esiste un'implementazione che usa una hash table, che espone metodi di add, remove e contains ancora in tempo costante per strutture dati qualsiasi (ammettendo che la funzione di hash sia "perfetta" rispetto agli elementi inseriti).
|