C++ STL: lower_bound 和 upper_bound 函数区别详解

lower_bound 和 upper_bound 是 C++ STL 中的两个重要函数，用于在有序容器（如 vector、set、map）中查找某个值的特定位置。

• lower_bound 返回第一个大于等于给定值的元素位置。如果所有元素都小于给定值，则返回容器的 end() 迭代器。

• upper_bound 返回第一个大于给定值的元素位置。如果所有元素都小于等于给定值，则返回容器的 end() 迭代器。

关键区别在于：

• lower_bound 返回第一个大于等于目标值的元素位置。
• upper_bound 返回第一个大于目标值的元素位置。

处理重复元素：

如果容器中存在多个相同的元素，lower_bound 和 upper_bound 返回的位置可能会不同。例如：

std::vector<int> v = {1, 2, 2, 3, 4};

auto it1 = std::lower_bound(v.begin(), v.end(), 2); // it1 指向第一个 2
auto it2 = std::upper_bound(v.begin(), v.end(), 2); // it2 指向第一个 3

总结：

lower_bound 和 upper_bound 是查找有序容器中元素位置的强大工具。了解它们的差异和如何处理重复元素对于高效使用 C++ STL 至关重要。