我想计算两个迭代器之间的条目数std::multimap在不到 O(N) 的时间内。有什么技巧或巧妙的方法可以做到这一点吗？
Since std::multimap有双向迭代器，我的理解是这样的std::distance可以在 O(N) 时间内完成。
其他详细信息：multimap的键是一个 N 元组。我正在尝试查找中的条目数multimap其键的第一个元素为 0。其键的第一个元素的选项为 0 和 1，并且multimap使用严格的弱排序，其中键的第一个元素始终是最重要的。即所有为 0 的元素都出现在任何为 1 的元素之前。
上下文：迭代器返回equal_range，以对数时间运行。声明性地，我想测量范围的长度。
谢谢。
你正在寻找的是所谓的异构比较查找 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3465.pdfN3465 中提出了这一点。它允许不同但兼容中的比较函数equal_range用于存储的成员函数Key。在您的情况下，查找比较运算符（第一个元组成员）将与元组字典比较不同但一致。
不幸的是，根据 C++14 标准草案，该论文只有一小部分被接受本次问答 https://stackoverflow.com/a/20383136/819272。然而，N3465论文的作者也是Boost.MultiIndex的作者，它已经实现了此功能 http://www.boost.org/doc/libs/1_55_0b1/libs/multi_index/doc/tutorial/basics.html#special_lookup。你可以模拟一个std::multimap http://www.boost.org/doc/libs/1_55_0b1/libs/multi_index/doc/tutorial/techniques.html#emulate_std_containers遵循 Boost.MultiIndex 文档。
一旦你使用了通用的equal_range适应的成员函数boost::multiindex_container，然后你可以简单地做std::distance()在返回的迭代器上。复杂性将是容器大小的对数equal_range与返回的迭代器范围的大小成线性关系。如果您对结果不感兴趣而只对计数感兴趣，那么还有一个广义的count()成员函数在相同的对数+线性时间内返回该值。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
