基础介绍

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#include <iostream>
 2#include <vector>
 3#include <algorithm>
 4
 5int main() {
 6    std::vector<int> vec = {5, 3, 1, 4, 2};
 7    
 8    // 使用STL算法进行排序
 9    std::sort(vec.begin(), vec.end());
10    
11    // 输出排序后的结果
12    for (int num : vec) {
13        std::cout << num << " ";
14    }
15    std::cout << std::endl;
16
17    return 0;
18}

容器

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

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

序列式容器

 1#include <vector>
 2#include <list>
 3#include <queue>
 4#include <iostream>
 5#include <stack>
 6
 7using namespace std;
 8
 9struct Print {
10
11	void operator()(int i) {
12		cout << i << " ";
13	}
14
15};
16
17int main() {
18	
19	int arr[] = { 1,2,3,4 };
20
21	// 初始化
22	// 左闭右开
23	vector<int> v_vec(arr, arr + 4);
24	list<int> v_list(arr, arr + 4);
25	deque<int> v_dequeue(arr, arr + 4);
26
27	for_each(v_vec.begin(), v_vec.end(), Print());
28	cout << endl << "===================================" << endl;
29	for_each(v_list.begin(), v_list.end(), Print());
30	cout << endl << "===================================" << endl;
31	for_each(v_dequeue.begin(), v_dequeue.end(), Print());
32	cout << endl << "===================================" << endl;
33
34	stack<int> v_stack(v_dequeue);
35	queue<int> v_queue(v_dequeue);
36	priority_queue<int> v_priority_queue(arr, arr + 4);
37
38	while (!v_stack.empty()) {
39		cout << v_stack.top() << " ";
40		v_stack.pop();
41	}
42	cout << endl << "================================" << endl;
43	
44	while (!v_queue.empty())
45	{
46		cout << v_queue.front() << " ";
47		v_queue.pop();
48	}
49
50	cout << endl << "================================" << endl;
51
52	return 0;
53}

关联式容器

 1#include <map>
 2#include <iostream>
 3#include <algorithm>
 4
 5using namespace std;
 6
 7struct Print {
 8	void operator()(pair<string, double> info) {
 9		cout << info.first << ":" << info.second << endl;
10	}
11};
12
13int main() {
14	map<string, double> student_scores;
15	student_scores["张三"] = 100.0;
16	student_scores["李四"] = 99.0;
17	student_scores["王五"] = 33.2;
18
19	student_scores.insert(pair<string, double>("赵六", 10.2));
20	student_scores.insert(pair<string, double>("钱琦", 88.2));
21
22	// 无法修改赵六
23	student_scores.insert(map<string, double>::value_type("赵六", 90.2));
24
25	// 这样可以修改
26	student_scores["张三"] = 12.2;
27
28	// 遍历
29	for_each(student_scores.begin(), student_scores.end(), Print());
30
31	// 迭代器遍历
32	map<string, double>::iterator iter;
33	iter = student_scores.begin();
34
35	while (iter != student_scores.end()) {
36		if (iter->second < 60) {
37			student_scores.erase(iter++);
38		}
39		else {
40			iter++;
41		}
42	}
43
44	cout << "=======================================" << endl;
45	for_each(student_scores.begin(), student_scores.end(), Print());
46
47	cout << "=======================================" << endl;
48	for (iter = student_scores.begin(); iter != student_scores.end(); iter ++) {
49		if (iter->second < 60) {
50			iter = student_scores.erase(iter);
51		}
52		else {
53		
54		}
55	}
56	for_each(student_scores.begin(), student_scores.end(), Print());
57
58	return 0;
59}

算法

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

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

 1#include<algorithm>
 2#include<numeric>
 3#include<functional>
 4#include<iostream>
 5#include<vector>
 6
 7using namespace std;
 8
 9template <class T>
10inline bool mt_sort(T const& a, T const& b) {
11	return a < b;
12}
13
14template<class T>
15inline void mt_print(T const& a) {
16	cout << a << " ";
17}
18
19int main() {
20	int temp = 1;
21	int arr_a[] = { 2,13,45,5,2, };
22	int arr_b[] = { 2,3,35,5,6,21,2 };
23
24	int result[5];
25	// 参数说明：
26	// 1. arr_a的起始位置和结束位置
27	// 2. arr_b的起始位置，不需要结束位置，会处理到和arr_a同样长度的位置。
28	// 3. 接收转换的结果值
29	// 4. 转换的方法（这里的plush为仿函数，还有许多其他的如：minus等）
30	transform(arr_a, arr_a + 5, arr_b, result, plus<int>());
31	for_each(result, result + 5, [](int a) -> void {cout << a << " "; });
32
33	// [](int a) -> void {cout << a << " "; } lambda表达式
34	// []: 表示外部变量, 比如上面定义的temp;
35	// (): 入参
36	// ->: 返回值
37	// {}: 结构体
38
39	cout << endl;
40
41	// find
42	int arr_c[] = {3,4,5,6,23,5,6,7,2,3,7,5,23,2,7,8};
43	int len = sizeof(arr_c) / sizeof(arr_c[0]);
44	int count_7 = count(arr_c, arr_c+ len, 7);
45	mt_print<int>(count_7);
46	cout << endl;
47	
48	int count_lt_7 = count_if(arr_c, arr_c + len, [](int a)->bool {return a < 7; });
49	mt_print<int>(count_lt_7);
50	cout << endl;
51
52	// 第二种方式：bind2nd
53	int count_lt_8 = count_if(arr_c, arr_c + len, bind2nd(less<int>(), 8));
54	mt_print<int>(count_lt_8);
55	cout << endl;
56
57	// 二分查找
58	mt_print<int>(binary_search(arr_c, arr_c + len, 23));
59	cout << endl;
60
61	// 查找子序列
62	vector<int> arr_c_sub = {5, 6, 7, 2};
63	cout << *search(arr_c, arr_c + len, arr_c_sub.begin(), arr_c_sub.end()) << endl;
64
65	return 0;
66}

transform

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

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

单一范围变换

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

 1#include <iostream>
 2#include <vector>
 3#include <algorithm>
 4
 5int add(int x, int y) {
 6    return x + y;
 7}
 8
 9int main() {
10    std::vector<int> vec1 = {1, 2, 3, 4, 5};
11    std::vector<int> vec2 = {10, 20, 30, 40, 50};
12    std::vector<int> result(vec1.size());
13
14    std::transform(vec1.begin(), vec1.end(), vec2.begin(), result.begin(), add);
15
16    for (int num : result) {
17        std::cout << num << " ";
18    }
19    std::cout << std::endl;
20
21    return 0;
22}

两个范围变换

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

 1#include <iostream>
 2#include <vector>
 3#include <algorithm>
 4
 5int add(int x, int y) {
 6    return x + y;
 7}
 8
 9int main() {
10    std::vector<int> vec1 = {1, 2, 3, 4, 5};
11    std::vector<int> vec2 = {10, 20, 30, 40, 50};
12    std::vector<int> result(vec1.size());
13
14    std::transform(vec1.begin(), vec1.end(), vec2.begin(), result.begin(), add);
15
16    for (int num : result) {
17        std::cout << num << " ";
18    }
19    std::cout << std::endl;
20
21    return 0;
22}

lambda表达式

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

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

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#include<list>
 2#include<algorithm>
 3#include<iostream>
 4
 5using namespace std;
 6
 7int main() {
 8
 9	list<int> arr_a;
10	arr_a.push_back(1);
11	arr_a.push_back(5);
12	arr_a.push_back(9);
13	arr_a.push_back(2);	
14	arr_a.push_back(8);
15
16	// 常量迭代器
17	list<int>::const_iterator const_it;
18	for (const_it = arr_a.begin(); const_it != arr_a.end(); const_it++) {
19		cout << *const_it << " ";
20	}
21	cout << endl;
22
23
24	list<int>::iterator it;
25	for (it = arr_a.begin(); it != arr_a.end(); it++) {
26		*it += 1;
27		cout << *it << " ";
28	}
29	cout << endl;
30
31	// 迭代器不支持"<"这种符号
32
33	// 逆序迭代器
34	list<int>::reverse_iterator r_it;
35	for (r_it = arr_a.rbegin(); r_it != arr_a.rend(); r_it++) {
36		*r_it += 1;
37		cout << *r_it << " ";
38	}
39	cout << endl;
40	
41	return 0;
42}

仿函数（functor）

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

 1#include <iostream>
 2#include <algorithm>
 3
 4
 5using namespace std;
 6
 7bool m_sort(double a, double b) {
 8	return a > b;
 9}
10
11void m_print(double a) {
12	cout << a << " ";
13}
14
15// 泛型
16template <class T>
17inline bool mt_sort(T const &a, T const &b) {
18	return a < b;
19}
20
21template<class T>
22inline void mt_print(T const &a) {
23	cout << a << " ";
24}
25
26// 仿函数
27template<class T>
28struct f_sort {
29
30	bool operator()(T const& a, T const& b) {
31		return a > b;
32	}
33
34};
35
36template<class T>
37struct f_print {
38	void operator()(T const& a) {
39		cout << a << " ";
40	}
41};
42
43int main() {
44	
45	double arr[] = {3.2,2.3,1.9,4.0};
46	sort(arr, arr+4, m_sort);
47	for_each(arr, arr + 4, m_print);
48
49	cout << endl;
50
51	sort(arr, arr+4, mt_sort<double>);
52	for_each(arr, arr+4, mt_print<double>);
53
54	cout << endl;
55
56	// 仿函数方式
57	sort(arr, arr + 4, f_sort<double>());
58	for_each(arr, arr + 4, f_print<double>());
59
60	return 0;
61}

容器适配器

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

容器适配器类型

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

1. `stack`

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

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

 1#include <iostream>
 2#include <stack>
 3
 4int main() {
 5    std::stack<int> s;
 6
 7    s.push(1);
 8    s.push(2);
 9    s.push(3);
10
11    while (!s.empty()) {
12        std::cout << s.top() << " ";
13        s.pop();
14    }
15    std::cout << std::endl;
16
17    return 0;
18}

2. `queue`

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

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

 1#include <iostream>
 2#include <queue>
 3
 4int main() {
 5    std::queue<int> q;
 6
 7    q.push(1);
 8    q.push(2);
 9    q.push(3);
10
11    while (!q.empty()) {
12        std::cout << q.front() << " ";
13        q.pop();
14    }
15    std::cout << std::endl;
16
17    return 0;
18}

3. `priority_queue`

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

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

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

 1#include <iostream>
 2#include <queue>
 3#include <vector>
 4
 5int main() {
 6    std::priority_queue<int> pq;
 7
 8    pq.push(3);
 9    pq.push(1);
10    pq.push(2);
11
12    while (!pq.empty()) {
13        std::cout << pq.top() << " ";
14        pq.pop();
15    }
16    std::cout << std::endl;
17
18    return 0;
19}

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

 1#include <iostream>
 2#include <queue>
 3#include <vector>
 4
 5int main() {
 6    // 使用greater<int>创建最小堆
 7    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
 8
 9    pq.push(3);
10    pq.push(1);
11    pq.push(2);
12
13    while (!pq.empty()) {
14        std::cout << pq.top() << " ";
15        pq.pop();
16    }
17    std::cout << std::endl;
18
19    return 0;
20}

底层容器

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

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

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

 1#include <iostream>
 2#include <stack>
 3#include <list>
 4
 5int main() {
 6    // 使用list作为底层容器
 7    std::stack<int, std::list<int>> s;
 8
 9    s.push(1);
10    s.push(2);
11    s.push(3);
12
13    while (!s.empty()) {
14        std::cout << s.top() << " ";
15        s.pop();
16    }
17    std::cout << std::endl;
18
19    return 0;
20}

空间配置器

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

— END —

Gang's Blog

C++中STL基础

基础介绍

示例代码

容器

序列式容器

关联式容器

算法

transform

单一范围变换

两个范围变换

lambda表达式

捕获列表

find

迭代器

迭代器的种类

迭代器的基本操作

仿函数（functor）

容器适配器

容器适配器类型

1. `stack`

2. `queue`

3. `priority_queue`

底层容器

空间配置器

基础介绍

示例代码

容器

序列式容器

关联式容器

算法

transform

单一范围变换

两个范围变换

lambda表达式

捕获列表

find

迭代器

迭代器的种类

迭代器的基本操作

仿函数（functor）

容器适配器

容器适配器类型

1. stack

2. queue

3. priority_queue

底层容器

空间配置器

1. `stack`

2. `queue`

3. `priority_queue`