C++ STL(十)算法

算法(Algorithm)：STL算法主要由头文件<algorithm>,<numeric>和<functional>组成

<algorithm> 比较、交换、查找、遍历、复制、修改、反转、排序、合并等等算法

<numeric> 只包括几个在序列上进行数学运算的模板函数，加法、乘法等

<functional> 定义了一些模板类，用于声明函数对象

查找算法：

_FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last) //查找标志范围内一对相邻重复元素,如果找到返回指向第一个元素迭代器,未找到返回迭代器等于_Last

inline void _adjacent_find()
{
    vector<int> vecInt;
    vecInt.push_back(1);
    vecInt.push_back(3);
    vecInt.push_back(2);
    vecInt.push_back(2);
    vecInt.push_back(5);

    vector<int>::iterator it = adjacent_find(vecInt.begin(), vecInt.end());
    if(it != vecInt.end())
    {
        cout<<"ok,Find"<<endl; //cout
    }else
    {
        cout<<"Error,NotFind"<<endl;
    }

    list<int> listInt;
    listInt.push_back(1);
    listInt.push_back(3);
    listInt.push_back(2);
    listInt.push_back(1);
    listInt.push_back(2);

    list<int>::iterator itList = adjacent_find(listInt.begin(), listInt.end());
    if(itList != listInt.end())
    {
        cout<<"ok,Find"<<endl;
    }else
    {
        cout<<"Error,NotFind"<<endl; //cout
    }

    getchar();
}

adjacent_find()

bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val) //在有序序列中查找val,找到返回ture.注意：无序序列中，不可使用

inline void _binary_search()
{
    vector<int> vecInt;
    vecInt.push_back(1);
    vecInt.push_back(3);
    vecInt.push_back(5);
    vecInt.push_back(7);
    vecInt.push_back(9);

    bool bFind = binary_search(vecInt.begin(), vecInt.end(), 3); //bFind = true
    bool bFind_1 = binary_search(vecInt.begin(), vecInt.end(), 8); //bFind_1 = false

    getchar();
};

binary_search

count(_InIt _First, _InIt _Last, const _Ty& _Val) //在有序序列中查找val,返回相同元素个数

inline void _count()
{
    vector<int> vecInt;
    vecInt.push_back(1);
    vecInt.push_back(2);
    vecInt.push_back(2);
    vecInt.push_back(4);
    vecInt.push_back(2);
    int nCount = count(vecInt.begin(), vecInt.end(), 2); //nCount = 3
    int nCount_1 = count(vecInt.begin(), vecInt.end(), 6); //nCount = 0

    getchar();
}

count

count_if(_InIt _First, _InIt _Last, _Pr _Pred) //与_count()功能相同，不同在于统计条件使用函数对象进行判断

bool GreaterEqualThree(int nNum)
{
    if(nNum >=3)
    {
        return true;
    }else
    {
        return false;
    }
}
inline void _count_if()
{
    vector<int> vecInt;
    vecInt.push_back(1);
    vecInt.push_back(2);
    vecInt.push_back(2);
    vecInt.push_back(4);
    vecInt.push_back(2);
    vecInt.push_back(5);
    //统计vecInt中元素值大于等于3的元素个数
    int nCount = count_if(vecInt.begin(), vecInt.end(), GreaterEqualThree); //nCount=2

    getchar();
}

count_if

iterator find(_InIt _First, _InIt _Last, const _Ty& _Val) //在标志范围内的元素进行查找val,返回找到的第一个元素迭代器

inline void _find()
{
    vector<int> vecInt;
    vecInt.push_back(1);
    vecInt.push_back(2);
    vecInt.push_back(2);
    vecInt.push_back(4);
    vecInt.push_back(2);
    vecInt.push_back(5);

    vector<int>::iterator it = find(vecInt.begin(), vecInt.end(),2);

    getchar();
}

find()

iterator find_if(_InIt _First, _InIt _Last, _Pr _Pred) //与_find()功能相同，不同在于查找条件使用函数对象进行判断

bool GreaterThree(int nNum)
{
    if(nNum > 3)
    {
        return true;
    }else
    {
        return false;
    }
}
inline void _find_if()
{
    vector<int> vecInt;
    vecInt.push_back(1);
    vecInt.push_back(2);
    vecInt.push_back(2);
    vecInt.push_back(4);
    vecInt.push_back(2);
    vecInt.push_back(5);
    //查找大于3的第一个迭代器
    vector<int>::iterator it = find_if(vecInt.begin(), vecInt.end(),GreaterThree);

    getchar();
}

find_if()

排序算法:

_OutIt merge(_InIt1 _First1, _InIt1 _Last1,_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest) //合并二个容器中的元素到Dest容器中

注意：Dest容器需要设置足够大的空间用于存储新元素

inline void _merge()
{
    vector<int> vecIntA;
    vecIntA.push_back(1);
    vecIntA.push_back(3);
    vecIntA.push_back(5);
    vecIntA.push_back(7);
    vecIntA.push_back(9);

    vector<int> vecIntB;
    vecIntB.push_back(2);
    vecIntB.push_back(4);
    vecIntB.push_back(6);
    vecIntB.push_back(8);

    vector<int> vecInResult;
    vecInResult.resize(9); //设置大小用足容合并过的新元素
    merge(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecInResult.begin());
    vector<int>::iterator it = vecInResult.begin();
    for (it; it!=vecInResult.end(); ++it)
    {
        cout<<*it<<" ";
    }
    //1 2 3 4 5 6 7 8 9
    getchar();
}

merge()

void sort(_RanIt _First, _RanIt _Last)

void sort(_RanIt _First, _RanIt _Last, _Pr _Pred)

class CStudent
{
public:
    CStudent(int nID, string strName)
    {
        this->m_nID = nID;
        this->m_strName = strName;
    }
    ~CStudent(){}

public:
    int m_nID;
    string m_strName;
};
bool Compare(CStudent &stu1, CStudent &stu2)
{
    return stu1.m_nID<stu2.m_nID;
}
inline void _sort()
{
    vector<int> vecIntA;
    vecIntA.push_back(3);
    vecIntA.push_back(2);
    vecIntA.push_back(1);
    vecIntA.push_back(5);
    vecIntA.push_back(7);

    sort(vecIntA.begin(), vecIntA.end());
    vector<int>::iterator it = vecIntA.begin();

    for (it; it!=vecIntA.end(); ++it)
    {
        cout<<*it<<" ";
    }
    //1 2 3 5 7

    cout<<endl;

    vector<CStudent> vecStu;
    vecStu.push_back(CStudent(2,"老二"));
    vecStu.push_back(CStudent(1,"老大"));
    vecStu.push_back(CStudent(3,"老三"));
    vecStu.push_back(CStudent(4,"老四"));
    sort(vecStu.begin(), vecStu.end(), Compare);
    vector<CStudent>::iterator itVecStu = vecStu.begin();
    for (itVecStu; itVecStu!=vecStu.end(); ++itVecStu)
    {
        cout<<itVecStu->m_nID<<":"<<itVecStu->m_strName.c_str()<<endl;
    }
/*
    1:老大
  2:老二
    3:老三
    4:老四*/

    getchar();
}

sort

void random_shuffle(_RanIt _First, _RanIt _Last)  //对容器中的元素使用随机排序, 注意：使用前需要设置随机种子srand(time(0));

inline void _random_shuffle()
{
    vector<int> vecIntA;
    vecIntA.push_back(1);
    vecIntA.push_back(2);
    vecIntA.push_back(3);
    vecIntA.push_back(4);
    vecIntA.push_back(5);

    srand((unsigned int)time(0)); //设置个随机种子
    random_shuffle(vecIntA.begin(), vecIntA.end());

    getchar();
}

random_shuffle()

拷贝和替换算法 :

_OutIt copy(_InIt _First, _InIt _Last,_OutIt _Dest) //把源容器中的元素复制到Dest容器中

注意：Dest容器需要设置足够大的空间用于存储新元素

inline void _copy()
{
    vector<int> vecIntA;
    vecIntA.push_back(3);
    vecIntA.push_back(2);
    vecIntA.push_back(1);
    vecIntA.push_back(5);
    vecIntA.push_back(7);

    vector<int> vecIntB;
    vecIntB.resize(vecIntA.size());
    copy(vecIntA.begin(), vecIntA.end(), vecIntB.begin());
    vector<int>::iterator it = vecIntB.begin();
    for (it; it!=vecIntB.end(); ++it)
    {
        cout<<*it<<" ";
    }

    getchar();
}

copy()

void replace(_FwdIt _First, _FwdIt _Last,const _Ty& _Oldval, const _Ty& _Newval) //用新的元素替换容器中指定元素

inline void _replace()
{
    vector<int> vecIntA;
    vecIntA.push_back(3);
    vecIntA.push_back(2);
    vecIntA.push_back(2);
    vecIntA.push_back(2);
    vecIntA.push_back(7);
    //把容器中所有元素为2的替换为8
    replace(vecIntA.begin(), vecIntA.end(), 2, 8);
    vector<int>::iterator it = vecIntA.begin();
    for (it; it!=vecIntA.end(); ++it)
    {
        cout<<*it<<" ";
    }
    //3 8 8 8 7

    getchar();
}

replace()

void replace_if(_FwdIt _First, _FwdIt _Last, _Pr _Pred, const _Ty& _Val)  //与_replace()功能相同，不同在于替换条件使用函数对象进行判断

bool GreaterEqualTwo(int nNum)
{
    if(nNum >= 2)
    {
        return true;
    }
    return false;
}
inline void _replace_if()
{
    vector<int> vecIntA;
    vecIntA.push_back(3);
    vecIntA.push_back(1);
    vecIntA.push_back(1);
    vecIntA.push_back(1);
    vecIntA.push_back(7);
    //把容器中所有>=2的元素替换为8
    replace_if(vecIntA.begin(), vecIntA.end(),GreaterEqualTwo,8);
    vector<int>::iterator it = vecIntA.begin();
    for (it; it!=vecIntA.end(); ++it)
    {
        cout<<*it<<" ";
    }
    //8 1 1 1 8

    getchar();
}

replace_if()

void fill(_FwdIt _First, _FwdIt _Last, const _Ty& _Val) //与replace()单一替换不同，fill可以批量替换容器中所有的元素

inline void _fill()
{
    vector<int> vecIntA;
    vecIntA.push_back(3);
    vecIntA.push_back(2);
    vecIntA.push_back(2);
    vecIntA.push_back(2);
    vecIntA.push_back(7);

    fill(vecIntA.begin(), vecIntA.end(), 0);

    getchar();
}

fill()

void swap(vector<_Ty, _Alloc>& _Left, vector<_Ty, _Alloc>& _Right) //把二个容器进行交换,注意：交换后容器的size和resize都会发生改变

inline void _swap()
{
    vector<int> vecIntA;
    vecIntA.push_back(3);
    vecIntA.push_back(2);
    vecIntA.push_back(1);
    vecIntA.push_back(5);
    vecIntA.push_back(7);

    vector<int> vecIntB;
    swap(vecIntA,vecIntB);
    
    vector<int>::iterator itA = vecIntA.begin();
    vector<int>::iterator itB = vecIntB.begin();

    cout<<"vecIntA"<<endl;
    for (itA; itA!=vecIntA.end(); ++itA)
    {
        cout<<*itA<<" ";
    }
    cout<<"vecIntB"<<endl;
    for (itB; itB!=vecIntB.end(); ++itB)
    {
        cout<<*itB<<" ";
    }
    
    getchar();
}

swap()

算术算法:

int accumulate(_InIt _First, _InIt _Last, _Ty _Val) //把指定范围内元素进行相加，最后再把结果加上Val,返回最终的结果

inline void _accumulate()
{
    vector<int> vecIntA;
    vecIntA.push_back(1);
    vecIntA.push_back(3);
    vecIntA.push_back(5);
    vecIntA.push_back(7);
    vecIntA.push_back(9);

    int nTotal = accumulate(vecIntA.begin(), vecIntA.end(), 100); //125

    getchar();
}

accumulate()

集合算法:

_OutIt set_union(_InIt1 _First1, _InIt1 _Last1,_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest) //二个容器并集后赋值给新容器，新容器中包含二个容器中所有元素，但是不会包含重复相同的部份.resize剩余部份以默认值0填充

注意：Dest容器需要设置足够大的空间用于存储新元素

inline void set_union()
{
    vector<int> vecIntA;
    vecIntA.push_back(1);
    vecIntA.push_back(3);
    vecIntA.push_back(5);
    vecIntA.push_back(7);
    vecIntA.push_back(9);

    vector<int> vecIntB;
    vecIntB.push_back(1);
    vecIntB.push_back(3);
    vecIntB.push_back(5);
    vecIntB.push_back(6);
    vecIntB.push_back(8);

    vector<int> vecIntC;
    vecIntC.resize(10);
    set_union(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin());
    for (size_t i = 0; i<vecIntC.size(); ++i)
    {
        cout<<vecIntC[i]<<" ";
    }
    //1 3 5 6 7 8 9 0 0 0
    getchar();
}

set_union

_OutIt set_intersection(_InIt1 _First1, _InIt1 _Last1,_InIt2 _First2, _InIt2 _Last2, _OutIt _Dest) //二个容器交集赋值给新容器，新容器中仅包含二个容器中相同的部份，resize剩余部份以默认值0填充

inline void set_intersection()
{
    vector<int> vecIntA;
    vecIntA.push_back(1);
    vecIntA.push_back(3);
    vecIntA.push_back(5);
    vecIntA.push_back(7);
    vecIntA.push_back(9);

    vector<int> vecIntB;
    vecIntB.push_back(1);
    vecIntB.push_back(3);
    vecIntB.push_back(5);
    vecIntB.push_back(6);
    vecIntB.push_back(8);

    vector<int> vecIntC;
    vecIntC.resize(10);
    set_intersection(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin());
    for (size_t i = 0; i<vecIntC.size(); ++i)
    {
        cout<<vecIntC[i]<<" ";
    }
    //1 3 5 0 0 0 0 0 0 0
    getchar();
}

set_intersection()

_OutIt set_difference(_InIt1 _First1, _InIt1 _Last1,_InIt2 _First2, _InIt2 _Last2,_OutIt _Dest) //二个容器差集赋值给新容器，新容器中仅包含二个容器中不相同部份，resize剩余部份以默认值0填充

inline void set_difference()
{
    vector<int> vecIntA;
    vecIntA.push_back(1);
    vecIntA.push_back(3);
    vecIntA.push_back(5);
    vecIntA.push_back(7);
    vecIntA.push_back(9);

    vector<int> vecIntB;
    vecIntB.push_back(1);
    vecIntB.push_back(3);
    vecIntB.push_back(5);
    vecIntB.push_back(6);
    vecIntB.push_back(8);

    vector<int> vecIntC;
    vecIntC.resize(10);
    set_difference(vecIntA.begin(), vecIntA.end(), vecIntB.begin(), vecIntB.end(), vecIntC.begin());
    for (size_t i = 0; i<vecIntC.size(); ++i)
    {
        cout<<vecIntC[i]<<" ";
    }
    //7 9 0 0 0 0 0 0 0 0
    getchar();
};

set_difference()

遍历算法:

_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func) //根据函数对象进行遍历容器

void ShowOut(const int &item)
{
    cout<<item<<" ";
}
inline void _for_each()
{
    int nArray[] = {0,1,2,3,4};
    vector<int> vecInt(nArray, nArray+5);
    for_each(vecInt.begin(), vecInt.end(), ShowOut);
    
    getchar();
}

for_each()

_OutIt transform(_InIt _First, _InIt _Last,_OutIt _Dest, _Fn1 _Func) //根据函数对象进行遍历容器，可以通过函数对象返回的值对容器中的元素进行修改

int AddOne(const int &item)
{
    return item+1;
}
inline void _transform()
{
    int nArray[] = {1,3,5,7,9};
    vector<int> vecInt(nArray, nArray+5);
    transform(vecInt.begin(), vecInt.end(), vecInt.begin(), AddOne);
    for_each(vecInt.begin(),vecInt.end(),ShowOut);
    //2 4 6 8 10
    getchar();
};

transform