蜗牛慢爬的李成广 2019-12-28
算法(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