iteratori bidirezionali in unordered_map?

Il seguente esempio minimale:iteratori bidirezionali in unordered_map?

#include <iostream> 

#include <boost/unordered_map.hpp> 

int main() 
{ 
     boost::unordered_map<int, int> m; 
     boost::unordered_map<int, int>::const_iterator i; 

     m.insert(std::make_pair(1, 2)); 

     i = m.end(); 
     --i; 

     std::cout << i->first << " -> " << i->second << std::endl; 

     return 0; 
}

... fallisce la compilazione.

bidi.cxx: In function ‘int main()’: 
bidi.cxx:13: error: no match for ‘operator--’ in ‘--i’

Secondo Boost's own documentation:

iterator, const_iterator sono almeno della categoria in avanti.

Sembrerebbe che sia tutto ciò che sono. Perché? Quale restrizione tecnica impone una mappa hash che impedisce agli iteratori di essere bidirezionali?

(gcc version 4.1.2, Boost versioni 1.40.0 e 1.43.0.)

fonte

2010-06-08 Thanatos

Questa è pura speculazione, ma tieni presente che puoi essere in grado di attraversare qualcosa all'indietro e in avanti, quindi ogni nodo dovrebbe avere un puntatore all'elemento successivo E all'elemento precedente. Se questa mappa fosse implementata con SOLO puntatori agli oggetti successivi, allora il tuo iteratore non avrebbe modo di capire cosa succedeva prima del nodo corrente, e quindi non c'era modo di tornare indietro. –

Sinceramente trovo strano (anche se occasionalmente utile) che le mappe non ordinate abbiano anche iteratori. –

@Niki Yoshiuchi: Ho usato molto il concetto corrispondente in Perl. Di solito, voglio che gli hash del Perl funzionino come array associativi, ma a volte voglio fare qualcosa per l'intero hash. In Perl, uso la funzione 'keys' per ottenere una lista delle chiavi, e iterare attraverso di essa, mentre in C++ l'ovvia equivalenza è un iteratore diretto. Mi mancherebbe davvero la possibilità di fare l'equivalente di 'foreach' su qualsiasi raccolta di dati. –

Non v'è alcuna ragione tecnica per cui un unordered_map non possono avere iteratori bidirezionali. La ragione principale è che aggiungerebbe un costo aggiuntivo all'implementazione, e i progettisti pensavano che nessuno avrebbe davvero bisogno di iteratori bidirezionali in una mappa hash. Dopo tutto, non c'è un ordine in un hash, e quindi l'ordine che l'iteratore ti dà è del tutto arbitrario. Cosa darebbe un ordine fisso ma arbitrario all'indietro?

Normalmente, si può accedere a unordered_map su base elemento per elemento o attraversare l'intera mappa. Non ho mai fatto diversamente in Perl, me stesso. Per fare ciò, è necessario un iteratore forward, e quindi ce n'è uno in là e Boost lo garantisce. Per avere iteratori bidirezionali, sarebbe probabilmente necessario includere un puntatore aggiuntivo in ogni voce, che aumenta l'utilizzo della memoria e il tempo di elaborazione.

Non mi viene in mente un caso valido e plausibile per gli iteratori bidirezionali. Se puoi, puoi chiedere ai manutentori Boost di prenderlo in considerazione, anche se sei quasi certamente troppo tardi per C++ 0x.

fonte

2010-06-08 15:15:30

In realtà, pensavo che il bit sulle mappe hash che restituivano risultati in un ordine arbitrario era abbastanza convincente. I soliti casi d'uso sono una ricerca o una completa iterazione. Nella mia testa, sono sempre stati implementati con un vettore di bucket e un bucket è una std :: list. Non ho mai considerato il risparmio di possibilmente utilizzando una lista collegata singolarmente. – Thanatos

iteratori bidirezionali in unordered_map?

risposta

Problemi correlati