std :: lower_bound和std :: upper_bound的基本原理？
STL提供了二进制search函数std :: lower_bound和std :: upper_bound，但我倾向于不使用它们，因为我一直无法记住它们做什么，因为它们的契约对我来说似乎完全神秘。
只要看名字，我猜想“lower_bound”可能是“last lower bound”的缩写，
即sorting列表中最后一个<=给定值（如果有的话）的元素。
同样，我猜“upper_bound”可能是“第一上限”的缩写，
即sorting列表中的第一个元素> =给定的val（如果有的话）。
但文件说，他们做了一些相当不同的东西 – 似乎是一种倒退和随机的混合物，对我来说。 解释文档：
– lower_boundfind> = val的第一个元素
– upper_boundfind> val的第一个元素
所以lower_bound根本找不到下界; 它find第一个上界！？ upper_boundfind第一个严格的上界。
这有意义吗？？ 你怎么记得它？
如果在[ first ， last ]范围内有多个元素，其值等于您要search的值val ，则范围[ l ， u ）在
l = std::lower_bound(first, last, val) u = std::upper_bound(first, last, val)
恰恰是等于[范围内first ， last范围内的val ]元素的范围。 所以l和u是相等范围的“下限”和“上限”。 如果你习惯于半开放的时间间隔思考，这是有道理的。
（请注意， std::equal_range将在一次调用中返回一对中的下限和上限。）
std::lower_bound
返回一个迭代器，它指向[first，last）范围中不小于（即大于或等于 ）值的第一个元素。
std::upper_bound
返回指向大于值的[first，last]范围中第一个元素的迭代器。
所以通过混合下限和上限，您可以准确地描述您的范围的起点和结束位置。
这有意义吗？？
对我来说，是的，但这是基于意见的。 （而且我不得不承认，前段时间我也很困惑，虽然现在我不明白为什么：p）
例：
想象vector
std::vector<int> data = { 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 }; auto lower = std::lower_bound(data.begin(), data.end(), 4); 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 // ^ lower auto upper = std::upper_bound(data.begin(), data.end(), 4); 1, 1, 2, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6 // ^ upper std::copy(lower, upper, std::ostream_iterator<int>(std::cout, " "));
打印：4 4 4
考虑序列
1 2 3 4 5 6 6 6 7 8 9
6的下界是前6的位置。
6的上界是7的位置。
这些职位作为共同（开始，结束）对指定运行的6值。
例：
#include <algorithm> #include <iostream> #include <vector> using namespace std; auto main() -> int { vector<int> v = {1, 2, 3, 4, 5, 6, 6, 6, 7, 8, 9}; auto const pos1 = lower_bound( v.begin(), v.end(), 6 ); auto const pos2 = upper_bound( v.begin(), v.end(), 6 ); for( auto it = pos1; it != pos2; ++it ) { cout << *it; } cout << endl; }
在这种情况下，我认为一张图片胜过千言万语。 假设我们使用它们在以下集合中search2 。 箭头显示了二者将返回的迭代器：
所以，如果你有多个对象的值已经存在于集合中，那么lower_bound将给你一个引用它们中第一个的迭代器，而upper_bound将给出一个迭代器，它在最后一个他们。
这（除其他外）使得返回的迭代器可以用作insert的hint参数。
因此，如果使用这些作为提示，则插入的项目将成为具有该值的新项目（如果使用lower_bound ）或具有该值的最后项目（如果使用upper_bound ）。 如果集合之前没有包含具有该值的项目，则仍然会得到一个可用作hint的迭代器，以将其插入集合中的正确位置。
当然，你也可以在没有提示的情况下插入，但是使用提示可以保证插入以不断的复杂性完成，只要可以在迭代器指向的项之前插入新的插入项（就像它将在这两种情况）。
我接受了Brian的回答，但我意识到另一个有用的思考方式，这为我增加了清晰度，所以我将其添加为参考。
把返回的迭代器想象成指向，而不是在元素* iter，而是在元素之前 ，即在元素和列表中前面的元素之间（如果有的话）。 考虑这种方式，两个函数的契约变得对称：lower_boundfind从<val到> = val的过渡位置，upper_boundfind从<= val到> val的过渡位置。 或者换句话说，lower_bound是比较等于val的项的范围的开始（即，std :: equal_range返回的范围），并且upper_bound是它们的结束。
我希望他们能够在文档中像这样（或者给出的任何其他好的答案）来谈论它。 那会让它变得更加神秘！
两个函数都非常相似，因为它们将在sorting顺序中find一个插入点来保存sorting。 如果序列中没有与search条目相同的元素，则它们将返回相同的迭代器。
如果您正在尝试查找序列中的某些内容，请使用lower_bound – 如果find，它将直接指向该元素。
如果你插入序列，使用upper_bound – 它保留了重复的原始顺序。
关于std::lower_bound和std::upper_bound是已经有很好的答案了。
我想回答你的问题“如何记住他们” ？
它很容易理解/记住，如果我们用任何容器的STL begin()和end()方法进行类比。 begin()将起始迭代器返回到容器，而end()返回容器外的迭代器，我们都知道它们在迭代时是多么有用。
现在，在一个已sorting的容器和给定值上， lower_bound和upper_bound将返回迭代器的范围，该值易于迭代（就像开始和结束一样）
实用用法::
除了上面提到的使用sorting列表来访问给定值的范围之外，upper_bound的更好的应用之一是访问映射中具有多对一关系的数据。
例如，考虑以下关系：1→a→2→a→3→a→4→b→5→c→6→c→7→c→8→c→9→ > c，10 – > c
以上10个映射可以保存在地图中，如下所示：
numeric_limits<T>::lowest() : UND 1 : a 4 : b 5 : c 11 : UND
值可以通过expression式(--map.upper_bound(val))->second来访问。
对于从最低到0的T值，expression式将返回UND 。 对于T的值从1到3，它将返回“a”等。
现在，想象我们有100个数据映射到一个值和100个这样的映射。 这种方法减小了地图的大小，从而使其效率。
对于数组或向量：
std :: lower_bound：返回指向范围中第一个元素的迭代器
- 小于或等于值（对于数组或降序的向量）
- 大于或等于值（对于数组或升序的向量）
std :: upper_bound：返回指向第一个元素的迭代器
-
小于值（对于数组或降序的向量）
-
大于值（对于数组或向量，按升序排列）
