Keep Calm and Carry On

STL算法

Posted on Edited on
STL 收录的一些算法，可以考虑某一算法有多少种实现的方式，STL 为何采用了这种实现方式？

1. STL 算法

STL 算法主要实现在 stl_algo.h、stl_algobase.h、stl_numeric.h 文件中，所有的 STL 算法都是作用在用迭代器 [first, last) 表示的范围上。可以根据算法执行过程中是否会改变给定区间的元素，将算法分为 mutating algorithm 和 nonmutating algorithm。mutating algorithm有诸如 copy、swap、replace、fill、remove、partition等，nonmutating algorithm有诸如find、search、count、for_each、equal、max、min等。

2. STL 算法的一般形式

所有的泛型算法前两个参数都是一对用于表示算法作用范围的迭代器[first, last)，迭代器使用前闭后开的区间，这样当 first == last 就可以表示一个空的区间范围，这对迭代器的必要条件就是 first 可以通过累加达到 last，也就是 operator++ 被正确的重载了。许多 STL 算法有多个版本，比如默认的行为、传递一个仿函数等。mutating algorithm 通常会有两个版本，一个是原地地改变操作地对象，另一版本就是将结果保存到指定的容器，而原来的容器不会有任何的变化（copy版总是以 _copy 结尾），比如 replace() 和 replace_copy()。所有地数值（numeric）算法都是实现在 stl_numeric.h 中，其它算法都是是现在 stl_algo.h 和 stl_algobase.h 中。这些文件的顶层文件都是平时写代码要 include 的 。

3. 算法的泛化过程

STL 算法的泛型化目标就是将算法独立于所处理的数据结构之外，不受数据结构的羁绊，使其适用于大多数的数据结构（这些数据结构可能使 array、vector、list、deque）。要实现这个目标，关键在于把操作对象的类型抽象化，同时把操作对象的表示法和移动行为抽象化，那么整个算法就是在一个抽象的层面工作了，这就是算法的泛化。

4. 数值算法 <stl_numeric.h>

数值算法被实现在文件 <stl_numeric.h> 中，要使用数值算法需要 include 文件 。

4.1 accumulate

accumulate 计算给定范围的的所有值的和，并且必须提供一个初始值（这是为了当给定范围是空的时候可以返回一个明确的值），可以执行二元操作的类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template<typename _InputIterator, typename _Tp>
    inline _Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init) {
        for (; __first != __last; ++__first)
            __init = __init + *__first;
        return __init;
    }

template<typename _InputIterator, typename _Tp, typename _BinaryOperation>
    inline _Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
       _BinaryOperation __binary_op) {
      // 执行指定的二元操作，可以是加减乘除之类的, 而且不必满足交换律和结合律
      for (; __first != __last; ++__first)
          __init = __binary_op(__init, *__first);
      return __init;
}

4.2 adjacent_difference

adjacent_difference 计算相邻元素得差值，结果存储在给定的第三个参数 result中。

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
template<typename _InputIterator, typename _OutputIterator>
_OutputIterator adjacent_difference(_InputIterator __first,
        _InputIterator __last, _OutputIterator __result) {
    if (__first == __last)
        return __result;
    _ValueType __value = *__first;
    *__result = __value;
    while (++__first != __last) {
        _ValueType __tmp = *__first;
        *++__result = __tmp - __value;
        __value = _GLIBCXX_MOVE(__tmp);
    }
    return ++__result;
}

// 版本二, 可以提供一种二元仿函数
template<typename _InputIterator, typename _OutputIterator,
typename _BinaryOperation>
_OutputIterator adjacent_difference(_InputIterator __first, _InputIterator __last,
    _OutputIterator __result, _BinaryOperation __binary_op) {

    typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
    if (__first == __last)
        return __result;
    _ValueType __value = *__first;
    // 存储第一个值
    *__result = __value;
    while (++__first != __last) {
        _ValueType __tmp = *__first;
        // 计算差值
        *++__result = __binary_op(__tmp, __value);
        __value = _GLIBCXX_MOVE(__tmp);
    }
    return ++__result;
}

4.3 inner_product

inner_product 用来计算两个容器的内积(对应元素之间的操作)，为了使的有容器为空时，可以获得一个明确定义的结果，比如要计算两个 vector 的内积，初值提供为0即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 这个版本提供的的就是最普遍意义的内积，对应元素相乘（*），然后累加
template<typename _InputIterator1, typename _InputIterator2, typename _Tp>
inline _Tp inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
_InputIterator2 __first2, _Tp __init) {
    for (; __first1 != __last1; ++__first1, (void)++__first2)
        __init = __init + (*__first1 * *__first2);
    return __init;
}
// 版本二：和上一个版本的唯一区别就是提供了仿函数替换 operator+ 和 operator*
// __binary_op1用于替换 operator+
// __bianry_op2用于替换 operator*
template<typename _InputIterator1, typename _InputIterator2, typename _Tp,
typename _BinaryOperation1, typename _BinaryOperation2>
inline _Tp inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
    _InputIterator2 __first2, _Tp __init, _BinaryOperation1 __binary_op1,
    _BinaryOperation2 __binary_op2) {
    for (; __first1 != __last1; ++__first1, (void)++__first2)
        __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
    return __init;
}

4.4 partial_sum

partial_sum 用于计算局部的和，将 *first 赋值给 *result ，然后将 *first 和 *(first + 1) 的和赋值给 *(result + 1)。

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
// 计算局部和，_OutputIterator也可以是__first，这样就是原地算法改变原来容器的值 
template<typename _InputIterator, typename _OutputIterator>
_OutputIterator partial_sum(_InputIterator __first, _InputIterator __last,
    _OutputIterator __result) {
    typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
    if (__first == __last)
        return __result;
    _ValueType __value = *__first;
    *__result = __value;
    while (++__first != __last) {
        __value = __value + *__first;
        *++__result = __value;
    }
    return ++__result;
}

// 版本二： 用提供的仿函数 __binary_op 来替换默认的 operator+
template<typename _InputIterator, typename _OutputIterator,
typename _BinaryOperation>
_OutputIterator partial_sum(_InputIterator __first, _InputIterator __last,
    _OutputIterator __result, _BinaryOperation __binary_op) {
    if (__first == __last)
        return __result;
    _ValueType __value = *__first;
    *__result = __value;
    while (++__first != __last) {
        __value = __binary_op(__value, *__first);
        *++__result = __value;
    }
    return ++__result;
}

4.5 iota

iota 是一个希腊字符的读音（eye-oh-duh），该算法从依次将范围[first, last)的值加上一个 value，而 value 每次都执行 operator++操作。

1
2
3
4
5
6
7
template<typename _ForwardIterator, typename _Tp>
void iota(_ForwardIterator __first, _ForwardIterator __last, _Tp __value) {
    for (; __first != __last; ++__first) {
        *__first = __value;
        ++__value;
    }
}

5. 基本算法 <stl_algobase.h>

STL算法并没有简单复杂之分，把一些常用的算法实现在 <stl_algobase.h>，其他的算法是现在 <stl_alog.h> 中。

5.1 equal, fill, fill_n, iter_swap, lexicographical_compare, max, min, mismatch, swap

这几个算法的实现都很简单，无非就是顺序遍历给定的迭代器区间，执行对应的操作。

  1. equal
    equal 用于判断两个容器在区间[first, last)之间是否相等，如果相等则返回 true，如果第二个容器元素比较多，则多出的部分不考虑，也就是说 equal() 是不能用来判断两个容器是否相等的，因为第二个容器多出来的元素没有被考虑。

  2. fill
    fill() 将所有容器区间[first, last)改为新的值。

  3. fill_n
    将[first, first + n)范围内的值改写为新的值，如果超出容器范围会有不可预期的结果，因此可以传入一个有插入功能的迭代器，而不是覆盖的迭代器。

    1
    2
    3
    4
    5
    6
    7
    int ia[] = { 0, 1, 2 };
    std::vector<int> ivec(ia, ia + 3);
    std::fill_n(std::inserter(ivec, ivec.begin()), 5, 9);
    for ( const int num : ivec )
        display<int>()(num);
    // 9 9 9 9 9 0 1 2
    std::cout << std::

  4. iter_swap
    iter_swap() 将两个迭代器指向的内容互换。

  5. lexicographical_compare
    故名思意就是字典序比较，比较给定区间[first1, last1)和[first2, last2)的对应位置，依次比较会出现三种情况

  • 某一对应元素彼此不相等
  • 两个区间大小相同，同时到达 last1 和 last2；
  • 两个区间大小不同，到达 last1 或者 last2；

返回值：当第一序列小于第二序列返回 true

  • 当某组对应元素不相等，如果第一序列较小，则返回 true，否则返回 false；
  • 当到达了 last1 而没有到达 last2，返回 true；
  • 当没有到达 last2 而到达了 last1，返回 false；
  • 同时到达 last1 和 last2（所有元素都匹配），那么返回 false（因为序列1不小于序列2）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename _II1, typename _II2, typename _Compare>
bool __lexicographical_compare_impl(_II1 __first1, _II1 __last1,
       _II2 __first2, _II2 __last2, _Compare __comp) {

    __last1 = __rai_type::__newlast1(__first1, __last1, __first2, __last2);
    for (; __first1 != __last1 && __rai_type::__cnd2(__first2, __last2);
        ++__first1, (void)++__first2) {
        if (__comp(__first1, __first2))
            return true;
        if (__comp(__first2, __first1))
            return false;
    }
    return __first1 == __last1 && __first2 != __last2;
}
  1. max
    max() 返回两个对象的大者，有两个版本，一个使用参数对象提供的的 operator< 来判断大者，另一个版本可以传入一个仿函数作为参数判断两个对象的大小。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename _Tp>
_GLIBCXX14_CONSTEXPR
inline const _Tp& max(const _Tp& __a, const _Tp& __b) {
    if (__a < __b)
        return __b;
    return __a;
}

template<typename _Tp, typename _Compare>
inline const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp) {
    if (__comp(__b, __a))
        return __b;
    return __a;
}

  1. min
    min() 返回两个给定对象中的小者，和 max 类似。

  2. mismatch
    mismatch() 用来平行比较两个序列，用一个 pair 的形式返回二者之间的第一个不匹配点。

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename _InputIterator1, typename _InputIterator2, typename _BinaryPredicate>
pair<_InputIterator1, _InputIterator2>
    __mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
    _InputIterator2 __first2, _InputIterator2 __last2,
   _BinaryPredicate __binary_pred) {
    while (__first1 != __last1 && __first2 != __last2
        && __binary_pred(__first1, __first2)) {
        ++__first1;
        ++__first2;
    }
    // pair<T1, T2>(v1, v2);
    return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
}
  1. swap
    swap() 用来交换两个位置的值。

    5.2 copy

    copy() 将容器的一个区间的内容拷贝到容器的另一个区间（可以是同一个容器），一般来说拷贝操作无非就是利用 assignment operator 或者 copy constructor，而 copy() 算法使用的就是 operator=。STL的原则就是尽量使用内存直接拷贝，节省时间开销。STL 算法使用了函数重载，类型特性，偏特化等方法加快 copy() 的执行速度。比如，泛化的 copy() 一般来说接受两个迭代器表示拷贝的范围，因此每次要逐一比较两个迭代器是不是相等来盘算是不是已经全部拷贝完了，这种方法是比较慢的。可以使用特化的方法，先算出需要拷贝的元素的数量，然后用一个循环来拷贝，不用多次比较迭代器，速度更快。
1
2
3
4
5
6
7
8
9
10
for ( ; first != last; ) {
    // ... 
}

for ( ; n < last - first; ) {
    // ...
}

// 当然使用 memmove() 会比使用迭代器一个一个元素赋值更快
// 当使用native pointer 的时候会调用 memmove 处理

5.3 copy_backward

copy_backward() 和 copy() 类似，将[first, last)逆向拷贝到以 result - 1 为起点的区间（方向也是反向，使用反向迭代器实现）。

6. set 相关算法

set 相关算法包括 union、intersection、difference、symmetric difference，实现在 <stl_algo.h>中。

6.1 set_difference

set_difference 返回两个有序区间的差集，差集包含“出现在第一个区间但是不出现在第二个区间的元素”。set_difference 是一种 stable 操作，也就是结果的元素顺序和区间一保持一致。这个算法有两个版本，第一个版本是使用 operator< 进行比较，另一个版本是提供一个仿函数 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

template<typename _InputIterator1, typename _InputIterator2,
   typename _OutputIterator, typename _Compare>
_OutputIterator __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
         _InputIterator2 __first2, _InputIterator2 __last2,
         _OutputIterator __result, _Compare __comp) {
  
  // 基础正是 set 是有序的
  // 在两个区间同时移动迭代器，当第一区间元素等于第二区间元素（表示元素同时出现）在迭代器同时步进
  // 当第一区间元素大于第二区间元素，就让第二区间迭代器前进
  // 当第一区间元素小于第二区间元素，记录当前元素，移动第一区间迭代器
  while (__first1 != __last1 && __first2 != __last2)
    if (__comp(__first1, __first2)) {
        *__result = *__first1;
        ++__first1;
        ++__result;
    }
    else if (__comp(__first2, __first1))
        ++__first2;
    else {
        ++__first1;
        ++__first2;
    }
  return std::copy(__first1, __last1, __result);
}

// 使用 operator< 的版本将__comp(_first1, __first2) 改为<即可
// 也就是传递一个 __gnu_cxx::__ops::__iter_less_iter())

6.2 set_union

set_union() 获得两个排序区间的并集，“并集包含所有出现在第一区间或者第二区间的元素”，返回一个指向结果区间末尾的迭代器。set_union 是一个 stable 操作，两个输入区间的元素都不要求唯一，如果一个元素在第一区间出现 a 次，在第二区间出现 b 次，那么并集中该元素出现次数为 max(a, b)。

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

// 如果第一区间元素等于第二区间元素：记录区间一元素，区间一、区间二迭代器前进
// 如果第一区间元素大于第二区间元素：记录区间二元素，区间二迭代器前进
// 如果第一区间元素小于第二区间元素：记录区间一元素，区间一迭代器前进
// 每次都去较小元素
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator, typename _Compare>
_OutputIterator __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
    _InputIterator2 __first2, _InputIterator2 __last2,
    _OutputIterator __result, _Compare __comp) {
    while (__first1 != __last1 && __first2 != __last2) {
        if (__comp(__first1, __first2)) {
            *__result = *__first1;
            ++__first1;
        }
        else if (__comp(__first2, __first1)) {
            *__result = *__first2;
            ++__first2;
        }
        else {
            *__result = *__first1;
            ++__first1;
            ++__first2;
        }
        ++__result;
    }
    // 只要有其中一个迭代器到达末尾，就将另一个区间剩下的拷贝到目标区间
    // [first1, last1), [first2, last2)必有一个是 empty的
    return std::copy(__first2, __last2, std::copy(__first1, __last1, __result));
}

// 另一个版本不提供仿函数，在实现上是提供了一个__gnu_cxx::__ops::__iter_less_iter()

6.3 set_intersection

set_intersection 构造两个有序区间的交集，“交集中包含的元素同时出现在一区间和二区间”。set_intersection 的两个输入区间不要求元素唯一，是一种 stable 的操作，同样提供两个版本，一个是operator<，另一个是仿函数用于比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator, typename _Compare>
_OutputIterator __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
    _InputIterator2 __first2, _InputIterator2 __last2,
    _OutputIterator __result, _Compare __comp) {
    // 求交集嘛
    // 找相等相等的元素即可了
        while (__first1 != __last1 && __first2 != __last2)
            if (__comp(__first1, __first2))
                ++__first1;
            else if (__comp(__first2, __first1))
                ++__first2;
            else {
                *__result = *__first1;
                ++__first1;
                ++__first2;
                ++__result;
            }
        return __result;
}

6.4 set_symmetric_difference

set_symetric_difference 对称差集，“对称差集包含出现在一区间但不出现在二区间，以及，出现在二区间但不出现在一区间的元素”, 同样不要求两个区间元素唯一，是 stable 操作。

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

template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator, typename _Compare>
_OutputIterator __set_symmetric_difference(_InputIterator1 __first1,
   _InputIterator1 __last1,
   _InputIterator2 __first2,
   _InputIterator2 __last2,
   _OutputIterator __result,
   _Compare __comp) {
    // 不相等取小者, 因为小的肯定不在另一个区间出现
    // 相等则同时前进
    while (__first1 != __last1 && __first2 != __last2)
        if (__comp(__first1, __first2)) {
            *__result = *__first1;
            ++__first1;
            ++__result;
        }
        else if (__comp(__first2, __first1)) {
            *__result = *__first2;
            ++__first2;
            ++__result;
        }
        else {
            ++__first1;
            ++__first2;
        }
    // 任一迭代器到达末尾，拷贝另一个区间剩余的元素
    return std::copy(__first2, __last2,  std::copy(__first1, __last1, __result));
}

7. heap 算法

heap 算法在序列式容器中，包含 ：push_heap, pop_heap, make_heap, sort_heap算法, <stl_algo.h>包含了文件<stl_heap.>。

8. 其他算法

由于STL算法常常需要传递一个谓词（predicate）或者仿函数（functor），先记录一下这两者的具体区别：

  1. functor：functor 是一个函数对象（Function object），使一个类看上去像一个函数，在实现上是重载 operator() ，functor 就是某个类的实例，行为和函数类似，像调用函数一样使用函数对象。
  2. predicate：谓词是一个判断式，是一个返回 bool 值得函数或者仿函数，几元谓词就表示函数参数得个数。

8.1 find

find() 返回给定区间[first, last)中出现的第一个与要查找元素相等的迭代器。find() 调用的是 std::__find_if()，并提供一个表示相等的谓词（predicate）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// __find_if有不同的重载版本, 针对无序的区间查找，只能逐一比较
template<typename _InputIterator, typename _Predicate>
inline _InputIterator __find_if(_InputIterator __first, _InputIterator __last,
    _Predicate __pred, input_iterator_tag) {
    while (__first != __last && !__pred(__first))
        ++__first;
    return __first;
}


template<typename _InputIterator, typename _Tp>
inline _InputIterator find(_InputIterator __first, _InputIterator __last,
    const _Tp& __val) {
    return std::__find_if(__first, __last, __gnu_cxx::__ops::__iter_equals_val(__val));
}

8.2 find_if

find_if() 返回给定区间中第一个使得给定谓词（predicate）为 true 的元素的迭代器，否则返回 end()。

1
2
3
4
5
template<typename _InputIterator, typename _Predicate>
inline _InputIterator find_if(_InputIterator __first, _InputIterator __last,
    _Predicate __pred) {
    return std::__find_if(__first, __last, __gnu_cxx::__ops::__pred_iter(__pred));
}

8.3 find_first_of

find_first_of() returns an iterator to the first element in the range [first1, last1) that matches any of the elements in [first2, last2). If no such element is found, the function returns last1. The elements in [first1, last1) ared sequentially compared to each of the values in [first2, last2) using operator==(or predicate in version 2), until a pair matches.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// version1 operator==
template<typename _InputIterator, typename _ForwardIterator>
_InputIterator find_first_of(_InputIterator __first1, _InputIterator __last1,
    _ForwardIterator __first2, _ForwardIterator __last2) {
    for (; __first1 != __last1; ++__first1)
        for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
            if (*__first1 == *__iter)
                return __first1;
    return __last1;
    }

// version2 predicate comp
template<typename _InputIterator, typename _ForwardIterator, typename _BinaryPredicate>
_InputIterator find_first_of(_InputIterator __first1, _InputIterator __last1,
    _ForwardIterator __first2, _ForwardIterator __last2, _BinaryPredicate __comp) {
    for (; __first1 != __last1; ++__first1)
        for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
            if (__comp(*__first1, *__iter))
                return __first1;
    return __last1;
}

8.4 find_end

find_end() 返回区间二在区间一出现的最后一个位置。

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
// find_end for forward iterators.
template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
_ForwardIterator1 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
    _ForwardIterator2 __first2, _ForwardIterator2 __last2,
    forward_iterator_tag, forward_iterator_tag,
    _BinaryPredicate __comp) {
    // 区间二为空
    if (__first2 == __last2)
        return __last1;

    _ForwardIterator1 __result = __last1;
    while (1) {
        _ForwardIterator1 __new_result
            = std::__search(__first1, __last1, __first2, __last2, __comp);
        // 当新的结果已经是找不到了,那么就是直接返回上一个结果
         if (__new_result == __last1)
            return __result;
        else {
            // 以当前结果为头继续查找
            __result = __new_result;
            __first1 = __new_result;
            ++__first1;
        }
    }
}

8.5 adjacent_find

Searches the range [first, last) for the first occurence of two consecutive elements that match, and return an iterator to the first of these two elements, or last if no such found. There are two versions of the function, one is compares equal using opeartor==, the other using pred.

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
template<typename _ForwardIterator, typename _BinaryPredicate>
_ForwardIterator __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
    _BinaryPredicate __binary_pred) {
    if (__first == __last)
        return __last;
    _ForwardIterator __next = __first;
    while (++__next != __last) {
        if (__binary_pred(__first, __next))
            return __first;
        __first = __next;
    }
    return __last;
}

template<typename _ForwardIterator>
inline _ForwardIterator
adjacent_find(_ForwardIterator __first, _ForwardIterator __last) {
    return std::__adjacent_find(__first, __last, __gnu_cxx::__ops::__iter_equal_to_iter());
}

template<typename _ForwardIterator, typename _BinaryPredicate>
inline _ForwardIterator adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
_BinaryPredicate __binary_pred) {
    return std::__adjacent_find(__first, __last,
        __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
}

8.6 count

count() returns the number of elements in the range [first, last) that compare equal to val. The function uses operator== to compare the individual elements to val.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

template<typename _InputIterator, typename _Tp>
inline typename iterator_traits<_InputIterator>::difference_type
    count(_InputIterator __first, _InputIterator __last, const _Tp& __value) {
    return std::__count_if(__first, __last,
     __gnu_cxx::__ops::__iter_equals_val(__value));
}

// __count_if is so easy, it is also called by count_if
template<typename _InputIterator, typename _Predicate>
typename iterator_traits<_InputIterator>::difference_type
    __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) {
    for (; __first != __last; ++__first)
        if (__pred(__first))
            ++__n;
    return __n;
}

8.7 count_if

count_if() returns the number of elements in the range [first, last) for which pred is true.

1
2
3
4
5
6
template<typename _InputIterator, typename _Predicate>
inline typename iterator_traits<_InputIterator>::difference_type
count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred) {
    return std::__count_if(__first, __last,
     __gnu_cxx::__ops::__pred_iter(__pred));
}

在区间一[first1, last1)中查找区间二[first2, last2)的首次出现的位置，如果找不到则返回 last1。
// 会不会使用KMP算法呢？为什么不适用KMP算法？可能的原因：

  1. 大部分出现的都是比较短的容器的匹配（短字符串），普通的算法已经表现足够用了。而KMP需要初始分配内存，需要预计算（生成偏移量表），这些都可能影响性能，导致在比较短的对象的情况下表现不如暴力法，而大数据量可能会需要更加专门的数据结构。
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

template<typename _ForwardIterator1, typename _ForwardIterator2,
typename _BinaryPredicate>
_ForwardIterator1
    __search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
    _ForwardIterator2 __first2, _ForwardIterator2 __last2,
    _BinaryPredicate  __predicate) {
    // S1和S2均为空
    if (__first1 == __last1 || __first2 == __last2)
        return __first1;
        
    // S2长度为1，直接查找是否有这个值
    _ForwardIterator2 __p1(__first2);
    if (++__p1 == __last2)
        return std::__find_if(__first1, __last1,
        __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));

    // 一般情况
    _ForwardIterator2 __p;
    _ForwardIterator1 __current = __first1;

    for (;;) {
        // 先找第一个出现S2头的位置
        __first1 = std::__find_if(__first1, __last1,
        __gnu_cxx::__ops::__iter_comp_iter(__predicate, __first2));

        // 如果没有出现S2头，就说明S2肯定没有在S1出现
        if (__first1 == __last1)
            return __last1;

        __p = __p1; // __p == first2
        __current = __first1; // __current是S1中出现的S2的头
        if (++__current == __last1) // S1中这个字符是最后一个字符了（之前已经排除S2长度为1）
            return __last1; // 说明没有出现
        
        // 逐一比较
        while (__predicate(__current, __p)) {
            // S2的最后一个字符都匹配了
            if (++__p == __last2)
                return __first1;
            // S1先匹配完毕，说明没有出现
            if (++__current == __last1)
                return __last1;
        }
        // 当前字符作为头不行，那就将下一个字符作为头，继续
        ++__first1;
    }
    \eturn __first1;
}

8.9 for_each

for_each() 对给定区间的元素执行给定操作，给定的操作必须不能改变元素，因为 for_each() 参数是 inputIterator，不保证接受赋值行为，仿函数f的返回值被忽略，返回值是给定的仿函数f（函数对象）。

1
2
3
4
5
6
template<typename _InputIterator, typename _Function>
_Function for_each(_InputIterator __first, _InputIterator __last, _Function __f) {
    for (; __first != __last; ++__first)
        __f(*__first);
    return __f; // N.B. [alg.foreach] says std::move(f) but it's redundant.
}

8.10 generate

generate() 将仿函数 gen 的执行结果写到给定区间的所有元素，所谓写，用的是元素的 assignment 操作符。

1
2
3
4
5
6
template<typename _ForwardIterator, typename _Generator>
void generate(_ForwardIterator __first, _ForwardIterator __last,
    _Generator __gen) {
    for (; __first != __last; ++__first)
        *__first = __gen();
}

8.11 generate_n

generate_n() 和 generate() 类似，但是仅仅将 gen 的执行结果填写从给定迭代器起的 n 个元素，如果容器范围不够，结果不可预测。

8.12 includes(应用于有序区间)

两个有序区间，判断区间二是否是区间一的子序列。

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
// 默认给定的两个区间是升序排序
template<typename _InputIterator1, typename _InputIterator2>
inline bool includes(_InputIterator1 __first1, _InputIterator1 __last1,
    _InputIterator2 __first2, _InputIterator2 __last2) {
    return std::__includes(__first1, __last1, __first2, __last2,
         __gnu_cxx::__ops::__iter_less_iter());
}
// 版本二
template<typename _InputIterator1, typename _InputIterator2,
   typename _Compare>
inline bool includes(_InputIterator1 __first1, _InputIterator1 __last1,
    _InputIterator2 __first2, _InputIterator2 __last2,
     _Compare __comp) {
  return std::__includes(__first1, __last1, __first2, __last2,
             __gnu_cxx::__ops::__iter_comp_iter(__comp));
}

// 判断区间一内是否有个子序列，其与区间二的每个对应的元素都满足二元运算 comp
// 前提：区间一、区间二都是有序的
template<typename _InputIterator1, typename _InputIterator2,
typename _Compare>
bool __includes(_InputIterator1 __first1, _InputIterator1 __last1,
    _InputIterator2 __first2, _InputIterator2 __last2,
    _Compare __comp) {
    while (__first1 != __last1 && __first2 != __last2) // 两个区间都没有到尽头
        if (__comp(__first2, __first1)) // 如果第一个元素都不满足，则不存在子序列
            return false;
        else if (__comp(__first1, __first2)) // S1的第一个太小了
            ++__first1;
        else { // 匹配了一个元素，S1 S2 都前进
            ++__first1;
            ++__first2;
        }
    return __first2 == __last2; // S1，S2任意一个走完了，判断S2是否还有剩下元素
}

8.13 max_element

max_element() 返回给定区间的最大值的迭代器，区间为空返回 first。max() 函数可以直接调用 max_element() 函数，获得迭代器后解引用即可。

1
2
3
4
5
6
7
8
9
10
11
12
// 
template<typename _ForwardIterator, typename _Compare>
_GLIBCXX14_CONSTEXPR
_ForwardIterator __max_element(_ForwardIterator __first, _ForwardIterator __last,
      _Compare __comp) {
    if (__first == __last) return __first;
        _ForwardIterator __result = __first;
    while (++__first != __last)
        if (__comp(__result, __first))
    __result = __first;
    return __result;
}

8.14 min_element

min_element() 和 max_element() 类似。

8.15 merge

merge() 将两个有序区间 merge 为 一个有序区间，输出到指定的结果容器。算法版本1使用 operator< 比较元素，版本2可以传递一个仿函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template<typename _InputIterator1, typename _InputIterator2,
typename _OutputIterator, typename _Compare>
_OutputIterator __merge(_InputIterator1 __first1, _InputIterator1 __last1,
    _InputIterator2 __first2, _InputIterator2 __last2,
    _OutputIterator __result, _Compare __comp) {
    while (__first1 != __last1 && __first2 != __last2) { // 没有一个区间到尽头
        if (__comp(__first2, __first1)) { // 取小者
            *__result = *__first2;
            ++__first2;
        }
        else {
            *__result = *__first1;
            ++__first1;
        }
        ++__result; 
    }
    // 无论哪个区间有剩余，都拷贝到结果后面
    return std::copy(__first2, __last2,
       std::copy(__first1, __last1, __result));
}

8.16 partition

partition() 将给定区间[first, last)的元素根据给定的一元运算条件 pred 判定为 true 或者 false 分为两部分。

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
template<typename _ForwardIterator, typename _Predicate>
_ForwardIterator
    __partition(_ForwardIterator __first, _ForwardIterator __last,
    _Predicate __pred, forward_iterator_tag) {
    if (__first == __last)  // 空区间
        return __first;

    while (__pred(*__first))  // 首先跳过所有 true 的元素，找到第一个 false
        if (++__first == __last) // 如果所有的都是 true，直接返回 last
            return __first;

    _ForwardIterator __next = __first; // 第一个 false 

    while (++__next != __last) //  next 不是 last，也就是 first不是最后一个元素
        // 找到下一个 true 的元素
        if (__pred(*__next)) {  // 如果下一个元素是 true，就和当前元素交换
            std::iter_swap(__first, __next);
            ++__first;
        }
    return __first;
}

template<typename _BidirectionalIterator, typename _Predicate>
_BidirectionalIterator
    __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
    _Predicate __pred, bidirectional_iterator_tag) {
    while (true) {                            
        while (true)
            if (__first == __last)            // 如果已经处理完
                return __first;               // 返回，false部分的第一个元素
            else if (__pred(*__first))        // 左标兵为 true
                ++__first;
            else
                break;
        --__last;
        while (true)
            if (__first == __last)
                return __first;
            else if (!bool(__pred(*__last)))
                --__last;
            else
                break;
        std::iter_swap(__first, __last);
        ++__first;
    }
}



// 可以看到，partition() 不保证原来的元素的相对位置，也就是 nonstable 的，要保持元素的相对位置，可以使用 stable_partition()。

8.17 remove 移除但是不删除

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
template<typename _ForwardIterator, typename _Predicate>
_ForwardIterator
    __remove_if(_ForwardIterator __first, _ForwardIterator __last,
    _Predicate __pred) {
    __first = std::__find_if(__first, __last, __pred); // 找到第一个 true 
    if (__first == __last) // 如果没有直接返回 first
        return __first;
    _ForwardIterator __result = __first; // 指向第一个 true 的元素
    ++__first; // 指向下一个元素
    for (; __first != __last; ++__first)
        if (!__pred(__first)) { // 当前元素为 false
            *__result = _GLIBCXX_MOVE(*__first); // 将当前值拷贝（移动）到result
            ++__result; // 也就是result之前的值都是false的
        }
    return __result;
    // 可以保证 false 的元素的稳定性
}

template<typename _ForwardIterator, typename _Tp>
inline _ForwardIterator
    remove(_ForwardIterator __first, _ForwardIterator __last,
    const _Tp& __value) {
    return std::__remove_if(__first, __last,
    __gnu_cxx::__ops::__iter_equals_val(__value));
}

8.18 remove_copy

remove_copy() 移除给定区间内所有和给定值相等的元素，但是不是从给定的区间中移除，也就是给定区间不会有任何的变化，而是将结果故知道一个 result 的容器中，如果 result 的大小不足以容纳结果，那么会产生无法预期的结果（不知道复制到哪里去了），返回值是指向被拷贝的元素的最后一个元素的下一个位置。remove_copy() 是 stable 的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<typename _InputIterator, typename _OutputIterator, typename _Tp>
inline _OutputIterator
    remove_copy(_InputIterator __first, _InputIterator __last,
    _OutputIterator __result, const _Tp& __value) {
    return std::__remove_copy_if(__first, __last, __result,
        __gnu_cxx::__ops::__iter_equals_val(__value));
}

template<typename _InputIterator, typename _OutputIterator,
typename _Predicate>
_OutputIterator
    __remove_copy_if(_InputIterator __first, _InputIterator __last,
     _OutputIterator __result, _Predicate __pred) {
    // 实际就是将给定区间的所有和给定值不相等的元素一个个赋值到结果容器
    for (; __first != __last; ++__first)
        if (!__pred(__first)) {
            *__result = *__first;
            ++__result;
        }
    return __result;
}

8.19 remove_if

remove_if() 移除给定区间的所有使得 functor pred 为 true 的元素，但是并不是真正移除元素，而是将所有使得 pred 为 false 的元素一个一个赋值给 first 之后的位置。返回最后一个 false 的元素的下一个位置。由于原来的容器还有残留数据，因此如果要清除这些数据可以使用容器的成员函数 erase() 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
template<typename _ForwardIterator, typename _Predicate>
inline _ForwardIterator
    remove_if(_ForwardIterator __first, _ForwardIterator __last,
    _Predicate __pred) {
    return std::__remove_if(__first, __last,
          __gnu_cxx::__ops::__pred_iter(__pred));
}

template<typename _ForwardIterator, typename _Predicate>
_ForwardIterator
    __remove_if(_ForwardIterator __first, _ForwardIterator __last,
    _Predicate __pred) {
    __first = std::__find_if(__first, __last, __pred); // 找到第一个true
    if (__first == __last) // 如果没有，那么直接返回 first
        return __first;
    _ForwardIterator __result = __first;
    ++__first;
    for (; __first != __last; ++__first)
        if (!__pred(__first)) {
            *__result = _GLIBCXX_MOVE(*__first);
            ++__result;
        }
return __result;
}

8.20 remove_copy_if

remove_copy_if() 将给定区间的所有使得仿函数 pred 判定为 true 的元素，但是不是真正删除元素，而是将判定为 false 的元素拷贝到一个以 result 为起始位置的容器中。新的结果容器可以和旧的容器重叠。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template<typename _InputIterator, typename _OutputIterator,
   typename _Predicate>
inline _OutputIterator
remove_copy_if(_InputIterator __first, _InputIterator __last,
       _OutputIterator __result, _Predicate __pred) {
    return std::__remove_copy_if(__first, __last, __result,
               __gnu_cxx::__ops::__pred_iter(__pred));
}

template<typename _InputIterator, typename _OutputIterator,
   typename _Predicate>
_OutputIterator
__remove_copy_if(_InputIterator __first, _InputIterator __last,
         _OutputIterator __result, _Predicate __pred) {
    for (; __first != __last; ++__first)
        if (!__pred(__first)) { // 一个一个将判定为 false 的元素赋值给result容器
            *__result = *__first;
            ++__result;
        }
    return __result;
}

8.21 replace

replace() 将给定区间的所有 old_value 替换为 new_value。

1
2
3
4
5
6
7
template<typename _ForwardIterator, typename _Tp>
void replace(_ForwardIterator __first, _ForwardIterator __last,
    const _Tp& __old_value, const _Tp& __new_value) {
    for (; __first != __last; ++__first)
        if (*__first == __old_value)
            *__first = __new_value;
}

8.22 replace_copy

replace_copy() 作用和 replace() 类似，但是原来的容器不会被改变，而是将结果拷贝到给定的容器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<typename _InputIterator, typename _OutputIterator, typename _Tp>
inline _OutputIterator
replace_copy(_InputIterator __first, _InputIterator __last,
    _OutputIterator __result,
    const _Tp& __old_value, const _Tp& __new_value) {
    return std::__replace_copy_if(__first, __last, __result,
        __gnu_cxx::__ops::__iter_equals_val(__old_value),
        __new_value);
}

template<typename _InputIterator, typename _OutputIterator,
typename _Predicate, typename _Tp>
_OutputIterator
__replace_copy_if(_InputIterator __first, _InputIterator __last,
    _OutputIterator __result,
    _Predicate __pred, const _Tp& __new_value) {
    for (; __first != __last; ++__first, (void)++__result)
        if (__pred(__first)) // 判定为 true 就插入新值
            *__result = __new_value;
        else                // 否则就插入旧值
            *__result = *__first;
    return __result;
}

8.23 replace_if

replace_if() 将给定区间的所有使得仿函数 pred 为 true 的元素赋值为新值。

1
2
3
4
5
6
7
8
template<typename _ForwardIterator, typename _Predicate, typename _Tp>
void
replace_if(_ForwardIterator __first, _ForwardIterator __last,
    _Predicate __pred, const _Tp& __new_value) {
    for (; __first != __last; ++__first)
        if (__pred(*__first))
            *__first = __new_value;
}

8.24 replace_copy_if

replace_copy_if() 和 replace_if 类似，但是结果将会被写到给定的一个 result 为起始位置的容器，而原来的容器不会由任何的变化。

1
2
3
4
5
6
7
8
9
10
11
12
13
template<typename _InputIterator, typename _OutputIterator,
typename _Predicate, typename _Tp>
_OutputIterator
__replace_copy_if(_InputIterator __first, _InputIterator __last,
    _OutputIterator __result,
    _Predicate __pred, const _Tp& __new_value) {
    for (; __first != __last; ++__first, (void)++__result)
        if (__pred(__first)) // 判定为 true 就插入新值
            *__result = __new_value;
        else                // 否则就插入旧值
            *__result = *__first;
    return __result;
}

8.25 reverse

reverse() 将给定的区间的元素颠倒重排。根据传递的不同的迭代器类型（比如 vector 和 list 就是不同的迭代器类型），很多 STL 算法都是这个实现的套路的，reverse() 调用不同的实现的版本。

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
template<typename _BidirectionalIterator>
inline void
reverse(_BidirectionalIterator __first, _BidirectionalIterator __last) {
    std::__reverse(__first, __last, std::__iterator_category(__first));
}

// 版本一 bidirectional iterator
template<typename _BidirectionalIterator>
void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
    bidirectional_iterator_tag) {
    while (true)
        if (__first == __last || __first == --__last)
            return;
        else {
            std::iter_swap(__first, __last);
            ++__first;
        }
}

// 版本二 random access iterator
template<typename _RandomAccessIterator>
void __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
  random_access_iterator_tag) {
    if (__first == __last)
        return;
    --__last;
    while (__first < __last) { // 要注意只有随机访问迭代器才可以使用 < 比较
        std::iter_swap(__first, __last);
        ++__first;
        --__last;
    }
}

8.26 reverse_copy

行为类似于上一个函数 reverse，只不过是不改变原来的序列，而是将结果写到一个以 result 为起始位置的容器中。

1
2
3
4
5
6
7
8
9
10
11
12
template<typename _BidirectionalIterator, typename _OutputIterator>
_OutputIterator
    reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
    _OutputIterator __result) {

    while (__first != __last) { // 从后往前将元素写到 result 容器中，result 容器空间不够将发生不可以预期的事情
        --__last;
        *__result = *__last;
        ++__result;
    }
    return __result;
}

8.27 rotate

rotate() 将区间 [first, middle) 的元素和区间 [middle, last) 的元素互换，middle 所指向的元素将会称为第0个元素，比如区间{ 9, 8, 7, 6, 5, 4, 3 }对 6 作旋转操作，那么结果是 { 6, 5, 4, 3, 9, 8, 7 }。用图来表示就是：

同样的迭代器的移动能力会影响算法的效率，或者是应该有一个最小功能原则，STL先将 rotate 定义为一个分发函数，根据不同的迭代器版本调用不同的实现，这里有三个不同的版本的 rotate，返回值是 last + (last - middle)

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
// 分发函数
template<typename _ForwardIterator>
inline _ForwardIterator
rotate(_ForwardIterator __first, _ForwardIterator __middle,
    _ForwardIterator __last) {
    return std::__rotate(__first, __middle, __last,
       std::__iterator_category(__first));
}

// version 1：forward iterator
template<typename _ForwardIterator>
_ForwardIterator __rotate(_ForwardIterator __first,
     _ForwardIterator __middle, _ForwardIterator __last,
     forward_iterator_tag) {
    if (__first == __middle) return __last; // 如果前半区间没有元素，按照第0个元素旋转，直接不用旋转
    else if (__last  == __middle) // 后半区间没有元素，也直接不用旋转
        return __first;
    _ForwardIterator __first2 = __middle;
    do {
        std::iter_swap(__first, __first2);
        ++__first;
        ++__first2;
        if (__first == __middle) // 如果前半段先完成
            __middle = __first2; // 剩余后半段以middle为起始位置
                                 // 如果后半段先完成,剩余前半段以first为起始位置
    }
    while (__first2 != __last);

    _ForwardIterator __ret = __first;

    __first2 = __middle; 
    
    // 无论是前半段先完成还是后半段先完成,都要继续以middle继续旋转
    while (__first2 != __last) {
        std::iter_swap(__first, __first2);
        ++__first;
        ++__first2;
        if (__first == __middle) // 如果前半段先完成
            __middle = __first2;
        else if (__first2 == __last) // 如果后半段先完成
            __first2 = __middle;
    }
    return __ret; // ret就是原来的
}

// version2 : bidirectionalIterator
// 这个很好理解
template<typename _BidirectionalIterator>
_BidirectionalIterator __rotate(_BidirectionalIterator __first,
    _BidirectionalIterator __middle, _BidirectionalIterator __last,
    bidirectional_iterator_tag) {
    if (__first == __middle)
        return __last;
    else if (__last  == __middle)
        return __first;
    // 前半段、后半段分别倒置
    std::__reverse(__first,  __middle, bidirectional_iterator_tag());
    std::__reverse(__middle, __last,   bidirectional_iterator_tag());

    while (__first != __middle && __middle != __last) {
        std::iter_swap(__first, --__last);
        ++__first;
    }

    if (__first == __middle) { // 前短后长
        std::__reverse(__middle, __last,   bidirectional_iterator_tag());
        return __last;
    }
    else { // 前长后短
        std::__reverse(__first,  __middle, bidirectional_iterator_tag());
        return __first;
    }
}

template<typename _RandomAccessIterator>
_RandomAccessIterator __rotate(_RandomAccessIterator __first,
    _RandomAccessIterator __middle, _RandomAccessIterator __last,
    random_access_iterator_tag) {
    if (__first == __middle) return __last;
    else if (__last  == __middle) return __first;

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type
    _Distance;
    typedef typename iterator_traits<_RandomAccessIterator>::value_type
    _ValueType;

    _Distance __n = __last   - __first; // 总长度，random access iterator才可这么计算
    _Distance __k = __middle - __first; // 前半段长度

    if (__k == __n - __k) { // 如果前后等长，直接交换，完事儿！
        std::swap_ranges(__first, __middle, __middle);
        return __middle;
    }

    _RandomAccessIterator __p = __first;
    _RandomAccessIterator __ret = __first + (__last - __middle);

    for (;;) {
        if (__k < __n - __k) { 前短后长
            if (__is_pod(_ValueType) && __k == 1) { // 前半段只有一个元素, 直接把这个元素移动到最后的位置
                _ValueType __t = _GLIBCXX_MOVE(*__p);
                _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
                *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
                return __ret;
            }
            _RandomAccessIterator __q = __p + __k;
            for (_Distance __i = 0; __i < __n - __k; ++ __i) {
                std::iter_swap(__p, __q);
                ++__p;
                ++__q;
            }
            __n %= __k;
            if (__n == 0)
                return __ret;
            std::swap(__n, __k);
            __k = __n - __k;
        }
        else { // 前长后短
        __k = __n - __k;
        if (__is_pod(_ValueType) && __k == 1) {
            _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
            _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
            *__p = _GLIBCXX_MOVE(__t);
            return __ret;
        }
        _RandomAccessIterator __q = __p + __n;
        __p = __q - __k;
        for (_Distance __i = 0; __i < __n - __k; ++ __i) {
            --__p;
            --__q;
            std::iter_swap(__p, __q);
        }
        __n %= __k;
        if (__n == 0)
            return __ret;
        std::swap(__n, __k);
        }
    }
}

除了这些算法还是其他的的算法，算法的实现都很简单：

search_n：在给定区间内，查找“连续 count 个符合条件之元素”形成的子序列，并返回一个指向这个子序列的迭代器。比如
查找“连续两个8”形成的子序列：iter = search_n(ivec.begin(), ivec.end(), 2, 8)；查找“连续三个小于8的元素”形成的子序列：iter = search_n(ivec.begin(), ivec.end(), 3, 8, less<int>())

transform：

unique：移除给定区间的重复元素，但是只移除相邻的重复元素，如果想要移除所有的重复元素，可以先排序使得所有的重复元素相邻。unique 返回新区间的尾端，会有残留数据，可以用容器的成员函数 erase 删除残留在后端的数据。

unique_copy：和 unique 类似，但是将结果复制到以 result 为起始位置的容器中。

9. 比较复杂的算法

9.1 lower_bound(应用于有序区间)

lower_bound() 是二分查找的一个版本，试图在一个有序区间种寻找 value。如果区间中有和 value 相等的元素，那么就返回一个指向这个元素的迭代器，如果没有相等的元素，那么就返回如果要将 value 插入区间，value应该在的位置，也就是会返回一个迭代器，指向第一个“不小于 value 的元素”，如果 value 比所有的元素都大，那么返回 last。该算法有两个版本，版本1采用 operator< 进行比较，版本2采用函数对象（functor）进行比较。

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
// forward iterator 版本
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_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); // middle 指向中间位置
        if (__comp(__middle, __val)) { //如果middle小于value
            __first = __middle;
            ++__first;
            __len = __len - __half - 1; // 更新查找范围
        }
        else
            __len = __half;
    }
    return __first;
}

9.2 upper_bound(应用于有序区间)

upper_bound() 和 lower_bound() 类似，都是二分查找的一个版本，返回“在不破坏顺序的情况下，可插入 value 的最后一个合适的位置”，这里不顺序不被破坏的意思就是排序的状态不变，也就是如果序列本来就是存在value，那么 upper_bound() 返回的是迭代器指向 value 的下一个位置。upper_bound() 同样有两个版本，版本一使用 operator< 进行比较，版本二使用 仿函数 comp 进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<typename _ForwardIterator, typename _Tp, typename _Compare>
_ForwardIterator
__upper_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); // middle 指向中间位置
        if (__comp(__val, __middle))  // value < middle 
            __len = __half;
        else {
            __first = __middle;
            ++__first;
            __len = __len - __half - 1;
        }
    }
    return __first;
}

binary_search() 是一种二分查找，用于查找给定区间是否有 vulue，返回一个 bool 值，同样两个版本，version1使用 operator< 进行比较，version2使用仿函数进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// version1
template<typename _ForwardIterator, typename _Tp>
bool binary_search(_ForwardIterator __first, _ForwardIterator __last,
const _Tp& __val) {
    _ForwardIterator __i
    = std::__lower_bound(__first, __last, __val,
         __gnu_cxx::__ops::__iter_less_val()); // 找到value的lower_bound
    
    // 如果lower_bound是区间的last,那么说明区间不存在value
    // 如果lower_bound比value还大那么说明区间不存在value
    return __i != __last && !(__val < *__i);
}

// version2
template<typename _ForwardIterator, typename _Tp, typename _Compare>
bool binary_search(_ForwardIterator __first, _ForwardIterator __last,
    const _Tp& __val, _Compare __comp) {
    // 原理同上
    _ForwardIterator __i = std::__lower_bound(__first, __last, __val,
         __gnu_cxx::__ops::__iter_comp_val(__comp));
    eturn __i != __last && !bool(__comp(__val, *__i));
}

9.4 next_permutation

next_permutation() 和 prev_permutation() 是STL提供的用来计算排列组合关系的两个函数，分别获得前一个排列组合和后一个排列组合。next_permutation() 获取下一个排列，如果没有（已经是最后一个排列），那么就返回 false，否则返回 true， 这是要给 mutation function。同样有两个版本的实现，version1使用元素所提供的 less-than 操作符来决定下一个排列，version2则使用仿函数来决定。
下一个排列其实就是找到下一个更大的数，比如 32654 的下一个数应该是 34256。
下一个排列算法：

  1. 从后往前找到两个相邻元素 i 和 ii，并且 i < ii；
  2. 继续从后往前找第一个大于 i 的元素j；
  3. swap(i, j);
  4. reverse(ii, last);
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
// version1：就是直接调用这个函数，并传递一个
template<typename _BidirectionalIterator>
inline bool
next_permutation(_BidirectionalIterator __first,
     _BidirectionalIterator __last) {
    return std::__next_permutation
    (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
}


// version2：可以传递一个仿函数
template<typename _BidirectionalIterator, typename _Compare>
bool
__next_permutation(_BidirectionalIterator __first,
   _BidirectionalIterator __last, _Compare __comp) {
    if (__first == __last) // 空区间没有下一个排列
        return false;
    _BidirectionalIterator __i = __first; // 
    ++__i;
    if (__i == __last) // 只有一个元素，也没有下一个排列
        return false;
    __i = __last; // 从后往前找一对元素 i 和 ii
    --__i;

    for(;;) {
        _BidirectionalIterator __ii = __i; 
        --__i;
        if (__comp(__i, __ii)) {                        // 如果 i < ii
            _BidirectionalIterator __j = __last;        // 从后往前找第一个大于i的元素  
            while (!__comp(__i, --__j)) {}              // 一直找
            std::iter_swap(__i, __j);                   // 交换i， j
            std::__reverse(__ii, __last,
                 std::__iterator_category(__first));    // reverse(ii, last)
            return true;                                // 找到了下一个排列
        }
        if (__i == __first) {                           // 如果i已经到了第一个元素，已经可以说明没有下一个排列了
            std::__reverse(__first, __last,             // 说明已经是一个降序序列了
                 std::__iterator_category(__first));    // 但是为啥还要 reverse 人家？变成了要给升序序列
            return false;
        }
    }
}

9.5 prev_permutation

prev_permutation() 获取前一个排列，相当于找到比当前数小，但是最接近当前数的数。算法返回值是bool值，当序列已经升序，没有前一个排列，同样重拍变成升序，实现方面也和 next_permutation() 类似：

  1. 从尾部往前找两个相邻元素，使得 i > ii(i前ii后)；
  2. 从尾部往前找出第一个小于 i 的元素 j；
  3. swap(i, j);
  4. reverse(ii, last);
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
template<typename _BidirectionalIterator, typename _Compare>
bool
__prev_permutation(_BidirectionalIterator __first,
   _BidirectionalIterator __last, _Compare __comp) {
    if (__first == __last)
        return false;
    _BidirectionalIterator __i = __first;
    ++__i;
    if (__i == __last)
        return false;
    __i = __last;
    --__i;

    for(;;) {
        _BidirectionalIterator __ii = __i;
        --__i;
        if (__comp(__ii, __i)) {
            _BidirectionalIterator __j = __last;
            while (!__comp(--__j, __i)) {}
            std::iter_swap(__i, __j);
            std::__reverse(__ii, __last,
                 std::__iterator_category(__first));
            return true;
        }
        if (__i == __first) {
        std::__reverse(__first, __last,
             std::__iterator_category(__first));
        return false;
        }
    }
}

9.6 random_shuffle

random_shuffle() 将给定区间的元素次序随机重拍，也就是在 N! 中可能中选择一种作为结果。random_shuffle()将形成在 N! 种可能种的均匀分布，每种排列的可能概率都相等。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
void
random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
#if __cplusplus >= 201103L
    _RandomNumberGenerator&& __rand)
#else
    _RandomNumberGenerator& __rand)
#endif
    {
    if (__first == __last) // 空区间
        return;
    for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) {
        // 随机选择一个和i交换
        _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
        if (__i != __j)
            std::iter_swap(__i, __j);
    }
}

9.7 partial_sort / partial_sort_copy

partial_sort() 接受三个迭代器，first、middle、last，任务是找出 middle - first 个最小的元素，也就是使得序列中的 middle - first 个最小的元素按照递增排序，放置在区间 [first, middle) 中，其余的 last - middle 个元素放置于区间 [middle, last) 中，但是不保证有序。当然使用 sort() 算法对整个区间排序然后获取前 N 个也可达到获取 N 个最小元素的目的，不这么做的唯一原因就是效率问题。partial_sort() 同样有两个版本，一个是使用 less-than 操作符 operator< 来比较元素，另一个版本是可以提供一个 functor 来比较元素。算法的内部使用 heap sort 来实现：

  1. 使用 make_heap() 将区间 [first, middle) 组织成要给 max-heap;
  2. 遍历区间 [middle, last) ，每个元素都和 max-heap 的最大元素（第一个元素）比较，如果小于该最大值，那么就互换；
  3. 遍历结束后 [first, middle) 中的所有值已经是整个区间的最小值；
  4. 使用 sort_heap 对区间 [first, middle) 排序即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// partial_sort 只接受随机访问迭代器
template<typename _RandomAccessIterator, typename _Compare>
inline void __partial_sort(_RandomAccessIterator __first,
       _RandomAccessIterator __middle, _RandomAccessIterator __last,
       _Compare __comp) {
    // 步骤1， 2， 3
    std::__heap_select(__first, __middle, __last, __comp);
    // 步骤4，排序
    std::__sort_heap(__first, __middle, __comp);
}

/// This is a helper function for the sort routines.
template<typename _RandomAccessIterator, typename _Compare>
void __heap_select(_RandomAccessIterator __first,
      _RandomAccessIterator __middle,
      _RandomAccessIterator __last, _Compare __comp) {
    // [first, middle) make一个max-heap
    std::__make_heap(__first, __middle, __comp);
    // 用后后面小于 max-heap 最大值的元素交换最大值
    // 保持 max-heap 特性
    for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
        if (__comp(__i, __first))
            std::__pop_heap(__first, __middle, __i, __comp);
}

至于 partial_sort_copy，实现上于 partial_sort 类似，但是将区间[first, last)排序后的结果写道[result_first, result_last)中。

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
template<typename _InputIterator, typename _RandomAccessIterator,
typename _Compare>
_RandomAccessIterator
__partial_sort_copy(_InputIterator __first, _InputIterator __last,
    _RandomAccessIterator __result_first, _RandomAccessIterator __result_last,
    _Compare __comp) {
    typedef typename iterator_traits<_InputIterator>::value_type
    _InputValueType;
    typedef iterator_traits<_RandomAccessIterator> _RItTraits;
    typedef typename _RItTraits::difference_type _DistanceType;

    if (__result_first == __result_last) // 结果区间为空
        return __result_last;
    _RandomAccessIterator __result_real_last = __result_first;
    // 将[first, last)元素赋值到[result_first, result_last)中
    while (__first != __last && __result_real_last != __result_last) {
        *__result_real_last = *__first;
        ++__result_real_last;
        ++__first;
    }
    // 在result 中make heap
    std::__make_heap(__result_first, __result_real_last, __comp);
    while (__first != __last) {
        if (__comp(__first, __result_first))
        std::__adjust_heap(__result_first, _DistanceType(0),
               _DistanceType(__result_real_last
                     - __result_first),
               _InputValueType(*__first), __comp);
        ++__first;
    }
    std::__sort_heap(__result_first, __result_real_last, __comp);
    return __result_real_last;
}

9.8 sort

sort() 是所有 STL 提供的算法中最庞大复杂的一个算法，算法接受一对随机访问寄存器，然后将这对寄存器表示的区间范围内的元素按照升序排序，另一个版本则是允许用户提供一个仿函数作为排序的标准。STL中所有的关联容器底部都有排序功能（RB-tree自动排序的功能），所以用不到这个算法。序列式容器 vector、deque和list中，前两个的迭代器是属于随机访问寄存器（random access iterator），因此可以使用 sort，但是 list 的迭代器是 bidirectional iterator，不能使用算法 sort，因此需要调用容器自己的成员函数sort。
为什么泛型算法 sort() 一定要 random access iterator？
sort() 算法不是单纯使用某一个算法，而是根据不同的情况使用不同的算法：当数据量大时，首先使用 quick sort 分段递归排序，一旦分段排序数据量足够小，就可以使用 insertion sort，而如果递归的层次过深，还会改用 heap sort：

  1. insertion_sort
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
/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
void __insertion_sort(_RandomAccessIterator __first,
         _RandomAccessIterator __last, _Compare __comp) {
    if (__first == __last) return; // empty range
    // 将 [first + 1, last) 的元素一个一个插入到有序区间
    for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i) {
        // [first, i) 是一个有序区间
        if (__comp(__i, __first)) { // 如果当前元素 i 应该插入到first之前
            typename iterator_traits<_RandomAccessIterator>::value_type
            __val = _GLIBCXX_MOVE(*__i);
            _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1); // [first, i) 区间往后移动一个单位
            *__first = _GLIBCXX_MOVE(__val); // 在first位置写入i的值
        }
        else // 否则从后往前找 i 应该在的位置
            std::__unguarded_linear_insert(__i,
            __gnu_cxx::__ops::__val_comp_iter(__comp));
    }
}

/// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Compare>
void __unguarded_linear_insert(_RandomAccessIterator __last,
      _Compare __comp) {
    typename iterator_traits<_RandomAccessIterator>::value_type
    __val = _GLIBCXX_MOVE(*__last);
    _RandomAccessIterator __next = __last;
    --__next;
    while (__comp(__val, __next)) {  // 当出现 __comp(val, next) 为false说明val找到了合适的位置
        *__last = _GLIBCXX_MOVE(*__next); // 一个一个往后移动
        __last = __next;
        --__next;
    }
    *__last = _GLIBCXX_MOVE(__val);
}
  1. quick_sort 🚗🚗🚗🚗🚗🚗🚗🚗😁
    insert_sort 的时间复杂度是O(N2)，显然不适合用来处理大量数据，而 quick_sort 就是用来处理大量数据，平均时间复杂度为 O(NlogN)，最坏情况（待排序序列已经是正序或者逆序，那么递归树退化为单支的链表，深度最大）为O(N2)。一般来说，平均时间复杂度为O(NlogN)的算法有快排、堆排、归并，那么为什么STL要选择快排呢？这是因为在这三种算法中，归并需要更大的空间复杂度，而快排和堆排二者表面数据相当，但是由于快排使用分治的思想，每次比较的数据都是在一段区域内，能够很好利用 CPU cache （空间局部性原理），而堆排每次都需要从堆中拿出元素替换，不能利用好局部性原理。事实上这可能也是为什么快排表现更好的一个原因。假设S是待排序序列，快排算法如下：
    • 如果S的元素个数是 0 或者 1，结束；
    • 取 S 的任何一个元素作为枢纽 v （根据 v 将 S　划分为两部分）；
      • 为了避免输入数据不够随机，也就是已经有序带来的效率影响问题
      • 在划分上通常采用 median-of-three 的方法，也就是取首、中、尾三个元素的中间值作为v；
      • 而为了能够快速或者中间元素，输入迭代器必须是 random access iterator
    • 将 S 划分为 L，R 两部分，其中 L 中的所有元素都小于 v，R 中的所有元素都大于等于 v；
    • 对 L，R 递归执行快排
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/// This is a helper function...
// 这个划分还是挺有意思的
template<typename _RandomAccessIterator, typename _Compare>
_RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first,
  _RandomAccessIterator __last,
  _RandomAccessIterator __pivot, _Compare __comp) {
    while (true) {
        while (__comp(__first, __pivot)) ++__first;
        --__last;
        while (__comp(__pivot, __last)) --__last;
        if (!(__first < __last))
            return __first;
        std::iter_swap(__first, __last);
        ++__first;
    }
}

  1. 调用 Insertion Sort 的阈值
    前面说到当数据量小的时候可以使用 Insertion Sort，那么具体是多小才可以调用呢？事实上这个问题并没有定数，具体情况要根据设备而有不同，可能是5，可能是20，也可能是中间的一个值。

  2. introSort（内省排序）
    所谓内省排序（Introspective Sort）是多种混合排序算法，它的行为在大多数情况下和 median-of-three Quick Sort 完全相同，但是当分割行为有恶化为二次（N2）的倾向时，能够自己检测，转而调用 Heap Sort，从而使效率维持在 Heap Sort O(NlogN)。

  3. sort() 整合

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
// version1：operator<
template<typename _RandomAccessIterator>
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last) {
    std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
}

// version2：Functor
template<typename _RandomAccessIterator, typename _Compare>
inline void
sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp) {
    std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
}

template<typename _RandomAccessIterator, typename _Compare>
inline void
__sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp) {
    if (__first != __last) {
    std::__introsort_loop(__first, __last,
        std::__lg(__last - __first) * 2, __comp);
    std::__final_insertion_sort(__first, __last, __comp);
    }
}

// 调用 heap sort
template<typename _RandomAccessIterator, typename _Compare>
inline void __partial_sort(_RandomAccessIterator __first,
       _RandomAccessIterator __middle,
       _RandomAccessIterator __last,
       _Compare __comp) {
  std::__heap_select(__first, __middle, __last, __comp);
  std::__sort_heap(__first, __middle, __comp);
}

template<typename _RandomAccessIterator, typename _Compare>
inline _RandomAccessIterator
__unguarded_partition_pivot(_RandomAccessIterator __first,
    _RandomAccessIterator __last, _Compare __comp) {
    _RandomAccessIterator __mid = __first + (__last - __first) / 2; // 区间中点
    std::__move_median_to_first(__first, __first + 1, __mid, __last - 1,
          __comp);
    return std::__unguarded_partition(__first + 1, __last, __first, __comp); // 调用 partition进行划分
}

// This is a helper function for the sort routine.
template<typename _RandomAccessIterator, typename _Size, typename _Compare>
void __introsort_loop(_RandomAccessIterator __first,
    _RandomAccessIterator __last,
    _Size __depth_limit, _Compare __comp) {

    while (__last - __first > int(_S_threshold)) { // 当元素数量大于调用insertion sort的阈值(16)
        if (__depth_limit == 0) { // 分割恶化
            std::__partial_sort(__first, __last, __last, __comp); // 调用 heap sort
            return;
        }
        --__depth_limit;
        _RandomAccessIterator __cut =
        std::__unguarded_partition_pivot(__first, __last, __comp); // 分割点使 cut
        std::__introsort_loop(__cut, __last, __depth_limit, __comp); // 对右半部分进行递归排序
        __last = __cut; // last置为 cut，然后回到 while 对半部分进行递归排序
        }
}

9.9 equal_range(应用于有序区间)

equal_range() 是二分查找的一个版本，在以排序的区间找 value，返回一对迭代器（pair)，i和j，其中 i 是在不破坏次序的情况下可插入的第一给位置（lower_bound），j 是在不破坏次序的情况下可插入的最后一个位置（upper_bound）。函数同样有两个版本，一个用 operator< 进行比较，另一个版本使用仿函数 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
template<typename _ForwardIterator, typename _Tp,
typename _CompareItTp, typename _CompareTpIt>
pair<_ForwardIterator, _ForwardIterator>
    __equal_range(_ForwardIterator __first, _ForwardIterator __last,
    const _Tp& __val,
    _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it) {
    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_it_val(__middle, __val)) {     // 和value比较，value应该在后半部分
            __first = __middle;
            ++__first;
            __len = __len - __half - 1;
        }
        else if (__comp_val_it(__val, __middle)) // value应该在前半部分
            __len = __half;
        else { // 找到了一个值
            // value肯定是连续出现的
            // 找左边位置
            _ForwardIterator __left = std::__lower_bound(__first, __middle, __val, __comp_it_val);
            std::advance(__first, __len);
            // 找右边位置
            _ForwardIterator __right
            = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
            // 返回
            return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
        }
    }
    // 没有value，返对一对迭代器，指向第一个大于value的元素
    return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
}

9.10 inplace_merge

inplace_merge() 将两个连在一起而且分别有序的序列结合成一个序列，并保持有序，如果两个子序列有相等的元素，第一个子序列的元素会在前。算法有两个版本，version1使用 operator< 进行比较，version2则使用用户提供的仿函数进行比较。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
// [first, middle),[middle, last)分别有序
template<typename _BidirectionalIterator, typename _Compare>
void __inplace_merge(_BidirectionalIterator __first,
    _BidirectionalIterator __middle, _BidirectionalIterator __last,
    _Compare __comp) {
    typedef typename iterator_traits<_BidirectionalIterator>::value_type
    _ValueType;
    typedef typename iterator_traits<_BidirectionalIterator>::difference_type
    _DistanceType;

    if (__first == __middle || __middle == __last) // 任一子区间是空的直接返回即可
        return;

    const _DistanceType __len1 = std::distance(__first, __middle); // 长度
    const _DistanceType __len2 = std::distance(__middle, __last);

    typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
    _TmpBuf __buf(__first, __last); // 辅助空间

    if (__buf.begin() == 0)  // 如果没有申请到空间，就原地操作
        std::__merge_without_buffer
        (__first, __middle, __last, __len1, __len2, __comp);
    else // 使用辅助空间操作，效率当然更好
        std::__merge_adaptive
        (__first, __middle, __last, __len1, __len2, __buf.begin(),
        _DistanceType(__buf.size()), __comp);
}


// 原地操作
template<typename _BidirectionalIterator, typename _Distance,
typename _Compare>
void __merge_without_buffer(_BidirectionalIterator __first,
   _BidirectionalIterator __middle, _BidirectionalIterator __last,
   _Distance __len1, _Distance __len2, _Compare __comp) {
    if (__len1 == 0 || __len2 == 0)
        return;

    if (__len1 + __len2 == 2) { // 各有一个元素，前大后小的话直接互换，否则直接返回
        if (__comp(__middle, __first))
            std::iter_swap(__first, __middle);
        return;
    }

    _BidirectionalIterator __first_cut = __first;
    _BidirectionalIterator __second_cut = __middle;
    _Distance __len11 = 0;
    _Distance __len22 = 0;
    if (__len1 > __len2) { // 前大后小
    __len11 = __len1 / 2;
    std::advance(__first_cut, __len11);
    __second_cut
    = std::__lower_bound(__middle, __last, *__first_cut,
         __gnu_cxx::__ops::__iter_comp_val(__comp));
    __len22 = std::distance(__middle, __second_cut);
    }
    else
    {
    __len22 = __len2 / 2;
    std::advance(__second_cut, __len22);
    __first_cut
    = std::__upper_bound(__first, __middle, *__second_cut,
         __gnu_cxx::__ops::__val_comp_iter(__comp));
    __len11 = std::distance(__first, __first_cut);
    }

    std::rotate(__first_cut, __middle, __second_cut);
    _BidirectionalIterator __new_middle = __first_cut;
    std::advance(__new_middle, std::distance(__middle, __second_cut));
    std::__merge_without_buffer(__first, __first_cut, __new_middle,
          __len11, __len22, __comp);
    std::__merge_without_buffer(__new_middle, __second_cut, __last,
          __len1 - __len11, __len2 - __len22, __comp);
}

// 
template<typename _BidirectionalIterator, typename _Distance, 
typename _Pointer, typename _Compare>
void __merge_adaptive(_BidirectionalIterator __first,
 _BidirectionalIterator __middle, _BidirectionalIterator __last,
 _Distance __len1, _Distance __len2,
 _Pointer __buffer, _Distance __buffer_size,
 _Compare __comp) {
    // case1：辅助空间能容纳子序列1
    if (__len1 <= __len2 && __len1 <= __buffer_size) {
        _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
        std::__move_merge_adaptive(__buffer, __buffer_end, __middle, __last,
                 __first, __comp);
    }
    // case2：辅助空间能容纳子序列2 
    else if (__len2 <= __buffer_size) {
        _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
        std::__move_merge_adaptive_backward(__first, __middle, __buffer,
                      __buffer_end, __last, __comp);
    }
    // 辅助空间无法容纳这两个区间
    else {
        _BidirectionalIterator __first_cut = __first;
        _BidirectionalIterator __second_cut = __middle;
        _Distance __len11 = 0;
        _Distance __len22 = 0;
        if (__len1 > __len2)
        {
        __len11 = __len1 / 2;
        std::advance(__first_cut, __len11);
        __second_cut
        = std::__lower_bound(__middle, __last, *__first_cut,
                 __gnu_cxx::__ops::__iter_comp_val(__comp));
        __len22 = std::distance(__middle, __second_cut);
        }
        else
        {
        __len22 = __len2 / 2;
        std::advance(__second_cut, __len22);
        __first_cut
        = std::__upper_bound(__first, __middle, *__second_cut,
                 __gnu_cxx::__ops::__val_comp_iter(__comp));
        __len11 = std::distance(__first, __first_cut);
        }

        _BidirectionalIterator __new_middle
        = std::__rotate_adaptive(__first_cut, __middle, __second_cut,
                 __len1 - __len11, __len22, __buffer,
                 __buffer_size);
        std::__merge_adaptive(__first, __first_cut, __new_middle, __len11,
            __len22, __buffer, __buffer_size, __comp);
        std::__merge_adaptive(__new_middle, __second_cut, __last,
            __len1 - __len11,
            __len2 - __len22, __buffer,
            __buffer_size, __comp);
    }
}

9.11 nth_element

nth_element()

9.12 merge sort

还真的全都忘记了！🐷