c++ - 有效地计算两个 std::multimap 迭代器之间的条目数

Question

我想在不到 O(N) 的时间内计算 std::multimap 的两个迭代器之间的条目数。有什么技巧或聪明的方法可以做到这一点吗？

因为 std::multimap 有双向迭代器，我的理解是像 std::distance 这样的东西可以在 O(N) 时间内完成。

其他详细信息:multimap 的键是一个 N 元组。我正在尝试查找 multimap 中键的第一个元素为 0 的条目数。它们键的第一个元素的选项是 0 和 1，而 multimap 使用严格的弱排序，其中键的第一个元素始终是最重要的。即，所有带 0 的元素出现在任何带 1 的元素之前。

上下文:迭代器由 equal_range 返回，它以对数时间运行。明确地说，我想测量范围的长度。

谢谢。

Answer 1

你要找的就是所谓的heterogeneous comparison lookup那是在 N3465 中提出的。它允许在用于存储 Key 的 equal_range 成员函数中使用一个不同但兼容 比较函数。在您的情况下，查找比较运算符(第一个元组成员)将不同于但与元组字典序比较一致。

不幸的是，根据 this Q&A，该论文只有一小部分被接受到 C++14 标准草案中。 .但是，N3465 论文的作者也是实现了 this feature 的 Boost.MultiIndex 的作者。 .你可以emulate a std::multimap遵循 Boost.MultiIndex 文档。

一旦您使用了改编boost::multiindex_container 的广义equal_range 成员函数，您就可以简单地执行std::distance() 在返回的迭代器上。复杂度与 equal_range 的容器大小成对数关系，与返回的迭代器范围的大小成线性关系。如果您对结果不感兴趣而只对计数感兴趣，还有一个通用的 count() 成员函数以相同的对数 + 线性时间返回结果。