C++中set与map内元素lower_bound的索引获取问题

这个问题的核心在于C++标准容器迭代器的类型差异，咱们来具体拆解：

1. 数组、vector的迭代器：随机访问迭代器 #

数组的原生指针（以及vector的迭代器）属于随机访问迭代器，这类迭代器支持完整的算术运算：

• 可以直接用+/-偏移固定步数（比如it + 5）
• 可以直接让两个迭代器相减，得到它们之间的元素个数（也就是你用到的lower_bound返回值 - begin()写法）

这是因为数组和vector的内存是连续存储的，迭代器本质和指针类似，能直接通过内存地址的加减计算位置差，所以这种写法完全合法。

2. set、map的迭代器：双向迭代器 #

而set和map的底层实现是红黑树，它们的迭代器属于双向迭代器，这类迭代器的能力有限：

• 只能通过++/--操作一步步移动到下一个/上一个元素
• 不支持直接的减法运算，所以编译器会提示no match for ‘operator-’——因为标准库根本没有为双向迭代器定义这个运算符。

怎么获取set/map中元素的位置序号？ #

如果你想得到lower_bound返回的元素在容器中的位置（从begin开始的计数），可以用标准库的std::distance函数：

#include <iterator> // 需要包含这个头文件

std::set<int> s = {1,3,5,7};
int number = 4;
auto it = s.lower_bound(number);
std::cout << std::distance(s.begin(), it) << std::endl; // 输出2

不过要注意：对于双向迭代器，std::distance会通过遍历从第一个迭代器走到第二个，时间复杂度是O(n)；而对于随机访问迭代器，它直接用减法实现，时间复杂度是O(1)。

另外要明确：set和map本身是无索引概念的有序容器，这里的“位置序号”只是从begin开始的元素计数，和数组/vector的索引不是同一个东西——后者是内存位置的直接映射，前者只是遍历顺序的计数。

内容的提问来源于stack exchange，提问作者Sai Teja T