Qualcuno è riuscito a risolvere questo problema senza ricorrere a trie o liste di adiacenza?
Io l’ho risolto con un albero normale. Puoi trovare la discussione sul forum.
Ah scusate non avevo visto…
Comunque mi è bastato usare un vector al posto di una deque e la memoria utilizzata (che era il mio problema) si è più che dimezzata. Mi sono avvicinato da poco al C++ (un paio di mesi fa usavo solo il C) e a queste strutture pertanto non ne sono esperto… perché c’è un divario così grande fra queste due strutture?
Ah scusate non avevo visto...Perché la deque permette anche il pop/push front, il vector noComunque mi è bastato usare un vector al posto di una deque e la memoria utilizzata (che era il mio problema) si è più che dimezzata. Mi sono avvicinato da poco al C++ (un paio di mesi fa usavo solo il C) e a queste strutture pertanto non ne sono esperto... perché c'è un divario così grande fra queste due strutture?marcoBeretta
Solo per quello?
La motivazione più nel dettaglio è che, per garantire push e pop front in O(1) ammortizzato, dobbiamo ammettere che i valori non siano in un'area di memoria contigua a tutti i costi (come avviene nei vettori).Solo per quello?marcoBeretta
Per fare ciò, tralasciando l'implementazione (che potrebbe essere un vettore di vettori piccoli oppure una mappa di puntatori a vettori piccoli), serve intuitivamente che vengano mantenuti dei puntatori che identifichino questi vari piccoli vettori.
Nel complesso la struttura introduce quindi un overhead rispetto alla memorizzazione dei soli dati. A seconda del problema e dell'implementazione, questo overhead può essere risibile oppure, come nel caso che presentavi, determinante.
Capito! Grazie!