unordered_map中的双向迭代器？ [英] Bidirectional iterators 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;
}

...无法编译。

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

根据 Boost自己的文档：

iterator ， const_iterator 至少是正向类别。

看起来这就是他们。为什么？哈希映射强加了什么技术限制，防止迭代器是双向的？

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版本4.1.2，Boost版本1.40.0和1.43.0） / p>

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

推荐答案

没有技术上的理由为什么 unordered_map 迭代器。主要原因是它会增加实现的额外成本，设计师认为没有人真的需要在哈希映射中的双向迭代器。毕竟，在哈希中没有顺序，所以迭代器给你的顺序是完全任意的。

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?

通常，在元素上访问 unordered_map 逐个元素基础，或遍历整个地图。我从来没有在Perl，我自己。为了做到这一点，前向迭代器是必要的，因此有一个在那里，Boost保证它。为了具有双向迭代器，可能需要在每个条目中包括一个附加的指针，这增加了内存使用和处理时间。

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.

我没有提出好，似是而非的，在这里的双向迭代器的用例。如果可以，你可以请求Boost维护者考虑它，虽然你几乎肯定是太晚了C ++ 0x。

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.

这篇关于unordered_map中的双向迭代器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！