stl算法
算法主要由
<algorithm>是所有stl头文件中最大的一个，其中涉及功能到比较，交换，查找边历，复制，修改，反转，排序，合并等
<numeric>体积很小，只包括在几个序列容器上进行简单运算的模板函数
<functional>定义了一些模板类，用以声明函数对象
1、常用边历算法
for_each算法
- 正向遍历，逆向遍历
- for_each绑定参数
- for_each修改元素值
- for_each返回值
transform算法
容器，目标容器，算法；
#include<algorithm>
#include<iostream>
#include<vector>
#include<functional>
#include<numeric>
using namespace std;
//for_each算法
class print{
public:
print() :count(0){}
void operator()(int v){
cout << v << " ";
}
int count;
};
void test01()
{
vector<int> v;
for (int i = 0; i < 10; i++)
{
v.push_back(i);
}
/*
template<class _InIt,
class _Fn1> inline
_Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
{ // perform function for each element
_DEBUG_RANGE(_First, _Last);
_DEBUG_POINTER(_Func);
_For_each(_Unchecked(_First), _Unchecked(_Last), _Func);
return (_STD move(_Func));
}*/
//他是拷贝过来的
print p1;
print p2=for_each(v.begin(), v.end(), p1);
cout << endl;
cout << "count:" << p1.count << endl;
cout << "count:" << p2.count << endl;
}
//transform算法
class myplus100{
int operator()(int v){
return v + 100;
}
};
class myminute{
public:
int operator()(int v1, int v2){
return v2 - v1;
}
};
void test02()
{
/*
vector<int> v1,v2;
for (int i = 0; i < 10; i++)
{
v1.push_back(i);
}
//第一种方式，一个容器经过运算，把结果放进目标容器v2
v2.resize(v1.size());
for_each(v2.begin(), v2.end(), print());
cout << endl;
transform(v1.begin(), v1.end(), v2.begin(), myplus100());
for_each(v2.begin(), v2.end(), print());
cout << endl;*/
//第二种方式
vector<int> v3, v4, v5;
for (int i = 0; i < 10; i++)
{
v3.push_back(i);
v4.push_back(i+1);
}
v5.resize(v3.size());
for_each(v5.begin(), v5.end(), print());
cout << endl;
transform(v3.begin(), v3.end(), v4.begin(), v5.begin(), myminute());
for_each(v5.begin(), v5.end(), print());
cout << endl;
}
int main()
{
test02();
return EXIT_SUCCESS;
} 2、常用的查找算法 - find算法
- find_if算法
- count算法
- count_if算法
- adiacent_find算法，返回相零的重复元素出现的第一个位置
- binary_search算法，二分查找法，需要容器中元素有序，需要排序
-
#include<iostream> #include<numeric> #include<vector> #include<algorithm> using namespace std; class print{ public: void operator()(int v){ /*if (v!=0) cout << v << " "; */ cout << v << " "; } }; //find void test01() { vector<int> v; v.push_back(8); v.push_back(4); v.push_back(5); v.push_back(3); /* template<class _InIt, class _Ty> inline _InIt find(_InIt _First, _InIt _Last, const _Ty& _Val) { // find first matching _Val _DEBUG_RANGE(_First, _Last); return (_Rechecked(_First, _Find(_Unchecked(_First), _Unchecked(_Last), _Val))); }*/ vector<int>::iterator pos = find(v.begin(), v.end(), 4); if (pos == v.end()) { cout << "没有找到" << endl; } else { cout << *pos << endl; } //for_each(v.begin(), v.end(), print()); } class student{ public: student(int id, int age) :id(id), age(age){} int id; int age; bool operator==(const student& s){ if (this->id == s.id && this->age == age) { return true; } else { return false; } return this->id == s.id && this->age == s.age; } }; //查找对象 void test02() { vector<student> v; student s1(1, 2), s2(3, 4), s3(5, 6); v.push_back(s1); v.push_back(s2); v.push_back(s3); vector<student>::iterator pos = find(v.begin(), v.end(), s1); if (pos != v.end()){ cout << "zhaodao" << pos->age <<" "<< pos->id << endl; } else{ cout << "没有找到" << endl; } } //find_if class mycompare03{ public: bool operator()(int v){ if (v > 2){ return true; } else{ return false; } } }; void test03() { vector<int> v; v.push_back(8); v.push_back(4); v.push_back(5); v.push_back(3); //find_if(v.begin(), v.end(), mycompare03()); vector<int>::iterator pos = find_if(v.begin(), v.end(), mycompare03()); if (pos == v.end()) { cout << "没有找到" << endl; } else { cout << *pos << endl; } } //ad_jacent_find查找相邻重复元素，并返回第一个重复元素出现的位置 void test04() { vector<int> v; v.push_back(8); v.push_back(4); v.push_back(4); v.push_back(5); v.push_back(3); /*_FwdIt adjacent_find(_FwdIt _First, _FwdIt _Last, _Pr _Pred) { // find first satisfying _Pred with successor _DEBUG_RANGE(_First, _Last); _DEBUG_POINTER(_Pred); return (_Rechecked(_First, _Adjacent_find(_Unchecked(_First), _Unchecked(_Last), _Pred))); }*/ vector<int>::iterator pos = adjacent_find(v.begin(), v.end()); if (pos == v.end()) { cout << "没有找到" << endl; } else { cout << *pos << endl; } } //binary_search二分查找法 void test05() { //binary_search需要对有序的元素查找 vector<int> v; v.push_back(8); v.push_back(4); v.push_back(5); v.push_back(3); sort(v.begin(), v.end()); /*template<class _FwdIt, class _Ty> inline bool binary_search(_FwdIt _First, _FwdIt _Last, const _Ty& _Val) { // test if _Val equivalent to some element, using operator< return (_STD binary_search(_First, _Last, _Val, less<>())); }*/ bool flag = binary_search(v.begin(), v.end(),11); if (flag) { cout << flag << endl; } else { cout << "没有找到" << endl; } } class mycompare06{ public: bool operator()(int v){ return v > 2; } }; //count count_if void test06() { //统计那个元素出现的次数 vector<int> v; v.push_back(3); v.push_back(8); v.push_back(4); v.push_back(5); v.push_back(3); sort(v.begin(), v.end()); int n=count(v.begin(), v.end(),3); cout << "n" << n << endl; n = count_if(v.begin(), v.end(), mycompare06()); cout << "n" << n << endl; } int main() { test06(); return EXIT_SUCCESS; }
3、常用的排序算法（需要容器支持随机访问，list不可以）
- sort算法
- merge算法（将两个容器中元素合并，放在第三个容器中，两个容器中元素必须是有序的）
- merge(iterator beg,iterator end,iterator beg,iterator end,iterator dest)
- random_shuffle算法（将容器元素打乱）
- reverse算法（将容器中元素反转）
4、常用的拷贝替换算法
- copy算法
- replace算法（替换）
- replace(iterator beg,iterator end,oldvalue,newvalue)
- replace_if算法（把所有满足条件的元素全部替换）
- swap算法（交换）
#include<iostream>
#include<numeric>
#include<vector>
#include<algorithm>
using namespace std;
class print{
public:
void operator()(int v){
/*if (v!=0)
cout << v << " ";
*/
cout << v << " ";
}
};
//copy
void test01()
{
vector<int> v1, v2;
for (int i = 0; i <= 10; i++)
{
v1.push_back(i);
}
v2.resize(v1.size());
copy(v1.begin(), v1.end(), v2.begin());
for_each(v2.begin(), v2.end(), print());
}
//replace
class mycompare02{
public:
bool operator() (int v){
return v > 5;
}
};
void test02()
{
vector<int> v1;
for (int i = 0; i <= 10; i++)
{
v1.push_back(i);
}
for_each(v1.begin(), v1.end(), print());
cout << endl;
replace(v1.begin(), v1.end(), 3, 100);
for_each(v1.begin(), v1.end(), print());
cout << endl;
//replace_if
replace_if(v1.begin(), v1.end(), mycompare02(), 365);
for_each(v1.begin(), v1.end(), print());
cout << endl;
//swap
vector<int> v2;
for (int i = 0; i <= 10; i++)
{
v2.push_back(i);
}
cout << "swap front ::" << endl;
for_each(v2.begin(), v2.end(), print());
swap(v1, v2);
cout << endl;
cout << "swap back ::" << endl;
for_each(v2.begin(), v2.end(), print());
}
int main()
{
test02();
return EXIT_SUCCESS;
} 6、常用的算术生成算法<numeric>
accumulate算法（将容器中元素累加）
fill算法
#include<iostream>
#include<numeric>
#include<vector>
#include<algorithm>
using namespace std;
void test01()
{
vector<int> v;
for (int i=0; i <= 100; i++)
{
v.push_back(i);
}
//将元素中的值加完再加100
int a=accumulate(v.begin(), v.end(), 100);
cout << "n" << a<< endl;
}
class print{
public:
void operator()(int v){
cout << v << " ";
}
};
void test02()
{
vector<int> v;
v.resize(100);//reserve(100)只开空间，未初始化
fill(v.begin(), v.end(), 100);
cout << "size" << v.size()<< endl;
for_each(v.begin(), v.end(), print());
}
int main()
{
test02();
return EXIT_SUCCESS;
} 7、常用的集合算法
set_intersection算法（求交集）
set_union算法（并集）
set_difference算法（求两个集合的差集）
#include<iostream>
#include<numeric>
#include<vector>
#include<algorithm>
using namespace std;
class print{
public:
void operator()(int v){
/*if (v!=0)
cout << v << " ";
*/
}
};
//求两个集合的交集
void test01()
{
vector<int> v1,v2,v3;
for (int i=0; i <= 10; i++)
{
v1.push_back(i);
}
for (int i = 12; i <= 30; i++)
{
v2.push_back(i);
}
v3.resi***(v1.size(), v2.size()));
//迭代器指向最后一个元素的shang一个位置
vector<int>::iterator myEnd=set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(),v3.begin());
for_each(v3.begin(),myEnd, print());
}
//求两个元素的并集
void test02()
{
vector<int> v1, v2, v3;
for (int i = 0; i <= 10; i++)
{
v1.push_back(i);
}
for (int i = 12; i <= 30; i++)
{
v2.push_back(i);
}
v3.resi***(v1.size(), v2.size()));
//迭代器指向最后一个元素的shang一个位置
vector<int>::iterator myEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
for_each(v3.begin(), v3.end(), print());
for_each(v3.begin(), myEnd, print());
}
void print3(int v){
cout << v << " ";
}
void test03()
{
vector<int> v1, v2, v3;
for (int i = 0; i <= 10; i++)
{
v1.push_back(i);
}
for (int i = 4; i <= 14; i++)
{
v2.push_back(i);
}
v3.resize(v1.size());
//v3.resize(max(v1.size(), v2.size()));
//迭代器指向最后一个元素的shang一个位置
set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
for_each(v3.begin(), v3.end(), print3);
cout << endl;
vector<int>::iterator myEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
for_each(v3.begin(), myEnd, print3);
}
int main()
{
//test02();
test03();
return EXIT_SUCCESS;
} 8、distace逆序算法
deque根据迭代器求数组下标distance（）
两个迭代器之间的距离
迭代器本身是指针来用
#include<iostream>
#include<numeric>
#include<vector>
#include<algorithm>
using namespace std;
class print{
public:
void operator()(int v){
cout << v << " ";
}
};
//distance
void test01()
{
vector<int> v;
for (int i=0; i <= 10; i++)
{
v.push_back(i);
}
for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
{
int index = distance(v.begin(), it);
cout << v[index]<<" ";
}
}
//for_each修改容器元素的值
void print(int& v){
v = v + 100;
}
void print2(const int& v)
{
cout << v << " ";
}
void test02()
{
vector<int> v;
for (int i = 0; i <= 10; i++)
{
v.push_back(i);
}
for_each(v.begin(), v.end(), print2);
cout << endl;
for_each(v.begin(), v.end(), print);
cout << endl;
for_each(v.begin(), v.end(), print2);
cout << endl;
}
//for_each逆向遍历
void test03()
{
vector<int> v;
for (int i = 0; i <= 10; i++)
{
v.push_back(i);
}
for_each(v.begin(), v.end(), print2);
cout << endl;
for_each(v.rbegin(), v.rend(), print2);
cout << endl;
//for_each(v.rbegin(), v.rend(), print2);
}
int main()
{
//test02();
test03();
return EXIT_SUCCESS;
} 