Bidirectional iterators in unordered_map?

Question

The following minimal 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;
}

...fails to 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 are of at least the forward category.

It would appear that that's all they are. Why? What technical restriction does a hash-map impose that prevents iterators from being bidirectional?

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

Answer 1

There is no technical reason why an unordered_map can't have bidirectional iterators. The main reason is that it would add additional cost to the implementation, and the designers thought nobody would really need bidirectional iterators in a hash map. After all, there's no order in a hash, and so the order the iterator gives you is entirely arbitrary. What would traversing a fixed but arbitrary order backwards give you?

Normally, one would access an unordered_map on an element-by-element basis, or traverse the whole map. I've never done otherwise in Perl, myself. To do this, a forward iterator is necessary, and therefore there is one in there, and Boost guarantees it. To have bidirectional iterators, it would likely be necessary to include an additional pointer in each entry, which increases memory use and processing time.

I'm not coming up with a good, plausible, use case for bidirectional iterators here. If you can, you can ask the Boost maintainers to consider it, although you're almost certainly too late for C++0x.