Gang 收录于 C++

2022-06-01 约 1700 字预计阅读 8 分钟

基础介绍

C++标准模板库（STL，Standard Template Library）是C++标准库的一部分，提供了一组通用的类和函数，用于处理数据结构和算法。STL主要由以下几个部分组成：

容器（Containers）：容器是用来存储和管理对象的集合。STL提供了多种容器，每种容器都有不同的特点和用途。常见的容器包括：
- 顺序容器（Sequence Containers）：例如vector、deque、list。
- 关联容器（Associative Containers）：例如set、map、multiset、multimap。
- 无序容器（Unordered Containers）：例如unordered_set、unordered_map、unordered_multiset、unordered_multimap。
迭代器（Iterators）：迭代器是用于遍历容器元素的对象。STL中的迭代器类似于指针，可以用来访问容器中的元素。根据功能不同，迭代器分为五种类型：
- 输入迭代器（Input Iterators）
- 输出迭代器（Output Iterators）
- 前向迭代器（Forward Iterators）
- 双向迭代器（Bidirectional Iterators）
- 随机访问迭代器（Random Access Iterators）
算法（Algorithms）：STL提供了丰富的算法，用于操作容器中的元素。这些算法主要包括排序、查找、复制、替换等。常见的算法有sort、find、copy、replace等。
函数对象（Function Objects）：函数对象是可以像函数一样调用的对象。STL中的算法可以接受函数对象作为参数，以实现自定义的操作行为。常见的函数对象有plus、minus、multiplies等。
适配器（Adapters）：适配器是一种用来将一个类的接口转换为另一个接口的设计模式。STL中有三种适配器：
- 容器适配器（Container Adapters）：例如stack、queue、priority_queue。
- 迭代器适配器（Iterator Adapters）：例如reverse_iterator、insert_iterator。
- 函数适配器（Function Adapters）：例如bind、mem_fn。
空间配置器：allocator

示例代码

以下是一个简单的示例，展示了如何使用STL中的vector容器和sort算法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vec = {5, 3, 1, 4, 2};
    
    // 使用STL算法进行排序
    std::sort(vec.begin(), vec.end());
    
    // 输出排序后的结果
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

容器

序列式容器其中的元素都是可排序的，STL提供了vector，list,deque等序列式容器，而stack，queue，priority_queue则是容器的适配器。
关联式容器

每个元素都是一个k-v键值对，当元素被插入到容器中的时候，按照其键值以某种特定的规则存放，常见的关联式容器：set，multiset，map，multimap

序列式容器

 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


#include <vector>
#include <list>
#include <queue>
#include <iostream>
#include <stack>

using namespace std;

struct Print {

	void operator()(int i) {
		cout << i << " ";
	}

};

int main() {
	
	int arr[] = { 1,2,3,4 };

	// 初始化
	// 左闭右开
	vector<int> v_vec(arr, arr + 4);
	list<int> v_list(arr, arr + 4);
	deque<int> v_dequeue(arr, arr + 4);

	for_each(v_vec.begin(), v_vec.end(), Print());
	cout << endl << "===================================" << endl;
	for_each(v_list.begin(), v_list.end(), Print());
	cout << endl << "===================================" << endl;
	for_each(v_dequeue.begin(), v_dequeue.end(), Print());
	cout << endl << "===================================" << endl;

	stack<int> v_stack(v_dequeue);
	queue<int> v_queue(v_dequeue);
	priority_queue<int> v_priority_queue(arr, arr + 4);

	while (!v_stack.empty()) {
		cout << v_stack.top() << " ";
		v_stack.pop();
	}
	cout << endl << "================================" << endl;
	
	while (!v_queue.empty())
	{
		cout << v_queue.front() << " ";
		v_queue.pop();
	}

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

	return 0;
}

关联式容器

 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


#include <map>
#include <iostream>
#include <algorithm>

using namespace std;

struct Print {
	void operator()(pair<string, double> info) {
		cout << info.first << ":" << info.second << endl;
	}
};

int main() {
	map<string, double> student_scores;
	student_scores["张三"] = 100.0;
	student_scores["李四"] = 99.0;
	student_scores["王五"] = 33.2;

	student_scores.insert(pair<string, double>("赵六", 10.2));
	student_scores.insert(pair<string, double>("钱琦", 88.2));

	// 无法修改赵六
	student_scores.insert(map<string, double>::value_type("赵六", 90.2));

	// 这样可以修改
	student_scores["张三"] = 12.2;

	// 遍历
	for_each(student_scores.begin(), student_scores.end(), Print());

	// 迭代器遍历
	map<string, double>::iterator iter;
	iter = student_scores.begin();

	while (iter != student_scores.end()) {
		if (iter->second < 60) {
			student_scores.erase(iter++);
		}
		else {
			iter++;
		}
	}

	cout << "=======================================" << endl;
	for_each(student_scores.begin(), student_scores.end(), Print());

	cout << "=======================================" << endl;
	for (iter = student_scores.begin(); iter != student_scores.end(); iter ++) {
		if (iter->second < 60) {
			iter = student_scores.erase(iter);
		}
		else {
		
		}
	}
	for_each(student_scores.begin(), student_scores.end(), Print());

	return 0;
}

算法

STL中的算法大致分为4类，位于<algorithm>，<numeric>，<functional>中：

非可变序列算法：不会修改容器内容
可变序列算法：会修改容器内容
排序算法；包括对

 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


#include<algorithm>
#include<numeric>
#include<functional>
#include<iostream>
#include<vector>

using namespace std;

template <class T>
inline bool mt_sort(T const& a, T const& b) {
	return a < b;
}

template<class T>
inline void mt_print(T const& a) {
	cout << a << " ";
}

int main() {
	int temp = 1;
	int arr_a[] = { 2,13,45,5,2, };
	int arr_b[] = { 2,3,35,5,6,21,2 };

	int result[5];
	// 参数说明：
	// 1. arr_a的起始位置和结束位置
	// 2. arr_b的起始位置，不需要结束位置，会处理到和arr_a同样长度的位置。
	// 3. 接收转换的结果值
	// 4. 转换的方法（这里的plush为仿函数，还有许多其他的如：minus等）
	transform(arr_a, arr_a + 5, arr_b, result, plus<int>());
	for_each(result, result + 5, [](int a) -> void {cout << a << " "; });

	// [](int a) -> void {cout << a << " "; } lambda表达式
	// []: 表示外部变量, 比如上面定义的temp;
	// (): 入参
	// ->: 返回值
	// {}: 结构体

	cout << endl;

	// find
	int arr_c[] = {3,4,5,6,23,5,6,7,2,3,7,5,23,2,7,8};
	int len = sizeof(arr_c) / sizeof(arr_c[0]);
	int count_7 = count(arr_c, arr_c+ len, 7);
	mt_print<int>(count_7);
	cout << endl;
	
	int count_lt_7 = count_if(arr_c, arr_c + len, [](int a)->bool {return a < 7; });
	mt_print<int>(count_lt_7);
	cout << endl;

	// 第二种方式：bind2nd
	int count_lt_8 = count_if(arr_c, arr_c + len, bind2nd(less<int>(), 8));
	mt_print<int>(count_lt_8);
	cout << endl;

	// 二分查找
	mt_print<int>(binary_search(arr_c, arr_c + len, 23));
	cout << endl;

	// 查找子序列
	vector<int> arr_c_sub = {5, 6, 7, 2};
	cout << *search(arr_c, arr_c + len, arr_c_sub.begin(), arr_c_sub.end()) << endl;

	return 0;
}

transform

std::transform 是 C++ 标准库中的一个算法，用于对一个或两个范围内的元素进行变换，并将结果存储到另一个范围中。它通过应用一个给定的操作（通常是一个函数或函数对象）来实现这一点。

1
2


template <class InputIterator, class OutputIterator, class UnaryOperation>
OutputIterator transform(InputIterator first1, InputIterator last1, OutputIterator result, UnaryOperation op);

单一范围变换

first1 和 last1：表示输入范围的起始和结束迭代器。
result：表示输出范围的起始迭代器。
op：表示应用于输入范围每个元素的一元操作。

 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 <vector>
#include <algorithm>

int add(int x, int y) {
    return x + y;
}

int main() {
    std::vector<int> vec1 = {1, 2, 3, 4, 5};
    std::vector<int> vec2 = {10, 20, 30, 40, 50};
    std::vector<int> result(vec1.size());

    std::transform(vec1.begin(), vec1.end(), vec2.begin(), result.begin(), add);

    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

两个范围变换

first1 和 last1：表示第一个输入范围的起始和结束迭代器。
first2：表示第二个输入范围的起始迭代器。
result：表示输出范围的起始迭代器。
op：表示应用于两个输入范围对应元素的二元操作。

 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 <vector>
#include <algorithm>

int add(int x, int y) {
    return x + y;
}

int main() {
    std::vector<int> vec1 = {1, 2, 3, 4, 5};
    std::vector<int> vec2 = {10, 20, 30, 40, 50};
    std::vector<int> result(vec1.size());

    std::transform(vec1.begin(), vec1.end(), vec2.begin(), result.begin(), add);

    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

lambda表达式

Lambda表达式是C++11引入的一种新特性，允许在代码中定义匿名函数（即没有名称的函数）。它们可以捕获周围作用域中的变量，并在需要时被调用。Lambda表达式的语法简洁且强大，常用于STL算法和事件处理等场景。

1
2
3


[capture](parameters) -> return_type {
    // function body
}

capture：指定哪些外部变量可以在lambda表达式中使用。
parameters：指定lambda表达式的参数列表。
return_type：指定lambda表达式的返回类型。如果可以从函数体的返回语句中推断出返回类型，可以省略。
function body：定义lambda表达式的函数体。

捕获列表

捕获列表用于指定lambda表达式可以访问哪些外部变量。常见的捕获方式有以下几种：

[ ]：不捕获任何外部变量。
[x]：按值捕获变量x。
[&x]：按引用捕获变量x。
[=]：按值捕获所有外部变量。
[&]：按引用捕获所有外部变量。
[=, &x]：按值捕获所有外部变量，按引用捕获变量x。
[&, x]：按引用捕获所有外部变量，按值捕获变量x。

find

迭代器

迭代器是C++标准模板库（STL）中的一种重要工具，提供了一种统一的方式来访问和遍历容器中的元素。迭代器的行为类似于指针，可以递增（移动到下一个元素）和解引用（访问元素值）。迭代器的使用使得STL算法能够与各种不同类型的容器协同工作。

迭代器的种类

STL定义了几种不同类型的迭代器，每种迭代器支持的操作不同，适用于不同类型的容器：

输入迭代器（Input Iterator）：只读迭代器，可以读取元素但不能修改。主要用于单次遍历。
输出迭代器（Output Iterator）：只写迭代器，可以修改元素但不能读取。主要用于输出操作。
前向迭代器（Forward Iterator）：读写迭代器，可以读取和修改元素，只能单向遍历。
双向迭代器（Bidirectional Iterator）：可以双向遍历的读写迭代器。
随机访问迭代器（Random Access Iterator）：支持常数时间的随机访问，可以进行双向遍历，类似于指针。数组和std::vector等容器的迭代器是随机访问迭代器。

迭代器的基本操作

迭代器支持一系列操作，主要包括以下几种：

解引用操作符 (*)：访问迭代器指向的元素。
箭头操作符 (->)：访问迭代器指向的元素的成员。
递增操作符 (++)：移动到下一个元素。
递减操作符 (--)：对于双向和随机访问迭代器，移动到前一个元素。
比较操作符 (==, !=)：检查两个迭代器是否相等。

 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


#include<list>
#include<algorithm>
#include<iostream>

using namespace std;

int main() {

	list<int> arr_a;
	arr_a.push_back(1);
	arr_a.push_back(5);
	arr_a.push_back(9);
	arr_a.push_back(2);	
	arr_a.push_back(8);

	// 常量迭代器
	list<int>::const_iterator const_it;
	for (const_it = arr_a.begin(); const_it != arr_a.end(); const_it++) {
		cout << *const_it << " ";
	}
	cout << endl;


	list<int>::iterator it;
	for (it = arr_a.begin(); it != arr_a.end(); it++) {
		*it += 1;
		cout << *it << " ";
	}
	cout << endl;

	// 迭代器不支持"<"这种符号

	// 逆序迭代器
	list<int>::reverse_iterator r_it;
	for (r_it = arr_a.rbegin(); r_it != arr_a.rend(); r_it++) {
		*r_it += 1;
		cout << *r_it << " ";
	}
	cout << endl;
	
	return 0;
}

仿函数（functor）

仿函数一般不会单独使用，主要是为了搭配STL算法使用
本质上就是重载了一个operator()，创建一个行为类似函数的对象。

 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


#include <iostream>
#include <algorithm>


using namespace std;

bool m_sort(double a, double b) {
	return a > b;
}

void m_print(double a) {
	cout << a << " ";
}

// 泛型
template <class T>
inline bool mt_sort(T const &a, T const &b) {
	return a < b;
}

template<class T>
inline void mt_print(T const &a) {
	cout << a << " ";
}

// 仿函数
template<class T>
struct f_sort {

	bool operator()(T const& a, T const& b) {
		return a > b;
	}

};

template<class T>
struct f_print {
	void operator()(T const& a) {
		cout << a << " ";
	}
};

int main() {
	
	double arr[] = {3.2,2.3,1.9,4.0};
	sort(arr, arr+4, m_sort);
	for_each(arr, arr + 4, m_print);

	cout << endl;

	sort(arr, arr+4, mt_sort<double>);
	for_each(arr, arr+4, mt_print<double>);

	cout << endl;

	// 仿函数方式
	sort(arr, arr + 4, f_sort<double>());
	for_each(arr, arr + 4, f_print<double>());

	return 0;
}

容器适配器

容器适配器（Container Adapters）是C++标准模板库（STL）中对标准容器进行包装的一类组件。它们通过对底层容器提供特定的接口，使得容器的使用更加方便和特定。STL中提供了三种主要的容器适配器：stack、queue 和 priority_queue。每一种适配器都有其特定的用法和特性。

容器适配器类型

stack：栈适配器，遵循后进先出（LIFO）的原则。
queue：队列适配器，遵循先进先出（FIFO）的原则。
priority_queue：优先队列适配器，元素按优先级排序。

1. `stack`

stack 适配器提供了一个简单的堆栈结构，支持以下主要操作：

push：将元素推入栈顶。
pop：移除栈顶元素。
top：访问栈顶元素。
empty：检查栈是否为空。
size：返回栈中的元素数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


#include <iostream>
#include <stack>

int main() {
    std::stack<int> s;

    s.push(1);
    s.push(2);
    s.push(3);

    while (!s.empty()) {
        std::cout << s.top() << " ";
        s.pop();
    }
    std::cout << std::endl;

    return 0;
}

2. `queue`

queue 适配器提供了一个简单的队列结构，支持以下主要操作：

push：将元素推入队列末尾。
pop：移除队列头部元素。
front：访问队列头部元素。
back：访问队列末尾元素。
empty：检查队列是否为空。
size：返回队列中的元素数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


#include <iostream>
#include <queue>

int main() {
    std::queue<int> q;

    q.push(1);
    q.push(2);
    q.push(3);

    while (!q.empty()) {
        std::cout << q.front() << " ";
        q.pop();
    }
    std::cout << std::endl;

    return 0;
}

3. `priority_queue`

priority_queue 适配器提供了一个优先队列结构，支持以下主要操作：

push：将元素推入优先队列。
pop：移除优先队列顶元素。
top：访问优先队列顶元素。
empty：检查优先队列是否为空。
size：返回优先队列中的元素数量。

默认情况下，priority_queue 使用最大堆，顶元素是最大值。可以通过指定比较函数来创建最小堆。默认最大值优先。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> pq;

    pq.push(3);
    pq.push(1);
    pq.push(2);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

最小堆示例，最小值优先。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <iostream>
#include <queue>
#include <vector>

int main() {
    // 使用greater<int>创建最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

    pq.push(3);
    pq.push(1);
    pq.push(2);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

底层容器

容器适配器通过使用一个底层容器来存储元素。默认情况下，适配器使用以下容器：

stack：默认使用 std::deque 作为底层容器。
queue：默认使用 std::deque 作为底层容器。
priority_queue：默认使用 std::vector 作为底层容器。

可以通过指定其他容器来替换默认的底层容器，只要新的容器支持适配器所需的操作。例如，可以使用 std::list 替换 std::deque：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <iostream>
#include <stack>
#include <list>

int main() {
    // 使用list作为底层容器
    std::stack<int, std::list<int>> s;

    s.push(1);
    s.push(2);
    s.push(3);

    while (!s.empty()) {
        std::cout << s.top() << " ";
        s.pop();
    }
    std::cout << std::endl;

    return 0;
}

空间配置器

空间配置器（Allocator）是C++标准模板库（STL）中的一种机制，用于抽象内存分配和管理。默认情况下，STL容器使用标准的分配器 std::allocator，但是通过自定义分配器，用户可以控制容器的内存分配方式，从而优化性能或适应特定的内存管理需求。

C++中STL基础

基础介绍

示例代码

容器

序列式容器

关联式容器

算法

transform

单一范围变换

两个范围变换

lambda表达式

捕获列表

find

迭代器

迭代器的种类

迭代器的基本操作

仿函数（functor）

容器适配器

容器适配器类型

1. `stack`

2. `queue`

3. `priority_queue`

底层容器

空间配置器

相关内容

C++中STL基础

基础介绍

示例代码

容器

序列式容器

关联式容器

算法

transform

单一范围变换

两个范围变换

lambda表达式

捕获列表

find

迭代器

迭代器的种类

迭代器的基本操作

仿函数（functor）

容器适配器

容器适配器类型

1. stack

2. queue

3. priority_queue

底层容器

空间配置器

相关内容

1. `stack`

2. `queue`

3. `priority_queue`