为什么std :: set :: lower_bound(x)(有效)定义为最小数> = x而不是最大数<= x？

Question

也许我误解了技术定义,lower bound但我希望如果我有一个集合a = { 0, 3, 4 }并计算a.lower_bound(2)结果将是0.即我希望std::set::lower_bound接近infimum的数学概念

然而,标准库将其定义为不小于(有效>=)x 的最大数字.

这背后的原因是什么？

Answer 1

" [lower|upper]_bound"函数用于返回集合中的位置,您可以在其中插入不会违反集合顺序的键.因为STL设置的迭代器指向下一个元素之前,如果lower_bound(2)返回迭代器0,那么插入2将违反你的集合的顺序,现在就是{2, 0, 3, 4}.上限用于显示您可以在不违反设置顺序的情况下插入的最后一个位置.

如果您的集合可能包含重复的键条目,则此选项非常有用.考虑{0, 3, 3, 4}.lower_bound(3)将返回一个迭代器到这里:{0, *, 3, 3, 4},同时upper_bound(3)将它返回到:{0, 3, 3, *, 4}.

Answer 2

它可以帮助考虑的行为lower_bound和upper_bound在一起.

在STL中,范围始终是闭合打开的间隔.的范围内通过两个迭代划界,first并且last包括所有的元素的first和last,其中包括first和排除last.使用区间符号,我们将其表示为[first, last).

lower_bound并且upper_bound定义为使得它们找到比较等于指定值的元素范围.如果在lower_bound(x)和之间进行迭代upper_bound(x),则将迭代所有比较等于的元素x.如果没有元素相等x,那么可以保证lower_bound(x) == upper_bound(x).

此功能不太重要std::map,每个键最多只有一个元素,但对于非唯一关联容器以及std::lower_bound可与任意排序元素序列一起使用的非成员非常有用.

[请注意,如果你想获得两者的下限和上限,你应该叫equal_range相反,这两者都返回.]