TheDarkJuster (Member)
Guru^2
Messaggi: 1620
Iscritto: 27/09/2013
|
Buongiorno e auguri a tutti.
Sto scrivendo una classe per gli array associativi in C++.
Per ora un elemento si aggiunge chiamando la funzione Insert, ma voglio dare la possibilità di poter fare:
AssociativeArray<int> array;
array["indice"] = 7;
C'è un "problema" l'overload dell'operatore [] serve già per ottenere il valore in quel dato indice.
La classe per il momemnto è così:
Codice sorgente - presumibilmente C++ |
template <class T> class AssociativeArray { public: AssociativeArray(); ~AssociativeArray(); size_t Size(); T& operator [] (string name); bool Contains(string name); void Insert(string index, T value); void Remove(string index); private: struct _Data { T data; string name; }; unique_ptr<vector<_Data>> array = unique_ptr<vector<_Data>>(nullptr); };
|
Ciò che chiedo è possibile? Se si come si fa (qual'è la firma della funzione)?
|
|
|
lumo (Member)
Expert
Messaggi: 449
Iscritto: 18/04/2010
|
|
|
|
TheDarkJuster (Member)
Guru^2
Messaggi: 1620
Iscritto: 27/09/2013
|
Perchè sto parzialmente "riscrivendo"/"rimpiazzando" la STL.
Motivi vari e disparati (e probabilmente anche disperati  ), ma è un esperimento/progetto carino.....
Il progetto fa parte di una libreria molto..... "H "
Comunque grazie!
"If k matches the key of an element in the container, the function returns a reference to its mapped value.
If k does not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value. Notice that this always increases the container size by one, even if no mapped value is assigned to the element (the element is constructed using its default constructor)." E' geniale  come ho fatto non pensarci???
|
|
|
lumo (Member)
Expert
Messaggi: 449
Iscritto: 18/04/2010
|
Ok ma prima di scrivere una libreria impara quando usare i const reference per il passaggio dei parametri.
Tra l'altro per una struttura associativa una linked list è un harakiri prestazionale.
Io sinceramente trovo bruttino il comportamento di operator[], preferisco il metodo at() e inserire con insert
|
|
|
TheDarkJuster (Member)
Guru^2
Messaggi: 1620
Iscritto: 27/09/2013
|
Postato originariamente da lumo:
Ok ma prima di scrivere una libreria impara quando usare i const reference per il passaggio dei parametri.
Tra l'altro per una struttura associativa una linked list è un harakiri prestazionale.
Io sinceramente trovo bruttino il comportamento di operator[], preferisco il metodo at() e inserire con insert
|
Beh, per non sbagliare è già possibile usare entrambi i metodi.....
Sono d'accordo sul punto che usare un vettore è una stupidaggine.... Consigli di usare una struttura a stack? Così da favorire gli accessi agli ultimi dati inseriti? Posso guadagnare prestazioni separando gli stack per lettera iniziale? Ne vale la pena?
Che altre strutture potrei usare? Ora non mi viene in mente nulla......
Volendo potrei anche usare un database sqlite in memoria per memorizzare i dati.... E' fattibile ma non penso porterà alcun beneficio Ultima modifica effettuata da TheDarkJuster il 08/01/2016 alle 17:21 |
|
|
Template (Member)
Pro
Messaggi: 177
Iscritto: 09/12/2015
|
La butto lì, forse è una cretinata ma non si sa mai... una tabella di simboli che converta gli indici alfabetici (gli array associativi li prevedono, giusto?) in analoghi numerici tramite l'opportuna funzione di hashing? 
Certo, se volessi utilizzare istruzioni del tipo
Codice sorgente - presumibilmente Plain Text |
mioarray[1] = qualcosa;
...
mioarray["stringa"] = qualchealtracosa;
|
Magari la funzione di hashing potrebbe creare collisioni, ma se fossero utilizzati come reciproche alternative potrebbe andar bene 
Ho avuto quest'idea per associazione: di fatto quanto hai citato circa le std:map
"If k matches the key of an element in the container, the function returns a reference to its mapped value.
If k does not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value. Notice that this always increases the container size by one, even if no mapped value is assigned to the element (the element is constructed using its default constructor)."
|
È esattamente ciò che si fa con le tabelle di simboli per registrare i nodi di un grafo (o almeno, ciò che vari autori - al momento mi viene in mente Sedgewick, ma credo lo faccia pure Cormen - propongono di fare) Ultima modifica effettuata da Template il 08/01/2016 alle 18:22 |
|
|
lumo (Member)
Expert
Messaggi: 449
Iscritto: 18/04/2010
|
Per strutture come map si usano in genere alberi di ricerca bilanciati, come gli AVL tree o i red-black tree.
In alternativa potresti usare un'hashtable visto che nella tua classe le chiavi sono stringhe (= non è troppo difficile creare una funzione di hashing)
|
|
|
TheDarkJuster (Member)
Guru^2
Messaggi: 1620
Iscritto: 27/09/2013
|
Va bene, andata per la ricerca tramite hashing! Se le prestazioni non mi comodano posso sempre cambiare il motore, ma un tentativo con codice più semplice va fatto
Dovrei usare un algoritmo di hashing particolarmente veloce (opzione che sceglierei) o uno con un basso numero di collisioni (magari più lento, opzione che scarterei)?
C'è qualcosa che non ho considerato e che, invece, dovrei rivedere?
P.S. tanto strutture ad albero dovrò comunque utilizzarne, visto che prevedo di implementare un algoritmo di compressione dati .....
Ultima modifica effettuata da TheDarkJuster il 08/01/2016 alle 20:39 |
|
|
Template (Member)
Pro
Messaggi: 177
Iscritto: 09/12/2015
|
Se, come credo, le inserzioni saranno importanti e frequenti, forse conviene tendere più verso la velocità (fermo restando che un algoritmo particolarmente sensibile al clustering potrà anche essere teoricamente velocissimo, ma con certe concentrazioni di dati risulterà comunque sconveniente)... anche se, chiaramente (sviluppo una riflessione puramente generale), qualsiasi algoritmo risulta di per sè ininfluente a livello di prestazioni se non è inserito in una struttura a sua volta efficientemente congegnata, e viceversa una struttura ben congegnata può spostare gli equilibri del programma sì da rendere utilizzabili algoritmi che, considerati individualmente, potrebbero non apparire particolarmente convenienti.
|
|
|
| 
