简析为何非成员函数的 lower_bound/upper_bound 在 map/set 中是 O(n) 的
albertting
·
·
算法·理论
起因：SCP 中这题挂了 /ll
杂鱼 gza 还没讲到底为啥是 O(n) 的导致我困惑了好久啊！！！
正题开始。
:::info[UPD]{open}
本文中指的是形如 lower_bound(st.begin(), st.end(), val) 的用法，并非 set/map 的成员函数 lower_bound/upper_bound。可能造成了困扰，在此谢罪了 /kk
:::
最初的理解
:::warning[里面的观点是错误的]{open}
$O(\log n)$ 在外部二分。
于是类似于线段树二分但是二分写在外面，是 $O(\log^2 n)$ 的。
:::
看起来很有道理啊！
**实际上是错误的。**
## 分析源码！
:::warning{open}
全文一切源码来自的编译器版本：
```
g++ (Ubuntu 15.2.0-16ubuntu1) 15.2.0
Copyright (C) 2025 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
```
:::
找到 `stl_algo_base.h` 约第 1521 行（这里是唯一的重载）：
```cpp
/**
* @brief Finds the first position in which @a val could be inserted
* without changing the ordering.
* @param __first An iterator.
* @param __last Another iterator.
* @param __val The search term.
* @return An iterator pointing to the first element <em>not less
* than</em> @a val, or end() if every element is less than
* @a val.
* @ingroup binary_search_algorithms
*/
template<typename _ForwardIterator, typename _Tp>
_GLIBCXX_NODISCARD _GLIBCXX20_CONSTEXPR
inline _ForwardIterator
lower_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val)
{
// concept requirements
__glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
__glibcxx_function_requires(_LessThanOpConcept<
typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
__glibcxx_requires_partitioned_lower(__first, __last, __val);
return std::__lower_bound(__first, __last, __val,
__gnu_cxx::__ops::__iter_less_val());
}
```
调用了 `__lower_bound`。
看看（同文件 1493 行）（这里还是唯一的重载）：
```cpp
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_GLIBCXX20_CONSTEXPR
_ForwardIterator
__lower_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
{
typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;
_DistanceType __len = std::distance(__first, __last);
while (__len > 0)
{
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half);
if (__comp(__middle, __val))
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
else
__len = __half;
}
return __first;
}
```
这是二分啊！
怎么是 $O(n)$ 呢（叉腰）。
别急，再仔细瞅瞅：
```cpp
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_GLIBCXX20_CONSTEXPR
_ForwardIterator
__lower_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
{
typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;
_DistanceType __len = std::distance(__first, __last); // <- HERE!
while (__len > 0)
{
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half); // <- HERE!
if (__comp(__middle, __val))
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
else
__len = __half;
}
return __first;
}
```
对于 `map`/`set` 来说，这两个东西的复杂度是什么呢。。。
### `distance` 函数
`stl_iterator_base_funcs.h` 第 146 行：
```cpp
template<typename _InputIterator>
_GLIBCXX_NODISCARD __attribute__((__always_inline__))
inline _GLIBCXX17_CONSTEXPR
typename iterator_traits<_InputIterator>::difference_type
distance(_InputIterator __first, _InputIterator __last)
{
// concept requirements -- taken care of in __distance
return std::__distance(__first, __last,
std::__iterator_category(__first));
}
```
调用了 `__distance`。
欸这个东西有一堆重载？
几个重载分别是：
```cpp
template<typename _InputIterator>
inline _GLIBCXX14_CONSTEXPR
typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last,
input_iterator_tag)
```
```cpp
template<typename _RandomAccessIterator>
__attribute__((__always_inline__))
inline _GLIBCXX14_CONSTEXPR
typename iterator_traits<_RandomAccessIterator>::difference_type
__distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
random_access_iterator_tag)
```
```cpp
template<typename _OutputIterator>
void
__distance(_OutputIterator, _OutputIterator, output_iterator_tag) = delete;
```
（其实还有 `list` 相关重载，在此按下不表）
我们检查一下迭代器类型：
在 `stl_tree.h` 第 371 行（底层的红黑树迭代器）：
```cpp
template<typename _Tp>
struct _Rb_tree_iterator
{
typedef _Tp value_type;
typedef _Tp& reference;
typedef _Tp* pointer;
typedef bidirectional_iterator_tag iterator_category; // <- Here.
typedef ptrdiff_t difference_type;
typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
typedef _Rb_tree_node<_Tp>* _Node_ptr;
}
```
`bidirectional_iterator_tag` 是什么？
`stl_iterator_base_types.h` 第 86 行：
```cpp
/**
* @defgroup iterator_tags Iterator Tags
* These are empty types, used to distinguish different iterators. The
* distinction is not made by what they contain, but simply by what they
* are. Different underlying algorithms can then be used based on the
* different operations supported by different iterator types.
*/
///@{
/// Marking input iterators.
struct input_iterator_tag { }; // <- ③再到这里
/// Marking output iterators.
struct output_iterator_tag { };
/// Forward iterators support a superset of input iterator operations.
struct forward_iterator_tag : public input_iterator_tag { }; // <- ②到这里
/// Bidirectional iterators support a superset of forward iterator
/// operations.
struct bidirectional_iterator_tag : public forward_iterator_tag { }; // <- ①这个东东
/// Random-access iterators support a superset of bidirectional
/// iterator operations.
struct random_access_iterator_tag : public bidirectional_iterator_tag { };
```
发现是 `input_iterator_tag`。
回到上面三个重载发现应该是第一个：
```cpp
template<typename _InputIterator>
inline _GLIBCXX14_CONSTEXPR
typename iterator_traits<_InputIterator>::difference_type
__distance(_InputIterator __first, _InputIterator __last,
input_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
typename iterator_traits<_InputIterator>::difference_type __n = 0;
while (__first != __last) // <- 盲生，你发现了华点
{
++__first;
++__n;
}
return __n;
}
```
这个东西是暴力跳转的！
**所以它是 $O(n)$ 的。**
### `advance` 函数
`stl_iterator_base_funcs.h` 第 207 行：
```cpp
/**
* @brief A generalization of pointer arithmetic.
* @param __i An input iterator.
* @param __n The @a delta by which to change @p __i.
* @return Nothing.
*
* This increments @p i by @p n. For bidirectional and random access
* iterators, @p __n may be negative, in which case @p __i is decremented.
*
* For random access iterators, this uses their @c + and @c - operations
* and are constant time. For other %iterator classes they are linear time.
*/
template<typename _InputIterator, typename _Distance>
__attribute__((__always_inline__))
inline _GLIBCXX17_CONSTEXPR void
advance(_InputIterator& __i, _Distance __n)
{
// concept requirements -- taken care of in __advance
typename iterator_traits<_InputIterator>::difference_type __d = __n;
std::__advance(__i, __d, std::__iterator_category(__i));
}
```
又是调用。
这里直接出现了（同一文件 168 行）：
```cpp
template<typename _BidirectionalIterator, typename _Distance>
inline _GLIBCXX14_CONSTEXPR void
__advance(_BidirectionalIterator& __i, _Distance __n,
bidirectional_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_BidirectionalIteratorConcept<
_BidirectionalIterator>)
if (__n > 0)
while (__n--)
++__i;
else
while (__n++)
--__i;
}
```
:::info[为啥这里突然变 `_BidirectionalIterator`]{open}
因为 `_BidirectionalIterator` 也是一种 `_InputIterator`，这里有优先级更高的就直接用了。
:::
好的呢又是暴力跳！
再次观察二分：
```cpp
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_GLIBCXX20_CONSTEXPR
_ForwardIterator
__lower_bound(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val, _Compare __comp)
{
typedef typename iterator_traits<_ForwardIterator>::difference_type
_DistanceType;
_DistanceType __len = std::distance(__first, __last);
while (__len > 0)
{
_DistanceType __half = __len >> 1;
_ForwardIterator __middle = __first;
std::advance(__middle, __half);
if (__comp(__middle, __val))
{
__first = __middle;
++__first;
__len = __len - __half - 1;
}
else
__len = __half;
}
return __first;
}
```
我们发现 `__half` 每轮折半，**于是总时间复杂度 $O(n)$。**
---
至此，我们就知道了这个二分其实是 $O(n)$ 的。
## 为啥 `vector` 上面就是 $O(\log n)$ 了
你不是只有一个重载吗怎么 `vector` 就变 $O(\log n)$ 了？
原因其实简单。
由于不是主要部分，这里就少放一些代码了。
`vector` 的迭代器实际上是 `_RandomAccessIterator`，这个东西的两个重点函数分别是：
`stl_iterator_base_funcs.h` 第 98 行：
```cpp
template<typename _RandomAccessIterator>
__attribute__((__always_inline__))
inline _GLIBCXX14_CONSTEXPR
typename iterator_traits<_RandomAccessIterator>::difference_type
__distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
random_access_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_RandomAccessIteratorConcept<
_RandomAccessIterator>)
return __last - __first;
}
```
`stl_iterator_base_funcs.h` 第 184 行：
```cpp
template<typename _RandomAccessIterator, typename _Distance>
inline _GLIBCXX14_CONSTEXPR void
__advance(_RandomAccessIterator& __i, _Distance __n,
random_access_iterator_tag)
{
// concept requirements
__glibcxx_function_requires(_RandomAccessIteratorConcept<
_RandomAccessIterator>)
if (__builtin_constant_p(__n) && __n == 1)
++__i;
else if (__builtin_constant_p(__n) && __n == -1)
--__i;
else
__i += __n;
}
```
这两个明显都是 $O(1)$ 的。
于是二分就是真的 $O(\log n)$ 了！