有效地计算两个std :: multimap迭代器之间的条目数 [英] Efficiently count number of entries between two std::multimap iterators

问题描述

我想在小于O（N）的时间内计算 std :: multimap 的两个迭代器之间的条目数。

由于 std :: multimap 有双向迭代器，我的理解是<@ c $ c> std :: distance 可以在O（N）时间执行此操作。

其他详细信息： multimap 的键是N元组。我试图找到 multimap 中键的第一个元素为0的条目数。键的第一个元素的选项为0和1， code> multimap 使用严格的弱顺序，其中键的第一个元素始终是最重要的。

上下文：迭代器由 equal_range 返回，其在对数时间中运行。在声明方面，我想测量范围的长度。

谢谢。

解决方案

您正在寻找的是所谓的 异质比较查找 。它允许在用于存储 Key 的 equal_range 成员函数中的不同但兼容 code>。在你的情况下，查找比较运算符（第一个元组成员）将不同于但与元组词典编码比较一致。

不幸的是，根据 此问答 。然而，N3465论文的作者也是Boost.MultiIndex的作者，它实现了 此功能 。您可以 模拟 std :: multimap 按照Boost.MultiIndex文档。

适应的 boost :: multiindex_container 的通用 equal_range 成员函数，然后可以简单地做 std :: distance（）。复杂性将在 equal_range 的容器大小中是对数的，并且在返回的迭代器范围的大小中是线性的。如果你对结果不感兴趣，但只在计数，还有一个广义的 count（）成员函数返回在同一对数+线性时间。 >

I would like to count the number of entries between two iterators of an std::multimap in less than O(N) time. Are there any tricks or clever ways to do this?

Since std::multimap has bidirectional iterators, my understanding is that something like std::distance could do this in O(N) time.

Additional details: The multimap's key is an N-tuple. I'm trying to find the number of entries in the multimap whose key's first element is 0. The options for the first element of they key are 0 and 1, and the multimap uses a strict weak ordering in which the first element of the key is always the most important. i.e., all elements with 0 come before any elements with 1.

Context: The iterators are returned by equal_range, which runs in logarithmic time. Declaratively, I'd like to measure the length of the range.

Thank you.

解决方案

What you are looking for is so-called heterogeneous comparison lookup that was proposed in N3465. It allows for a different but compatible comparison function in the equal_range member function that is being used to store the Key. In your case, the lookup comparison operator (first tuple member) would be different from but consistent with the tuple lexicographical comparison.

Unfortunately, only a small portion of that paper has been accepted into the draft C++14 Standard, according to this Q&A. However, the N3465 paper's author is also the author of Boost.MultiIndex that has implemented this feature. You can emulate a std::multimap by following the Boost.MultiIndex documentation.

Once you have used the generalized equal_range member function of an adapted boost::multiindex_container, you can then simply do std::distance() on the returned iterators. Complexity would be logarithmic in the container size for the equal_range and linear in the size of the returned iterator range. If you are not interested in the result but only in the count, there is also a generalized count() member function returning that in the same logarithmic + linear time.

这篇关于有效地计算两个std :: multimap迭代器之间的条目数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！