基本语法——lower/upper_bound 学习笔记
正文
本文保证：你看了也不懂
| \(\texttt{lower\_bound}\) | \(\texttt{upper\_bound}\) | |
|---|---|---|
| 默认比较函数 | 返回第一个 \(\cancel{<}\text{value}\) 的元素 | 返回第一个 \(>\text{value}\) 的元素 |
| 自定义比较函数 | 返回第一个 \(\texttt{false}\) 的元素 | 返回第一个 \(\texttt{true}\) 的元素 |
| 使用限制 | 序列前半部分为 \(\texttt{true}\) 后面均为 \(\texttt{false}\) |
序列前半部分为 \(\texttt{false}\) 后面均为 \(\texttt{true}\) |
相同点
| 自定义比较符号 | \(<\) |
| 指向范围 | \([\text{first},\text{last})\) |
| 无结果返回 | \(\text{last}\) |
| 最大比较次数 | \(\mathcal{O}(\log_2\text{size})\) |
特殊性质
| \(\texttt{std::(multi)map/set}\) | 其成员函数的表现更好 其复杂度与容器大小成对数 |
记忆方法
- \(\texttt{lower}\) 是小于，但是 \(\texttt{lower}\) 比较 \(\text{low}\)，所以她在 \(<\) 上加了一笔，成了 \(\cancel{<}\)；
- \(\texttt{upper}\) 是大于，她的格局比较大，所以她 \(\text{accept}\) 了 \(>\)；
- \(\texttt{false}=0<1=\texttt{true}\)，因此 \(\texttt{lower}\) 找 \(\texttt{false}\)，\(\texttt{upper}\) 找 \(\texttt{true}\):
- 她们找不到朋友，就会很郁闷，不知不觉就走过了，到了 \(\text{last}\) 发现回不去了。
Reference
[1] https://blog.csdn.net/qq_42303573/article/details/128082762
[2] https://zh.cppreference.com/w/cpp/algorithm/lower_bound
[3] https://zh.cppreference.com/w/cpp/algorithm/upper_bound
[4] https://zh.cppreference.com/w/cpp/container/map/lower_bound
[5] https://zh.cppreference.com/w/cpp/container/map/upper_bound