C++ 进阶基础之十一

发表于 更新于 阅读次数： 评论数： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

大纲

算法

算法的基本概念

算法的简介

函数库对数据类型的选择对其可重用性起着至关重要的作用。举例来说，一个求方根的函数，在使用浮点数作为其参数类型的情况下的可重用性肯定比使用整型作为它的参数类性要高。而 C++ 通过模板的机制允许推迟对某些类型的选择，直到真正想使用模板或者说对模板进行特化的时候，STL 就利用了这一点提供了相当多的算法。它是在一个有效的框架中完成这些算法的 —— 可以将所有的类型划分为少数的几类，然后就可以在模板的参数中使用一种类型替换掉同一种类中的其他类型。

算法的头文件

STL 提供了大约 100 个实现算法的函数模板，比如算法 for_each 将为指定序列中的每一个元素调用指定的函数，stable_sort 以调用者所指定的规则对序列进行稳定性排序等等。这样一来，只要熟悉了 STL 之后，许多代码可以被大大地简化，只需要通过调用一两个算法模板，就可以完成所需要的功能。算法主要由头文件 <algorithm>、<numeric>、<functional> 组成。<algorithm> 是所有 STL 头文件中最大的一个，它是由一大堆函数模板组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历、复制、修改、移除、反转、排序、合并操作等。<numeric> 的体积很小，只包括几个在序列上面进行简单数学运算的函数模板，包括加法和乘法在序列上的一些操作。<functional> 中则定义了一些类模板，用来声明函数对象。

常用算法的使用

常用的遍历算法

for_each
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
/**
 * for_each 算法，遍历容器元素
 * @param beg 开始迭代器
 * @param end 结束迭代器
 * @param callback 普通函数或者函数对象
 * @return 函数对象
*/
for_each(iterator beg, iterator end, callback) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>

using namespace std;

// 普通函数
void myPrint(int v) {
    cout << v << " ";
}

// 函数对象
class MyPrint {

public:
    void operator()(const int &v) {
        cout << v << " ";
    }

};

// 函数对象
class MyPrint2 {

public:
    void operator()(const int &v) {
        cout << v << " ";
        count++;
    }

    int count;

};

// 函数对象
class MyPrint3 : public binary_function<int, int, void> {

public:
    void operator()(int v, int start) const {
        cout << v + start << " ";
    }

};

int main() {

    vector<int> v;

    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

    // for_each 使用普通函数
    for_each(v.begin(), v.end(), myPrint);

    cout << endl;

    // for_each 使用匿名函数
    for_each(v.begin(), v.end(), [](int value) { cout << value << " "; });

    cout << endl;

    // for_each 使用函数对象
    for_each(v.begin(), v.end(), MyPrint());

    cout << endl;

    // for_each 拥有返回值（基于函数对象），可用于保存内部记录
    MyPrint2 myPrint2 = for_each(v.begin(), v.end(), MyPrint2());
    cout << endl << "count = " << myPrint2.count << endl;

    // for_each 可以绑定参数进行输出（基于函数适配器）
    for_each(v.begin(), v.end(), bind2nd(MyPrint3(), 100));

    return 0;
}

程序运行输出的结果如下：

1
2
3
4
5
6
0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9 
count = 10
100 101 102 103 104 105 106 107 108 109
transform
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
11
12
/**
 * transform 算法，将指定容器区间元素搬运到另一个容器中
 * 注意：transform 算法不会给目标容器分配内存空间，所以需要开发者提前手动分配好内存空间
 * @param beg1 源容器的开始迭代器
 * @param end1 源容器的结束迭代器
 * @param beg2 目标容器的开始迭代器
 * @param callback 普通函数或者函数对象
 * @return 函数对象
*/
transform(iterator beg1, iterator end1, iterator beg2, callback) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// 函数对象
class MyTransForm {

public:
    int operator()(int val) {
        return val + 10;
    }

};

// 第一种使用方法
void test01() {
    cout << "----------- transform 的第一种用法 -------------" << endl;

    // 源容器
    vector<int> vOrigin;
    for (int i = 0; i < 10; i++) {
        vOrigin.push_back(i);
    }

    // 遍历打印
    for_each(vOrigin.begin(), vOrigin.end(), [](int value) { cout << value << " "; });

    cout << endl;

    // 目标容器
    vector<int> vTarget;
    // 手动分配内存空间
    vTarget.resize(vOrigin.size());
    // 将指定容器区间元素搬运到另一个容器中
    transform(vOrigin.begin(), vOrigin.end(), vTarget.begin(), MyTransForm());

    // 遍历打印
    for_each(vTarget.begin(), vTarget.end(), [](int value) { cout << value << " "; });

    cout << endl;
}

// 函数对象
class MyTransForm2 {

public:
    int operator()(int val1, int val2) {
        return val1 + val2;
    }

};

// 第二种使用方法
void test02() {

    cout << "----------- transform 的第二种用法 -------------" << endl;

    // 源容器
    vector<int> vOrigin1;
    vector<int> vOrigin2;

    int size = 10;
    for (int i = 0; i < size; i++) {
        vOrigin1.push_back(100 + i);
        vOrigin2.push_back(200 + i);
    }

    // 遍历打印
    for_each(vOrigin1.begin(), vOrigin1.end(), [](int value) { cout << value << " "; });

    cout << endl;

    // 遍历打印
    for_each(vOrigin2.begin(), vOrigin2.end(), [](int value) { cout << value << " "; });

    cout << endl;

    // 目标容器
    vector<int> vTarget;
    // 手动分配内存空间
    vTarget.resize(size);
    // 将两个源容器的数据相加，然后搬运到目标容器
    transform(vOrigin1.begin(), vOrigin1.end(), vOrigin2.begin(), vTarget.begin(), MyTransForm2());

    // 遍历打印
    for_each(vTarget.begin(), vTarget.end(), [](int value) { cout << value << " "; });

}

int main() {
    test01();
    test02();
    return 0;
}

程序运行输出的结果如下：

1
2
3
4
5
6
7
----------- transform 的第一种用法 -------------
0 1 2 3 4 5 6 7 8 9 
10 11 12 13 14 15 16 17 18 19 
----------- transform 的第二种用法 -------------
100 101 102 103 104 105 106 107 108 109 
200 201 202 203 204 205 206 207 208 209 
300 302 304 306 308 310 312 314 316 318

常用的查找算法

find
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
/**
 * find 算法，查找元素
 * @param beg 容器开始迭代器
 * @param end 容器结束迭代器
 * @param value 查找的元素
 * @return 返回查找元素的位置
*/
find(iterator beg, iterator end, value) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>

using namespace std;

// 自定义数据类型
class Person {

public:

    Person(string name, int age) {
        this->name = name;
        this->age = age;
    }

    string getName() const {
        return this->name;
    }

    int getAge() const {
        return this->age;
    }

    // 重载 == 操作符
    bool operator==(const Person &p) {
        return this->name == p.name && this->age == p.age;
    }

private :

    string name;
    int age;

};

void test01() {
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

    // 查找基础数据类型
    vector<int>::iterator pos = find(v.begin(), v.end(), 5);
    if (pos != v.end()) {
        cout << "found value for " << *pos << endl;
    } else {
        cout << "not found value" << endl;
    }
}

void test02() {
    vector<Person> v;

    Person p1("Jim", 15);
    Person p2("Peter", 18);
    Person p3("David", 16);
    Person p4("Tom", 20);

    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);

    // 查找自定义数据类型
    // 自定义数据类型必须重载 == 操作符
    vector<Person>::iterator pos = find(v.begin(), v.end(), p2);
    if (pos != v.end()) {
        cout << "found person for " << pos->getName() << ", age is " << pos->getAge() << endl;
    } else {
        cout << "not found person" << endl;
    }
}

int main() {
    test01();
    test02();
    return 0;
}

程序运行输出的结果如下：

1
2
found value for 5
found person for Peter, age is 18
find_if
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
/**
 * find_if 算法，根据条件查找
 * @param beg 容器开始迭代器
 * @param end 容器结束迭代器
 * @param callback 普通函数或者谓词（返回值为 bool 类型的函数对象）
 * @return 返回查找元素的位置
*/
find_if(iterator beg, iterator end, callback) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>

using namespace std;

// 自定义数据类型
class Person {

public:

    Person(string name, int age) {
        this->name = name;
        this->age = age;
    }

    string getName() const {
        return this->name;
    }

    int getAge() const {
        return this->age;
    }

    // 重载 == 操作符
    bool operator==(const Person &p) {
        return this->name == p.name && this->age == p.age;
    }

private :

    string name;
    int age;

};

// 函数对象
class MyPersonCompare : public binary_function<Person *, Person *, bool> {

public:

    // 重载 () 操作符
    bool operator()(Person *p1, Person *p2) const {
        return p1->getName() == p2->getName() && p1->getAge() == p2->getAge();
    }

};

// 普通函数
bool MyCompare(Person &p) {
    return p.getName() == "Peter" && p.getAge() == 18;
}

void test01() {
    vector<Person> v;

    Person p1("Jim", 15);
    Person p2("Peter", 18);
    Person p3("David", 16);
    Person p4("Tom", 20);

    v.push_back(p1);
    v.push_back(p2);
    v.push_back(p3);
    v.push_back(p4);

    // 根据条件查找（使用普通函数）
    vector<Person>::iterator pos = find_if(v.begin(), v.end(), MyCompare);
    if (pos != v.end()) {
        cout << "found person for " << pos->getName() << ", age is " << pos->getAge() << endl;
    } else {
        cout << "not found person" << endl;
    }
}

void test02() {
    vector<Person *> v;

    Person p1("Jim", 15);
    Person p2("Peter", 18);
    Person p3("David", 16);
    Person p4("Tom", 20);

    v.push_back(&p1);
    v.push_back(&p2);
    v.push_back(&p3);
    v.push_back(&p4);

    Person *p5 = new Person("David", 16);

    // 根据条件查找（使用函数对象）
    vector<Person *>::iterator pos = find_if(v.begin(), v.end(), bind2nd(MyPersonCompare(), p5));
    if (pos != v.end()) {
        cout << "found person for " << (*pos)->getName() << ", age is " << (*pos)->getAge() << endl;
    } else {
        cout << "not found person" << endl;
    }
}

int main() {
    test01();
    test02();
    return 0;
}

程序运行输出的结果如下：

1
2
found person for Peter, age is 18
found person for David, age is 16
adjacent_find
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
/**
 * adjacent_find 算法，查找相邻重复元素
 * @param beg 容器开始迭代器
 * @param end 容器结束迭代器
 * @param callback 普通函数或者谓词（返回值为 bool 类型的函数对象）
 * @return 返回相邻元素的第一个位置的迭代器
*/
adjacent_find(iterator beg, iterator end, callback) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v;

    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(5);
    v.push_back(6);
    v.push_back(2);

    // 查找相邻重复元素
    vector<int>::iterator pos = adjacent_find(v.begin(), v.end());
    if (pos != v.end()) {
        cout << *pos << ", " << *pos++ << endl;
    } else {
        cout << "not found element" << endl;
    }

    return 0;
}

程序运行输出的结果如下：

1
5, 5
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
11
/**
 * binary_search 算法，二分法查找
 * 注意：在无序序列中不可用
 * @param beg 容器开始迭代器
 * @param end 容器结束迭代器
 * @param value 查找的元素
 * @return 查找返回 true 或者 false
*/
binary_search(iterator beg, iterator end, value) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v;

    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

    // 二分法查找元素
    bool result = binary_search(v.begin(), v.end(), 5);
    if (result) {
        cout << "find number for 5" << endl;
    } else {
        cout << "not found number for 5" << endl;
    }

    return 0;
}

程序运行输出的结果如下：

1
find number for 5
count
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
/**
 * count 算法，统计元素出现次数
 * @param beg 容器开始迭代器
 * @param end 容器结束迭代器
 * @param value 查找的元素
 * @return 返回元素个数
*/
count(iterator beg, iterator end, value) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v;

    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(5);
    v.push_back(6);

    // 统计元素出现次数
    int total = count(v.begin(), v.end(), 5);
    cout << "total: " << total << endl;

    return 0;
}

程序运行输出的结果如下：

1
total: 2
count_if
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
/**
 * count_if 算法，根据条件统计元素出现次数
 * @param beg 容器开始迭代器
 * @param end 容器结束迭代器
 * @param callback 普通函数或者谓词（返回值为 bool 类型的函数对象）
 * @return 返回元素个数
*/
count_if(iterator beg, iterator end, callback) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// 普通函数
bool MyGreaterThenFive(const int &v) {
    return v > 5;
}

// 函数对象
class GreaterThenFiveFunctor {

public:
    bool operator()(const int &v) {
        return v > 5;
    }

};

int main() {
    vector<int> v;

    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.push_back(5);
    v.push_back(6);
    v.push_back(7);

    // 根据条件统计元素出现次数（基于普通函数）
    int total = count_if(v.begin(), v.end(), MyGreaterThenFive);
    cout << "total: " << total << endl;

    // 根据条件统计元素出现次数（基于函数对象）
    int count = count_if(v.begin(), v.end(), GreaterThenFiveFunctor());
    cout << "count: " << total << endl;

    return 0;
}

程序运行输出的结果如下：

1
2
total: 2
count: 2

常用的排序算法

merge
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
11
12
/**
 * merge 算法 将两个容器元素合并，并存储到另一个容器中
 * 注意：合并的两个容器必须是有序的
 * @param beg1 容器一开始迭代器
 * @param end1 容器一结束迭代器
 * @param beg2 容器二开始迭代器
 * @param end2 容器二结束迭代器
 * @param beg3 目标容器开始迭代器
*/
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator beg3) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    vector<int> v1;
    vector<int> v2;

    for (int i = 1; i <= 5; i++) {
        v1.push_back(i);
        v2.push_back(i * 10);
    }

    vector<int> vTarget;
    vTarget.resize(v1.size() + v2.size());

    // 将两个容器元素合并，并存储到另一个容器中
    merge(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

    for_each(vTarget.begin(), vTarget.end(), [](int value) { cout << value << " "; });

    return 0;
}

程序运行输出的结果如下：

1
1 2 3 4 5 10 20 30 40 50
sort
  • 算法的定义
1
2
3
4
5
6
7
8
9
/**
 * sort 算法 将容器元素排序
 * @param beg 容器开始迭代器
 * @param end 容器结束迭代器
 * @param callback 普通函数或者谓词（返回值为 bool 类型的函数对象）
*/
sort(iterator beg, iterator end, callback) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

bool MyCompare(int v1, int v2) {
    return v1 > v2;
}

void test01() {
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(5);
    v1.push_back(8);
    v1.push_back(7);
    v1.push_back(9);

    // 默认从小到大排序
    sort(v1.begin(), v1.end());

    for_each(v1.begin(), v1.end(), [](int value) { cout << value << " "; });

    cout << endl;
}

void test02() {
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(5);
    v1.push_back(8);
    v1.push_back(7);
    v1.push_back(9);

    // 从大到小排序（基于普通函数）
    sort(v1.begin(), v1.end(), MyCompare);

    for_each(v1.begin(), v1.end(), [](int value) { cout << value << " "; });

    cout << endl;
}

void test03() {
    vector<int> v1;
    v1.push_back(10);
    v1.push_back(5);
    v1.push_back(8);
    v1.push_back(7);
    v1.push_back(9);

    // 从大到小排序（基于函数对象）
    sort(v1.begin(), v1.end(), greater<int>());

    for_each(v1.begin(), v1.end(), [](int value) { cout << value << " "; });

    cout << endl;
}

int main() {
    test01();
    test02();
    test03();
    return 0;
}

程序运行输出的结果如下：

1
2
3
5 7 8 9 10 
10 9 8 7 5 
10 9 8 7 5
reverse
  • 算法的定义
1
2
3
4
5
6
7
8
/**
 * reverse 算法 反转指定范围元素的位置
 * @param beg 容器开始迭代器
 * @param end 容器结束迭代器
*/
reverse(iterator beg, iterator end) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>

using namespace std;

int main() {

    vector<int> v;
    v.push_back(10);
    v.push_back(5);
    v.push_back(8);
    v.push_back(7);
    v.push_back(9);

    for_each(v.begin(), v.end(), [](int value) { cout << value << " "; });

    cout << endl;

    // 反转指定范围元素的位置
    reverse(v.begin(), v.end());

    for_each(v.begin(), v.end(), [](int value) { cout << value << " "; });

    return 0;
}

程序运行输出的结果如下：

1
2
10 5 8 7 9 
9 7 8 5 10
random_shuffle
  • 算法的定义
1
2
3
4
5
6
7
8
/**
 * random_shuffle 算法 对指定范围内的元素随机调整顺序（洗牌）
 * @param beg 容器开始迭代器
 * @param end 容器结束迭代器
*/
random_shuffle(iterator beg, iterator end) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>

using namespace std;

int main() {

    // 初始化随机种子
    srand((unsigned int) time(NULL));

    vector<int> v;

    for (int i = 0; i < 10; i++) {
        v.push_back(i);
    }

    for_each(v.begin(), v.end(), [](int value) { cout << value << " "; });

    cout << endl;

    // 对指定范围内的元素随机调整顺序（洗牌）
    random_shuffle(v.begin(), v.end());

    for_each(v.begin(), v.end(), [](int value) { cout << value << " "; });

    return 0;
}

程序运行输出的结果如下：

1
2
0 1 2 3 4 5 6 7 8 9 
7 0 3 5 2 4 9 8 1 6

常用拷贝和替换算法

copy
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
/**
 * copy 算法 将容器内指定范围的元素拷贝到另一个容器中
 * 注意：copy 算法不会给目标容器分配内存空间，所以需要开发者提前手动分配好内存空间
 * @param beg 源容器的开始迭代器
 * @param end 源容器的结束迭代器
 * @param dest 目标容器的开始迭代器
*/
copy(iterator beg, iterator end, iterator dest) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>

using namespace std;

int main() {
    vector<int> vOrigin;

    for (int i = 0; i < 10; i++) {
        vOrigin.push_back(i);
    }

    vector<int> vTarget;

    // 手动分配内存空间
    vTarget.resize(vOrigin.size());

    // 将容器内指定范围的元素拷贝到另一个容器中
    copy(vOrigin.begin(), vOrigin.end(), vTarget.begin());

    // 第一种方式打印
    for_each(vTarget.begin(), vTarget.end(), [](int value) { cout << value << " "; });

    cout << endl;

    // 第二种方式打印
    copy(vTarget.begin(), vTarget.end(), ostream_iterator<int>(cout, " "));

    return 0;
}

程序运行输出的结果如下：

1
2
0 1 2 3 4 5 6 7 8 9 
0 1 2 3 4 5 6 7 8 9
replace
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
/**
 * replace 算法 将容器内指定范围的旧元素替换为新元素
 * @param beg 容器开始迭代器
 * @param end 容器结束迭代器
 * @param oldValue 旧元素
 * @param newValue 新元素
*/
replace(iterator beg, iterator end, oldValue, newValue) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v;

    v.push_back(1);
    v.push_back(1);
    v.push_back(3);
    v.push_back(3);
    v.push_back(5);
    v.push_back(5);

    for_each(v.begin(), v.end(), [](int value) { cout << value << " "; });

    cout << endl;

    // 将容器内指定范围的旧元素替换为新元素
    replace(v.begin(), v.end(), 3, 8);

    for_each(v.begin(), v.end(), [](int value) { cout << value << " "; });

    return 0;
}

程序运行输出的结果如下：

1
2
1 1 3 3 5 5 
1 1 8 8 5 5
replace_if
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
/**
 * replace_if 算法 根据条件将容器内指定范围的旧元素替换为新元素
 * @param beg 容器开始迭代器
 * @param end 容器结束迭代器
 * @param callback 普通函数或者谓词（返回值为 bool 类型的函数对象）
 * @param newValue 新元素
*/
replace_if(iterator beg, iterator end, callback, newValue) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

// 函数对象
class GreaterThenFive {

public:

    // 重载 () 操作符
    bool operator()(const int &value) {
        return value > 5;
    }

};

int main() {
    vector<int> v;

    v.push_back(2);
    v.push_back(2);
    v.push_back(4);
    v.push_back(4);
    v.push_back(6);
    v.push_back(6);

    for_each(v.begin(), v.end(), [](int value) { cout << value << " "; });

    cout << endl;

    // 将大于 5 的元素替换为新元素（基于函数对象）
    replace_if(v.begin(), v.end(), GreaterThenFive(), 8);

    for_each(v.begin(), v.end(), [](int value) { cout << value << " "; });

    return 0;
}

程序运行输出的结果如下：

1
2
2 2 4 4 6 6 
2 2 4 4 8 8
swap
  • 算法的定义
1
2
3
4
5
6
7
8
/**
 * swap 算法 互换两个容器的元素
 * @param c1 容器一
 * @param c2 容器二
*/
swap(container c1, container c2) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    v1.push_back(12);
    v1.push_back(12);
    v1.push_back(14);
    v1.push_back(14);
    v1.push_back(16);
    v1.push_back(16);


    vector<int> v2;
    v2.push_back(32);
    v2.push_back(32);
    v2.push_back(34);
    v2.push_back(34);

    cout << endl << "----------- before swap -------------" << endl;

    for_each(v1.begin(), v1.end(), [](int value) { cout << value << " "; });
    cout << endl;
    for_each(v2.begin(), v2.end(), [](int value) { cout << value << " "; });

    // 互换两个容器的元素
    swap(v1, v2);
    
    cout << endl << "----------- after swap -------------" << endl;

    for_each(v1.begin(), v1.end(), [](int value) { cout << value << " "; });
    cout << endl;
    for_each(v2.begin(), v2.end(), [](int value) { cout << value << " "; });

    return 0;
}

程序运行输出的结果如下：

1
2
3
4
5
6
----------- before swap -------------
12 12 14 14 16 16 
32 32 34 34 
----------- after swap -------------
32 32 34 34 
12 12 14 14 16 16

常用算数生成算法

accumulate
  • 算法的定义
1
2
3
4
5
6
7
8
9
/**
 * accumulate 算法 计算容器元素累计总和
 * @param beg 容器开始迭代器
 * @param end 容器结束迭代器
 * @param value 累加值
*/
accumulate(iterator beg, iterator end, value) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {

    vector<int> v;
    v.push_back(1);
    v.push_back(3);
    v.push_back(2);

    // 计算容器元素累计总和
    int sum = accumulate(v.begin(), v.end(), 0);

    cout << "sum = " << sum << endl;

    return 0;
}

程序运行输出的结果如下：

1
sum = 6
fill
  • 算法的定义
1
2
3
4
5
6
7
8
9
/**
 * fill 算法 向容器中填充元素
 * @param beg 容器开始迭代器
 * @param end 容器结束迭代器
 * @param value 填充的元素
*/
fill(iterator beg, iterator end, value) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <algorithm>

using namespace std;

int main() {

    vector<int> v;
    v.resize(5);

    // 向容器中填充元素
    fill(v.begin(), v.end(), 6);

    for_each(v.begin(), v.end(), [](int value) { cout << value << " "; });

    return 0;
}

程序运行输出的结果如下：

1
6 6 6 6 6

常用集合算法

set_intersection
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * set_intersection 算法 求两个集合的交集
 * 注意：两个集合必须是有序序列
 * @param beg1 容器一的开始迭代器
 * @param end1 容器一的结束迭代器
 * @param beg2 容器二的开始迭代器
 * @param end2 容器二的结束迭代器
 * @param dest 目标容器的开始迭代器
 * @return 目标容器的最后一个元素的迭代器地址
*/
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, dest) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(3);
    v1.push_back(5);
    v1.push_back(7);

    vector<int> v2;
    v2.push_back(5);
    v2.push_back(7);
    v2.push_back(9);
    v2.push_back(11);

    vector<int> vTarget;
    vTarget.resize(min(v1.size(), v2.size()));

    // 求两个集合的交集
    vector<int>::iterator itEnd = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

    for_each(vTarget.begin(), itEnd, [](int value) { cout << value << " "; });

    return 0;
}

程序运行输出的结果如下：

1
5 7
set_union
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * set_union 算法 求两个集合的并集
 * 注意：两个集合必须是有序序列
 * @param beg1 容器一的开始迭代器
 * @param end1 容器一的结束迭代器
 * @param beg2 容器二的开始迭代器
 * @param end2 容器二的结束迭代器
 * @param dest 目标容器的开始迭代器
 * @return 目标容器的最后一个元素的迭代器地址
*/
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, dest) {

}
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(3);
    v1.push_back(5);
    v1.push_back(7);

    vector<int> v2;
    v2.push_back(5);
    v2.push_back(7);
    v2.push_back(9);
    v2.push_back(11);

    vector<int> vTarget;
    vTarget.resize(v1.size() + v2.size());

    // 求两个集合的并集
    vector<int>::iterator itEnd = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

    for_each(vTarget.begin(), itEnd, [](int value) { cout << value << " "; });

    return 0;
}

程序运行输出的结果如下：

1
1 3 5 7 9 11
set_difference
  • 算法的定义
1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * set_difference 算法 求两个集合的差集
 * 注意：两个集合必须是有序序列
 * @param beg1 容器一的开始迭代器
 * @param end1 容器一的结束迭代器
 * @param beg2 容器二的开始迭代器
 * @param end2 容器二的结束迭代器
 * @param dest 目标容器的开始迭代器
 * @return 目标容器的最后一个元素的迭代器地址
*/
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, dest) {

}
  • 算法的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(3);
    v1.push_back(5);
    v1.push_back(7);

    vector<int> v2;
    v2.push_back(5);
    v2.push_back(7);
    v2.push_back(9);
    v2.push_back(11);

    vector<int> vTarget;
    vTarget.resize(max(v1.size(), v2.size()));

    // 求两个集合的差集(v1 差 v2)
    vector<int>::iterator itEnd = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), vTarget.begin());

    for_each(vTarget.begin(), itEnd, [](int value) { cout << value << " "; });

    cout << endl;

    // 求两个集合的差集(v2 差 v1)
    itEnd = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), vTarget.begin());

    for_each(vTarget.begin(), itEnd, [](int value) { cout << value << " "; });

    return 0;
}

程序运行输出的结果如下：

1
2
1 3 
9 11