在使用lower_bound和upper_bound时，想自定义比较函数，在这个过程中出现了参数定义顺序导致的错误问题，于是查找学习了下自定义比较函数需要符合的规则。
目录
1 lower_bound和upper_bound函数
1.1 lower_bound
lower_bound 函数返回一个迭代器，指向容器中第一个大于或等于给定值的元素。如果容器中没有这样的元素，则返回容器的 end() 迭代器。
语法：
iterator lower_bound(iterator begin, iterator end, const value_type& value);
iterator lower_bound(iterator begin, iterator end, const value_type& value, Compare compare);参数：
begin和end：指定要搜索的容器的范围。value：要查找的值。- compare：比较函数。
返回值：
一个迭代器，指向容器中第一个大于或等于 value 的元素。如果容器中没有这样的元素，则返回 end() 迭代器。
示例：
std::vector<int> v = {1, 4, 5, 7, 9};
// 查找第一个大于或等于 4 的元素
auto it = std::lower_bound(v.begin(), v.end(), 4);
// 输出迭代器指向的元素
std::cout << *it << std::endl; // 输出 4
1.2 upper_bound
upper_bound 函数返回一个迭代器，指向容器中第一个大于给定值的元素。如果容器中没有这样的元素，则返回容器的 end() 迭代器。
语法：
iterator upper_bound(iterator begin, iterator end, const value_type& value);
iterator upper_bound(iterator begin, iterator end, const value_type& value，Compare compare);
参数：
begin和end：指定要搜索的容器的范围。value：要查找的值。
返回值：
一个迭代器，指向容器中第一个大于 value 的元素。如果容器中没有这样的元素，则返回 end() 迭代器。
示例：
std::vector<int> v = {1, 4, 5, 7, 9};
// 查找第一个大于 4 的元素
auto it = std::upper_bound(v.begin(), v.end(), 4);
// 输出迭代器指向的元素
std::cout << *it << std::endl; // 输出 5
从上面示例中可以看到二者的区别：
lower_bound查找第一个大于或等于给定值的元素，- 而
upper_bound查找第一个大于给定值的元素。
起初，我认为二者的区别仅仅在此，但很快，就遇到了新的问题。
2 问题产生
观察这两行代码：
auto left = lower_bound(intervals.begin(),intervals.end(),newInterval[0],[](auto& a, int b) { return a[1] < b; });
auto right = upper_bound(left,intervals.end(),newInterval[1],[](int b,auto& a) { return a[0] > b; });或许乍一看没什么特别的，但是强迫症一定能看到问题所在：两个匿名函数定义的参数顺序太不整齐了。
但当我尝试交换参数顺序使其看起来整齐一些，啪的一下，编译出错。
In file included from prog_joined.cpp:1:
In file included from /leetcode/precompiled/headers.h:13:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/cmath:1935:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/specfun.h:45:
In file included from /usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/stl_algobase.h:71:
/usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/predefined_ops.h:240:16: error: no matching function for call to object of type '(lambda at prog_joined.cpp:14:70)'
231 | { return bool(_M_comp(__val, *__it)); }
| ^~~~~~~
/usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/stl_algo.h:2041:8: note: in instantiation of function template specialization '__gnu_cxx::__ops::_Val_comp_iter<(lambda at prog_joined.cpp:14:70)>::operator()<const int, __gnu_cxx::__normal_iterator<std::vector<int> *, std::vector<std::vector<int>>>>' requested here
2032 | if (__comp(__val, __middle))
| ^
/usr/bin/../lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/stl_algo.h:2108:19: note: in instantiation of function template specialization 'std::__upper_bound<__gnu_cxx::__normal_iterator<std::vector<int> *, std::vector<std::vector<int>>>, int, __gnu_cxx::__ops::_Val_comp_iter<(lambda at prog_joined.cpp:14:70)>>' requested here
2099 | return std::__upper_bound(__first, __last, __val,
| ^
Line 5: Char 22: note: in instantiation of function template specialization 'std::upper_bound<__gnu_cxx::__normal_iterator<std::vector<int> *, std::vector<std::vector<int>>>, int, (lambda at solution.cpp:14:70)>' requested here
5 | auto right = upper_bound(left,intervals.end(),newInterval[1],[](auto& a, int b) { return a[0] > b; });
| ^
Line 5: Char 70: note: candidate function template not viable: no known conversion from 'std::vector<int>' to 'int' for 2nd argument
5 | auto right = upper_bound(left,intervals.end(),newInterval[1],[](auto& a, int b) { return a[0] > b; });
| ^ ~~~~~
1 error generated.3 问题研究及原因
难道我们定义的匿名函数都不可以随便定义吗？
并非如此，将匿名函数拉出upper_bound和lower_bound放到其他位置，运行的好好的。
那基本可以确定问题处在upper_bound和lower_bound上。
这里要理解像这样一条语句，究竟是如何运行的？编译器怎么知道我们的a和b究竟是什么东西？
auto left = lower_bound(intervals.begin(),intervals.end(),newInterval[0],[](auto& a, int b) { return a[1] < b; });那么就涉及到了lower_bound的具体实现。
可以想到的是，其内部将intervals这个容器的起始到结尾作为需要比较的对象，newInterval[0]这个值作为目标值。
那它又如何确定a对应的intervals容器还是newInterval[0]这个值？
答案是约定，它需要约定我们传入参数的顺序，也就是出现问题的这个匿名函数参数顺序的地方。
来看lower_bound的源码：
template<class ForwardIt, class T, class Compare>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
ForwardIt it;
typename std::iterator_traits<ForwardIt>::difference_type count, step;
count = std::distance(first, last);
while (count > 0)
{
it = first;
step = count / 2;
std::advance(it, step);
if (comp(*it, value))
{
first = ++it;
count -= step + 1;
}
else
count = step;
}
return first;
}注意这一句：
comp(*it, value)它约定了比较函数的第一个参数是容器内容，第二个参数是目标值。
那upper_bound呢？
template<class ForwardIt, class T, class Compare>
ForwardIt upper_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
ForwardIt it;
typename std::iterator_traits<ForwardIt>::difference_type count, step;
count = std::distance(first, last);
while (count > 0)
{
it = first;
step = count / 2;
std::advance(it, step);
if (!comp(value, *it))
{
first = ++it;
count -= step + 1;
}
else
count = step;
}
return first;
}好嘛，正好是反过来的。
comp(value, *it)4 总结
- 在自定义比较函数的时候需要知道函数原型，即约定的哪个参数代表什么含义，这样编译器才会知道我们传入的是什么。
- 对于upper_bound，比较函数的第一个参数是目标值，第二个参数是需要比较的容器内容。
- 对于lower_bound，比较函数的第一个参数是需要比较的容器内容，第二个参数是目标值。
- lower_bound和upper_bound的开发维护人员，一定不是强迫症。
- 附一张文心一言画得强迫症，好像emmm......一言难尽
