[C++] Inserimento non ordinato in container STL

[clros]

• 

Ciao a tutti,

se voglio inserire qualcosa in un container STL (esempio un set oppure un(a) map), l'elemento viene inserito sulla base di una funzione di confronto (es: std::less<>).
E' possibile mantenere l'ordine degli elementi inseriti in base all'ordine di inserimento stesso nel programma?

es:

Codice: [Seleziona]

int main()
{
    set<int, less<int> > s;
    set<int, less<int> >::iterator i;

    s.insert(4);
    s.insert(0);
    s.insert(-9);
    s.insert(7);
    s.insert(-2);
    s.insert(4);
    s.insert(2);

    cout << "The set contains the elements: ";
    for (i=s.cbegin(); i!=s.cend(); i++)
                 cout << *i << ' ';
    cout << endl;
}

In questo caso otterrei un output "ordinato".

Ma se volessi ottenere l'output nello stesso ordine in cui ho inserito gli elementi?
(In pratica vorrei che il contenitore non ordini in nessun modo quello che inserisco...)

[TheKaneB]

• 

map e set sono implementati in modo da riordinare gli elementi per un lookup rapido in fase di ricerca. Se vuoi gli elementi nell'ordine in cui li hai inseriti allora stai cercando una coda (Queue).

Puoi usare ad esempio una linked list in cui inserisci in testa (push_front) e cancelli in coda (back, pop_back).

Se hai bisono sia della mappa che della lista ordinata, allora considera la possibilità di gestire simultaneamente le due strutture dati, incapsulandole in un container custom, oppure valuta se il tuo design non sia in qualche modo fallato in origine (sarebbe utile conoscere il contesto di utilizzo di tale struttura).

[clros]

• 

map e set sono implementati in modo da riordinare gli elementi per un lookup rapido in fase di ricerca. Se vuoi gli elementi nell'ordine in cui li hai inseriti allora stai cercando una coda (Queue).

Puoi usare ad esempio una linked list in cui inserisci in testa (push_front) e cancelli in coda (back, pop_back).

Se hai bisono sia della mappa che della lista ordinata, allora considera la possibilità di gestire simultaneamente le due strutture dati, incapsulandole in un container custom, oppure valuta se il tuo design non sia in qualche modo fallato in origine (sarebbe utile conoscere il contesto di utilizzo di tale struttura).

Nessun contesto per adesso, mi chiedevo solo come mai non sia possibile una cosa del genere.
In ogni caso, una Queue, non credo si comporti come un set (nessuna duplicazione degli elementi inseriti)...

[TheKaneB]

• 

No infatti, sono strutture diverse con relative caratteristiche peculiari.

[TheKaneB]

• 

Quello che mi viene in mente è la seguente soluzione (in pseudo-C++)

Codice: [Seleziona]

template< typename K, typename T >
class MyContainer
{
public:
MyContainer()
{
mHistoryCursor = mHistory.begin();
}

T* put(K key, T value)
{
DictionaryType::iterator it = mDictionary.find(key);

if (it == mDictionary.end() )
{
T* tmp = &(mDictionary[key] = value);
mHistory->push_front(tmp);
return tmp;
}

return null;
}

// Versione non ordinata
T* get(K key) const
{
DictionaryType::iterator it = mDictionary.find(key);
if (it != mDictionary.end())
return (*it)->second;
else
return null;
}

// Versione ordinata
T* getNext()
{
if (mHistoryCursor != mHistory.end())
{
T* ret = *(++mHistoryCursor);
return ret;
}
else
return null;
}

void resetCursor()
{
mHistoryCursor = mHistory.begin();
}

private:
list< T* > mHistory;
list< T* >::iterator mHistoryCursor;
typedef hash_map< K, T > DictionaryType;
DictionaryType mDictionary;

};

Non l'ho compilato, nè testato, è solo un pezzo di codice scritto di getto per darti un'idea in linea di massima di come sia possibile implementare una struttura dati complessa a partire da due più semplici. In questo caso effettuo gli inserimenti nella hash_map solamente se la chiave non è già mappata (ma potresti voler inserire ugualmente, in modo da aggiornare la vecchia coppia key-value con un nuovo value, dipende dalle tue esigenze). Una volta inserito nella hash_map, metto un puntatore a questo elemento anche nella linked list.
Ho fatto una list di puntatori a value, ma potrei anche fare una list di map::iterator, in base a quello che ti serve.
Se volessi implementare l'interfaccia standard dei container STL allora sarebbe più sensato implementare i vari tipi di iteratori (invece del Cursor, molto basilare, che ho mostrato qui).
E' una cosa fondamentale che la lista non contenga una copia di "value" ma un puntatore. In questo modo, se il codice utente prende un reference ad un oggetto del container, sei sicuro che i dati in esso presenti saranno sempre consistenti, altrimenti potrebbe verificarsi che uno modifica la map e la lista rimane non aggiornata o viceversa.

Ripeto un'altra volta: ho buttato giù un po' di "pseudo c++" solo per illustrare la tecnica, quasi sicuramente questo codice non funzionerà perchè non so nemmeno se compila  :geek:

[cdimauro]

• 

map e set sono implementati in modo da riordinare gli elementi per un lookup rapido in fase di ricerca.

Purtroppo non è così. L'STL prevede l'utilizzo di un albero in entrambi i casi per "tenere ordinati" gli elementi (sic.), per cui la ricerca impiega tempo O(log(n)).

E' una scelta del tutto priva di senso perché un insieme è per definizione disordinato e non avrebbe di certo bisogno di tenere ordinati i suoi elementi. Idem le mappe.

Insieme e mappe nascono e sono usati principalmente per testare se un elemento esiste nell'insieme oppure no, e recuperare il valore associato. Sono queste le operazioni che andrebbero velocizzate (assieme all'inserimento) e difatti le implementazioni di queste strutture dati in altri linguaggi richiedono generalmente tempo O(1).

Non so cosa passasse nella mente di Stroustrup per decidere diversamente, ma a mio avviso si è trattato di una scelta veramente stupida.

[TheKaneB]

• 

Esiste comunque anche la struttura hash map, ma occupa più memoria

[cdimauro]

• 

Ricordavo soltanto la hash. Buono a sapersi.

[clros]

• 

In ogni caso, una Queue, non credo si comporti come un set (nessuna duplicazione degli elementi inseriti)...

Le STL del C++ non implementano l'unordered set? I cointaner di Ada offrono entrambe le implementazioni (che però si chiamano hashed e ordered). Anche Java mi pare offra l'alternativa.

Però non credo che li inserisca come dici tu (ordinati dall'inserimento), semplicemente non ti garantisce l'ordine che dipende dal tipo di implementazione, quindi non dovresti fare alcuna supposizione sull'ordinamento. Il modo più elementare (e veloce) per implementare l'unordered set è l'hash table, più disordinato di così!

L'unordered_set (di sicuro l'unordered_map) è implementato nel C++11.
Però..hai ragione; non li inserisce in base all'inserimento ma proprio usando una hash table, quindi li "ordina" in base all'algoritmo di hashing usato...

[clros]

• 

[...]

Non so cosa passasse nella mente di Stroustrup per decidere diversamente, ma a mio avviso si è trattato di una scelta veramente stupida.

Che io sappia, STL non l'ha progettata/scritta Stroustrup...

[cdimauro]

• 

Boh. Penso che l'abbia comunque seguita. Ne era così contento nel '95 (se non ricordo male), quando la presentò a un seminario alla New York University (all'epoca ero lì in stage universitario ).

[clros]

• 

Boh. Penso che l'abbia comunque seguita. Ne era così contento nel '95 (se non ricordo male), quando la presentò a un seminario alla New York University (all'epoca ero lì in stage universitario ).

Non ne sono sicuro...ricordo che le prime implementazioni erano della SGI (Silicon Graphics), ma magari dico una cavolata.
Cmq è possibile che Stroustrup l'abbia seguita come scrivi tu...

[cdimauro]

• 

Vero, sembra che sia arrivata molto tardi al comitato (di cui faceva parte Stroustrup) e siano poi stati fatti dei cambiamenti.

Boh. Magari la contentezza di Stroustrup era per il fatto che il C++ aveva una sua libreria standard.

[clros]

• 

Vero, sembra che sia arrivata molto tardi al comitato (di cui faceva parte Stroustrup) e siano poi stati fatti dei cambiamenti.

Boh. Magari la contentezza di Stroustrup era per il fatto che il C++ aveva una sua libreria standard.

   
OT
Cmq: letto adesso su Wikipedia:

"Le STL (Standard Template Library) sono state progettate e sviluppate presso la Hewlett-Packard da Alexander Stepanov e Meng Lee e sono state incluse nello standard ANSI/ISO nel 1995."

Su Wikipedia inglese invece riporta che l'attuale STL è basata sull'implementazione di SGI: "More specifically, the C++ Standard Library is based on the STL published by SGI."
Mi sembra cmq di capire che l'mplementazione della SGI si basi su quella di HP...
/OT

[clros]

• 

Ok, alla fine, trovando un po' di tempo libero, sono riuscito ad implementare un set con la capacità di restituire gli elementi in base all'ordine di inserimento, basandomi sul listato di esempio fornito da TheKaneB.

Un'altra domanda (OT): com'è possibile implementare un iteratore nella mia classe? (E' una cosa che non ho mai fatto!)
Attualmente uso un metodo per scorrere gli elementi molto simile a quando suggerito da TheKaneB, ma non è il massimo..