std::multimap获取两个范围

Question

我正在使用C++的std::multimap，需要循环遍历两个不同的键。除了创建两个范围并分别循环遍历这些范围之外，是否有更有效的方法来完成这项任务？

这是我现在的做法：

std::pair<std::multimap<String, Object*>::iterator,std::multimap<String, Object*>::iterator> range;
std::pair<std::multimap<String, Object*>::iterator,std::multimap<String, Object*>::iterator> range2;

// get the range of String key
range = multimap.equal_range(key1);
range2 = multimap.equal_range(key2);

for (std::multimap<String, Object*>::iterator it = range.first; it != range.second; ++it)
{
    ...
}
for (std::multimap<String, Object*>::iterator it2 = range2.first; it2 != range2.second; ++it2)
{
    ...
}

- Kaiser Wilhelm

---

你为什么认为它不够高效？ - Andriy Tylychko

这是我第一次使用multimap，所以我对它们不太熟悉。我将在这些循环中进行大量工作，我想知道是否有另一种操作可以同时获取两个范围或类似的东西。 - Kaiser Wilhelm

你能举一个键重叠但不相等的例子吗？也许我的大脑有点迟钝，但似乎对键进行简单的相等性检查就可以了。如果每个查询都有单独的下限和上限，那么对我来说更有意义。 - Tom Kerr

这是一个很好的例子，单个typedef可以消除更大部分的代码，并使代码显着更易读：typedef std::multimap<String, Object*>::iterator Iter。 - Andriy Tylychko

Answer 1

你使用的代码是最直接的。

如果你真的想在同一个循环中迭代两个范围，你可以创建一个自定义迭代器，它接受两个迭代器范围，遍历第一个范围直到完成，然后切换到第二个。这可能比它值得的麻烦，因为你需要自己实现所有迭代器成员。

编辑：我考虑过度了；将这两个循环修改为一个循环非常容易。

for (std::multimap<String, Object*>::iterator it = range.first; it != range2.second; ++it)
{
    if (it == range.second)
    {
        it = range2.first;
        if (it == range2.second)
            break;
    }
    ...
}

- Mark Ransom

---

我也考虑过这个。但是，这两个键必须紧挨着才能生效吗？例如，如果我有3个键，并且我想循环遍历第一个和第三个，它会将第二个键包含在其中吗？或者那些if语句可以解决这个问题吗？ - Kaiser Wilhelm

@Kaiser，if语句处理从第一个范围到第二个范围的转换。它们甚至可以无序。唯一不能做的事情是相交；如果range2包含range.second，那么你将得到一个无限循环。 - Mark Ransom

啊，我明白了。我的range2是静态的，而range1总是会不同。它们永远不应该相交，对吧？因为multimap在插入时进行排序？ - Kaiser Wilhelm

@Kaiser，只要键不同并且您像在问题中所做的那样使用equal_range，范围就不会相交。我还检查了一下插入是否会使您的range2迭代器失效：https://dev59.com/OGw15IYBdhLWcg3wuuGn - Mark Ransom

Answer 2

Boost当然可以实现这一点。使用Boost.Range和它的join函数，你就可以得到你想要的结果。详情请参见Boost Range Library: Traversing Two Ranges Sequentially。

- deft_code

---

谢谢，Boost看起来非常强大。不幸的是，我的公司很传统，讨厌新事物...我想他们只能忍受低效率了。 - Kaiser Wilhelm

这次不是关于效率，而是关于方便。 - Andriy Tylychko

Answer 3

如果您可以访问C++-11（Visual Studio 10+，gcc-4.5+）并被允许使用它，auto是一个真正的宝石：

// get the range of String key
auto range = multimap.equal_range(key1);
auto range2 = multimap.equal_range(key2);

for (auto it = range.first; it != range.second; ++it)
{
    ...
}
for (auto it2 = range2.first; it2 != range2.second; ++it2)
{
    ...
}

无论如何，我只会测试键并且仅在key2 != key1时执行第二个循环。在循环中每次检查迭代器都有一些成本。

从第二个范围中std::set_difference第一个范围可能简化代码。 也许std::set_union两个范围并通过back_inserter插入到一个集合中，这样你只会得到一个副本？

一些实验可能是必要的。不要忘记将您的第一个猜测放入混合物中。它可能会让你惊讶，因为速度非常好。除非范围通常非常长和/或循环操作很昂贵，否则增加额外的簿记可能不值得头痛。

- emsr