一、算法概述

算法主要是由头文件<algorithm><functional><numeric>组成。

• <algorithm>是所有STL头文件中最大的一个,其中常用的功能涉及到比较，交换，查找,遍历，复制，修改，反转，排序，合并等...
• <numeric>体积很小，只包括在几个序列容器上进行的简单运算的模板函数.
• <functional> 定义了一些模板类,用以声明函数对象。

二、常用遍历算法

2.1 for_each 算法 遍历

    遍历算法 遍历容器元素
    @param beg 开始迭代器
    @param end 结束迭代器
    @param _callback  函数回调或者函数对象
    @return 函数对象
    for_each(iterator beg, iterator end, _callback);

struct myPrint
{
public:
    myPrint()
    {
        a = 0;
    }
    void operator()(const int val)
    {
        cout << val << " ";
        a++;
    }

public:
    int a;
};

void test01()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);

   /*
        template <class _InputIterator, class _Function>
        inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
        _Function  for_each(_InputIterator __first, _InputIterator __last, _Function __f)
        {
            for (; __first != __last; ++__first)
                __f(*__first);
            return __f;
        }
   */
    myPrint m = for_each(v.begin(), v.end(), myPrint()); // myPrint() 匿名函数
    cout << endl; // 10 20 30 40 50 
    cout << m.a << endl; // 5
}

2.2 transform算法

    transform算法 将指定容器区间元素搬运到另一容器中
    注意 : transform 不会给目标容器分配内存，所以需要我们提前分配好内存
    @param beg1 源容器开始迭代器
    @param end1 源容器结束迭代器
    @param beg2 目标容器开始迭代器
    @param _callback 回调函数或者函数对象
    @return 返回目标容器迭代器
    transform(iterator beg1, iterator end1, iterator beg2, _callbakc)

// 将指定容器区间元素搬运到另一容器中
struct MyAdd
{
    int operator()(int v1)
    {
        return v1 + 100;
    }
};

void test02()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);

    vector<int> v2;
    v2.resize(v.size()); // 要手动分配空间
    /*
        _OutputIterator transform(_InputIterator __first, _InputIterator __last, _OutputIterator __result, _UnaryOperation __op)
        {
        for (; __first != __last; ++__first, (void) ++__result)
            *__result = __op(*__first);
        return __result;
        }
    */
    transform(v.begin(), v.end(), v2.begin(), MyAdd());
    for_each(v2.begin(), v2.end(), myPrint()); // 110 120 130 140 150
    cout << endl;
}

// 把两个容器的元素处理后放到第三个容器
struct MyAdd2
{
    int operator()(int v1, int v2)
    {
        return v1 + v2;
    }
};
void test03()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);

    vector<int> v2;
    v2.push_back(100);
    v2.push_back(200);
    v2.push_back(300);
    v2.push_back(400);
    v2.push_back(500);
    v2.push_back(600);

    int len = v.size() > v2.size() ? v.size() : v2.size();

    vector<int> v3;
    v3.resize(len);

    /*
        _OutputIterator transform(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2,
                _OutputIterator __result, _BinaryOperation __binary_op)
        {
        for (; __first1 != __last1; ++__first1, (void) ++__first2, ++__result)
            *__result = __binary_op(*__first1, *__first2);
        return __result;
        }
    */
    transform(v.begin(), v.end(), v2.begin(), v3.begin(), MyAdd2());
    for_each(v3.begin(), v3.end(), myPrint()); // 110 220 330 440 550 0 
    cout << endl;
}

三、查找算法

3.1 find算法 查找元素

    find算法 查找元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param value 查找的元素
    @return 返回查找元素的位置
    find(iterator beg, iterator end, value)

3.2 find_if算法 条件查找

    find_if算法 条件查找
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param  callback 回调函数或者谓词(返回bool类型的函数对象)
    @return bool 查找返回true 否则false
    find_if(iterator beg, iterator end, _callback);

// 查找基础类型
struct MyFunc1
{
    bool operator()(int val)
    {
        return val > 30;
    }
};

void test01()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);
    /*
        _InputIterator find(_InputIterator __first, _InputIterator __last, const _Tp& __value_)
        {
        for (; __first != __last; ++__first)
        if (*__first == __value_)
            break;
        return __first;
        }
    */
    vector<int>::iterator it = find(v.begin(), v.end(), 20);  // 20
    if (it == v.end())
    {
        cout << "查找失败" << endl;
    }
    else
    {
        cout << "查找成功"
             << " " << *it << endl;
    }
    /*
        _InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
        {
        for (; __first != __last; ++__first)
            if (__pred(*__first))
                break;
        return __first;
        }

    */

    vector<int>::iterator it1 = find_if(v.begin(), v.end(), MyFunc1()); // MyFunc1()匿名函数对象. // 40
    if (it1 == v.end())
    {
        cout << "查找失败" << endl;
    }
    else
    {
        cout << "查找成功"
             << " " << *it1 << endl;
    }
}

// 查找对象
class Maker
{
public:
    Maker(string name, int age)
    {
        this->name = name;
        this->age = age;
    }
    bool operator==(const Maker &m2) const
    {
        if (this->name == m2.name && this->age == m2.age)
        {
            return true;
        }
        return false;
    }
    bool operator<(const Maker &m2) const
    {
        return this->age < m2.age;
    }

    bool operator>(const Maker &m2) const 
    {
        return this->age > m2.age;
    }

public:
    string name;
    int age;
};

struct MyFindMaker : public binary_function<Maker, Maker, bool>
{
    bool operator()(Maker m, Maker m2) const
    {
        return m.name == m2.name && m.age == m2.age;
    }
};

void test02()
{
    vector<Maker> v;
    v.push_back(Maker("aaa1", 18));
    v.push_back(Maker("aaa2", 19));
    v.push_back(Maker("aaa3", 20));
    v.push_back(Maker("aaa4", 21));
    v.push_back(Maker("aaa5", 22));

    vector<Maker>::iterator it = find(v.begin(), v.end(), Maker("aaa2", 19));

    if (it == v.end())
    {
        cout << "查找失败" << endl;
    }
    else
    {
        cout << "查找成功"
             << " " << (*it).name << " " << (*it).age << endl;
    }

    cout << "-----------------" << endl;

    Maker m = Maker("aaa2", 19);
    it = find_if(v.begin(), v.end(), bind2nd(MyFindMaker(), m));

    if (it == v.end())
    {
        cout << "查找失败" << endl;
    }
    else
    {
        cout << "查找成功"
             << " " << (*it).name << " " << (*it).age << endl;
    }
}

3.3 adjacent_find算法

    adjacent_find算法 查找相邻重复元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param  _callback 回调函数或者谓词(返回bool类型的函数对象)
    @return 返回相邻元素的第一个位置的迭代器
    adjacent_find(iterator beg, iterator end, _callback);

bool MyFunc2(const Maker &m1,const Maker &m2){
    return m1.age == m2.age && m1.name == m2.name;
}

void test03()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(40);
    v.push_back(40);
    v.push_back(50);

    /*
        _ForwardIterator adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
        {
            typedef typename iterator_traits<_ForwardIterator>::value_type __v;
            return _VSTD::adjacent_find(__first, __last, __equal_to<__v>());
        }

        adjacent_find(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred)
        {
            if (__first != __last)
            {
                _ForwardIterator __i = __first;
                while (++__i != __last)
                {
                    if (__pred(*__first, *__i))
                        return __first;
                    __first = __i;
                }
            }
            return __last;
        }

    */

    vector<int>::iterator it = adjacent_find(v.begin(), v.end()); // 成功
    if (it == v.end())
    {
        cout << "查找相邻重复元素失败" << endl;
    }
    else
    {
        cout << "查找相邻重复元素成功" << " " << *it << endl;
    }

    vector<Maker> v2;
    v2.push_back(Maker("aaa1", 18));
    v2.push_back(Maker("aaa2", 19));
    v2.push_back(Maker("aaa3", 20));
    v2.push_back(Maker("aaa4", 20));
    v2.push_back(Maker("aaa3", 20));

    // 查找对象 需要提供operater== 或者谓词
    vector<Maker>::iterator it2 = adjacent_find(v2.begin(), v2.end(),MyFunc2); // 失败
    if (it2 == v2.end())
    {
        cout << "查找相邻重复元素失败" << endl;
    }
    else
    {
        cout << "查找相邻重复元素成功" << " " << it2->name << " " << it2->age << endl;
    }
}

3.4 binary_search算法

    binary_search算法 二分查找法
    注意: 在无序序列中不可用
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param value 查找的元素
    @return bool 查找返回true 否则false

    bool binary_search(iterator beg, iterator end, value);

void test04() {
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);
    v.push_back(60);

    /*
        bool binary_search(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value_)
        {
            return _VSTD::binary_search(__first, __last, __value_,
                                    __less<typename iterator_traits<_ForwardIterator>::value_type, _Tp>());
        }
    */
    // 升序 需要使用less<int>() 做谓词进行二分查找
    bool res1 = binary_search(v.begin(),v.end(),30); // 查找成功
    if(res1){
        cout << "查找成功" << endl;
    }else{
        cout << "查找失败" << endl;
    }

    vector<int> v2;
    v2.push_back(60);
    v2.push_back(50);
    v2.push_back(40);
    v2.push_back(30);
    v2.push_back(20);
    v2.push_back(10);

    // 降序 需要使用greater<int>()做谓词进行二分查找
    bool res2 = binary_search(v2.begin(),v2.end(),40,greater<int>()); // 查找成功
    if(res2){
        cout << "查找成功" << endl;
    }else{
        cout << "查找失败" << endl;
    }

}

bool MyFunc3(const Maker &m1,const Maker &m2)
{
    return m1.age < m2.age; 
}

bool MyFunc4(const Maker &m1,const Maker &m2)
{
    return m1.age > m2.age; 
}
// 二分查找对象
void test05() {

    vector<Maker> vs;
    vs.push_back(Maker("aaa1", 18));
    vs.push_back(Maker("aaa2", 19));
    vs.push_back(Maker("aaa3", 20));
    vs.push_back(Maker("aaa4", 21));
    vs.push_back(Maker("aaa5", 22));
    vs.push_back(Maker("aaa6", 23));

    // 升序 需要重载< 或谓词<
    // bool res1 = binary_search(vs.begin(),vs.end(),Maker("aaa2",19));
    bool res1 = binary_search(vs.begin(),vs.end(),Maker("aaa5",22),MyFunc3);
    if(res1){
        cout << "查找成功" << endl;
    }else{
        cout << "查找失败" << endl;
    }


    vector<Maker> vs2;
    vs2.push_back(Maker("aaa1", 22));
    vs2.push_back(Maker("aaa2", 21));
    vs2.push_back(Maker("aaa3", 20));
    vs2.push_back(Maker("aaa4", 19));
    vs2.push_back(Maker("aaa5", 18));
    vs2.push_back(Maker("aaa6", 17));

    // 降序 需要重载> 或者 提供谓词>
    // bool res2 = binary_search(vs2.begin(),vs2.end(),Maker("aaa4",19),greater<Maker>());
    bool res2 = binary_search(vs2.begin(),vs2.end(),Maker("aaa2",21),MyFunc4);
    if(res2){
        cout << "查找成功" << endl;
    }else{
        cout << "查找失败" << endl;
    }

}

3.5 count算法

    count算法 统计元素出现次数
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param  value 查找的数据
    @return int返回元素个数
    count(iterator beg, iterator end, value);

void test06()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(20);
    v.push_back(40);
    v.push_back(20);
    v.push_back(60);

    int res = count(v.begin(),v.end(),20); // 3
    cout <<"出现的次数: " << res <<endl;
}

3.6 count_if

    count_if 算法 统计元素出现次数
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param  callback 回调函数或者谓词(返回bool类型的函数对象)
    @return int返回元素个数

    count_if(iterator beg, iterator end, _callback);

struct MyFunc5:public binary_function<int, int, bool>
{
    bool operator()(int val1,int val2) const
    {
        return val1 > val2;
    }
};

bool MyFunc6(int val1,int val2){
    return val1 < val2;
}

void test07()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(20);
    v.push_back(40);
    v.push_back(20);
    v.push_back(60);

    int res1 = count_if(v.begin(),v.end(),bind2nd(MyFunc5(),20)); // > 20
    cout <<"出现的次数: " << res1 <<endl; // 2

    int res2 = count_if(v.begin(),v.end(),bind2nd(ptr_fun(MyFunc6),20));// <20
    cout <<"出现的次数: " << res2 <<endl; // 1

    int res3 = count_if(v.begin(),v.end(),not1(bind2nd(MyFunc5(),20))); // <= 20 
    cout <<"出现的次数: " << res3 <<endl; // 4

}

四、排序算法

4.1 merge算法

    merge算法 容器元素合并，并存储到另一容器中
    @param beg1 容器1开始迭代器
    @param end1 容器1结束迭代器
    @param beg2 容器2开始迭代器
    @param end2 容器2结束迭代器
    @param dest  目标容器开始迭代器
    merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)

void test01()
{

    vector<int> v1;
    vector<int> v2;

    for(int i=0; i<5; i++){
        v1.push_back(i+1);
        v2.push_back(i+2);
    }

    vector<int> v3;
    v3.resize(v1.size() + v2.size());

    /*
        _OutputIterator merge(_InputIterator1 __first1, _InputIterator1 __last1,
        _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
        {
           typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
           return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp);
        }
    */
    /*

template <class _Compare, class _InputIterator1, class _InputIterator2, class _OutputIterator>
_OutputIterator
__merge(_InputIterator1 __first1, _InputIterator1 __last1,
        _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
{
    for (; __first1 != __last1; ++__result)
    {
        if (__first2 == __last2)
            return _VSTD::copy(__first1, __last1, __result);
        if (__comp(*__first2, *__first1))
        {
            *__result = *__first2;
            ++__first2;
        }
        else
        {
            *__result = *__first1;
            ++__first1;
        }
    }
    return _VSTD::copy(__first2, __last2, __result);
}

   */
    // 如果数据是升序，那么第6个参数默认为less，结果为升序排列
    merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin()); // 1 2 2 3 3 4 4 5 5 6
    for_each(v3.begin(),v3.end(),MyPrint);
    cout << endl;

    v1.clear();
    v2.clear();

    for(int i=5; i>0; i--){
        v1.push_back(i+4);
        v2.push_back(i+2);
    }
    v3.resize(v1.size() + v2.size());
    // 如果数据是降序，那么第6个参数就要为greator，结果为降序序排列
    merge(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin(),greater<int>()); // 9 8 7 7 6 6 5 5 4 3
    for_each(v3.begin(),v3.end(),MyPrint);
    cout << endl;
}

4.2 sort算法

    sort算法 容器元素排序
    注意:容器必须是有序的
    @param beg 容器1开始迭代器
    @param end 容器1结束迭代器
    @param _callback 回调函数或者谓词(返回bool类型的函数对象)
    sort(iterator beg, iterator end, _callback)

void test02()
{
    vector<int> v;
    v.push_back(80);
    v.push_back(20);
    v.push_back(70);
    v.push_back(40);
    v.push_back(30);

    sort(v.begin(),v.end()); // 20 30 40 70 80
    for_each(v.begin(),v.end(),MyPrint);
    cout << endl;

    sort(v.begin(),v.end(),greater<int>()); // 80 70 40 30 20 
    for_each(v.begin(),v.end(),MyPrint);
    cout << endl;

    // 如果元素是对象，需要写第三个参数，谓词
    // sort(容器开始迭代器,容器结束迭代器,谓词);

}

4.3 random_shuffle算法

    random_shuffle算法 对指定范围内的元素随机调整次序
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    random_shuffle(iterator beg, iterator end)

void test03()
{
    vector<int> v1;
    for(int i=0; i<10; i++){
        v1.push_back(i+1);
    }
    for_each(v1.begin(),v1.end(),MyPrint);
    cout << endl;

    // 加随机种子，使得每次打乱结果不一样
    srand((unsigned int)time(NULL));
    random_shuffle(v1.begin(),v1.end());
    for_each(v1.begin(),v1.end(),MyPrint); // 7 1 4 6 8 9 5 2 3 10 
    cout << endl;



}

4.4 reverse算法

    reverse算法 反转指定范围的元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    reverse(iterator beg, iterator end)

void test04()
{
    vector<int> v1;
    for(int i=0; i<10; i++){
        v1.push_back(i+1);
    }

    for_each(v1.begin(),v1.end(),MyPrint); // 1 2 3 4 5 6 7 8 9 10
    cout << endl;

    reverse(v1.begin(),v1.end());
    for_each(v1.begin(),v1.end(),MyPrint); // 10 9 8 7 6 5 4 3 2 1
    cout << endl;

}

五、拷贝和替换算法

5.1 copy算法

    copy算法 将容器内指定范围的元素拷贝到另一容器中
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param dest 目标容器开始迭代器
    copy(iterator beg, iterator end, iterator dest)

void test01()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(5);
    v.push_back(7);
    v.push_back(9);
    v.push_back(6);

    vector<int> v2;
    v2.resize(v.size());

    copy(v.begin(),v.end(),v2.begin()); // 10 5 7 9 6
    for_each(v2.begin(),v2.end(),MyPrint);
    cout<<endl;


}

5.2 replace算法

    replace算法 将容器内指定范围的旧元素修改为新元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param oldvalue 旧元素
    @param oldvalue 新元素
    replace(iterator beg, iterator end, oldvalue, newvalue)

void test02()
{
    vector<int> v;
    v.push_back(10);
    v.push_back(5);
    v.push_back(7);
    v.push_back(9);
    v.push_back(6);
    for_each(v.begin(),v.end(),MyPrint);
    cout<<endl;

    replace(v.begin(),v.end(),9,100); // 10 5 7 100 6 
    for_each(v.begin(),v.end(),MyPrint);
    cout<<endl;

}

5.3 replace_if算法

/*
    replace_if算法 将容器内指定范围满足条件的元素替换为新元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param callback函数回调或者谓词(返回Bool类型的函数对象)
    @param oldvalue 新元素
    replace_if(iterator beg, iterator end, _callback, newvalue)
*/

struct MyFunc1: public binary_function<int,int,bool>
{
    bool operator()(int v1,int v2) const
    {
        return v1 > v2;
    }
};


void test03()
{
    vector<int> v;
    v.push_back(8);
    v.push_back(5);
    v.push_back(6);
    v.push_back(7);
    v.push_back(9);

    for_each(v.begin(),v.end(),MyPrint);
    cout<<endl;
    /*
        void replace_if(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, const _Tp& __new_value)
        {
            for (; __first != __last; ++__first)
                if (__pred(*__first))
                    *__first = __new_value;
        }

    */

    replace_if(v.begin(),v.end(),bind2nd(MyFunc1(),6),100);
    for_each(v.begin(),v.end(),MyPrint);
    cout<<endl;

    replace_if(v.begin(),v.end(),bind1st(MyFunc1(),6),100);
    for_each(v.begin(),v.end(),MyPrint);
    cout<<endl;


}

5.4 swap算法

/*
    swap算法 互换两个容器的元素
    @param c1容器1
    @param c2容器2
    swap(container c1, container c2)
*/

void test04()
{
    vector<int> v1;
    v1.push_back(8);
    v1.push_back(5);
    v1.push_back(6);
    v1.push_back(7);
    v1.push_back(9);

    vector<int> v2;
    v2.push_back(108);
    v2.push_back(105);
    v2.push_back(106);

    swap(v1,v2);

    for_each(v1.begin(),v1.end(),MyPrint);
    cout<<endl;

    for_each(v2.begin(),v2.end(),MyPrint);
    cout<<endl;

}

六、算术生成算法

#include <numeric> // 算术生成算法头文件

6.1 accumulate算法

/*
    accumulate算法 计算容器元素累计总和
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param value累加值
    accumulate(iterator beg, iterator end, value)
*/

void test01()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(40);
    /*
        accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
        {
            for (; __first != __last; ++__first)
                __init = __init + *__first;
            return __init;
        }

    */
    // 默认 加法
    int res1 = accumulate(v1.begin(),v1.end(),0);
    cout << res1 << endl;

    // 指定 减法
    int res2 = accumulate(v1.begin(),v1.end(),0,minus<int>());
    cout << res2 << endl;
    
    // 指定 乘法
    int res3 = accumulate(v1.begin(),v1.end(),1,multiplies<int>());
    cout << res3 << endl;
}

class Maker
{
public: 
    Maker(int age)
    {
        this->age = age;
    } 
public:
    int age;
};

struct MyMakerPlus
{
    int operator()(int val,Maker &m){
        return val + m.age;
    }
};


void test02()
{
    vector<Maker> v;
    v.push_back(Maker(10));
    v.push_back(Maker(20));
    v.push_back(Maker(30));

    int ret = accumulate(v.begin(),v.end(),0,MyMakerPlus());
    cout << ret << endl;
}

6.2 fill算法

/*
    fill算法 向容器中添加元素
    @param beg 容器开始迭代器
    @param end 容器结束迭代器
    @param value 填充元素
    fill(iterator beg, iterator end, value)
*/

void MyPrint(int val) {
    cout << val << " ";
}

void test03()
{
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    v1.push_back(40);

    fill(v1.begin(),v1.end(),50);
    for_each(v1.begin(),v1.end(),MyPrint);
    cout << endl;

    vector<int> v2;
    v2.resize(10); // 要开辟空间
    fill(v2.begin(),v2.end(),50);
    for_each(v2.begin(),v2.end(),MyPrint);
    cout << endl;
}

七、集合算法

7.1 set_intersection算法

/*
    set_intersection算法 求两个set集合的交集
    注意:两个集合必须是有序序列
    @param beg1 容器1开始迭代器
    @param end1 容器1结束迭代器
    @param beg2 容器2开始迭代器
    @param end2 容器2结束迭代器
    @param dest  目标容器开始迭代器
    @return 目标容器的最后一个元素的迭代器地址
    set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
*/

void MyPrint(int val) {
    cout << val << " ";
}

void test01()
{
    vector<int> v1;
    for(int i=0; i<10; i++){
        v1.push_back(i);
    }

    vector<int> v2;
    for(int i=5; i<10; i++){
        v2.push_back(i+2);
    }

    vector<int> v3;
    v3.resize(min(v1.size(),v2.size()));

    vector<int>::iterator it =  set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());
    for_each(v3.begin(),v3.end(),MyPrint);
    cout<<endl;

    cout <<"---------------"<<endl;
    // 去除因开辟空间多出的默认值
    cout << *it << endl;
    v3.erase(it,v3.end());
    for_each(v3.begin(),v3.end(),MyPrint);
    cout<<endl;
}

7.2 set_union算法

/*
    set_union算法 求两个set集合的并集
    注意:两个集合必须是有序序列
    @param beg1 容器1开始迭代器
    @param end1 容器1结束迭代器
    @param beg2 容器2开始迭代器
    @param end2 容器2结束迭代器
    @param dest  目标容器开始迭代器
    @return 目标容器的最后一个元素的迭代器地址
    set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
*/

void test02()
{
    vector<int> v1;
    for(int i=0; i<10; i++){
        v1.push_back(i);
    }

    vector<int> v2;
    for(int i=5; i<10; i++){
        v2.push_back(i);
    }

    vector<int> v3;
    v3.resize(v1.size()+v2.size());
    vector<int>::iterator it = set_union(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());
    for_each(v3.begin(),v3.end(),MyPrint);
    cout<<endl;

    cout <<"---------------"<<endl;
    // 去除因开辟空间多出的默认值
    cout << *it << endl;
    v3.erase(it,v3.end());
    for_each(v3.begin(),v3.end(),MyPrint);
    cout<<endl;

}

7.3 set_difference算法

/*
    set_difference算法 求两个set集合的差集
    注意:两个集合必须是有序序列
    @param beg1 容器1开始迭代器
    @param end1 容器1结束迭代器
    @param beg2 容器2开始迭代器
    @param end2 容器2结束迭代器
    @param dest  目标容器开始迭代器
    @return 目标容器的最后一个元素的迭代器地址
    set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest)
*/

// 假如 A集合 1，2，3，4，5 B集合 2，3，4，5，6,A-B 为1，B-A为6
void test03()
{
    vector<int> v1;
    for(int i=0; i<5; i++){
        v1.push_back(i+1);
    }

    vector<int> v2;
    for(int i=0; i<5; i++){
        v2.push_back(i+2);
    }

    vector<int> v3;
    v3.resize(min(v1.size(),v2.size()));

    vector<int>::iterator it = set_difference(v1.begin(),v1.end(),v2.begin(),v2.end(),v3.begin());
    for_each(v3.begin(),v3.end(),MyPrint);
    cout<<endl;

    set_difference(v2.begin(),v2.end(),v1.begin(),v1.end(),v3.begin());
    for_each(v3.begin(),v3.end(),MyPrint);
    cout<<endl;
}

八、综合案例

学校演讲比赛介绍
1）某市举行一场演讲比赛（ speech_contest ），共有24个人参加。比赛共三轮，前两轮为淘汰赛，第三轮为决赛。
2）比赛方式：分组比赛，每组6个人；选手每次要随机分组，进行比赛；
第一轮分为4个小组，每组6个人。比如100-105为一组，106-111为第二组，依次类推，
每人分别按照抽签（draw）顺序演讲。当小组演讲完后，淘汰组内排名最后的三个选手，然后继续下一个小组的比赛。
第二轮分为2个小组，每组6人。比赛完毕，淘汰组内排名最后的三个选手，然后继续下一个小组的比赛。
第三轮只剩下6个人，本轮为决赛，选出前三名。
4）比赛评分：10个评委打分，去除最低、最高分，求平均分
每个选手演讲完由10个评委分别打分。该选手的最终得分是去掉一个最高分和一个最低分，求得剩下的8个成绩的平均分。
选手的名次按得分降序排列，若得分一样，按参赛号升序排名。

用STL编程，求解这个问题
1）请打印出所有选手的名字与参赛号，并以参赛号的升序排列。
2）打印每一轮比赛后，小组比赛成绩和小组晋级名单
3）打印决赛前三名，选手名称、成绩。

#include <iostream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <map>
#include <deque>
#include <ctime>

using namespace std;

class Player
{
public:
    string mName;
    int mAge;
    int mScore[3]; // 选手最多有3轮比赛成绩
};

// 创建选手
void CreatePlayers(vector<int> &v1, map<int, Player> &mlist)
{
    string tempstring = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for (int i = 0; i < 24; i++)
    {
        Player p;
        p.mName = "选手";
        p.mName += tempstring[i];
        p.mAge = rand() % 5 + 15;

        for (int j = 0; j < 3; j++)
        {
            p.mScore[j] = 0;
        }

        // 生成选手编号
        int ID = 100 + i;
        // 保存选手编号
        v1.push_back(ID);
        // 保存选手信息
        mlist.insert(make_pair(ID, p));
    }
}

// 抽签
void PlayerByRandom(vector<int> &v)
{
    return random_shuffle(v.begin(), v.end());
}
// 比赛
void StartMatch(int index, vector<int> &v1, map<int, Player> &mlist, vector<int> &v2)
{
    // 定义multimap容器,键值是分数，实值是选手编号
    // 降序排列
    multimap<int, int, greater<int> > mGroups;

    for (vector<int>::iterator sit = v1.begin(); sit != v1.end(); ++sit)
    {
        // 评委评分
        deque<int> dScore;
        for (int i = 0; i < 10; i++)
        {
            int score = rand() % 30 + 70;
            dScore.push_back(score);
        }

        // 排序
        sort(dScore.begin(), dScore.end());
        // 去除最高分和最低分
        dScore.pop_front();
        dScore.pop_back();

        // 总分
        int total_score = accumulate(dScore.begin(), dScore.end(), 0);

        // 平均分
        int average_score = total_score / dScore.size();

        // 保存选手分数
        mlist[*sit].mScore[index - 1] = average_score;

        // 把选手放到multimap容器中
        mGroups.insert(make_pair(average_score, *sit));

        // 评比
        if (mGroups.size() == 6)
        {
            // 容器中一共6人 选取前面3位
            int tempIndex = 0;
            for (multimap<int, int>::iterator mit = mGroups.begin(); mit != mGroups.end() && tempIndex < 3; ++mit, ++tempIndex)
            {
                v2.push_back((*mit).second);
            }
            // 清空容器
            mGroups.clear();
        }
    }
}

// 打印本轮晋级选手
void ShowPlayerScore(int index, vector<int> &v, map<int, Player> &mlist)
{
    cout << "第" << index << "轮 晋级名单:" << endl;
    for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    {
        cout << "Name: " << mlist[*it].mName << " Age: " << mlist[*it].mAge << " Score: " << mlist[*it].mScore[index - 1] << endl;
    }
}

void test()
{
    vector<int> v1;         // 保存选手编号
    map<int, Player> mlist; // 保存选手信息
    vector<int> v2;         // 保存第一轮晋级选手编号
    vector<int> v3;         // 保存第二轮晋级选手编号
    vector<int> v4;         // 保存第三轮晋级选手编号

    // 创建选手
    CreatePlayers(v1, mlist);

    // 第一轮比赛
    // 抽签
    PlayerByRandom(v1);
    // 比赛
    StartMatch(1, v1, mlist, v2);
    // 打印本轮晋级选手
    ShowPlayerScore(1, v2, mlist);

    // 第二轮比赛：抽签 比赛 打印本轮晋级选手
    // 抽签
    PlayerByRandom(v2);
    // 比赛
    StartMatch(2, v2, mlist, v3);
    // 打印本轮晋级选手
    ShowPlayerScore(2, v3, mlist);

    // 第三轮比赛
    // 抽签
    PlayerByRandom(v3);
    // 比赛
    StartMatch(3, v3, mlist, v4);
    // 打印本轮晋级选手
    ShowPlayerScore(3, v4, mlist);
}

int main()
{
    srand((unsigned int)time(NULL));
    test();
    return EXIT_SUCCESS;
}