代码之家  ›  专栏  ›  技术社区  ›  Thanatos

无序映射中的双向迭代器?

c++
  •  6
  • Thanatos  · 技术社区  · 15 年前

    以下最小示例:

    #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's own documentation :

    iterator , const_iterator 至少属于转发类别。

    看来他们就是这样。为什么?散列映射施加了哪些技术限制,以防止迭代器是双向的?

    (GCC版本4.1.2,Boost版本1.40.0和1.43.0。)

    1 回复  |  直到 15 年前
        1
  •  10
  •   David Thornley    15 年前

    没有技术原因 unordered_map 不能有双向迭代器。主要原因是它会增加实现的额外成本,并且设计者认为没有人真正需要哈希图中的双向迭代器。毕竟,散列中没有顺序,所以迭代器给出的顺序完全是任意的。向后遍历一个固定但任意的顺序会给你什么?

    通常情况下,一个人可以访问 无序映射 在一个元素一个元素的基础上,或者遍历整个地图。我自己从来没有用过Perl。要做到这一点,前向迭代器是必要的,因此其中有一个,Boost保证它的存在。要使用双向迭代器,可能需要在每个条目中包含一个额外的指针,这将增加内存使用和处理时间。

    我并没有想到一个好的,合理的,双向迭代器的用例。如果可以,你可以让Boost维护者考虑它,尽管对于C++ 0x来说,你肯定是太晚了。