<algorithm>

STL 算法的操作参数可以用函数对象, 也可以用函数指针: (模板)函数实参推断可以推断出操作实参的类型

不用记算法有没有 _if 版本, 代码测一下即可, 若有, 把特定元素位置参数换成条件pred即可

迭代器名称

(1) 含 Reslut 指 输出区间 正向 起始位置

(2) 不带迭代器类型标识: 指 inputIterator

1 不改变序列的操作

(1) for_each(first, Last, f)

应用函数(f)到 区间内每个元素

`返回值被忽略`

template<class InputIterator, class Function>
    Function 
for_each(InputIterator first, InputIterator last, Function f)
{
    while (first != last) 
    {
        f(*first);
        ++first;
    }
    return f;      // or, since C++11: return move(f);
}

Note: for_each 的 f 最好不要改 区间元素, 要改则应该用 transform

(2) find(first, last, value) / find_if(first, last, unaPred) / find_if_not(...)

找第1个 符合条件(== / if unaPred(*first) ) / 不符合条件 (if !unaPred(*first) ) 的元素 pos

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;
}

template<class InputIterator, class UnaryPredicate>
    InputIterator 
find_if (InputIterator first, InputIterator last, UnaryPredicate uniPred)
    实现仅1处差别
    `if ( uniPred(*first) )` 

find_if_not
    if ( !uniPred(*first) )

find_first_of(first1, last1, forwardFirst2, forwardLast2, pred)

在序列1中 查找 序列2 任一元素 的 首次 出现(==)/满足条件(if pred(*it, *first1) ) 的 pos

2层循环

template<class InputIterator, class ForwardIterator>
    InputIterator 
find_first_of ( InputIterator first1, InputIterator last1,
                ForwardIterator first2, ForwardIterator last2)
{
    while (first1 != last1) 
    {
        for (ForwardIterator it = first2; it != last2; ++it) 
            if (*it == *first1) // version2: if (pred(*it, *first1) )
                return first1;
                
        ++first1;
    }
    return last1;
}

find_end(forwardFirst1, forwardLast1, forwardFirst2, forwardLast2)

在序列1中 查找 整个 序列2 的 最后1次 出现(==)/满足条件(if pred(*it, *first1) ) 的 pos

2层循环, 要 记录 外层循环 上次匹配查找过程 中 序列1的 起始查找位置

template<class ForwardIterator1, class ForwardIterator2>
    ForwardIterator1 
find_end (ForwardIterator1 first1, ForwardIterator1 last1,
          ForwardIterator2 first2, ForwardIterator2 last2)
{
    if (first2 == last2) 
        return last1; 

    ForwardIterator1 startFindPosInSeq1 = last1; // [1] 外层循环 `上次匹配查找过程` 中 序列1的 `起始查找位置`

    while (first1 != last1)  // [2] `序列1 在外层遍历完`
    {
        ForwardIterator1 it1 = first1;
        ForwardIterator2 it2 = first2;
        
        while (*it1 == *it2) // version2: while (pred(*it1,*it2))
        {    
            ++it1; ++it2;
            if (it2 == last2) // [3] 序列2 遍历完 
            { 
                startFindPosInSeq1 = first1; // [4] 本次查找匹配成功 
                break; 
            }
            
            if (it1 == last1) // [5] `序列1 在内层遍历完`
                return startFindPosInSeq1;
        }
        
        ++first1; // [5] 更新 下次查找匹配 的 起始位置
    }
    return startFindPosInSeq1;
}

adjacent_find(forwardFirst, forwardlast)

找第1组 满足条件(== / pred(*first, *next) == true ) 的 相邻元素 pos(前面元素 pos)

template <class ForwardIterator>
    ForwardIterator 
adjacent_find (ForwardIterator first, ForwardIterator last)
{
    if (first != last)
    {
        ForwardIterator next = first; 
        ++next;
        
        while (next != last) 
        {
            if (*first == *next) // version2: if pred(*first, *next)
                return first;
            ++first; ++next;
        }
    }
    return last;
}

(3) count(first, last, value) / count_if(first, last, unaPred)

数 满足条件(== / pred... ) 的 元素个数

template <class InputIterator, class T>
    typename iterator_traits<InputIterator>::difference_type
count (InputIterator first, InputIterator last, const T& val)
{
    typename iterator_traits<InputIterator>::difference_type n = 0;
    while (first!=last) 
    {
        if (*first == val) 
            ++n;
        ++first;
    }
    return n;
}

count_if
    uniPred(*first) 

(4) search(forward1First, forward1Last, forward2First, forward2Last)

在 seq1 中匹配查找 子序列 seq2 出现的 pos, 没找到, 返回 last1

    template<class ForwardIterator1, class ForwardIterator2>
        ForwardIterator1 
    search ( ForwardIterator1 first1, ForwardIterator1 last1,
             ForwardIterator2 first2, ForwardIterator2 last2)
    {
        if (first2==last2) 
            return first1;  // specified in C++11

        while (first1! = last1)   // [1] n(未知)次遍历
        {
            ForwardIterator1 it1 = first1;
            ForwardIterator2 it2 = first2;
            
            while (*it1 == *it2)  // [2] ver2: while (pred(*it1, *it2) )
            {    
                ++it1;            // [3] 双指针联动
                ++it2;
                if (it2 == last2) // [4] 若子序列 seq2 走完
                    return first1;
                    
                if (it1 == last1) // [5] 若母序列 seq1 走完
                    return last1;
            }
            ++first1;             // [4] 母序列 `seq1 下一次匹配查找 起始位置 更新` (子序列 ... 总是为 起始位置)
        }
        return last1;
    }

search_n(forwardFirst, forwardLast, count, value[, binPred] ) // == / pred(*iter, value)

匹配查找 连续 count 个符合条件之元素的 子序列, 返回子序列 起始迭代器

Note: 外循环内本次匹配失败时, 为提高效率, 下次匹配查找, 直接从当前遍历位置开始, 因为 上次匹配查找 走过的 最多 count 个 elem 其后必然不会出现符合条件的能连续的元素 => 不必从上次匹配查找过程的 下一位置开始

    template<class ForwardIterator, class Size, class T>
        ForwardIterator 
    search_n (ForwardIterator first, ForwardIterator last,
              Size count, const T& val) // version1

    // 2层循环
    外循环
        先 find() 本次匹配查找过程 value 第1次符合条件 pos
        
        leftCount = count - 1
        
        内循环: 最多走 leftCount 步
        
        if 找到剩余leftCount 个 符合条件之元素
            匹配成功 
        else // 本次匹配失败
            更新 下次匹配查找 的起始位置
    匹配失败        
    
    if(count <= 0)
        return last; // 匹配失败
    else
    {
        first = find(fist, last, value); // (1)
        
        while(first != last)             // (2) `Note: 若 本次匹配失败, 则 更新下次匹配查找 的起始位置` 
        {
            Size countLeft = count - 1;
            ForwardIterator cur = first;
            ++cur;
            
            // (3) 3个条件: 区间没遍历完 / 剩余匹配数 ！= 0 / 元素符合条件
            while(cur != last && countLeft != 0 && *cur == value) 
            {
                ++cur;
                --countLeft;
            }
            
            if(countLeft == 0) // [1] 匹配成功
                return first;
            else               // [2] Note: 本次匹配失败, 为提高效率, `下次匹配查找, 直接从当前遍历位置开始`, 
                first = find(cur, last, value); // 因为 `本次匹配查找 走过的 最多 count 个 elem 其后必然不会出现符合条件的能连续的元素` => `不必从本次匹配查找过程的 下一位置开始`
        }
        return last; // (4) 匹配失败
    }

(5) mismatch(first1, last1, first2)

找2个序列 第1个不匹配 pos, 返回1对(pair)迭代器, 分别指向2序列中 不匹配 pos

Note: 要求 序列2长度 >= 序列1长度, 否则, undefined behavior

template <class InputIterator1, class InputIterator2>
    pair<InputIterator1, InputIterator2>
mismatch (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2 )
{
    while ( first1 != last1 && *first1 == *first2 )  // version2: pred(*first1,*first2)
    { 
        ++first1; 
        ++first2; 
    }
    return std::make_pair(first1,first2);
}

(6) is_permutation(first1, last1, first2)

permutation: 排列

匹配查找 seq1 是否为 seq2 的1个 子排列(元素全匹配, 顺序可不同)

Note: 要求 seq2Len >= seq1Len, 否则, undefined behavior

template <class InputIterator1, class InputIterator2>
    bool
is_permutation(InputIterator1 first1, InputIterator1 last1,
              InputIterator2 first2)
{
    // (1) `mismatch 更新2个区间 起始查找位置` 
    auto iterPair = std::mismatch(first1, last1, first2);
    first1 = iterPair.first;
    first2 = iterPair.second;

    // (2) 若 seq1 先走完, 则 `匹配成功` 
    if (first1 == last1)
        return true;

    // (3) last2 归位 
    InputIterator2 last2 = first2;
    std::advance(last2, std::distance(first1, last1));

    // (4) 遍历 seq1剩余区间, 
    for (InputIterator1 cur1 = first1; cur1!= last1; ++cur1)
    {
        // [1] `当前遍历位置上元素` 在剩余区间 `首次出现` 时
        if (std::find(first1, cur1, *cur1) == cur1)
        {
            // [2] count seq2 中 *cur1 个数, 若 == 0 或 与 seq1 中 *cur 个数不等, 则 `匹配失败` 
            auto n = std::count(first2, last2, *cur1);

            if (n == 0 || std::count(cur1, last1, *cur1) != n)
                return false;
        }
        // else( `非首次出现, 则 略过, 继续向后遍历` )
    }

    // (2) seq1 先走完 => `匹配成功` 
    return true;
}

例

    // (1)
    struct myClass 
    {           
        void operator() (int i) 
        {
            std::cout << ' ' << i;
        }
    } myObj;
    for_each (vec.begin(), vec.end(), myObj);
    
    // (2)
    auto it = find (vec.begin(), vec.end(), 5);
    if (it != vec.end() )
        std::cout << "found: " << *it << '\n';
        
    bool isOdd (int i) { return i % 2 == 1; }
    auto it = std::find_if (vec.begin(), vec.end(), IsOdd);
    
    // (3)
    std::count_if (vec.begin(), vec.end(), IsOdd);
    
    // (4) 
    // vec = [1, 2, 3, 4, 5, 6], targetArr = [4, 5, 6]
    auto it = std::search (vec.begin(), vec.end(), targetArr, targetArr + 3);
    
    // (5)
    for (int i = 0; i < 3; i++) 
        vec.push_back (i*10); // vec: 10 20 30
    int arr[] = {10,20,80};   // arr: 10 20 80, Note 若 arr = [10, 20] => 结果 undefined behavior
    auto p = std::mismatch (vec.begin(), vec.end(), arr);
    std::cout << *p.first << ", " << *p.second << '\n';
    
    std::cout << std::is_permutation (vec.begin(), vec.end(), arr);

2 改变序列的操作

(1) copy

copy(first, last, outputIterResult)

将区间 [first, last) 所有元素 逐个 复制 到 outputIterFirst 开始的区间

返回 目标区间尾 迭代器

复制操作 无非用 copy ctor 或 copy assignment, copy() 算法用的是 后者

Note: src/dst 区间重叠 & 向后 copy 时, 发生覆盖, 若 srcFirst 距 dstFirst 为 d 个元素 => src 区间以 d 个元素重复

      first     last 
        |       }
        |       |
    1   2   3   4   5   6   7
        |           2|\ 3   4
        | _ _ _ _ _  | 覆盖
         copy      | |
                  \| |
    1   2   3   4   2   3   4

copy() 提高效率的方法: 1个 中间 functor 隔开 2层 特化

(1) 第1层特化 直接用 memmove

(2) 第2层泛化和特化中均用 标签分发 分出普通版和 高效版本 -> 共 3种版本

[1] 每次迭代用 迭代器是否相等(first != last) 决定循环是否继续

[2] ... 用 n = last - first 是否 > 0 ...

[3] memmove

                                                                                                        for(; first != last; ...)
                                                                                                     /      *result = *first;
                                                                                                    /
                                                                                                   / input_iterator_tag 
                                                    泛化      _copy(, iteratorCategory(fitst) )
                                                    <InputIter,              标签分发              \ random_access_iterator_tag
                                                    OutputIter>                                     \ <RAIter, RAIter>
                                                         /                                           \
                                                        /                                                _copy_d(, differencePtrType(first) )
                                                       /                                                    |
                                                      /                                                     |/
                                                     /                                                      for(DifferenceType n = last - first; n > 0; --n, ...)
                                                    /                                                       |\  *result = *first;
            泛化  _copy_dispatch<InputIter,      /                                                        |
                                  OutputIter>()(.)                                                      _copy_d(, (ptrdiff_t*)0 )
        <InputIter,            functorTempObj      |                                                 / 
        OutputIter>                                |                                                / _false_type   
       /                                           | - 特化1  _copy_t(, _type_traits<T>::has_trivial operator= 的临时对象 ) 
      /                                            |  <T*, T*>     |                    标签分发    \ 
copy(.)                                            |               | 实现思路相同                  \ _true_type 
      \                                            | - 特化2  _copy_t()                               memmove 
       \                                              <const T*, T*>                                        
            特化      memmove                                                                             
        (const char*, 
         const char*)

    template<class InputIterator, class OutputIterator>
        OutputIterator 
    copy (InputIterator first, InputIterator last, OutputIterator result)
    {
        while (first != last) 
        {
            *result = *first;
            
            ++result; 
            ++first;
        }
        return result;
    }

copy_backward(biFirst, biLast, biResultLast)

返回 目标区间首 迭代器

template<class BidirectionalIterator1, class BidirectionalIterator2>
    BidirectionalIterator2 
copy_backward ( BidirectionalIterator1 first,
                BidirectionalIterator1 last,
                BidirectionalIterator2 resultLast )
{
    while (last != first) 
        *--resultLast = *--last;
    return resultLast;
}

copy_n(first, n, outputIterResult)

template<class InputIterator, class Size, class OutputIterator>
    OutputIterator 
copy_n (InputIterator first, Size n, OutputIterator result)

copy_if(first, last, outputIterResult, unaPred)

template <class InputIterator, class OutputIterator, class UnaryPredicate>
    OutputIterator 
copy_if (InputIterator first, InputIterator last,
         OutputIterator result, UnaryPredicate pred)
                      
    if ( pred(*first) ) 
    {
        *result = *first;

        ++result;
    }

(2) move

move(first, last, outputIterReslut)

与 copy 区别仅在于 copy 语义换为 move 语义 => 用于 handle 容器, 如 std::vector<std::string>

    template<class InputIterator, class OutputIterator>
        OutputIterator 
    move (InputIterator first, InputIterator last, OutputIterator result)
    {
        while (first!=last) 
        {
            *result = std::move(*first); // move 语义
            
            ++result; 
            ++first;
        }
        return result;
    }

move_backward

(3) fill

fill(forwardFirst, forwardLast, val)

将区间 [first, last) 所有元素 赋值 为 val

template <class ForwardIterator, class T>
    void 
fill (ForwardIterator first, ForwardIterator last, const T& val)
{
    while (first != last) 
    {
        *first = val;
        ++first;
    }
}

fill_n(outputFirst, n, val)

前 n 个元素

template <class OutputIterator, class Size, class T>
    OutputIterator 
fill_n (OutputIterator first, Size n, const T& val)

(4) remove

remove(forwardFirst, forwardLast, value) 移除但不删除

将 不满足条件( !(*first == value) ) 的 elem 前移 <=> 满足条件(*first == value) 的 elem 后移/移除

返回 不满足条件的 last 位置

value = 1
                      |
    1, 2, 3, 4, 5, 1, |  1, 6, 6
    |\                |  |
    | 覆盖            |  |    残留
    |                 |  |/
    2, 3, 4, 5, 6, 6, |  1, 6, 6
                      |

template <class ForwardIterator, class T>
    ForwardIterator 
remove (ForwardIterator first, ForwardIterator last, const T& val)
{
    ForwardIterator lastPosNotSatisfiedCond = first;
    while (first != last) 
    {
        if ( !(*first == val) )     // (1) 当前遍历元素 不满足条件(!= 指定值) 时, 前移到 不满足条件的第1个位置
        {
            if (lastPosNotSatisfiedCond != first)   
                *lastPosNotSatisfiedCond = *first;
            ++lastPosNotSatisfiedCond;
        }
        ++first;    // (2) `更新 遍历指针`
    }
    return lastPosNotSatisfiedCond;
}

remove_if(forwardFirst, forwardLast, unaPred)

    template <class ForwardIterator, class UnaryPredicate>
        ForwardIterator 
    remove_if (ForwardIterator first, ForwardIterator last,
                UnaryPredicate pred)
                                 
        if ( !uniPred(*first) )

remove_copy(first, last, outputResult, val)

copy 1份到新区间去 remove => 满足条件的(要移除的) 不 copy 到新区间

remove 中 lastPosNotSatisfiedCond 换为 dst 区间 起始迭代器, 去掉 if (lastPosNotSatisfiedCond != first) 条件

template <class InputIterator, class OutputIterator, class T>
        OutputIterator 
    remove_copy (InputIterator first, InputIterator last,
                 OutputIterator result, const T& val)
    {
        while (first != last) 
        {
            if ( !(*first == val) ) 
            {
                *result = *first;
                ++result;
            }
            ++first;
        }
        return result;
    }

remove_copy_if

(5) unique: 类似 remove, 移除但不删除

unique (forwardFirst, forwardLast[, binPred])

移除 相邻重复元素 中第1个之外的元素

重复: == / 满足某条件 pred(*dupFirstPos, *dupOtherPos)

思路: 双指针, 遍历指针 每步都前移, 结果指针在 不满足条件时才前移

Note

[1] 想移除 所有(含不相邻的)重复元素: 先排序, 使所有重复元素相邻; 再 unique()

[2] 尾部 残留元素 可用 erase() 算法去除

[3] 稳定: 保留下来的元素, 原始相对次序不变

    template <class ForwardIterator>
        ForwardIterator 
    unique (ForwardIterator first, ForwardIterator last)
    {
        if (first == last) 
            return last;
        
        first = adjacent_find(first, last); // 找到相邻重复元素的起点
        
        ForwardIterator result = first;
        while (++first != last) // 遍历指针, 结果指针 
        {
            if ( !(*result == *first) )  // ver2: if ( !pred(*result, *first) )
              *(++result) = *first;
        }
        return ++result;
    }

unique_copy(first, last, outputResult)

    template <class InputIterator, class OutputIterator>
        OutputIterator 
    unique_copy (InputIterator first, InputIterator last,
                 OutputIterator result)

(6) transform

transform(inputFirst, inputLast, outputResult, uniOp)

对输入区间上每个元素 用 1元操作, 结果写到 outputReslut 开始的输出区间

transform(inputFirst1, inputLast1, inputFirst2, outputReslut, binOp)

// version 
template <class InputIterator, class OutputIterator, class UnaryOperator>
    OutputIterator 
transform (InputIterator first1, InputIterator last1,
           OutputIterator result, UnaryOperator op)
{
    while (first1 != last1) 
    {
        *result = op(*first1);  // or: *result=binary_op(*first1,*first2++);
        ++result; 
        ++first1;
    }
    return result;
}   

// eg
int op_increase (int i) { return ++i; }

std::vector<int> foo;
std::vector<int> bar;

for (int i = 1; i < 3; i++)
    foo.push_back (i*10);    // foo: 10 20 30

bar.resize(foo.size() );   

std::transform (foo.begin(), foo.end(), bar.begin(), op_increase);  // bar: 11 21 31

(7) swap

swap(a, b)

交换 a, b 的值

要求: a/b 必须为 左值, a/b 可以为数组

    template <class T> 
        void 
    swap (T& a, T& b)
    {
        T tmp(std::move(a) ); 
        a = std::move(b); 
        b = std::move(tmp);
    }

    // 数组类型的引用
    template <class T, size_t N> 
        void 
    swap (T (&a)[N], T (&b)[N])
    {
        for (size_t i = 0; i < N; ++i) 
            swap (a[i], b[i]);
    }

swap_ranges(forwardFirst1, forwardLast1, forwardFirst2)

交换2个 区间 中每对元素的值, 循环 + swap (*forwardFirst1, *forwardFirst2)

iter_swap(forwardIter1, forwardIter2)

交换2个 迭代器 所指对象的值

    template <class ForwardIterator1, class ForwardIterator2>
        void 
    iter_swap (ForwardIterator1 forwardIter1, ForwardIterator2 forwardIter2)
    {
      swap (*forwardIter1, *forwardIter2);
    }

(8) replace

replace(forwardFirst, forwardLast, oldValue, newValue)

将区间 [forwardFirst, forwardLast) 中所有等于 oldValue 的 元素 替换为 新值 newValue

    template <class ForwardIterator, class T>
      void 
    replace (ForwardIterator first, ForwardIterator last, 
             const T& old_value, const T& new_value)
    {
        while (first != last) 
        {
            if (*first == old_value) 
                *first = new_value;

            ++first;
        }
    }

replace_if(forwardFirst, forwardLast, unaPred, new_value)

replace_copy(first, last, outputResult, oldValue, newValue)

replace_copy_if(first, last, outputResult, unaPred, newValue)

(9) reverse

reverse(binFirst, binLast)

反转 区间中 元素顺序: 循环 + 双指针 (first, --last) 联动 + iter_swap

    template <class BidirectionalIterator>
        void 
    reverse (BidirectionalIterator first, BidirectionalIterator last)
    {
        while (first != last && first != --last) 
        {
            std::iter_swap (first, last);
            ++first;
        }
    }

reverse_copy(binFirst, binLast, outResult)

(10) rotate

rotate(forwardFirst, forwardMid, forwardLast)

将 [forwardFirst, forwardMid) 与 [forwardMid, forwardLast) 内元素对调

Note: 看似和 swap_ranges() 相近, 实则不同, 前/后者 可以/只能 对调 长度不同/相同的区间

据迭代器类型 分3种实现

[1] 前向

前/后段均设 遍历指针(first / back) 和 哨兵指针(mid / last)

遍历双指针联动

前半段结束, 同时后半段结束
    对调完成, return 

`前/后 半段先结束(但不同时结束)`
    则 `更新 mid = back / back = mid`

    template <class ForwardIterator>
        void 
    rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last)
    {
        for(ForwardIterator back = middle; ; )
        {
            iter_swap(first, back);
            
            ++first;
            ++back；
            
            if(first == middle) // 前半段先结束
            {
                if(back == last) // 同时后半段结束
                    return;
                mid = back;
            }
            else if(back == last) // 后半段先结束
            {
                back = mid;
            }
        }
    }          

[2] 双向

    前段区间 reverse()
    后段区间 reverse()
    整体   reverse()

[3] 随机: 特殊算法复杂

    first   mid       last
    |       |           |
    |/      |/          |/
    A   B   C   D   E   

    C   D   E   A   B
    

rotate_copy(forwardFirst, forwardMid, forwardLast, outputReslut)

    template <class ForwardIterator, class OutputIterator>
        OutputIterator 
    rotate_copy (ForwardIterator first, ForwardIterator middle,
                 ForwardIterator last, OutputIterator result)
    {
        result = std::copy (middle, last, result);
        return std::copy (first, middle, result);
    }

(11) random_shuffle(raFirst, raLast)

随机重排

3 Partitions 重排

(1) partition(binFirst, binLast, unaPred)

将 [first, last) 中元素 重排, 满足/不满足 条件( pred() == true/false ) 的放 前/后段

返回 满足条件的最后1个元素的 next 位置

思路: 双指针(first / last), 2层循环, 内层2个循环

[1] 循环1: first 从前往后走, 遇到 不满足条件的就停下来

[2] 后指针 last 移到上1个有效位置

[3] 循环2: last 从后往前走, 遇到 满足条件的就停下来

[4] 交换 first, last 所指元素

[5] 更新 前指针 first

Note: 不稳定 ( 原始相对位置 可能变)

    // eg: 满足条件 == elem 为 偶数 

        seq =   0   1   2   3   4   5   6   7   8
                |\                                  |\
                |                                   |
               first                               last
                    
        stop:      first                       last 
        swap:   0   8   2   3   4   5   6   7   1
     first更新:         first         
     
        stop:              first      last 
        swap:   0   8   2   6   4   5   3   7   1
     first更新:                 first
     
                                  last(移到前先检测是否双指针相遇)
        stop:                     first(返回)    
        swap:   0   8   2   6   4   5   3   7   1             

    template <class BidirectionalIterator, class UnaryPredicate>
        BidirectionalIterator 
    partition (BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred)
    {
        while(true)
        {
            while(true) // [1]
            {
                if(first == last) // Note: 移到前先检测是否双指针相遇, 相遇则终止
                    return first;
                else if(pred(*first) )
                    ++first;
                else
                    break;
                    
            }
            
            --last; // [2] 因后面要用 pred(*(last)
            
            while(true) // [3]
            {
                if(first == last)
                    return first;
                else if(! pred(*(last) )
                    --last;
                else
                    break;
            }
            
            iter_swap(first, last); // [4]
            
            ++first; // [5]
        }
    }

stable_partition(binFirst, binLast, unaPred)

Note: 保留元素的 原始相对位置 不变

4 排序 sort: 严格弱序比较

[1] 小于比较(LessThan comparable)

5种比较 小于/大于/小于等于/大于等于/等于

等价表示为 1个 基础比较: 小于比较

    大于      x > y   <=>   y < x

    大于等于    x >= y  <=>  !(x < y)

    小于等于    x <= y  <=>  !(y < x)

    等于      !(x < y) && !(y < x)

[2] 严格弱序(strict weak ordering): 定义了 等价 (的条件)

两个元素中 任一个 都不小于/按指定比较规则去比较 都不满足规则的含义 另一个

    !(x < y) && !(y < x) 
    
    广义
        !cmp(x, y) && !cmp(y, x)  

[3] 严格弱序比较 (strick weakly comparable)

满足 小于比较 和 严格弱序 2个条件

反例：cmp 定义为 小于等于

    若 x == y, 则 `按等价定义 !cmp(x, y) && !cmp(y, x)`
    
        => !true && !true => false
        
        `相等, 推导出来的结果却是 不等 => 错误`

(1) sort(raFirst, raLast[, comp])

版本1: 升序 <=> comp == operator <

底层 快排

=> 不稳定 = 不保持原始相对位置

时间复杂度O(nlog(n)).

    bool cmp (int i, int j) { return (i < j); }

    struct Cmp 
    {
        bool operator() (int i, int j) { return (i < j);}
    } cmp;
    
    std::sort (vec.begin(), vec.end(), cmp);  

(2) stable_sort(raFirst, raLast[, comp])

保持原始相对位置

(3) partial_sort(raFirst, raMid, raLast[, comp])

部分排序 [raFirst, raMid) 内排序, 其余无序

(4) nth_element(raFirst, raNth, raLast[, comp])

新区间 nth(第 n+1 个) 元素 与 sort 完整排序结果 nth 元素 值相同, nth 左、右子区间之间 整体有序(< / comp) 但各自内部无序

    std::vector<int> vec{2, 3, 2, 5, 1, 4, 6, 7, 9, 8};

    std::random_shuffle(vec.begin(), vec.end());                // 1 5 7 9 2 4 2 3 6 8

    std::nth_element(vec.begin(), vec.begin() + 3, vec.end()); //  2 1 2 3 4 5 9 7 6 8

5 二分查找

a, b 等价: (!(a < b) && !(b < a)) / (!comp(a, b) && !comp(b, a) )

(1) lower_bound/upper_bound(forwardFirst, forwardLast, value[, comp])

含义: 不破坏排序 下, 可插入 value 的 第1个位置 / 最后1个合适位置 => 等价区间的 前闭端/后开端

实现

二分过程 且 first 指针更新 时, 满足条件

    [1] *mid < value / comp(*mid, value), lower_bound
    
    [2] !(value < *mid) / !comp(value < *mid), upper_bound

最终 可插入 value 的 pos(first) 是 等价于 value 的

    [1] `第1个 位置`                !(*first < value) == *first >= value / !comp(*first, value)
        
        若 `value 存在`, 返回的迭代器 将指向 value 的 `位置`
                  不存在,                             `合适(前插含义)位置`
                  
    [2] `最后1个 合适位置`         value < *first                      / comp(value < *first)
        
        若 value 存在, 返回的迭代器 将指向 value 的 `下一位置`
                 不存在,                           合适(前插含义)位置

    template <class ForwardIterator, class T>
        ForwardIterator 
    lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
    {

        iterator_traits<ForwardIterator>::difference_type len, half;
        
        // (1)
        len = std::distance(first, last);
        
        ForwardIterator mid;
        
        while(len > 0)
        {
            half = len >> 1;
            
            // (2) 取/更新 中间指针
            mid = first;
            std::anvance(mid, half);
            
            if(*mid < value) // comp(*mid, value), [1] 中间位置处比较, 满足条件 
            {
                first = mid; // [2] 更新 遍历指针
                ++first;
                
                len = len - half - 1; // [3] 更新 查找区间长度
            }
            else 
                len = half;
        }
        
        // (3)
        return first;
    }

    template <class ForwardIterator, class T>
        ForwardIterator 
    upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
        
         仅1处不同 if( !(value < *mid ) )

(2) equal_range(forwardFirst, forwardLast, value[, comp])

思路: 先用 lower_bound(first, last, value[, comp]) 找出 等价区间 的 前闭端 firstPos, 再用 upper_bound(firstPos, last, value[, comp]) 找出 等价区间 的 后开端 lastPos

返回 pair(firstPos, lastPos)

    template <class ForwardIterator, class T>
        pair<ForwardIterator,ForwardIterator>
    equal_range (ForwardIterator first, ForwardIterator last, const T& val)
    {
          ForwardIterator firstPos = std::lower_bound (first, last, val);
          
          return std::make_pair ( firstPos, std::upper_bound(firstPos, last, val) );
    }

(3) binary_search(forwardFirst, forwardLast, value[, comp])

查找 [first, last) 是否有 等价于 value 的元素, 返回 true/false

思路: 用 lower_bound 找出 "假设 vlaue 存在的话, 应该出现的位置", 再 比较 该位置上是否为 期望 等价的目标, 并返回 true/false

实现: lower_bound + 是否找到 && !(value < *first)

    template <class ForwardIterator, class T>
        bool 
    binary_search (ForwardIterator first, ForwardIterator last, const T& value)
    {
        first = std::lower_bound(first, last, value); // => !(*first < value)
        
        return (first != last && !(value < *first) );
    }

6 合并: 基于 已排序区间

(1) merge(first1, last1, first2, last2[, comp])

合并2个有序区间为1个新有序区间

稳定

    template <class InputIterator1, class InputIterator2, class OutputIterator>
        OutputIterator 
    merge (InputIterator1 first1, InputIterator1 last1,
           InputIterator2 first2, InputIterator2 last2,
           OutputIterator result)
    {
        // (1) 2个序列都没走完
        while(first1 != last1 && first2 != last2)
        {
            result++ = *first1 < *first2 ? *first1++ : *first2++;
        }
        
        // (2) 至少1个序列走完 => 至少1个 copy 直接返回 第3参数
        return copy(first2, last2, copy(first1, first1, result) );
    }

(2) inplace_merge(biFIrst, biMid, biLast)

将同一序列中 2段连续的有序序列 [first, middle) 和 [middle, last) 合并为1个有序序列 [first, last)

思路: 用 中间缓冲区

    std::inplace_merge (v.begin(), v.begin() + 5, v.end() );

(3) includes(first1, last1, first2, last2)

测试 [first1, last1) 中是否 包含(含子序列) [first2, last2)

(4) 构造 STL set(集合, 并不是 std::set<.>): 无重复, 排序( < / comp)

set_union(first1, last1, first2, last2, outputReslut[, comp])

并集 S1 并 S2

    int first[] = {5,10,15,20,25};
    int second[] = {50,40,30,20,10};
    std::vector<int> v(10);        // 0  0  0  0  0  0  0  0  0  0

    std::sort (first, first+5);     //  5 10 15 20 25
    std::sort (second, second+5);   // 10 20 30 40 50

    std::vector<int>::iterator it = std::set_union (first, first + 5, second, second + 5, v.begin() );
                                               // 5 10 15 20 25 30 40 50  0  0
    v.resize(it-v.begin());                    // 5 10 15 20 25 30 40 50

set_intersection

交集 S1 交 S2

set_difference

差集 S1 - S2: 出现于 S1 但不出现于 S2

set_symmetric_difference

对称差集: (S1 - S2) 并 (S2 - S1)

7 极值

(1) min(a, b[, comp])

    template <class T> 
        const T& 
    min (const T& a, const T& b) 
    {
        return !(b < a) ? a : b;     // !comp(b, a) ? a : b;
    }

max

    template <class T> 
        const T& 
    max (const T& a, const T& b) 
    {
        return (a < b)? b : a;     // comp(a, b)?b:a; 
    }

(2) min_element(forwardFirst, forwardLast[, comp])

返回 区间 [first,last) 中最小元素的迭代器

    ...
    if (*first < *smallest)    // comp(*first, *smallest)
        smallest = first;

max_element

8 其他

(1) lexicographical_compare(first1, last1, first2, last2[, comp])

以 "字典排列方式" 比较 seq1 = [first1, last1) 与 seq2 = [first2, last2)

seq1, seq2 对应元素逐个比较, 直到

[1] seq1 elem 小 -> return true; else, false -> 继续循环

[2] seq1 先走完(seq1 短) -> return true

[3] seq2 先走完, false

[4] seq1, seq2 同时走完(同长度), return fase

    ...
    return first1 == last1 && first2 != last2;
    
    // (first1 == last1) && (first2 != last2) 
    
    // [2] = true && true == true
    
    // [3] = false && false == false 
    
    // [4] = true && false = false 
    
    // [1] = false && true == seq1 没走完 && seq2 没走完 => 1, 但运行到 return 前, 1已经不可能了

(2) bool next_permutation(biFirst, biLast[, comp])

将 区间转换 为 下一个(用 < / comp 决定) 排列组合

没有下一个, 推导出第1个( reverse() 即可 ), 返回 fasle

从前到后, 依次固定1个, 然后 变化 其后部分

    3个字符{a b c}的6种排列组合
    
    abc
    acb
    bac
    bca
    cab
    cba

(3) prev_permutation

    #include <iostream>     
    #include <algorithm>

    int main() 
    {
        int arr[] = { 1, 2, 3 };

        std::sort(arr, arr + 3);
        std::reverse(arr, arr + 3);

        std::cout << arr[0] << ' ' << arr[1] << ' ' << arr[2] << '\n';
        while (std::prev_permutation(arr, arr + 3) )
            std::cout << arr[0] << ' ' << arr[1] << ' ' << arr[2] << '\n';

        std::cout << "After loop: " << arr[0] << ' ' << arr[1] << ' ' << arr[2] << '\n';
    }

    // print
    1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1
    After loop: 1 2 3