Una possibilità è fare sì che la superclasse che contiene l'algoritmo di ordinamento erediti da una classe completamente virtuale (o classe astratta virtuale*) che dichiara i metodi per accedere agli elementi, così che qualunque container che erediti dalla classe dell'algoritmo di ordinamento sia obbligato ad implementare questi metodi virtuali puri per poter essere istanziabile.
* in linguaggi che le supportano sarebbe un'interfaccia - e in C++ è bene che segua le regole delle interfacce: niente campi di dati in modo da evitare casini con l'ereditarietà multipla, potenzialmente solo funzioni virtuali pure.
codice:
template <typename T>
class RandomAccessibleContainer
{
public:
virtual T & Element(size_t Index) = 0;
virtual size_t Count () = 0;
};
template <typename T>
class QuickSortable : RandomAccessibleContainer<T>
{
public:
void Sort(); // implementata nel .cpp
};
template <typename T>
class Vector : QuickSortable<T>
{
public:
// ...
virtual T & Element(size_t Index); // implementata nel .cpp; l'avere questa funzione effettivamente definita consente a Sort() di funzionare correttamente
virtual size_t Count (); // idem con patate
}
Naturalmente per avere uno schema più flessibile (per container che ad esempio non consentono un accesso casuale, come le liste) un bisogna implementare un po' più di astrazione:
codice:
// Classe base per tutti i container in cui si può accedere a qualunque elemento direttamente
template <typename T>
class RandomAccessibleContainer
{
public:
virtual T & Element(size_t Index) = 0;
virtual size_t Count () = 0;
};
// Classe base per tutti i container in cui si può accedere agli elementi solo sequenzialmente
template <typename T>
class SequentiallyAccessibleContainer
{
public:
virtual bool NextElement() = 0;
virtual bool PreviousElement() = 0;
virtual T & Element() = 0;
virtual size_t Count () = 0;
};
// Classe base per tutte le classi che implementano un sort
class Sortable
{
public:
virtual void Sort() = 0;
};
template <typename T>
class QuickSortable : Sortable, RandomAccessibleContainer<T> // Il quicksort richiede un accesso casuale agli elementi
{
public:
virtual void Sort(); // questo è effettivamente implementato nel .cpp
};
template <typename T>
class StrangeSortable : Sortable, SequentiallyAccessibleContainer<T> // Supponiamo che al nostro StrangeSort sia più efficiente del quicksort se si può solo andare avanti e indietro nel container
{
public:
virtual void Sort(); // questo è effettivamente implementato nel .cpp
};
template <typename T>
class Vector : QuickSortable<T>
{
public:
// ...
virtual T & Element(size_t Index); // implementata nel .cpp; l'avere questa funzione effettivamente definita consente a Sort() di funzionare correttamente
virtual size_t Count (); // idem con patate
};
template <typename T>
class DoublyLinkedList : StrangeSortable<T>
{
public:
// ...
virtual bool NextElement(); // tutte implementate nel .cpp, consentono a Sort() di funzionare
virtual bool PreviousElement();
virtual T & Element();
virtual size_t Count ();
};
D'altra parte, in un'accezione meno stretta di OOP si possono vedere gli algoritmi come funzioni libere che operano su container che hanno determinate caratteristiche. In tal caso, eviteremmo in blocco tutte le classi "***Sortable" e i container erediterebbero direttamente dalla classe-base che descrive il tipo di accesso che si può avere ai loro elementi. Si potrebbe implementare quindi una funzione Sort con gli overload adeguati ad ogni tipo di ***AccessibleContainer.
codice:
// SequentiallyAccessibleContainer e RandomAccessibleContainer come nell'esempio precedente
template <typename T>
class Vector : RandomAccessibleContainer<T>
{
public:
// ...
virtual T & Element(size_t Index); // implementata nel .cpp
virtual size_t Count (); // idem con patate
};
template <typename T>
class DoublyLinkedList : SequentiallyAccessibleContainer<T>
{
public:
// ...
virtual bool NextElement(); // tutte implementate nel .cpp
virtual bool PreviousElement();
virtual T & Element();
virtual size_t Count ();
};
template <T>
void Sort(RandomAccessibleContainer<T> & Cont)
{
// ...
}
template <T>
void Sort(SequentiallyAccessibleContainer<T> & Cont)
{
// ...
}
Spingendosi ancora più lontani dall'OOP classico, c'è l'approccio di generic programming della STL: gli algoritmi sono tutti funzioni libere, e i container non ereditano da classi basi virtuali che ne descrivono l'accesso; piuttosto, forniscono come metodo preferenziale di accesso agli elementi (almeno per gli algoritmi) degli iteratori, ossia degli oggetti che possono essere incrementati/decrementati/confrontati/... per spostarsi nel container.
L'"interfaccia comune" sfruttata dagli algoritmi per operare sugli iteratori sono gli operatori che essi ridefiniscono (++ passa all'elemento successivo, -- al precedente, ==/!= valutano se i due operatori sono nella stessa posizione nel container, + va un tot di elementi oltre, * (inteso come operatore unario di dereferenziazione) ottiene il valore relativo alla posizione nella sequenza, ...); si possono vedere come generalizzazione dei puntatori su container di qualunque genere.
Naturalmente non tutti i container consentono le stesse operazioni: in un vettore si può saltare qua e là senza problemi, in una doubly-linked list ci si può muovere solo avanti e indietro.
La questione è gestita fornendo agli iteratori degli operatori solo per le operazioni che sanno compiere: un iteratore relativo ad una lista avrà ++ e --, ma non + o -, né (in linea di massima) > o <. Al contrario, un iteratore relativo ad un vector avrà più o meno tutti gli operatori possibili (++, --, +, -, >, <, ==, !=, ...), dato che si possono implementare in maniera molto efficiente tramite operazioni sui puntatori.
Avendo iteratori non legati ad un tipo particolare, ma che possono essere di qualunque tipo purché implementino gli operatori adeguati, non è possibile sfruttare l'overloading "classico" per scegliere quale particolare versione dell'algoritmo richiamare: l'unico appiglio che si ha per scegliere qual'è la versione giusta è capire quali operatori implementa l'iteratore; per questo interviene la SFINAE, che viene sfruttata per far scegliere al compilatore la versione dell'algoritmo più adeguata all'iteratore passato.
L'approccio STL, rispetto ai metodi citati sopra, ha sicuramente come vantaggio una maggiore efficienza, dato che tutte le chiamate vengono risolte a compile-time e vengono evitate in blocco le chiamate virtuali; inoltre si riesce ad effettuare spesso l'inlining di buona parte delle funzioni, che in genere sono molto brevi e guadagnano abbastanza da questo tipo di ottimizzazione.
Per contro, lo stile STL è meno comprensibile da chi ha un background di OOP "classica", e l'uso degli iteratori può dare origine a codice verboso e non troppo leggibile. D'altra parte essi consentono una flessibilità unica, sia per chi implementa un container nuovo (che, fornendo iteratori, può essere immediatamente gestito da tutti gli algoritmi già esistenti) sia per chi implementa nuovi algoritmi, che si possono applicare a qualunque container già esistente, a patto che fornisca iteratori che implementano gli operatori necessari all'algoritmo.
Per inciso, è possibile implementare un approccio ad iteratori andando di sole classi virtuali senza tutti i trucchi di template e SFINAE, basterebbe fare sì che tutti gli iteratori forniti dai container ereditassero da una classe virtuale che ne definisce gli operatori, spostando cioè sugli iteratori quello che rappresentavano le ***AccessibleContainer sui container negli esempi precedenti.
D'altra parte questo approccio annullerebbe parte dei benefici in termini di ottimizzazione (gli iteratori avrebbero chiamate virtuali a palate) e richiederebbe che tutti fossero d'accordo sul tipo di classe base da impiegare per ogni iteratore, cosa che in C++ di rado accade. 
Inoltre, dato che in C++ i tipi primitivi non sono oggetti e non possono ereditare da nulla, un normale puntatore relativo ad un array (che di suo implementa gli operatori necessari per praticamente tutti gli algoritmi: ++, --, +, -, >, <, !=, ==, *, ...) non potrebbe essere impiegato in un algoritmo che richiederebbe che gli iteratori passati ereditino da una determinata classe base; al contrario, i puntatori possono essere impiegati senza problemi negli algoritmi template usati nella STL, dato che l'unica cosa che importa non è il loro tipo, quanto gli operatori che implementano.
Rispondi quotando
