特定的数据结构 往往是为了实现/解决 特定的算法

查找 
    二叉查找树 
    RB-tree
    hashTable
    
堆排序 
    max-heap / min-heap

STL 算法共性: 都作用在 由迭代器 [first, last) 所标示的区间上

mutable: 算法运算过程会 更改 区间内元素

0 算法概述

0.1 质变(mutable) 算法

copy 
fill 

swap 
replace 
remove 

sort 

partition (分割)

permutation(排列组合)

random shuffling(随机重排)

0.2 非...

find 

search: 匹配查找子序列 

count 

for_each 

比较 
    equal
    mismatch 
    
取极值 
    max 
    min 

Note: 
    for_each 仿函数可能会改变 区间元素
    
    #include <vector>
    #include <algorithm>

    template <class T>
    struct plus2
    {
        void operator()(T& x) const
        {
            x += 2;
        }
    };

    int main()
    {
        std::vector<int> vec{ 1, 2 };
        for_each(vec.begin(), vec.end(), plus2<int>() );
    }

0.3 共性

(1) STL 算法声明其所需的 最低程度的迭代器类型

不特别说明, 最低程度的迭代器类型 为 inputIter

Note: outputIter 与 inputIter 无继承关系 => 相互 arg 传到 para 则运行时报错

Note: 不特别说明

(2) 某类算法 有 2个版本: 缺省 functor 参数 / 带 ...

version1:   缺省..., 默认为 equality, 即 == 

version2:   带..., 提供 `用户 1/2元操作符`

有点同时用函数名 `不带/带 _if` 区分

(3) 质变算法 通常有2个版本: 改操作对象 本身 / 本身的 copy -> / _copy()

sort() 无 _copy() 版本

(4) 算法的2种上层头文件

<numeric>
    所有数值算法 
    
<algorithm>
    其他算法 

0.4 算法的泛化

让算法能处理未知 数据结构(数组 / vector / list / ...)

2种泛化 
    
    [1] `序列区间的泛化: 用迭代器区间 [first, last)` 
    
    [2] `操作元素型别的泛化: T` 
    
    // 如 
    template<class InputIterator, class T>
        InputIterator 
    find (InputIterator first, InputIterator last, const T& val)
    {
        while (first != last) 
        {
            if (*first == val) 
                return first;
            ++first;
        }
        return last;
    }

1 数值算法 <numeric>

(1) accumulate(first, last, init)

将 [first,last) 上每个元素 "累积"( version1: 累加 / version2: 按2元操作符 init = binary_op(init,*first) 更新 init ) 到初值 init

template <class InputIterator, class T>
    T 
accumulate (InputIterator first, InputIterator last, T init)
{
    while (first!=last) 
    {
        init = init + *first;  // ver2: init = binary_op(init, *first) 
        ++first;
    }
    return init;
}

template <class InputIterator, class T, class BinaryOperation>   
    T 
accumulate (InputIterator first, InputIterator last, T init, BinaryOperation binary_op);

(2) adjacent_difference(first, last, resultOutputIterFirst, binaryOp)

存第1元素(作参考), 然后存 后继元素之 差值/二元运算值 (差分编码) -> 可重建原区间内容

与 partial_sum 互逆

[1, 2, 3] -> adjacent_difference(...) -> [1, 1, 1] -> partial_sum(...) -> [1, 2, 3]

template <class InputIterator, class OutputIterator>
    OutputIterator 
adjacent_difference (InputIterator first, InputIterator last,
                     OutputIterator result)
{
    if (first!=last) 
    {
        typename iterator_traits<InputIterator>::value_type val, prev;
        
        // [1]
        *result = prev = *first;
        
        while (++first!=last) 
        {
            val = *first;
            *++result = val - prev;  // [2] version2: *++result = binary_op(val,prev)
            prev = val;
        }
        ++result;
    }
    return result;
}

std::adjacent_difference (vec.begin(), vec.end(), resultVec.begin(), std::multiplies<int>() );

(3) partial_sum(first, last, resultOutputIterFirst, binaryOp)

template <class InputIterator, class OutputIterator>
    OutputIterator 
partial_sum (InputIterator first, InputIterator last,
             OutputIterator result)
{
    if (first!=last) 
    {
        typename iterator_traits<InputIterator>::value_type val = *first;
        
        *result = val;
        
        while (++first!=last) 
        {
            val = val + *first;   // version2: val = binary_op(val, *first)
            *++result = val;
        }
        ++result;
    }
    return result;
}

(4) iota(forwardFirst, forwardLast, value)

设定区间元素值 = 从 value 开始, 逐个递增(++)

(5) inner_product