C++中实现了很多的泛型算法，大约100多个，使用前要添加#include<algorithm>
下面介绍的基本可以满足绝大部分需求，其他的用到再查
一、计数算法
1.count
template <class InputIterator, class T> typename iterator_traits<InputIterator>::difference_type count (InputIterator first, InputIterator last, const T& val);统计并返回迭代器范围内的元素T的个数
2.count_if
template <class InputIterator, class UnaryPredicate> typename iterator_traits<InputIterator>::difference_type count_if (InputIterator first, InputIterator last, UnaryPredicate pred);统计并返回迭代器范围内使条件pred为true的元素个数
这两个函数和list中的remove和remove_if类似
示例
bool comp(char &c) { return c > '2'; } void counttest() { string s="111222333444"; int cnt=count(s.begin(), s.end(), '1'); int cnt2=count_if(s.begin(), s.end(), comp); cout<<cnt<<","<<cnt2<<endl; }
二、最值算法
1.max_element
template <class ForwardIterator> ForwardIterator max_element (ForwardIterator first, ForwardIterator last); template <class ForwardIterator, class Compare> ForwardIterator max_element (ForwardIterator first, ForwardIterator last, Compare comp);计算并返回迭代器范围内的最大值的迭代器
2.min_element
template <class ForwardIterator> ForwardIterator min_element (ForwardIterator first, ForwardIterator last); template <class ForwardIterator, class Compare> ForwardIterator min_element (ForwardIterator first, ForwardIterator last, Compare comp);计算并返回迭代器范围内的最大值
comp默认是用 operator< 比较元素，表示第一个参数传递的元素是否小于第二个参数。
示例
bool comp1(int a, int b) {return abs(a)<abs(b);} void minmaxtest() { deque<int> d={1,2,3,4,5,6,-1,-2,-3,-4,-5}; deque<int>::iterator max= max_element(d.begin(),d.end()); deque<int>::iterator min= min_element(d.begin(),d.end()); deque<int>::iterator maxodd= max_element(d.begin(),d.end(), comp1);//如果 abs(a)<abs(b)，更新最大值迭代器 deque<int>::iterator minodd= min_element(d.begin(),d.end(), comp1);//如果 abs(a)<abs(b)，更新最小值迭代器 cout<<*max<<","<<*min<<","<<*maxodd<<","<<*minodd<<endl; }
3.minmax_element
template <class ForwardIterator> pair<ForwardIterator,ForwardIterator> minmax_element (ForwardIterator first, ForwardIterator last); template <class ForwardIterator, class Compare> pair<ForwardIterator,ForwardIterator> minmax_element (ForwardIterator first, ForwardIterator last, Compare comp);计算迭代器范围内的最大和最小值，并以一个pair对象进行返回
示例
bool comp1(int a, int b) {return abs(a)<abs(b);} void minmaxpair() { int a[6]={1,2,3,-9,-8,-7}; pair<int *, int *> p=minmax_element(a, a+6); cout<<*p.first<<*p.second<<endl;//输出最小值和最大值 pair<int *, int *> p2=minmax_element(a, a+6, comp1); cout<<*p2.first<<*p2.second<<endl;//输出绝对值最小的值和绝对值打的值 }
此外还有两个求区最值的函数max和min
函数声明如下：
max
template <class T> const T& max (const T& a, const T& b); template <class T, class Compare> const T& max (const T& a, const T& b, Compare comp); template <class T> T max (initializer_list<T> il); template <class T, class Compare> T max (initializer_list<T> il, Compare comp);min的函数声明类似
这两个函数的用法同上
三、元素查找
1.find
template <class InputIterator, class T> InputIterator find (InputIterator first, InputIterator last, const T& val);查找第一个值为val的元素，并对应的返回迭代器，如果没找到，返回last迭代器
2.find_if
template <class InputIterator, class UnaryPredicate> InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);查找第一个满足条件的元素并返回对应的迭代器，如果没找到，返回last
3.find_if_not
template <class InputIterator, class UnaryPredicate> InputIterator find_if_not (InputIterator first, InputIterator last, UnaryPredicate pred);查找第一个不满足条件的元素并返回对应的迭代器，如果没找到，返回last
示例
bool pred(int a) {return a <0;} void findtest() { list<int> l={1,2,3,-9,-8,-7}; list<int>::iterator it=find(l.begin(), --l.end(), 4);//在l.begin(), --l.end()范围内查找4 cout<<*it<<endl;//没找到，输出*--l.end() it=find_if(l.begin(), --l.end(), pred);//查找第一个小于0的数 cout<<*it<<endl; it=find_if_not(l.begin(), --l.end(), pred);//查找第一个不小于零的数 cout<<*it<<endl; }
四、区间的比较判断
equal
template <class InputIterator1, class InputIterator2> bool equal (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); template <class InputIterator1, class InputIterator2, class BinaryPredicate> bool equal (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred);比较范围[first1,last1)中的元素和从first2开始的元素，如果两个范围中的所有元素都满足相等或者满足条件pred，则返回true。
示例
bool equalcmp(int a, int b) {return a<b;} void equaltest() { vector<int> v1={1,2,3,4,5,6}; vector<int> v2={2,3,4,5,6,7}; bool res1=equal(v1.begin()+1, v1.end()-1, v2.begin());//判断v1.begin()+1, v1.end()-1范围内的元素和 以v2.begin()为起点，相同长度范围内的元素是否相等 cout<<res1<<endl; bool res2=equal(v1.begin(), v1.end(), v2.begin(), equalcmp);//判断两个序列是否满足v1的每个元素都比v2的元素小 cout<<res2<<endl; }
五、排序和判断序列是否有序
1.is_sorted
template <class ForwardIterator> bool is_sorted (ForwardIterator first, ForwardIterator last); template <class ForwardIterator, class Compare> bool is_sorted (ForwardIterator first, ForwardIterator last, Compare comp);判断序列是否有序
2.sort, stable_sort
template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp); template <class RandomAccessIterator> void stable_sort (RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void stable_sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);不稳定排序和稳定排序
关于排序的稳定性，见博客https://www.cnblogs.com/codingmylife/archive/2012/10/21/2732980.html
简单来说就是，如果两个元素a,b相等，且a在前，b在后，那么排序后，a仍然在前，b仍然在后
示例
void sorttest() { int a[]={5,7,6,3,9,-10,20,-12,-1}; stable_sort(a, a+sizeof(a)/sizeof(*a));//按照默认的小于号方式（升序）排序 for (int i=0;i<sizeof(a)/sizeof(*a);++i) { cout<<a[i]<<endl; } cout<<is_sorted(a, a+sizeof(a)/sizeof(*a))<<endl; }bool sortcmp(int a, int b) {return abs(a)>abs(b);}//按照绝对值从打到小进行排序 void sorttest() { int a[]={5,7,6,3,9,-10,20,-12,-1}; stable_sort(a, a+sizeof(a)/sizeof(*a), sortcmp); for (int i=0;i<sizeof(a)/sizeof(*a);++i) { cout<<a[i]<<endl; } cout<<is_sorted(a, a+sizeof(a)/sizeof(*a), sortcmp)<<endl; }
sort的用法同stable_sort
六、复制元素
1.copy
template <class InputIterator, class OutputIterator> OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result);将迭代器范围中的元素拷贝到另一个容器中，起始范围是result
返回值为目标容器中最后复制元素的下个元素的迭代器。返回值一般用不到
2.copy_if
template <class InputIterator, class OutputIterator, class UnaryPredicate> OutputIterator copy_if (InputIterator first, InputIterator last, OutputIterator result, UnaryPredicate pred);含义与copy类似
注意：
1.目标容器必须有足够的空间容纳拷贝的元素，所以目标容器必须要分配足够的空间，copy并不负责分配空间
2.输出迭代器result不能处于迭代器范围[first, last)中
示例
bool copyfunc(int a) {return a>0;} void copytest() { int a[]={5,7,6,3,9,-10,20,-12,-1}; vector<int> v(10);//必须分配空间，否则无法拷贝 copy(a, a+sizeof(a)/sizeof(*a), v.begin());//将数组拷贝到vector中 for (vector<int>::iterator it=v.begin();it!=v.end();++it) { cout<<*it<<endl; } cout<<"-------------"<<endl; deque<int> d(10); copy_if(a, a+sizeof(a)/sizeof(*a), d.begin(), copyfunc); for (deque<int>::iterator it=d.begin();it!=d.end();++it) { cout<<*it<<endl; } }
七、替换元素
1.replace
template <class ForwardIterator, class T> void replace (ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value);将迭代器范围内的值为old_value的元素替换为new_value
2.replace_if
template <class ForwardIterator, class UnaryPredicate, class T> void replace_if (ForwardIterator first, ForwardIterator last, UnaryPredicate pred, const T& new_value );将迭代器范围内满足pred的值替换为new_value
示例和copy与copy_if类似
参考
《C++ Primer》
《C++标准库》
http://www.cplusplus.com/reference/algorithm/
https://zh.cppreference.com/w/cpp/algorithm
欢迎大家评论交流，作者水平有限，如有错误，欢迎指出
