首页 > 代码库 > (转)常用算法（Algorithm）的用法介绍
(转)常用算法（Algorithm）的用法介绍
2算法部分主要由头文件<algorithm>，<numeric>和<functional>组成。
2<algorithm>是所有STL头文件中最大的一个，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改、反转、排序、合并等等。
2<numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。
2<functional>中则定义了一些模板类，用以声明函数对象。
2STL提供了大量实现算法的模版函数，只要我们熟悉了STL之后，许多代码可以被大大的化简，只需要通过调用一两个算法模板，就可以完成所需要的功能，从而大大地提升效率
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;
2常用的查找算法：
adjacent_find()（ adjacent 是邻近的意思）,binary_search(),count(),
count_if(),equal_range(),find(),find_if()。
2常用的排序算法：
merge(),sort(),random_shuffle()（shuffle是洗牌的意思） ,reverse()。
2常用的拷贝和替换算法：
copy(), replace(),
replace_if(),swap()
2常用的算术和生成算法：
accumulate()（ accumulate 是求和的意思）,fill(),。
2常用的集合算法：
set_union(),set_intersection(),
set_difference()。
2常用的遍历算法：
for_each(), transform()（ transform 是变换的意思）
2adjacent_find(): 在iterator对标识元素范围内，查找一对相邻重复元素，找到则返回指向这对元素的第一个元素的迭代器。否则返回past-the-end。
例如：vecInt是用vector<int>声明的容器，现已包含1,2,2,4,5元素。
vector<int>::iteratorit=adjacent_find(vecInt.begin(),vecInt.end());
此时 *it == 2
2binary_search: 在有序序列中查找value,找到则返回true。注意：在无序序列中，不可使用。
例如： setInt是用set<int>声明的容器，现已包含1，3，5，7，9元素。
bool bFind =binary_search(setInt.begin(),setInt.end(),5);
此时 bFind == true
2count: 利用等于操作符，把标志范围内的元素与输入值比较，返回相等的个数。
2count_if: 利用输入的函数，对标志范围内的元素进行比较操作，返回结果为true的个数。
例如：vecInt是用vector<int>声明的容器，已包含1,3,5,7,9元素，现要求求出大于等于3的元素个数
//先定义比较函数
bool GreaterThree(int iNum)
{
if(iNum>=3)
{
return true;
}
else
{
return false;
}
}
int iCount = count_if(vecIntA.begin(),vecIntA.end(), GreaterThree);
//此时iCount == 4
2equal_range: 返回一对iterator，第一个表示lower_bound,第二个表示upper_bound。
2
2find: 利用底层元素的等于操作符，对指定范围内的元素与输入值进行比较。当匹配时，结束搜索，返回该元素的迭代器。
例如： vecInt是用vector<int>声明的容器，已包含1,3,5,7,9
vector<int>::iterator it =find(vecInt.begin(),vecInt.end(),5);
此时 *it == 5
2find_if: 使用输入的函数代替等于操作符执行find。返回被找到的元素的迭代器。
例如：vecInt是用vector<int>声明的容器，已包含1,3,5,3,9元素。现要找出第一个大于等于3的元素的迭代器。
vector<int>::iterator it =find_if(vecInt.begin(),vecInt.end(),GreaterThree);
此时 *it==3, *(it+1)==5,*(it+2)==3, *(it+3)==9
2常用的查找算法：
adjacent_find(),binary_search(),count(),
count_if(),equal_range(),find(),find_if()。
2常用的排序算法：
merge(),sort(),random_shuffle(),reverse()。
2常用的拷贝和替换算法：
copy(), replace(),
replace_if(),swap()
2常用的算术和生成算法：
accumulate(),fill()
2常用的集合算法：
set_union(),set_intersection(),
set_difference()。
2常用的遍历算法：
for_each(), transform()
2以下是排序和通用算法：提供元素排序策略
2merge: 合并两个有序序列，存放到另一个序列。
例如：vecIntA,vecIntB,vecIntC是用vector<int>声明的容器，vecIntA已包含1,3,5,7,9元素，vecIntB已包含2,4,6,8元素
vecIntC.resize(9); //扩大容量
merge(vecIntA.begin(),vecIntA.end(),vecIntB.begin(),vecIntB.end(),vecIntC.begin());
此时vecIntC就存放了按顺序的1,2,3,4,5,6,7,8,9九个元素
2sort: 以默认升序的方式重新排列指定范围内的元素。若要改排序规则，可以输入比较函数。
例如: vecInt是用vector<int>声明的容器，已包含2,1,4,3,6,5元素
sort(vecInt.begin(),vecInt.end());
此时，vecInt包含了1,2,3,4,5,6元素。
如果vector<T>,T是自定义类型，则要提供T类型的比较函数
学生类有学号跟姓名的属性，有一个存着学生对象的vector容器，要使该容器按学号升序排序。
//学生类
Class CStudent:
{
public:
CStudent(int iID, string strName)
{m_iID=iID; m_strName=strName; }
public:
int m_iID;
string m_strName;
}
2//学号比较函数
bool Compare(const CStudent &stuA,constCStudent &stuB)
{
return(stuA.m_iID<strB.m_iID);
}
void main()
{
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);
// 此时，vecStu容器包含了按顺序的"老大对象","老二对象","老三对象","老四对象"
}
2random_shuffle: 对指定范围内的元素随机调整次序。
2reverse: 对指定范围内元素重新反序排序
2常用的查找算法：
adjacent_find(),binary_search(),count(),
count_if(),equal_range(),find(),find_if()。
2常用的排序算法：
merge(),sort(),random_shuffle(),reverse()。
2常用的拷贝和替换算法：
copy(), replace(),
replace_if(),swap()
2常用的算术和生成算法：
accumulate(),fill(),。
2常用的集合算法：
set_union(),set_intersection(),
set_difference()。
2常用的遍历算法：
for_each(), transform()
copy: 复制序列
例如：vecIntA,vecIntB是用vector<int>声明的对象，vecIntA已包含1,3,5,7,9元素。
vecIntB.resize(5);
copy(vecIntA.begin(),vecIntA.end(),vecIntB.begin());
此时vecIntB也包含了1,3,5,7,9元素
2replace_if : 将指定范围内所有操作结果为true的元素用新值替换。
用法举例：
replace_if(vecIntA.begin(),vecIntA.end(),GreaterThree,newVal)
其中 vecIntA是用vector<int>声明的容器
GreaterThree 函数的原型是 bool GreaterThree(int iNum)
swap: 交换两个容器的元素
2accumulate: 对指定范围内的元素求和，然后结果再加上一个由val指定的初始值。
2fill: 将输入值赋给标志范围内的所有元素。
讲解要点
一、容器的共通能力；
二、各个容器的使用时机；
三、常用算法（Algorithm）的用法介绍。
各个容器的使用时机
adjacent_find()
vector<int>vecInt;
vecInt.push_back(1);
vecInt.push_back(2);
vecInt.push_back(2);
vecInt.push_back(4);
vecInt.push_back(5);
vector<int>::iteratorit = adjacent_find(vecInt.begin(),vecInt.end()); //*it == 2
binary_search
set<int>setInt;
setInt.insert(3);
setInt.insert(1);
setInt.insert(7);
setInt.insert(5);
setInt.insert(9);
boolbFind = binary_search(setInt.begin(),setInt.end(),5);
count()
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);
intiCount =count(vecInt.begin(),vecInt.end(),2); //iCount==3
count_if()
假设vector<int>vecIntA，vecIntA包含1,3,5,7,9元素
//先定义比较函数
bool GreaterThree(int iNum)
{
if(iNum>=3)
{
returntrue;
}
else
{
returnfalse;
}
}
int iCount =count_if(vecIntA.begin(),vecIntA.end(), GreaterThree);
//此时iCount == 4
find()
vector<int> vecInt;
vecInt.push_back(1);
vecInt.push_back(3);
vecInt.push_back(5);
vecInt.push_back(7);
vecInt.push_back(9);
vector<int>::iterator it =find(vecInt.begin(),vecInt.end(),5); //*it ==5
find_if()
假设vector<int>vecIntA，vecIntA包含1,3,5,3,9元素
vector<int>::it=find_if(vecInt.begin(),vecInt.end(),GreaterThree);
此时 *it==3,*(it+1)==5,*(it+2)==3, *(it+3)==9
merge()
例如：vecIntA,vecIntB,vecIntC是用vector<int>声明的容器，vecIntA已包含1,3,5,7,9元素，vecIntB已包含2,4,6,8元素
vecIntC.resize(9); //扩大容量
merge(vecIntA.begin(),vecIntA.end(),vecIntB.begin(),vecIntB.end(),vecIntC.begin());
此时vecIntC就存放了按顺序的1,2,3,4,5,6,7,8,9九个元素
sort()
//学生类
Class CStudent:
{
public:
CStudent(intiID, string strName)
{
m_iID=iID;
m_strName=strName;
}
public:
intm_iID;
stringm_strName;
}
//学号比较函数
bool Compare(const CStudent&stuA,constCStudent &stuB)
{
return (stuA.m_iID<strB.m_iID);
}
void main()
{
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);
// 此时，vecStu容器包含了按顺序的"老大对象","老二对象","老三对象","老四对象"
}
random_shuffle()
srand(time(0)); //设置随机种子
vector<int>vecInt;
vecInt.push_back(1);
vecInt.push_back(3);
vecInt.push_back(5);
vecInt.push_back(7);
vecInt.push_back(9);
stringstr("UIPower");
random_shuffle(vecInt.begin(),vecInt.end()); //随机排序，结果比如：9,7,1,5,3
random_shuffle(str.begin(),str.end()); //随机排序，结果比如："owreUIP"
reverse()
vector<int>vecInt;
vecInt.push_back(1);
vecInt.push_back(3);
vecInt.push_back(5);
vecInt.push_back(7);
vecInt.push_back(9);
reverse(vecInt.begin(),vecInt.end()); //{9,7,5,3,1}
copy()
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.resize(5); //扩大空间
copy(vecIntA.begin(),vecIntA.end(), vecIntB.begin()); //vecIntB:{1,3,5,7,9}
replace()
vector<int>vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(3);
vecIntA.push_back(9);
replace(vecIntA.begin(),vecIntA.end(), 3,8); //{1,8,5,8,9}
replace_if()
//把大于等于3的元素替换成8
vector<int>vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(3);
vecIntA.push_back(9);
replace_if(vecIntA.begin(),vecIntA.end(), GreaterThree,8); //GreaterThree的定义在上面。
swap()
vector<int>vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vector<int>vecIntB;
vecIntB.push_back(2);
vecIntB.push_back(4);
swap(vecIntA,vecIntB); //交换
accumulate()
vector<int>vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);
intiSum = accumulate(vecIntA.begin(), vecIntA.end(),100); //iSum==125
fill()
vector<int>vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);
fill(vecIntA.begin(),vecIntA.end(),8); //8, 8, 8,8, 8
set_union(),set_intersection(),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_union(vecIntA.begin(),vecIntA.end(), vecIntB.begin(), vecIntB.end(),vecIntC.begin()); //vecIntC :{1,3,5,6,7,8,9,0,0,0}
//并集
fill(vecIntC.begin(),vecIntC.end(),0);
set_intersection(vecIntA.begin(),vecIntA.end(), vecIntB.begin(), vecIntB.end(),vecIntC.begin()); //vecIntC:{1,3,5,0,0,0,0,0,0,0}
//差集
fill(vecIntC.begin(),vecIntC.end(),0);
set_difference(vecIntA.begin(),vecIntA.end(), vecIntB.begin(), vecIntB.end(),vecIntC.begin()); //vecIntC:{7,9,0,0,0,0,0,0,0,0}
for_each()
void show(const int &iItem)
{
cout<< iItem;
}
main()
{
intiArray[] = {0,1,2,3,4};
vector<int>vecInt(iArray,iArray+sizeof(iArray)/sizeof(iArray[0]));
for_each(vecInt.begin(),vecInt.end(), show);
//结果打印出0 1 2 3 4
}
transform()
int increase (int i)
{
returni+1;
}
main()
{
vector<int>vecIntA;
vecIntA.push_back(1);
vecIntA.push_back(3);
vecIntA.push_back(5);
vecIntA.push_back(7);
vecIntA.push_back(9);
transform(vecIntA.begin(),vecIntA.end(),vecIntA.begin(),increase); //vecIntA : {2,4,6,8,10}
}
(转)常用算法（Algorithm）的用法介绍