Senza modificare l'interfaccia visibile in Set.h possiamo cambiare l'implementazione. Questa volta useremo la memoria dinamica e rappresenteremo set ed oggetti come strutture:
count tiene traccia del numero di elementi in un set. Per un elemento, count registra quante volte questo elemento è stato aggiunto al set. Se decrementiamo count ogni volta che un elemento viene passato alla funzione drop() e rimuoviamo l'elemento una volta che count vale 0, avremo un bag (paniere), ossia un set dove gli elementi hanno un contatore di riferimento.
Poichè useremo la memoria dinamica per rappresentare set ed oggetti, avremo bisogno di inizializzare i descrittori Set e Object in modo che new() possa determinare quanta memoria riservare:
new() è molto più semplice:
delete() può passare il suo argomento direttamente a free() - in C ANSI il puntatore nullo può essere passato a free().
add() incrementa il contatore di riferimento dell'elemento e il numero di elementi presenti nel set.
find() ancora una volta controlla se l'elemento punta al set appropriato:
contains() si basa su find() e rimane inalterata
Se drop() trova il suo elemento nel set, decrementa il contatore relativo all'elemento e il numero di elementi presenti nel set. Se il contatore raggiunge lo zero, l'elemento viene rimosso dal set.
Possiamo pertanto implementare una nuova funzione count() che ritorna il numero di elementi in un set:
Sarebbe stato più semplice lasciare che l'applicazione leggesse il componente, contasse direttamente ma ci preme sottolineare che il metodo che abbiamo utilizzato permette di non rivelare la rappresentazione del set. L'overhead dovuto alla chiamata ad una funzione è praticamente insignificante rispetto al potenziale "danno" che un applicazione potrebbe fare se fosse in grado di modificare/sovrascrivere un valore critico.
I Bag, o panieri, si comportano diversamente dai set: un elemento può essere aggiunto più di una volta. Un elemento scompare dal set se viene eliminato tante volte quante è stato aggiunto. La nostra applicazione nel paragrafo 1.6 aggiunge l'oggetto a due volte nel set. Dopo che viene effettuato il drop() una volta dal set, la funzione contains() trova l'elemento ancora nel set. Il programma di test avrà pertanto come output
Conclusioni
Per un tipo di dato astratto nascondiamo completamente ogni dettaglio implementativo, come ad esempio la rappresentazione dei singoli dati. Il codice dell'applicazione accede solamente all'header file dove si trova il descrittore del puntatore che rappresenta il tipo di dato e dove le operazioni sul tipo di dato sono dichiarate come funzioni. Le funzioni accettano pertanto parametri e ritornano puntatori generici. Il descrittore del puntatore viene passato ad una funzione generale new() per ottenere un puntatore al dato, e questo puntatore viene poi passato alla funzione generale delete() per riciclare le risorse associate.
Normalmente, ogni tipo di dato astratto viene implementato in un singolo file sorgente. Idealmente, non ha accesso alla rappresentazione di altri tipi di dato. Il descrittore del puntatore punta normalmente ad almento una costante size_t indicante lo spazio richiesto dall'elemento del dato.