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

Question

我想计算一个std::multimap小于O(N)时间的两个迭代器之间的条目数.有没有任何技巧或聪明的方法来做到这一点？

由于std::multimap具有双向迭代器,我的理解是std::distance在O(N)时间内可以做到这一点.

其他细节:multimap关键是N元组.我试图找到multimap其键的第一个元素为0 的条目数.它们键的第一个元素的选项是0和1,并multimap使用严格的弱顺序,其中键的第一个元素始终最重要的.即,所有带0的元素都来自任何带有1的元素.

上下文:迭代器返回equal_range,以对数时间运行.据说,我想测量范围的长度.

谢谢.

Answer 1

您正在寻找的是N3465中提出的所谓的异构比较查找.它允许在用于存储的成员函数中使用不同但兼容的比较函数.在您的情况下,查找比较运算符(第一个元组成员)将与元组词典比较不同但是一致.equal_rangeKey

不幸的是,根据这个问答环节,该文章中只有一小部分被C++ 14标准接受.但是,N3465论文的作者也是实现此功能的Boost.MultiIndex的作者.您可以通过遵循Boost.MultiIndex文档来模拟astd::multimap.

一旦使用了equal_range自适应的通用成员函数boost::multiindex_container,就可以简单地std::distance()对返回的迭代器进行操作.容器大小的复杂性将是对数,equal_range并且返回迭代器范围的大小为线性.如果您对结果不感兴趣但仅对计数感兴趣,那么还有一个广义count()成员函数返回相同的对数+线性时间.