c++ - 对映射中的 lower_bound 和 upper_bound

Question

我试图从这里了解配对地图中的lower_bound和upper_bound。

定义如下：

lower_bound： 在对的映射中，pair(x, y)的lower_bound( )将返回一个迭代器，该迭代器指向第一个值大于或等于 x 且第二个值大于或等于 y 的对。如果不满足上述条件，则返回一个指向对{map.size(), 0}的迭代器。

upper_bound： 在pair(x, y)的映射中， upper_bound( )将返回一个迭代器，该迭代器指向第一个值大于 x 且第二个值大于 y 的对。如果不满足上述条件，则返回一个指向对{map.size(), 0}的迭代器。

现在，让我们考虑下面的例子。

map<pair<int, int>, int> mp;

mp.insert({ { 2, 3 }, 8 });
mp.insert({ { 2, 5 }, 5 });
mp.insert({ { 7, 1 }, 3 });
mp.insert({ { 9, 3 }, 1 });
mp.insert({ { 5, 0 }, 3 });

我们有上面的配对图。

现在，如果我想找到对{2, 4}的下限，结果是 {2, 5} 根据定义对我来说似乎很好。定义说“ lower_bound 将返回一个迭代器，该迭代器指向第一个值大于或等于 x 且第二个值大于或等于 y 的对”。因此，在这种情况下，2 等于 2，5 大于 4。

但是，如果我想找到对{2,2}的上限，结果是{2, 3}根据定义在我看来这是错误的。定义说“ upper_bound 将返回一个迭代器，该迭代器指向第一个值大于 x 且第二个值大于 y的对”但在上述情况下，第一个值等于 x。根据定义，{2,2}的上界应为{9, 3}，其中 9 大于 2，3 大于 2。

我想我在这里错过了一些东西。任何人都可以在这里帮助我吗？

标签： c++stl

Answer 1

您通过键值将其存储在有序映射中。地图键的顺序如下：

<2, 3> | <2, 5> | <5, 0> | <7, 1> | <9, 3> 

看这里。

因此，实际std::map::upper_bound参考说明如下：

iterator upper_bound( const Key& key );

返回一个迭代器，指向大于 key 的第一个元素。

由此不难看出，列表中大于<2, 2>is的第一个键<2, 3>（对于 call mp.upper_bound(std::make_pair(2, 2))）。