C++ STL 算法

　　STL中给出的算法，大部分定义在头文件algorithm里头，还有一些定义在numeric头文件里头，有时候为了绑定适配器还需要引入头文件functional。STL算法通常配合容器使用，它们之间通过迭代器建立联系。

一、常用的遍历算法

(1)for_each

 1 #include <iostream>
 2 #include <vector>
 3 #include <string>
 4 #include <algorithm>
 5 #include <functional>
 6 using namespace std;
 7 
 8 //普通函数
 9 void PrintTest01(const int &val)
10 {
11     cout << val << " ";
12 }
13 
14 //函数对象
15 class PrintTest01Pro
16 {
17 public:
18     void operator()(int &val) const
19     {
20         cout << val << " ";
21     }
22 };
23 
24 void test01(void)
25 {
26     vector<int> v;
27     for (int i = 0; i < 6; ++i)
28         v.push_back(i+1);
29 
30     //给for_each传入普通函数PrintTest01
31     for_each(v.begin(), v.end(), PrintTest01);
32 
33     cout << endl << "--------------" << endl;
34 
35     //给for_each传入函数对象
36     for_each(v.begin(), v.end(), PrintTest01Pro());
37 }
38 
39 //函数对象
40 class PrintTest02
41 {
42 public:
43     PrintTest02()
44     {
45         mCount = 0;
46     }
47     void operator()(const int &val)
48     {
49         mCount++;
50         cout << val << " ";
51     }
52 public:
53     int mCount;
54 };
55 
56 //for_each返回值：函数对象
57 void test02(void)
58 {
59     vector<int> v;
60     for (int i = 0; i < 6; ++i)
61         v.push_back(i + 1);
62 
63     //给for_each传入普通函数
64     PrintTest02 ret = for_each(v.begin(), v.end(), PrintTest02());
65     cout << endl << "调用次数:" << ret.mCount << endl;
66 }
67 
68 
69 class PrintTest03 : public binary_function<int,string,void>
70 {
71 public:
72     void operator()(int val, string str) const
73     {
74         cout << str << " " << val << endl;
75     }
76 };
77 
78 //for_each绑定参数输出
79 void test03(void)
80 {
81     vector<int> v;
82     for (int i = 0; i < 6; ++i)
83         v.push_back(i + 1);
84 
85     for_each(v.begin(), v.end(), bind2nd(PrintTest03(),string("我是for_each的参数")));
86 }
87 
88 int main(void)
89 {
90     //test01();
91     //test02();
92     //test03();
93     return 0;
94 }

for_each使用方法

(2)transform

  1 #include<iostream>
  2 #include<vector>
  3 #include<string>
  4 #include<algorithm>
  5 #include<functional>
  6 using namespace std;
  7 
  8 class TransformTest01
  9 {
 10 public:
 11     int operator()(int val)
 12     {
 13         //让val加上增量100，但是增量被写死了，不灵活
 14         return val + 100;
 15     }
 16 };
 17 
 18 void test01(void)
 19 {
 20     //vector的元素类型为基本类型
 21     vector<int> v1;
 22     v1.push_back(1);
 23     v1.push_back(2);
 24     v1.push_back(3);
 25 
 26     /* transform不会给目标容器分配内存，所以需要提前分配好内存
 27        分配内存可以使用resize()，不能使用reserve() */
 28     vector<int> v2(v1.size());
 29     
 30     //将v1容器中的元素搬运到v2容器中
 31     transform(v1.begin(), v1.end(), v2.begin(), TransformTest01());
 32 
 33     //输出vector
 34     for_each(v2.begin(), v2.end(), [](int val)->void{ cout << val << " "; });
 35     cout << endl;
 36 }
 37 
 38 class TransformTest02 : public binary_function<int, int, int>
 39 {
 40 public:
 41     int operator()(int val,int addNum) const
 42     {
 43         //让val加上增量addNum
 44         return val + addNum;
 45     }
 46 };
 47 
 48 void test02(void)
 49 {
 50     //vector的元素类型为基本类型
 51     vector<int> v1;
 52     v1.push_back(1);
 53     v1.push_back(2);
 54     v1.push_back(3);
 55 
 56     vector<int> v2(v1.size());
 57 
 58     /* 将v1容器中的元素搬运到v2容器中，搬运过程中让每个
 59        元素加一个指定值,需要绑定适配器 */
 60     transform(v1.begin(), v1.end(), v2.begin(), bind2nd(TransformTest02(),100));
 61 
 62     //输出vector
 63     for_each(v2.begin(), v2.end(), [](int val)->void{ cout << val << " "; });
 64     cout << endl;
 65 }
 66 
 67 class Person
 68 {
 69 public:
 70     Person()
 71     {
 72         mName = "Undefined";
 73         mAge = 0;
 74     }
 75     Person(string name, int age)
 76     {
 77         mName = name;
 78         mAge = age;
 79     }
 80 public:
 81     string mName;
 82     int mAge;
 83 };
 84 
 85 class TransformTest03 : public binary_function<Person,int,Person>
 86 {
 87 public:
 88     Person operator()(Person person, int addAge) const
 89     {
 90         return Person(person.mName, person.mAge + addAge);
 91     }
 92 };
 93 
 94 void test03()
 95 {
 96     //vector的元素类型为自定义类型
 97     vector<Person> v1;
 98     v1.push_back(Person("John", 10));
 99     v1.push_back(Person("Peter", 20));
100     v1.push_back(Person("Marry", 30));
101     v1.push_back(Person("John", 40));
102 
103     vector<Person> v2(v1.size());
104 
105     transform(v1.begin(), v1.end(), v2.begin(), bind2nd(TransformTest03(),20));
106 
107     for (vector<Person>::iterator it = v2.begin(); it != v2.end(); ++it)
108     {
109         cout << "Name:" << it->mName << " Age:" << it->mAge << endl;
110     }
111 }
112 
113 class TransformTest04 : public binary_function<Person*, int, Person*>
114 {
115 public:
116     Person *operator()(Person *person, int addAge) const
117     {
118         return new Person(person->mName, person->mAge + addAge);
119     }
120 };
121 
122 void test04()
123 {
124     //vector容器元素为自定义类型的指针类型
125     vector<Person*> v1;
126     v1.push_back(new Person("John", 10));
127     v1.push_back(new Person("Peter", 20));
128     v1.push_back(new Person("Marry", 30));
129     v1.push_back(new Person("John", 40));
130 
131     vector<Person*> v2(v1.size());
132 
133     transform(v1.begin(), v1.end(), v2.begin(), bind2nd(TransformTest04(), 30));
134 
135     for (vector<Person*>::iterator it = v2.begin(); it != v2.end(); ++it)
136     {
137         cout << "Name:" << (*it)->mName << " Age:" << (*it)->mAge << endl;
138     }
139 }
140 
141 int main(void)
142 {
143     //test01();
144     //test02();
145     //test03();
146     //test04();
147     return 0;
148 }

transform使用方法

二、常用查找算法

(1)find/find_if

  1 #include <iostream>
  2 #include <vector>
  3 #include <string>
  4 #include <algorithm>
  5 #include <functional>
  6 using namespace std;
  7 
  8 //查找基础数据类型
  9 void test01(void)
 10 {
 11     vector<int> v;
 12     v.push_back(10);
 13     v.push_back(20);
 14     v.push_back(30);
 15     v.push_back(40);
 16     /*
 17         find返回值:
 18         1、查找成功，返回指向这个值的迭代器
 19         2、查找失败，返回指向end()的迭代器
 20     */
 21     vector<int>::iterator it = find(v.begin(), v.end(), 40);
 22     if (it != v.end())
 23         cout << "找到了 " << *it << endl;
 24     else
 25         cout << "没找到" << endl;
 26 }
 27 
 28 class Person
 29 {
 30 public:
 31     Person()
 32     {
 33         mName = "Undefined";
 34         mAge = 0;
 35     }
 36     Person(string name,int age)
 37     {
 38         mName = name;
 39         mAge = age;
 40     }
 41     bool operator==(const Person &p)
 42     {
 43         return mName == p.mName && mAge == p.mAge;
 44     }
 45 public:
 46     string mName;
 47     int mAge;
 48 };
 49 
 50 //查找自定义类型对象：需要重载==操作符
 51 void test02(void)
 52 {
 53     vector<Person> v;
 54     v.push_back(Person("John", 10));
 55     v.push_back(Person("Peter", 20));
 56     v.push_back(Person("Snow", 30));
 57     v.push_back(Person("Marry", 40));
 58 
 59     vector<Person>::iterator it = find(v.begin(), v.end(), Person("Marry", 40));
 60     if (it != v.end())
 61         cout << "找到了! Name:" << it->mName << " Age:" << it->mAge << endl;
 62     else
 63         cout << "没找到" << endl;
 64 }
 65 
 66 class search_condition : public binary_function<Person*, Person*, bool>
 67 {
 68 public:
 69     bool operator()(Person *p1, Person *p2)const
 70     {
 71         return p1->mName == p2->mName && p1->mAge == p2->mAge;
 72     }
 73 };
 74 
 75 // find_if 查找指针对象
 76 void test03(void)
 77 {
 78     vector<Person*> v;
 79     Person p1("John", 10);
 80     Person p2("Peter", 20);
 81     Person p3("Snow", 30);
 82     Person p4("Marry", 40);
 83     v.push_back(&p1);
 84     v.push_back(&p2);
 85     v.push_back(&p3);
 86     v.push_back(&p4);
 87 
 88     //find_if函数根据用户提供的search_considtion()和&p2去查找
 89     vector<Person*>::iterator it = find_if(v.begin(), v.end(), bind2nd(search_condition(), &p2));
 90 
 91     if (it != v.end())
 92         cout << "找到了! Name:" << (*it)->mName << " Age:" << (*it)->mAge << endl;
 93     else
 94         cout << "没找到" << endl;
 95 }
 96 
 97 int main(void)
 98 {
 99     //test01();
100     //test02();
101     //test03();
102     return 0;
103 }

find/find_if使用方法

(2)adjacent_find

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 //adjacent_find 查找相邻重复元素;
 7 void test01()
 8 {
 9     vector<int> v;
10     v.push_back(10);
11     v.push_back(20);
12     v.push_back(30);
13     v.push_back(30);
14 
15     vector<int>::iterator it = adjacent_find(v.begin(),v.end());
16     if (it == v.end())
17         cout << "没找到" << endl;
18     else
19         cout << "找到了,相邻重复的元素：" << *it << endl;
20 }
21 
22 
23 int main(void)
24 {
25     //test01();
26     return 0;
27 }

adjacent_find使用方法

(3)binary_search

 1 #include <iostream>
 2 #include <vector>
 3 #include <string>
 4 #include <algorithm>
 5 #include <functional>
 6 using namespace std;
 7 
 8 //binary_search二分查找法 需要序列有序的，找到了返回值true，未找到返回false
 9 void test01(void)
10 {
11     vector<int> v;
12     for (int i = 1; i <= 10; ++i)
13         v.push_back(i*i);
14     if (true == binary_search(v.begin(), v.end(), 64))
15         cout << "找到了" << endl;
16     else
17         cout << "未找到" << endl;
18 
19 }
20 
21 class Person
22 {
23 public:
24     Person()
25     {
26         mName = "Undefined";
27         mAge = 0;
28     }
29     Person(string name, int age)
30     {
31         mName = name;
32         mAge = age;
33     }
34     bool operator<(const Person &p) const 
35     {
36         if (mName == p.mName)
37         {
38             return mAge < p.mAge;
39         }
40         return mName < p.mName;
41     }
42 public:
43     string mName;
44     int mAge;
45 };
46 
47 //二分查找自定义类型对象：需要重载<操作符,重载函数为const函数
48 void test02(void)
49 {
50     vector<Person> v;
51     v.push_back(Person("John", 10));
52     v.push_back(Person("Peter", 20));
53     v.push_back(Person("Snow", 30));
54     v.push_back(Person("Marry", 40));
55 
56     if (true == binary_search(v.begin(), v.end(), Person("Peter", 20)))
57         cout << "找到了"<< endl;
58     else
59         cout << "没找到" << endl;
60 }
61 
62 int main(void)
63 {
64     //test01();
65     //test02();
66     return 0;
67 }

binary_search使用方法

(4)count/count_if

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <functional>
 5 using namespace std;
 6 
 7 class GreaterThanTwo
 8 {
 9 public:
10     bool operator()(int v)
11     {
12         return v > 10;
13     }
14 };
15 
16 class GreaterThanNumPro : public binary_function<int, int, bool>
17 {
18 public:
19     bool operator()(int v,int num) const
20     {
21         return v > num;
22     }
23 };
24 
25 //count count_if 统计元素的个数
26 void test01(void)
27 {
28     vector<int> v;
29     v.push_back(10);
30     v.push_back(10);
31     v.push_back(20);
32     v.push_back(21);
33     v.push_back(22);
34     v.push_back(10);
35 
36     //统计元素中为10的元素个数
37     int num = count(v.begin(), v.end(), 10);
38     cout << "10的个数为" << num << endl;
39 
40     //统计大于10的元素个数
41     num = count_if(v.begin(), v.end(), GreaterThanTwo());
42     cout << "大于10的元素个数为" << num << endl;
43 
44     //统计大于number的元素个数
45     int number = 20;
46     num = count_if(v.begin(), v.end(), bind2nd(GreaterThanNumPro(), number));
47     cout << "大于10的元素个数为" << num << endl;
48 }
49 
50 int main(void)
51 {
52     //test01();
53     return 0;
54 }

count/count_if使用方法

三、常用排序算法

(1)merge

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <functional>
 5 using namespace std;
 6 
 7 //merge 合并两个有序序序列,默认从小到大排序
 8 void test01()
 9 {
10     vector<int> v1; 
11     vector<int> v2;
12     for (int i = 1; i <= 5; ++i)
13     {
14         v1.push_back(i);
15         v2.push_back(i + 2);
16     }
17     vector<int> vTarget(v1.size()+v2.size());
18 
19     merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());
20 
21     //输出vTarget
22     for_each(vTarget.begin(), vTarget.end(), [](int val)->void{cout << val << " "; } );
23 
24 }
25 
26 class MyCompare
27 {
28 public:
29     bool operator()(int v1, int v2)
30     {
31         return v1 > v2;
32     }
33 };
34 
35 //merge 改变默认排序规则，按照从大到小排序
36 void test02()
37 {
38     vector<int> v1;
39     vector<int> v2;
40     for (int i = 5; i > 0; --i)
41     {
42         v1.push_back(i);
43         v2.push_back(i+3);
44     }
45     vector<int> vTarget(v1.size() + v2.size());
46 
47     merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin(), MyCompare());
48 
49     //输出vTarget
50     for_each(vTarget.begin(), vTarget.end(), [](int val)->void{cout << val << " "; });
51 }
52 
53 int main(void)
54 {
55     //test01();
56     //test02();
57     return 0;
58 }

merge使用方法

(2)sort

 1 //sort算法：使用sort算法，容器必须支持随机访问。list不能用sort算法
 2 #include <iostream>
 3 #include <vector>
 4 #include <algorithm>
 5 #include <functional>
 6 using namespace std;
 7 
 8 void test01(void)
 9 {
10     vector<int> v;
11     v.push_back(10);
12     v.push_back(70);
13     v.push_back(50);
14     v.push_back(20);
15 
16     //sort默认按照从小到大排序
17     sort(v.begin(), v.end());
18     for_each(v.begin(), v.end(), [](int val)->void{cout << val << " "; });
19     cout << endl;
20     sort(v.begin(), v.end(),greater<int>());
21     for_each(v.begin(), v.end(), [](int val)->void{cout << val << " "; });
22     cout << endl;
23 }
24 
25 int main(void)
26 {
27         //test01();
28     return 0;
29 }

sort使用方法

(3)random_shuffle

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <functional>
 5 using namespace std;
 6 
 7 //random_shuffle 洗牌，打乱容器中元素的次序
 8 void test01()
 9 {
10     vector<int> v;
11     v.push_back(11);
12     v.push_back(76);
13     v.push_back(13);
14     v.push_back(89);
15     v.push_back(52);
16     v.push_back(48);
17 
18     for_each(v.begin(), v.end(), [](int val){cout << val << " "; }); cout << endl;
19     random_shuffle(v.begin(), v.end());
20     for_each(v.begin(), v.end(), [](int val){cout << val << " "; }); cout << endl;
21 }
22 
23 int main(void)
24 {
25     //test01();
26      return 0;
27 }

random_shuffle使用方法

(4)reverse

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <functional>
 5 using namespace std;
 6 
 7 void test01()
 8 {
 9     vector<int> v;
10     v.push_back(1);
11     v.push_back(2);
12     v.push_back(3);
13     v.push_back(4);
14     v.push_back(5);
15     v.push_back(6);
16 
17     for_each(v.begin(), v.end(), [](int val){cout << val << " "; }); cout << endl;
18     reverse(v.begin(), v.end());
19     for_each(v.begin(), v.end(), [](int val){cout << val << " "; }); cout << endl;
20 }
21 
22 int main(void)
23 {
24     test01();
25     return 0;
26 }

reverse使用方法

四、常用拷贝和替换算法

(1)copy/copy_if

 1 #include<iostream>
 2 #include<vector>
 3 #include<functional>
 4 #include<algorithm>
 5 #include<iterator>
 6 using namespace std;
 7 
 8 //copy
 9 void test01(void)
10 {
11     vector<int> v1;
12     for (int i = 0; i < 10; i++){
13         v1.push_back(i + 1);
14     }
15     vector<int> v2;
16     v2.resize(v1.size());
17     copy(v1.begin(), v1.end(), v2.begin());
18     copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
19 }
20 
21 class CopyCondition : public binary_function<int, int , bool>
22 {
23 public:
24     bool operator()(int v1, int num) const
25     {
26         return v1 == num;
27     }
28 };
29 
30 //copy_if：按照用户传入的函数对象来拷贝
31 void test02()
32 {
33     vector<int> v1;
34     for (int i = 0; i < 10; i++){
35         v1.push_back(i + 1);
36     }
37     vector<int> v2;
38     v2.resize(v1.size());
39     int num = 3;
40     copy_if(v1.begin(), v1.end(), v2.begin(), bind2nd(CopyCondition(),num));
41     copy(v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));
42 }
43 
44 int main(void)
45 {
46     //test02();
47     return 0;
48 }

copy/copy_if使用方法

(2)replace/replace_if

 1 #include<iostream>
 2 #include<vector>
 3 #include<functional>
 4 #include<algorithm>
 5 #include<iterator>
 6 using namespace std;
 7 
 8 //replace
 9 void test01()
10 {
11     vector<int> v;
12     v.push_back(2);
13     v.push_back(7);
14     v.push_back(2);
15     v.push_back(9);
16     v.push_back(10);
17     v.push_back(3);
18     v.push_back(0);
19 
20     replace(v.begin(),v.end(),10,1000);
21 
22     //输出vector
23     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
24 }
25 
26 
27 bool ReplaceCondition(int v){
28     return v > 2;
29 }
30 
31 //replace_if：按照用户提供的函数指针来进行替换
32 void test02(void)
33 {
34     vector<int> v1;
35     v1.push_back(2);
36     v1.push_back(7);
37     v1.push_back(2);
38     v1.push_back(9);
39     v1.push_back(10);
40     v1.push_back(3);
41     v1.push_back(0);
42 
43     replace_if(v1.begin(), v1.end(), ReplaceCondition, 100);
44 
45     //输出替换后的vector
46     copy(v1.begin(), v1.end(), ostream_iterator<int>(cout, " "));
47 }
48 
49 int main(void)
50 {
51     //test01();
52     //test02();
53     return 0;
54 }

replace/replace_if使用方法

(3)swap

 1 #include<iostream>
 2 #include<vector>
 3 #include<functional>
 4 #include<algorithm>
 5 #include<iterator>
 6 using namespace std;
 7 
 8 void test01()
 9 {
10     vector<int> v1;
11     vector<int> v2;
12     for (int i = 0; i < 10; i++){
13         v1.push_back(i + 1);
14         v2.push_back(i);
15     }
16 
17     for_each(v1.begin(), v1.end(), [](int val){cout << val << " "; }); cout << endl;
18     for_each(v2.begin(), v2.end(), [](int val){cout << val << " "; }); cout << endl;
19     swap(v1, v2);
20     cout << "------------" << endl;
21     for_each(v1.begin(), v1.end(), [](int val){cout << val << " "; }); cout << endl;
22     for_each(v2.begin(), v2.end(), [](int val){cout << val << " "; }); cout << endl;
23 }
24 
25 int main(void)
26 {
27     test01();
28     return 0;
29 }

swap使用方法

五、常用的算数生成算法

(1)accumulate

 1 #include <iostream>
 2 #include <vector>
 3 #include <numeric> /* accumulate() */
 4 using namespace std;
 5 
 6 void test01()
 7 {
 8     vector<int> v;
 9     for (int i = 0; i <= 100; i++){
10         v.push_back(i);
11     }
12 
13     int total = accumulate(v.begin(), v.end(), 0);
14     cout << "total:" << total << endl;
15 }
16 
17 int main(void)
18 {
19     test01();
20     return 0;
21 }

accumulate使用方法

(2)fill

 1 #include <iostream>
 2 #include <vector>
 3 #include <functional>
 4 #include <algorithm>
 5 #include <iterator>
 6 #include <numeric> /* accumulate() */
 7 using namespace std;
 8 
 9 void test01()
10 {
11     vector<int> v;
12     v.resize(10);
13     fill(v.begin(), v.end(), 100);
14     copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
15 }
16 
17 int main(void)
18 {
19     test01();
20     return 0;
21 }

fill使用方法

六、常用集合算法

(1)set_intersection/set_union/set_difference

 1 #include<iostream>
 2 #include<vector>
 3 #include<functional>
 4 #include<iterator>
 5 #include<algorithm>
 6 using namespace std;
 7 
 8 //求交集 set_intersection
 9 void test01(void)
10 {
11     vector<int> v1;
12     vector<int> v2;
13     for (int i = 0; i < 10; ++i)
14         v1.push_back(i);
15     for (int i = 5; i < 15; ++i)
16         v2.push_back(i);
17     vector<int> v3(v1.size() + v2.size());
18     vector<int>::iterator MyEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
19     copy(v3.begin(), MyEnd, ostream_iterator<int>(cout, " "));
20 }
21 
22 //求并集 set_union
23 void test02()
24 {
25     vector<int> v1;
26     vector<int> v2;
27     for (int i = 0; i < 10; ++i)
28         v1.push_back(i);
29     for (int i = 5; i < 15; ++i)
30         v2.push_back(i);
31     vector<int> v3(v1.size() + v2.size());
32     vector<int>::iterator MyEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
33     copy(v3.begin(), MyEnd, ostream_iterator<int>(cout, " "));
34 }
35 
36 //求差集 set_difference
37 void test03()
38 {
39     vector<int> v1;
40     vector<int> v2;
41     for (int i = 0; i < 10; ++i)
42         v1.push_back(i);
43     for (int i = 5; i < 15; ++i)
44         v2.push_back(i);
45     vector<int> v3(v1.size() + v2.size());
46     vector<int>::iterator MyEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
47     copy(v3.begin(), MyEnd, ostream_iterator<int>(cout, " "));
48 }
49 
50 int main(void)
51 {
52     //test01();
53     //test02();
54     test03();
55     return 0;
56 }

set_intersection/set_union/set_difference使用方法