lower_bound 和 upper_bound 在配对图中

Question

我试图理解 lower_bound 和 upper_bound 中的成对映射 here.

定义如下：

lower_bound: 在成对映射中，lower_bound() for pair(x, y) 将 return 指向该对的迭代器其第一个值大于或等于 x，第二个值大于或等于 y。如果不满足上述条件，那么它 return 是一个指向对 {map.size(), 0}.[=14 的迭代器=]

upper_bound: 在成对映射中 upper_bound() for pair(x, y) 将 return 指向该对的迭代器其第一个值大于 x，第二个值大于 y。如果不满足上述条件，那么它 return 是一个指向对 {map.size(), 0}.[=14 的迭代器=]

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

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 将 return 指向第一个值大于或等于 x 和第二个值大于或等于 y[=49= 的对的迭代器]”。因此，在这种情况下，2 等于 2，5 大于 4。

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

我想我在这里漏掉了什么。有人可以帮我吗？

Answer 1

For upper_bound greater 表示根据映射中键的类型更大。本例中的键是一对整数，一对整数的 operator< 用于此比较。根据此运算符的定义，如果对中的第一个元素相同，则比较第二个元素，因此 {2, 3} 实际上 比 {2, 2} 大 。

这里是link到gnu implementation供参考。

Answer 2

您正在按键值将其存储在 ordered 映射中。地图键的顺序如下：

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

See here.

因此，实际的 std::map::upper_bound reference 表示如下：

iterator upper_bound( const Key& key );

Returns an iterator pointing to the first element that is greater than key.

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

lower_bound 和 upper_bound 在配对图中

lower_bound and upper_bound in Map of Pairs

c++

stl