Bidirectional iterators in unordered_map?

Question

The following minimum example:

#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; } 

... cannot compile.

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

According to Boost's own documentation :

iterator , const_iterator have at least the following category.

It would seem that they are all there. What for? What technical limitation introduces a hash map that prevents bidirectional iteration?

(gcc version 4.1.2, Boost versions 1.40.0 and 1.43.0.)

Answer 1

There are no technical reasons why unordered_map cannot have bidirectional iterators. The main reason is that this will add additional implementation costs, and the designers thought that no one would need bidirectional iterators for the hash map. After all, there is no order in the hash, and so the order that the iterator gives you is completely arbitrary. What can happen with a fixed but arbitrary backward order?

Typically, you could access unordered_map for each element or go through the entire map. I have never done otherwise in Perl. This requires an advanced iterator, and therefore there is one, and Boost guarantees it. To have bidirectional iterators, you probably need to include an extra pointer in each record, which increases memory usage and processing time.

I have not come up with a good, believable option for bidirectional iterators. If you can, you can ask Boost maintainers to consider this, although you are almost certainly too late for C ++ 0x.