Java ha questo sotto forma di un set ordinato. Non ho nulla in C++, ma non è così difficile da implementare. Quello che i ragazzi del Sun hanno fatto con la classe Java è stato quello di estendere la tabella hash in modo tale che ogni elemento fosse contemporaneamente inserito in una tabella hash e conservato in un doppio elenco collegato. Ci sono pochissime spese generali in questo, specialmente se si preallocano gli elementi utilizzati per costruire l'elenco collegato.
Se io dovessi scrivere una classe che utilizzava un vettore privato per archiviare gli elementi o implementare un hashtable nella classe. Quando un elemento deve essere inserito nel set, controlla se è nella tabella hash e se lo sostituisci, opzionalmente sostituiscilo. Quindi trova il vecchio elemento nella tabella hash, aggiorna l'elenco in modo che punti al nuovo elemento e il gioco è fatto.
Per inserire un nuovo elemento si fa lo stesso, tranne che è necessario utilizzare un nuovo elemento nell'elenco - non è possibile riutilizzare quelli vecchi.
Per eliminare un elemento, si riordina l'elenco in modo che punti intorno ad esso e liberi l'elemento dell'elenco.
Nota che dovrebbe essere possibile ottenere la parte dell'elenco collegato in cui l'elemento che ti interessa è direttamente dall'elemento in modo da non dover camminare sulla catena ogni volta che devi spostarti o cambia un elemento.
Se si prevede di avere molti di questi articoli modificati durante l'esecuzione del programma, è possibile mantenere un elenco degli elementi dell'elenco, in modo tale che si possa semplicemente assumere la testa di questo elenco, anziché allocare memoria ogni volta che si devo aggiungere un nuovo elemento.
Si potrebbe voler osservare l'algoritmo dei collegamenti di danza.
La soluzione di Greg nella domanda duplicata non sembra richiedere il wrapper. Grazie per avermi indicato nella direzione più indolore, però. –