使用vector反向迭代器与降序vector正向迭代器调用lower_bound()结果是否一致？

结论 #

两个表达式始终返回逻辑等价的结果，但二者的底层工作机制存在差异。

结果一致性分析 #

首先明确std::lower_bound的核心行为：当传入自定义比较函数greater<int>()时，要求目标序列必须是按该比较函数定义的有序序列（即序列满足降序排列，因为greater<int>()(a,b)为真意味着a > b），函数会返回第一个不满足greater<int>()(some_number, element)的元素迭代器——也就是第一个element >= some_number的元素（当some_number不存在于序列中时，返回第一个大于等于它的元素；存在时返回第一个匹配的元素）。

• 表达式1中，inc是升序序列，通过rbegin()和rend()反向迭代器遍历，实际访问的元素顺序为7,6,4,3,2,1，和dec的元素顺序完全一致，且满足降序的有序性要求。
• 表达式2直接遍历本身就是降序的dec序列，同样满足greater<int>()要求的有序性。

由于两个表达式遍历的元素序列完全相同，且lower_bound的查找逻辑一致，因此最终找到的元素值必然相同，返回的迭代器在各自序列中指向的是逻辑等价的位置（即对应相同值的元素）。

工作机制差异 #

1. 迭代器类型不同

   • 表达式1使用的是reverse_iterator（反向迭代器），它是对原正向迭代器的封装，底层通过偏移原正向迭代器来实现反向遍历。例如，inc.rbegin()对应的底层正向迭代器是inc.end()，解引用时会访问前一个位置的元素。
   • 表达式2使用的是普通的vector<int>::iterator（正向迭代器），直接按序列物理顺序遍历。

2. 迭代器指向的物理位置与操作特性不同

   • 即使找到的元素值相同，两个迭代器的底层物理指向分属不同容器（inc和dec是独立容器），且操作逻辑相反：反向迭代器的++操作等价于正向迭代器的--操作，后续若对迭代器进行遍历，两者的遍历方向完全相反。

内容的提问来源于stack exchange，提问作者SHUBHAM KUMAR