unordered_map中的双向迭代器？

Question

以下最小例子:

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

...无法编译.

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

根据Boost自己的文档:

iterator,const_iterator至少是前瞻性类别.

似乎就是这样.为什么？哈希映射强加了什么技术限制来阻止迭代器是双向的？

(gcc版本4.1.2,Boost版本1.40.0和1.43.0.)

Answer 1

没有技术原因导致unordered_map无法使用双向迭代器.主要原因是它会增加实现的额外成本,设计人员认为没有人真的需要哈希映射中的双向迭代器.毕竟,哈希中没有顺序,因此迭代器给你的顺序完全是任意的.什么会向后移动固定但任意的顺序给你？

通常,人们可以unordered_map逐个元素地访问,或者遍历整个地图.我自己从未在Perl中做过其他事情.要做到这一点,前向迭代器是必要的,因此有一个,并且Boost保证它.要拥有双向迭代器,可能需要在每个条目中包含一个额外的指针,这会增加内存使用和处理时间.

我不会在这里提出一个好的,合理的双向迭代器用例.如果可以,你可以要求Boost维护者考虑它,尽管你几乎肯定对C++ 0x来说太迟了.