算法主要由
<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; }
全部评论
(0) 回帖