残局

不过在等杀死希望的最后一刀

0%

STL源码-算法

发表于 更新于
本文字数： 13k 阅读时长 ≈ 12 分钟

本文是在阅读SGI STL v3.3源码中关于algorithm部分，遇到的一些问题及有意思的点。

至此，STL六大件告一段落。（源码中，还有一些实现相应辅助功能的其他文件在此假装没有）。

algorithm

从实现角度看，STL算法实质上也是一种模板类。

STL中所有的算法前两个参数都是一对迭代器，所包含的元素都是左闭右开[first,last)

最后一个可选参数一般都是自定义规则（仿函数传入点），鉴于仿函数( _Compare __comp)传入进来只是比较规则位置发生变化，下文中以默认带有仿函数的为准。

max/min/swap略过

此外，在众多的函数中有着如下规律：

xxx 和xxx_if

  • xxx一般为对值为value的元素进行操作
  • xxx_if则是对value满足一定条件(__pred)的元素进行操作

xxx 和 xxx_n

  • xxx一般前两个参数为iter first和iter last表示对一个区间内进行操作
  • xxx_n则是iter first和size_t n是以first为首的n个元素进行操作(也是一个区间)

xxx 和xxx_copy

  • xxx一般是对原数组[first,last)进行操作。
  • xxx_copy是将操作的结果保存到[result,result+last−first)中。

accumulate

将[first,last)的值累加到init上。（init在原基础上增加区间和。）

1
2
3
4
5
6
7
8
9
10
// 用二元函数 op 计算
template <class _InputIterator, class _Tp, class _BinaryOperation>
_Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,
               _BinaryOperation __binary_op)
{
  for ( ; __first != __last; ++__first)
      __init = __binary_op(__init, *__first);
    //    __init = __init + *__first;
    return __init;
}
  • __binary_op — 累加方式

inner_product

我们知道两个向量的内积公式：已知两个向量：a→=(a1,a2,…,ai)b→=(b1,b2,…,bi)

两个向量的内积：a→⋅b→=a1b1+a2b2+⋯+aibi

两个数组的内积公式依然，数组中元素的个数类比向量的维度。

将[first1,last1)与[first2,first2+last1−first1)两个区间做内积，并将结果累加到init。

由于第二区间只给了首迭代器(first2)，要保证容器中的元素个数充足。

1
2
3
4
5
6
7
8
9
10
11
12
template <class _InputIterator1, class _InputIterator2, class _Tp,
          class _BinaryOperation1, class _BinaryOperation2>
_Tp inner_product(_InputIterator1 __first1, _InputIterator1 __last1,
                  _InputIterator2 __first2, _Tp __init, 
                  _BinaryOperation1 __binary_op1,
                  _BinaryOperation2 __binary_op2)
{
    for ( ; __first1 != __last1; ++__first1, ++__first2)
        __init = __binary_op1(__init, __binary_op2(*__first1, *__first2));
        //     __init = __init + (*__first1 * *__first2);
    return __init;
}
  • __binary_op1 — 累加方式
  • __binary_op2 — 内积方式

partial_sum

计算范围[first,last)的子范围中元素的部分和，并写入到始于 result 的范围

假设[first,last)表示数组X=[x1,x2,…,xi,…,xn]，由result开始的数组Y=[y1,y2,…,yi,…,yn]。则该函数实现的功能是yi=∑n=0ixn。

类似于数列的aiSi

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 <class _InputIterator, class _OutputIterator, class _Tp,
          class _BinaryOperation>
_OutputIterator 
__partial_sum(_InputIterator __first, _InputIterator __last, 
              _OutputIterator __result, _Tp*, _BinaryOperation __binary_op)
{
    _Tp __value = *__first;
    while (++__first != __last) {
        __value = __binary_op(__value, *__first);
        //__value = __value + *__first;
        *++__result = __value;
  }
    return ++__result;
}

template <class _InputIterator, class _OutputIterator, class _BinaryOperation>
_OutputIterator 
partial_sum(_InputIterator __first, _InputIterator __last,
            _OutputIterator __result, _BinaryOperation __binary_op)
{
    if (__first == __last) return __result;//首尾指针重合 含有0个元素 无操作
    *__result = *__first;
    return __partial_sum(__first, __last, __result, __VALUE_TYPE(__first), 
                         __binary_op);
}
  • __binary_op — 累加方式

adjacent_difference

计算范围[first,last)的相邻元素的差值，并写入到始于 result 的范围。

假设[first,last)表示数组X=[x1,x2,…,xi,…,xn]，由result开始的数组Y=[y1,y2,…,yi,…,yn]。则该函数实现的功能是yi=xi−xi−1，特例y0=x0

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
template <class _InputIterator, class _OutputIterator, class _Tp, 
          class _BinaryOperation>
_OutputIterator
__adjacent_difference(_InputIterator __first, _InputIterator __last, 
                      _OutputIterator __result, _Tp*,
                      _BinaryOperation __binary_op) {
    _Tp __value = *__first;// x_{i-1}
    while (++__first != __last) {
        _Tp __tmp = *__first;
        *++__result = __binary_op(__tmp, __value);
        // *++__result = __tmp - __value; 
        __value = __tmp;
  }
    return ++__result;
}

template <class _InputIterator, class _OutputIterator, class _BinaryOperation>
_OutputIterator 
adjacent_difference(_InputIterator __first, _InputIterator __last,
                    _OutputIterator __result, _BinaryOperation __binary_op)
{
    if (__first == __last) return __result;//重合无任何操作
    *__result = *__first;//y0 = x0
    return __adjacent_difference(__first, __last, __result,
                                 __VALUE_TYPE(__first),
                                 __binary_op);
}
  • __binary_op — 作差方式

power

快速幂求xn。

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 <class _Tp, class _Integer, class _MonoidOperation>
inline _Tp power(_Tp __x, _Integer __n, _MonoidOperation __opr)
{
    return __power(__x, __n, __opr);
    //return __power(__x, __n, multiplies<_Tp>());  
    //不传操作符默认调用算数仿函数multiplies
    //影响的是移位时值改变的方式。
}

template <class _Tp, class _Integer, class _MonoidOperation>
_Tp __power(_Tp __x, _Integer __n, _MonoidOperation __opr)
{
    if (__n == 0)
        return identity_element(__opr);
    else {
        while ((__n & 1) == 0) {
            __n >>= 1;
            __x = __opr(__x, __x);
            //默认传参multiplies是相乘，在此可更改
        }

        _Tp __result = __x;
        __n >>= 1;
        while (__n != 0) {
            __x = __opr(__x, __x);
            if ((__n & 1) != 0)
                __result = __opr(__result, __x);
            __n >>= 1;
        }
        return __result;
    }
}

iota

将[value,value+last−first)元素的值赋给[fist,last)

1
2
3
4
5
6
template <class _ForwardIter, class _Tp>
void  iota(_ForwardIter __first, _ForwardIter __last, _Tp __value)
{
    while (__first != __last)
        *__first++ = __value++;
}

iter_swap

交换所指向的元素。（指向的内存不变）

以下几个copy/fill函数均有针对字符串的重载，调用memset去赋值。

由于实现的功能是赋值，也没有额外增加运算规则的重载。

copy

正向拷贝（从前往后读取并赋值）。有random_access_iterator_tag、input_iterator_tag、__copy_trivial等多个版本所实现的功能均为将[first,last)区域的内容拷贝至[result,result+last−first)内。

copy_backward

反向拷贝（从后往前读取并赋值）。同样有多个重载版本，但实现的功能一样。

将[first,last)区域的内容拷贝至[result−(last−first),result)内。

copy_n

将[first,first+n)拷贝给[result,result+n)

fill

将[first,last)的值赋为value

fill_n

将[first,first+n)的值赋为value

mismatch

将[first1,last1)与[first2,first2+last1−first1)中对应位置的元素进行对比。返回 值不相等时的两个迭代器

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
                                        _InputIter1 __last1,
                                        _InputIter2 __first2,
                                        _BinaryPredicate __binary_pred) {
    while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
        						//*__first1 == *__first2
        ++__first1;
        ++__first2;
  }
  return pair<_InputIter1, _InputIter2>(__first1, __first2);
}

  • __binary_pred — 自定义的比较规则

equal

对比[first1,last1)与[first2,first2+last1−first1)对应位置的元素是否相等，完全相等返回true

lexicographical_compare

以字典序对比[first1,last1)与[first2,last2)。区间1小于区间2则返回true

1
2
3
4
5
6
7
8
9
10
11
12
13
template <class _InputIter1, class _InputIter2, class _Compare>
bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
                             _InputIter2 __first2, _InputIter2 __last2,
                             _Compare __comp) {
    for ( ; __first1 != __last1 && __first2 != __last2
          ; ++__first1, ++__first2) {
        if (__comp(*__first1, *__first2))
            return true;//字符小于
        if (__comp(*__first2, *__first1))
            return false;
  }//前面字符相等 但2长（1为2的前缀）
    return __first1 == __last1 && __first2 != __last2;
}

__median

一个辅助函数，用于寻找3个元素中的最小值。

  • 可传入第四个参数__comp，用于更改元素间的比对规则。

for_each

遍历。遍历[first,last)区间，并对每个元素执行_Function __f

以下 find/count函数针对iterator_category不同

分为input_iterator_tag和random_access_iterator_tag两个版本

find

在[first,last)中查找第一个值为val的位置。

find_if

在[first,last)中查找第一个值满足__pred条件的位置。

adjacent_find

在[first,last)中查找 2 个连续相等的元素。如果能找到返回前一个元素位置的迭代器。

允许自定义判断规则__binary_pred

count

判断[first,last)中val出现的次数，并将值加在n上。

count_if

判断[first,last)中元素满足__pred条件的个数，并将值加在n上。

在[first1,last1)中寻找第一个与[first2,last2)相等（或满足__predicate条件）的子数组，返回首个元素的位置。

search_n

在[first,last)中寻找第一次连续出现__count个元素值等于__val（或满足__binary_pred条件的__val）的位置。（返回首元素位置）

swap_ranges

调用[iter_swap](# iter_swap)实现，互换[first1,last1)与[first2,first2+last1−first1)区间元素（交换所存的值）

1
2
3
4
5
6
7
template <class _ForwardIter1, class _ForwardIter2>
_ForwardIter2 swap_ranges(_ForwardIter1 __first1, _ForwardIter1 __last1,
                          _ForwardIter2 __first2) {
    for ( ; __first1 != __last1; ++__first1, ++__first2)
        iter_swap(__first1, __first2);
    return __first2;
}

transform

将函数__opr(可一元和二元)应用到序列[first1,last1)的元素上，并将这个函数返回的值保存到另一个序列中[result,result+last1−first1)。

当传入二元仿函数时，需要额外传入一个迭代器first2，所实现的功能是：将[first1,last1)与[first2,first2+last1−first1)进行__binary_op运算并将结果存储在[result,result+last1−first1)

transform与for_each的区别

  • for_each所调用的仿函数没有返回值，且只能在原位置上修改。
  • transform所调用的函数必须有返回值（要依次赋值给另一区间），原位置元素不受影响。

replace

将[first,last)中值等于__old_value的元素（满足pred条件的元素）替换为__new_value

replace_copy(_if)

replace中的替换是在原位置上进行，该函数是以原数组为基础进行操作，并将结果存在新位置。

将[first,last)中的值赋值到[result,result+last−first)中，并将其中等于__old_value的元素（满足pred条件的元素，增加_if）替换为__new_value。

generate(_n)

为[first,last)（或[first,first+n)）中元素赋值为__gen。__gen要求为lambda表达式。

generate与for_each区别

1
2
3
4
5
6
//generate
for ( ; __first != __last; ++__first)
    *__first = __gen();
//for_each
for ( ; __first != __last; ++__first)
    __f(*__first);

因为函数调用的形式不同，进而对输入的要求也不同。for_each传入的是一个仿函数，而generate传入的是lambda表达式。

remove(_copy) (_if)

值为__value可以替换成满足__pred条件（函数名增加_if）

remove

在[first,last)中删除掉值为__value的元素（后面元素前移实现覆盖。）

为实现后面元素前移的覆盖，使用的是remove_copy函数

remove_copy

在[first,last)中删除掉值为__value的元素并将结果保存到以__result为首地址的容器中。

unique_copy

将[first,last)，拷贝到[result,result+last−first)中，并将连续相等元素删除后者。

(相邻且满足__binary_pred条件的后者)

unique

对[first,last)中连续相等的元素删除后者(相邻且满足__binary_pred条件的后者)

reverse

翻转[first,last)区间内的元素。（从两端向中间，依次交换所存储的值）

1
2
3
4
5
6
7
8
9
10
11
template <class _BidirectionalIter>
inline void reverse(_BidirectionalIter __first, _BidirectionalIter __last) {
    __reverse(__first, __last, __ITERATOR_CATEGORY(__first));
}

template <class _RandomAccessIter>
void __reverse(_RandomAccessIter __first, _RandomAccessIter __last,
               random_access_iterator_tag) {
    while (__first < __last)
        iter_swap(__first++, --__last);
}

reverse_copy

与先reverse后拷贝实现上有些差别

逆序读取[first,last)区间的值，并写入[result,result+last−first)中

rotate

将[first,last)中的元素以middle断开。先存放[middle,last)再存放[first,middle)。返回，开始时first指向的元素现在的位置。（底层实现上疯狂转轮，看不懂）

rotate_copy

与先rotate后拷贝实现上有些差别

先调用copy(__middle, __last, __result)将[middle,last)的元素存放在以result开始的空间，然后利用copy返回值iter（result开始的数组下一可存放位置）再次调用copy(__first, __middle,iter)将[first,middle)中的元素拷贝到剩余部分。

下述扰乱函数 可加入一个生成随机数的仿函数__rand

random_shuffle

将[first,last)中的元素随机扰乱。（随机洗牌）有(last−first)!种可能。

random_sample_n

将[first,last)中的min(last−first,n)个元素随机的复制到[out,out+n)中。（原数组中每个位置的元素仅能出现一次。）

random_sample

将[first,last)中的min(last−first,olast−ofirst)个元素随机的复制到[olast,ofirst)中。（原数组中每个位置的元素仅能出现一次。）

以n=olast−ofirst 为参数调用random_sample_n

partition

以__pred为规则对[first,last)中的元素进行分组（不保证顺序）满足条件的移动至前半部分。

stable_partition

同样执行partition相关功能，但保证各自分组内元素的相对顺序。

sort

对[first,last)进行升序排序。所使用的底层排序算法为插入排序、堆排序（调用partial_sort函数，底层堆排序）。

值相同的元素再排序后，不保证其相对位置。

stable_sort

对[first,last)进行升序排序。底层排序算法 归并排序。值相同会保证相对位置。

partial_sort

在[first,last)中选出middle - first个最小元素存放在[first,middle)中。

partial_sort_copy

在[first,last)中选出rfirst−rlast个最小元素，存放在[rfirst,rlast)中

nth_element

在[first,last)中找到第n小的元素，并将其移动到第n个位置（first+n−1）

lower_bound

在[first,last)中寻找第一个不小于val的元素。（__comp重载比较规则）

upper_bound

在[first,last)中寻找第一个大于val的元素。（__comp重载比较规则）

equal_range

在[first,last)中寻找等于val的所有元素。（__comp重载比较规则）

在[first,last)中二分查找是否存在元素val

merge

将[first1,last1)与[first2,last2)归并排序后存在[result,result+last1−first1+last2−first2)中

需要注意[first1,last1)与[first2,last2)均为升序。

inplace_merge

同样是归并排序。所不同的是该函数是在一个数组中间选定一个中间值，分成前后两个子数组，两个子数组进行归并排序，最终结果存在原数组中。由于涉及到元素换位置问题，故和merge有些出入。

[first,middle)和[middle,last)进行排序。

includes

判断[first2,last2)是否存在于[first1,last1)中，返回T/F

set_union

实现两个有序集合[first1,last1)和[first2,last2)的并集操作，并将结果（仍有序）保存在以result开始的数组中。

α∪β

与merge不同点在于，set_union遇到相同元素会去重。

set_intersection

求两个集合[first1,last1)和[first2,last2)中相同的元素（或comp(1,2)与comp(2,1)均不满足的）。并将结果（仍有序）保存在以result开始的数组中。

α∩β

set_difference

求在[first1,last1)不在[first2,last2)中的元素。并将结果（仍有序）保存在以result开始的数组中。

α−β

set_symmetric_difference

[first1,last1)与[first2,last2)不重复的元素。

α∪β−α∩β

max_element

返回[first,last)中元素值最大的元素的迭代器（重定义比较规则comp）

min_element

返回[first,last)中元素值最小的元素的迭代器（重定义比较规则comp）

next_permutation

由[first,last)中所有元素组成的排列中，按照从小到大排序后，当前的下一个排列。

prev_permutation

由[first,last)中所有元素组成的排列中，按照从小到大排序后，当前的上一个排列。

find_first_of

寻找[first2,last2)中的（任意）字符在[first1,last1)中出现最早的位置。返回该位置的下一位置。（或[first2,last2)）中满足__comp条件的元素。

[first1,last1)中每读取一个元素便与[first2,last2)中所有元素比对一次。

find_end

在[first1,last1)中寻找最后一个与[first2,last2)相等（或满足__predicate条件）的子数组，返回首个元素的位置。

is_sorted

[first,last)是否有序(或 任意相邻元素满足__comp关系)

-------------感谢阅读有缘再见-------------