我正在std::upper_bound从http://www.cplusplus.com/reference/algorithm/upper_bound/学习
，我发现这可能在非随机访问迭代器上以线性时间运行。
我需要将其用于已排序的向量。现在我不知道什么是非随机访问迭代器以及它是否会在排序向量上以对数时间运行。
任何人都可以为我清除这个。
问问题
7262 次
1 回答
9
§ 23.3.6.1 [vector.overview]/p1：
向量是支持随机访问迭代器的序列容器。
随机访问迭代器能够在恒定时间内计算任意元素的偏移量，而无需从一个地方迭代到另一个地方（这会导致线性复杂度）。
std::lower_bound它本身提供了二分搜索算法的通用实现，它不太关心使用什么迭代器来指示范围（它只要求迭代器至少是一个前向类别）。它使用辅助函数std::advance来迭代地限制其二进制搜索的范围。它属于随机访问类别，就迭代元素所需的步骤数而言，它以对数时间复杂度运行，因为它可以在恒定时间内将每个步骤中的范围划分为一半std::vector<T>::iterator。std::lower_bound
§ 25.4.3 [alg.binary.search]/p1：
本节中的所有算法都是二进制搜索的版本，并假设正在搜索的序列是根据通过将搜索键绑定到隐含或显式比较函数的参数而形成的表达式进行分区的。他们在非随机访问迭代器上工作，最大限度地减少比较次数，这对于所有类型的迭代器都是对数的。它们特别适用于随机访问迭代器，因为这些算法通过数据结构执行对数步数。对于非随机访问迭代器，它们执行线性数量的步骤。
于 2015-08-16T10:53:56.110 回答