Bidirektionale Iteratoren in unordered_map?

Das folgende minimal Beispiel:Bidirektionale Iteratoren 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; 
}

... nicht kompilieren.

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

Nach Boost's own documentation:

iterator, const_iterator sind zumindest die Vorwärts-Kategorie.

Es scheint, dass das alles ist, was sie sind. Warum? Welche technische Einschränkung gibt eine Hash-Map vor, die verhindert, dass Iteratoren bidirektional sind?

(gcc Version 4.1.2, Boost-Versionen 1.40.0 und 1.43.0.)

Quelle

2010-06-08 Thanatos

Das ist pure Spekulation, aber bedenken Sie, dass Sie in der Lage sind, etwas rückwärts und vorwärts zu durchlaufen, dann müsste jeder Knoten einen Zeiger auf das nächste Element und das vorherige Element haben. Wenn diese Map mit ONLY-Zeigern auf die nächsten Elemente implementiert würde, hätte Ihr Iterator keine Möglichkeit, herauszufinden, was vor dem aktuellen Knoten lag, und somit keine Möglichkeit, rückwärts zu gehen. –

Ehrlich gesagt finde ich es merkwürdig (obwohl gelegentlich nützlich), dass unordered_maps sogar Iteratoren haben. –

@ Niki Yoshiuchi: Ich habe das entsprechende Konzept in Perl sehr oft verwendet. Normalerweise möchte ich, dass Perl-Hashes als assoziative Arrays fungieren, aber manchmal möchte ich etwas mit dem gesamten Hash tun. In Perl verwende ich die 'keys' -Funktion, um eine Liste der Schlüssel zu erhalten, und iteriere durch sie, während in C++ die offensichtliche Äquivalenz ein Vorwärtsiterator ist. Ich würde wirklich die Fähigkeit vermissen, das Äquivalent zu foreach bei jeder Datensammlung zu machen. –

Es gibt keinen technischen Grund, warum ein unordered_map nicht bidirektionale Iteratoren haben kann. Der Hauptgrund ist, dass die Implementierung zusätzliche Kosten verursachen würde, und die Entwickler dachten, dass niemand bidirektionale Iteratoren in einer Hash-Map wirklich brauchen würde. Schließlich gibt es keine Reihenfolge in einem Hash, und so ist die Reihenfolge, die der Iterator Ihnen gibt, völlig willkürlich. Was würde dir eine feste aber willkürliche Reihenfolge rückwärts geben?

Normalerweise würde man Element für Element auf ein unordered_map zugreifen oder die gesamte Karte durchlaufen. Ich habe noch nie in Perl etwas anderes gemacht. Um dies zu tun, ist ein Vorwärts-Iterator notwendig, und daher ist einer drin und Boost garantiert dies. Um bidirektionale Iteratoren zu haben, wäre es wahrscheinlich notwendig, einen zusätzlichen Zeiger in jeden Eintrag einzufügen, was die Speicherbenutzung und die Verarbeitungszeit erhöht.

Ich habe hier keinen guten, plausiblen Anwendungsfall für bidirektionale Iteratoren. Wenn Sie können, können Sie die Boost-Betreuer bitten, darüber nachzudenken, obwohl Sie mit ziemlicher Sicherheit zu spät für C++ 0x sind.

Quelle

2010-06-08 15:15:30

Eigentlich dachte ich, das bisschen über Hash-Maps, die Ergebnisse in einer willkürlichen Reihenfolge liefern, war ziemlich überzeugend. Die üblichen Anwendungsfälle sind entweder ein Nachschlagen oder eine vollständige Iteration. In meinem Kopf wurden sie immer mit einem Vektor von Buckets implementiert, und ein Bucket ist eine std :: list. Niemals die Ersparnisse in Betracht gezogen, möglicherweise eine einfach verknüpfte Liste zu verwenden. – Thanatos

Bidirektionale Iteratoren in unordered_map?

Antwort

Verwandte Themen