前言

从本节开始，将会分析 algo.h 中的算法，这部分的算法有很多，也不可能逐一分析，因此这里就挑几个典型且重要的进行分析，即使这样依然有很多啊喂，主要会分析 equal_range、rotate、next_permutation、merge、sort、nth_element，其他的函数如果读者感兴趣的话可以自行查看 STL 的实现。

equal_range

算法 equal_range 是二分查找法的一个版本，试图在已排序的 (first, last) 中寻找 value。它返回一对迭代器 i 和 j，其中 i 是在不破坏次序的前提下，value 可插入的第一个位置（亦即lower_bound）,j 则是在不破坏次序的前提下, value 可插入的最后一个位置（亦即upper_bound）。

当 (first, last) 并未含有与 vaiue 相同的任何元素时，返回的区间将是一个空区间，即返回的 i 和 j 指向同一个位置。

这个函数的效果有点类似于 python 中的 bisect_left 和 bisect_right 综合后的结果，STL 中与此对应的二分查找算法为 lower_bound 与 upper_bound。因此，先来分析基本的二分查找的实现。

lower bound / upper bound

lower_bound 也会根据迭代器类型选择最有效率的做法并且也会提供一个重载版本允许根据 comp 来作为判断元素大小的标准，这里就只分析原始版本。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/*****************************************************************************************/
// lower_bound
// 在[first, last)中查找第一个不小于 value 的元素，并返回指向它的迭代器，若没有则返回 last
// 使用二分查找，所以要求[first, last)内的元素必须有序
// 相当于 python 中的 bisect.bisect_left，返回的位置即为可以被插入的第一个合适位置
/*****************************************************************************************/

/// @brief lower_bound 的 forward_iterator_tag 版本
template <class ForwardIterator, class T>
ForwardIterator lbound_dispatch(ForwardIterator first, ForwardIterator last, 
                               const T& value, forward_iterator_tag) {
    auto len = tinystl::distance(first, last);
    auto half = len;
    ForwardIterator middle;
    // 二分查找
    while (len > 0) {
        half = len >> 1;
        middle = first;
        tinystl::advance(middle, half);
        if (*middle < value) {
            first = middle;
            ++first;
            len = len - half - 1;
        } 
        else len = half;
    }
    return first;
} 

/// @brief lower_bound 的 random_access_iterator_tag 版本 
template <class RandomAccessIterator, class T>
RandomAccessIterator lbound_dispatch(RandomAccessIterator first, RandomAccessIterator last, 
                                    const T& value, random_access_iterator_tag) {
    auto len = last - first;
    auto half = len;
    RandomAccessIterator middle;
    // 二分查找
    while (len > 0) {
        half = len >> 1;
        middle = first + half;
        if (*middle < value) {
            first = middle + 1;
            len = len - half - 1;
        } 
        else len = half;
    }
    return first;
}

/// @brief 在[first, last)中查找第一个不小于 value 的元素，根据迭代器类型调用不同版本的 lbond_dispatch
/// @return  返回指向第一个不小于 value 的元素的迭代器，若没有则返回 last
template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value) {
    return tinystl::lbound_dispatch(first, last, value, iterator_category(first));
}

由 lower_bound 转调用 lbound_dispatch，二分的过程就不再赘述，寻找 lower_bound 的条件是 *middle < value 时左指针前进，这样最终左右指针就会交会在 lower_bound 处。稍后将会看到 upper_bound 的逻辑刚好相反。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/*****************************************************************************************/
// upper_bound
// 在[first, last)中查找第一个大于value 的元素，并返回指向它的迭代器，若没有则返回 last
// 使用二分查找，所以要求[first, last)内的元素必须有序
// 相当于 python 中的 bisect.bisect_right，返回的位置即为可以被插入的最后一个合适位置
/*****************************************************************************************/

/// @brief upper_bound 的 forward_iterator_tag 版本
template <class ForwardIterator, class T>
ForwardIterator ubound_dispatch(ForwardIterator first, ForwardIterator last, 
                                const T& value, forward_iterator_tag) {
    auto len = tinystl::distance(first, last);
    auto half = len;
    ForwardIterator middle;
    while (len > 0) {
        half = len >> 1;
        middle = first;
        tinystl::advance(middle, half);
        // 注意这里的条件
        if (value < *middle) len = half;
        else {
            first = middle;
            ++first;
            len = len - half - 1;
        }
    }
    return first;
}

/// @brief upper_bound 的 random_access_iterator_tag 版本
/// ...

/// @brief 在[first, last)中查找第一个大于 value 的元素，根据迭代器类型调用不同版本的 ubound_dispatch
template <class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& value) {
    return tinystl::ubound_dispatch(first, last, value, iterator_category(first));
}

upper_bound 中，判断条件是 value < *middle 时，右指针就后退，这样一来最终就会交会在 upper_bound 处。

lower_bound 和 upper_bound 都说了就顺便分析一下 binary_search 吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*****************************************************************************************/
// binary_search
// 二分查找，如果在[first, last)内有等同于 value 的元素，返回 true，否则返回 false
/*****************************************************************************************/

/// @brief 二分查找，如果在[first, last)内有等同于 value 的元素，返回 true，否则返回 false
template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value) {
    auto i = tinystl::lower_bound(first, last, value);
    // 最终 i 指向的位置如果不为 last，那么其中的值必然是 >= value 的，因此去除掉 > value 的情况
    // 即可判断是否存在等于 value 的元素
    return i != last && !(value < *i);
}

/// @brief 重载版本使用函数对象 comp 代替比较操作
template <class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last, const T& value, Compare comp) {
    auto i = tinystl::lower_bound(first, last, value, comp);
    return i != last && !comp(value, *i);
}

binary_search 调用 lower_bound 来进行二分查找。什么，你问我为什么不用 upper_bound？那当然是因为使用 upper_bound 后的查找结果相比于 lower_bound 的判断更为繁琐。

另外比较奇怪的就是最后的条件判断了：return i != last && !(value < *i);；判断 i != last 还好理解，为什么最后不用 value == *i 呢？我想应该是 == 相较于 < 的判断成本更加高一些。至于这样判断的合理性已经放在了注释中，应该比较好理解。

equal_range

OK，前摇完成，让我们一起分析 equal_range 本体，equal_range 这个算法，相信大家的直觉反应都是直接在整个区间上直接分别执行一次 lower_bound 和 upper_bound 即可得到结果，想必 STL 也是这样做的，吧？

按照 STL 中的做法，这个算法的完整实现是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/// @brief ForwardIterator 版本
template <class ForwardIterator, class T>
tinystl::pair<ForwardIterator, ForwardIterator>
erange_dispatch(ForwardIterator first, ForwardIterator last, const T& value, forward_iterator_tag) {
    auto len = tinystl::distance(first, last);
    auto half = len;
    ForwardIterator middle, left, right;
    while (len > 0) {
        // Start
        half = len >> 1;
        middle = first;
        tinystl::advance(middle, half);
        if (*middle < value) {
            first = middle;
            ++first;
            len = len - half - 1;
        }
        else if (value < *middle) len = half;
        //  End
        // 以上相当于先做了一次二分查找，确定 value 在大概哪个区间内，再在子区间上做二分查找
        // 相比于直接在整个区间上搜 lower_bound 与 upper_bound 会节省很多操作

        // 在子区间上做二分查找
        else {
            left = tinystl::lower_bound(first, middle, value);
            tinystl::advance(first, len);
            right = tinystl::upper_bound(++middle, first, value);
            return tinystl::pair<ForwardIterator, ForwardIterator>(left, right);
        }
    }
    return tinystl::pair<ForwardIterator, ForwardIterator>(first, first);
}

/// @brief RandomAccessIterator 版本
template <class RandomAccessIterator, class T>
tinystl::pair<RandomAccessIterator, RandomAccessIterator>
erange_dispatch(RandomAccessIterator first, RandomAccessIterator last, 
    const T& value, random_access_iterator_tag) {
    auto len = last - first;
    auto half = len;
    RandomAccessIterator middle, left, right;
    while (len > 0) {
        half = len >> 1;
        middle = first + half;
        if (*middle < value) {
            first = middle + 1;
            len = len - half - 1;
        }
        else if (value < *middle) len = half;
        else {
            left = tinystl::lower_bound(first, middle, value);
            right = tinystl::upper_bound(++middle, first + len, value);
            return tinystl::pair<RandomAccessIterator, RandomAccessIterator>(left, right);
        }
    }
    return tinystl::pair<RandomAccessIterator, RandomAccessIterator>(first, first);
}

/// @brief 查找[first,last)区间中与 value 相等的元素所形成的区间，返回一对迭代器指向区间首尾
template <class ForwardIterator, class T>
tinystl::pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value) {
    return tinystl::erange_dispatch(first, last, value, iterator_category(first));
}

其实分析已经写在了注释里，这里就不卖关子了，STL 中为了效率更高，会先在 [first, last) 上执行二分查找，确定 value 大致都在哪个区间范围内，再在相应的子区间做二分查找，找到值等于 value 的范围，相比于直接在整个区间上执行 lower_bound 和 upper_bound，效率会高不少。

实际上博主在一开始实现到这部分时也十分不理解，因此擅自改成了下面的做法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 已弃用
/// @brief 查找[first,last)区间中与 value 相等的元素所形成的区间，返回一对迭代器指向区间首尾
template <class ForwardIterator, class T>
tinystl::pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value) {
    return tinystl::pair<ForwardIterator, ForwardIterator>(
        tinystl::lower_bound(first, last, value),
        tinystl::upper_bound(first, last, value));
}

/// @brief 重载版本使用函数对象 comp 代替比较操作
template <class ForwardIterator, class T, class Compare>
tinystl::pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T& value, Compare comp) {
    return tinystl::pair<ForwardIterator, ForwardIterator>(
        tinystl::lower_bound(first, last, value, comp),
        tinystl::upper_bound(first, last, value, comp));
}

就是简单地在整个区间上调用两个函数。但进行测试就会发现，效率差的不是一点半点。

测试程序

为了测试性能，这里定义了一些很糟糕的宏，关于测试程序之后会开一个番外说明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#define TEST_EQUAL_RANGE(mode, len, count) do {                 \
  srand((int)time(0));                                          \
  clock_t start, end;                                           \
  mode::list<int> l;                                            \
  char buf[10];                                                 \
  mode::vector<int> v(len);                                     \
  mode::iota(v.begin(), v.end(), 1);                            \
  start = clock();                                              \
  for (int i = 0; i < count; ++i) {                             \
    int target = rand() % len + 1;                              \
    auto range = mode::equal_range(v.begin(), v.end(), target); \
  }                                                             \
  end = clock();                                                \
  int n = static_cast<int>(static_cast<double>(end - start)     \
      / CLOCKS_PER_SEC * 1000);                                 \
  std::snprintf(buf, sizeof(buf), "|   %d", n);                 \
  std::string t = buf;                                          \
  t += "ms    |";                                               \
  std::cout << std::setw(WIDE) << t << std::endl;               \
} while (0)

TEST(equal_range_pk) {
    std::cout << "|    std    |" << std::endl;
    TEST_EQUAL_RANGE(std, 100000, 100000);
    std::cout << "|  tinystl  |" << std::endl;
    TEST_EQUAL_RANGE(tinystl, 100000, 100000);
}

  • 简单在整个区间上查找的版本

    1
    2
    3
    4
    5
    // Run TestCase:equal_range_pk
    //  |    std    |
    //  |    9ms    |
    //  |  tinystl  |
    //  |   18ms    |

    效率比 STL 整整低了一倍。

  • STL 版本

    1
    2
    3
    4
    5
    // Run TestCase:equal_range_pk
    // |    std    |
    // |    9ms    |
    // |  tinystl  |
    // |    9ms    |

    这里的执行时间就和 STL 中的差不多了毕竟程序完全一样。

equal_range 也提供了可以输出 comp 的重载，这里就不分析了。

总结

本节对 equal_range 及其相关的一些函数做了分析，可以看出 STL 针对每个函数都做了优化，力求运行时的效率最佳，即使是很做法很显然的 equal_range 也是有很大的优化空间的，效率甚至可以提升一倍，这也再次展现了 STL 的强大之处。