STL的概述

STL的基础知识

STL诞生的原因

长久以来，软件界一直希望建立一种可重复利用的东西，数据结构和算法也是如此，我们希望提高数据结构和算法的复用性。而复用性必须建立在某种标准之上。但是在许多环境下，软件开发最基本的数据结构(data structures)和算法(algorithm)都未能有一套标准。大量程序员被迫从事大量重复的工作，竟然是为了完成前人已经完成而自己手上并未拥有的程序代码，这不仅是人力资源的浪费,也是挫折与痛苦的来源。

为了建立数据结构和算法的一套标准，提高数据结构和算法的复用性，诞生了STL

STL的理解

当我们编写程序时，经常会涉及到各种数据结构和算法的实现。例如，我们可能需要使用数组、链表、栈、队列等数据结构来存储和管理数据，也可能需要使用排序、查找、合并等算法来操作这些数据。
而在C++中，STL（也叫标准模板库），提供了多种容器（如vector、map、set等）、算法（如排序、查找、合并等）以及迭代器等这些组件，使得我们可以方便地完成这些常见的编程任务。
同时，STL几乎所有的代码都采用了模板类或者模板函数，这相比传统的由函数和类组成的库来说提供了更好的代码重用机

STL的组件

[[1.01-STL容器-STL的概述(Av432064775,P1).mp4#t=05:58.516,08:50]]

1）容器：存放数据
2）算法：操作数据
3）迭代器：算法 通过迭代器 操作容器数据
4）仿函数（函数对象）：为算法提供更多的策略
5）适配器：为算法提供更多参数的接口
6）空间配置器：为算法和容器动态分配、管理空间，它还可以控制内存的分配和释放行为，实现高效的内存管理。它在STL中非常重要，但是我们在学习STL的时候，可以不去了解他，因为STL会自动地去使用空间配置器。

STL特性

STL的一个重要特性是将数据和操作分离。数据由容器类别加以管理，操作则由特定的算法完成。

容器的基础知识

容器的理解

STL中的容器是一些用来存储数据的类模板，不同的容器，用不同数据结构来实现，也就提供了不同的存储和访问方式，可以满足不同的需求。具体的容器包括vector、list、deque、set、map等。

例如，vector是基于动态数组实现的，可以在常数时间内随机访问任何一个元素，适合需要随机访问的场景；而list是基于双向链表实现的，可以在常数时间内进行插入和删除操作，适合需要频繁插入和删除元素的场景。又如set和map是基于红黑树实现的，可以进行高效的查找、插入和删除操作，适合需要有序存储和查找元素的场景。

通过使用不同的容器，我们可以根据具体的场景和需求来选择最合适的容器，提高程序的效率和性能。

容器的分类

容器分为序列容器和关联容器。

序列容器的理解

序列容器是一种线性存储结构的容器，它以元素在容器中添加的顺序为序，所以序列容器支持在任意位置添加、删除元素。序列容器还支持多种排序算法，比如快速排序、归并排序等，可以对容器中的元素进行排序。序列容器的典型代表包括vector、deque、list、forward_list等。

关联容器的理解

关联容器则是基于键值对的存储结构的容器，元素以key-value的形式存储，并且关联容器中的元素按照key的大小自动排序。因此，我们可以将关联容器视为具有两个值的容器，其中一个值是用于标识元素的键，另一个值是元素自身的值。关联容器的一个重要特点是，它们是按照key的顺序进行排序的，而不是按照元素的插入顺序进行排序的。

关联容器的主要作用是将元素存储在有序的数据结构中，以便于进行查找操作。关联容器不支持直接修改元素的原因。是因为关联容器内部元素通常是基于红黑树、哈希表等有序的数据结构进行存储，这些数据结构的特性决定了它们的插入、删除、查找操作具有高效性，但修改操作的效率相对较低，因为在进行修改时，同时需要保持关联容器内部元素的有序性。如果直接修改某个元素的值，可能会导致关联容器内部元素的有序性受到破坏，进而影响到查找等操作的效率和正确性。因此，STL中的关联容器只支持添加、删除、查找等操作，而不支持直接修改元素。
虽然关联容器不支持直接修改元素，但是可以通过删除原有的元素，再添加一个新的元素来实现“修改”的效果。

STL中提供了两种关联容器：set和map。set容器仅仅存储关键字（key），而map容器存储一对键值对（key-value）。

迭代器的基础知识

迭代器的理解

当我们使用STL提供的算法来对容器进行操作时，例如排序、查找、遍历等，需要指定对哪些元素进行操作，这时就需要使用迭代器。
迭代器可以理解为就是通用的指针，它指向容器中某个元素，算法通过迭代器，可以访问容器中的元素，从而实现对容器的操作。

迭代器是用类模板构建的 ,本质是封装了原生指针 ，它模拟了指针的⼀些功能，通过重载了指针的⼀些操作符， -> 、 *、 ++ 、 -- 等。它是指针概念的⼀种提升，提供了比指针更高级的行为，相当于⼀种智能指针，他可以根据不同类型的数据结构来实现不同的++ ， -- 等操作。
比如指向数组元素的迭代器++操作，迭代器就会指向下一个元素，而指向链表的迭代器++操作，迭代器也会指向下一个元素操作。
迭代器的作用，本质就是为了能够让不同的容器，有通用的遍历容器元素的方式。

迭代器的使用举例

1
2
3
4
5
6
7
8
9
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    std::sort(v.begin(), v.end());
    return 0;
}
//在这个例子中，v.begin()和v.end()就是迭代器，它们分别指向vector中的第一个元素和最后一个元素的下一个位置。sort算法通过这两个迭代器来访问vector中的元素，实现排序的操作。

迭代器和指针的区别

在STL中，之所以不用指针来操控元素，而是用迭代器来操控元素，是因为不同的容器使用不同的数据结构来实现，如果使用指针来操控元素，就不利于算法的复用，同样的算法思想，不同的容器因为其数据结构不同，就得有不同的实现。

例如一个容器使用链表来存储元素，而另一个容器使用数组来存储元素。那么此时我们要对这两个容器进行遍历操作。
如果我们使用指向元素的指针来操作容器,那么，因为这两个容器用了不同的数据结构，我们就得根据这两个容器，实现这两个容器各自的遍历算法，比如指向数组元素的指针进行++，那么指针就将指向下一个元素，但如果是指向链表元素的指针进行++，指针就不一定指向下一个元素，因此，使用指针来操作容器，相同的算法就得根据不同的数据结构，来进行不同的实现。而这不利于代码的复用性。

而如果使用迭代器来操控容器，那么同一个遍历算法，就可以根据两个容器迭代器来操控两个容器。就大大提高了算法的复用性。比如指向数组元素的迭代器++，那么迭代器就是指向下一个元素。而指向链表元素的迭代++，迭代器也会将指向下一个元素。也就是说迭代器能够让不同的容器，有通用的遍历容器元素的方式。因此使用迭代器来操作容器，同一个算法可以作用于不同数据结构的容器。

迭代器的类别

输入迭代器：提供对数据的只读访问 ，支持++、==、！=
输出迭代器：提供对数据的只写访问 ，支持++
前向迭代器：提供读写操作，并能向前推进迭代器，支持读写、++、==、！=
双向迭代器：提供读写操作，并能向前和向后操作 ，支持读写、++、--，
随机访问迭代器：提供读写操作，并能以跳跃的方式访问容器的任意数据，是功能最强的迭代器支持读写、++、--、[n]、-n、<、<=、>、

使用迭代器遍历容器的举例


[[5.05-STL容器-未雨绸缪机制(Av432064775,P5).mp4#t=02:04.437,05:20,14:02]]

算法概述

函数对象（仿函数）的基础知识

函数对象的理解

STL中的函数对象，是一个类对象（不是普通的函数或函数指针），但他可以像函数一样去执行，因此被称为函数对象（仿函数）。
函数对象的本质，是重载函数调用操作符的类的对象。重载函数调用操作符的类，其实就是重载“()”操作符的类，使得类对象可以像函数那样调用，因此也被叫仿函数(functor)。

注意:
1.函数对象(仿函数)是一个类对象，不是一个函数。
2.函数对象(仿函数)重载了”() ”操作符使得它可以像函数一样调用

函数对象的分类

假定某个类有一个重载的 operator()，而且重载的 operator()要求获取一个参数，我们就将这个类称为“一元仿 函数”（unary functor）；相反，如果重载的 operator()要求获取两个参数，就将这个类称为“二元仿函数”（binary functor）

函数对象的举例说明

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
//函数对象是重载了函数调用符号的类
class MyPrint
{
public:
	int m_Num;
	MyPrint()
	{
		m_Num = 0;
	}
	
public:
	void operator() (int num)
	{
		cout << num << endl;
		m_Num++;
	}
};

//函数对象

//重载了()操作符的类实例化的对象，可以像普通函数那样调用,可以有参数 ，可以有返回值
void test01()
{
	MyPrint myPrint;
	myPrint(20);
}


// 函数对象超出了普通函数的概念，可以保存函数的调用状态
void test02()
{
	MyPrint myPrint;
	myPrint(20);
	myPrint(20);
	myPrint(20);
	cout << myPrint.m_Num << endl;
}

//函数对象作为参数
void doBusiness(MyPrint print,int num)
{
	print(num);
}

void test03()
{
	//参数 1：匿名函数对象
	doBusiness(MyPrint(),30);
}
/*
1、函数对象通常不定义构造函数和析构函数，所以在构造和析构时不会发生任何问题，避免了函数调用的运行时问题。 
2、函数对象超出普通函数的概念，函数对象可以有自己的状态 
3、函数对象可内联编译，性能好。用函数指针几乎不可能 
4、模版函数对象使函数对象具有通用性，这也是它的优势之一*/

谓词的基础知识

谓词的理解

谓词指的是返回值是bool类型的函数，或者是重载“()”操作符且返回值是bool类型的类的对象。总的来说，谓词就是bool类型的函数，或者是bool类型的函数对象。
谓词接受一个参数，那么叫做一元谓词,如果接受两个参数，那么叫做二元谓词。
谓词的本质，就是可以用来是接受一个或多个参数，并返回一个bool值的函数或者函数对象，他可以用于表示一个条件是否成立。
在STL中，谓词被广泛应用于算法，例如在排序、查找、去重等算法中都需要传入一个谓词参数，用来定义这些算法在使用的过程中，遵守什么样的规则。以排序算法为例，当需要对一个序列进行排序时，可以使用sort函数，并传入一个谓词参数，用于定义排序的规则。

作为谓词的函数或函数对象需要满足以下条件：

  1. 返回值必须是 bool 类型，表示谓词的真假值。
  2. 接受一个或多个参数，用来进行判断。

谓词的使用举例1

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

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

bool greater_than_or_equal_to_5(int x) {
    return x >= 5;
}

int main() {
    std::vector<int> v{1, 3, 5, 7, 9};
    
    // 使用 std::find_if() 和谓词 greater_than_or_equal_to_5 查找大于等于 5 的元素。std::find_if 算法会对指定范围内的每个元素都调用谓词 greater_than_or_equal_to_5，直到找到第一个满足条件的元素，然后返回该元素的迭代器。所以，执行该代码可以查找大于等于 5 的元素
	auto it = std::find_if(v.begin(), v.end(), greater_than_or_equal_to_5);
    while (it != v.end()) {
        std::cout << *it << " ";
        it = std::find_if(++it, v.end(), greater_than_or_equal_to_5);
    }
    
    return 0;
}

/*
在这个例子中，我们定义了一个名为 greater_than_or_equal_to_5 的谓词，它接受一个整数参数 x，如果 x 大于等于 5，就返回 true，否则返回 false。
然后，我们使用标准算法 std::find_if() 结合谓词 greater_than_or_equal_to_5 查找大于等于 5 的元素。在循环中，每次找到一个符合条件的元素就打印出来，并继续查找下一个符合条件的元素，直到查找到容器的末尾。
*/

谓词的使用举例2

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
class MyCompare
{
	public:
	bool operator()(int num1, int num2)
	{
		return num1 > num2;
	}
};
void test02()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(40);
	v.push_back(20);
	v.push_back(90);
	v.push_back(60);
	//默认快速排序，是从小到大的排序
	sort(v.begin(), v.end());
	//这里循环输出的是从小到大的序列
	for (vector<int>::iterator it = v.begin(); it != v.end();it++)
	{
		cout << *it << " ";
	}
	cout << endl;
	cout << "----------------------------" << endl;
	
	//使用函数对象作为谓词参数传入，改变算法策略，使排序从大到小
	sort(v.begin(), v.end(),MyCompare());
	//这时候输出的序列就是从大到小
	for (vector<int>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
		cout << endl;
}

使用例子3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <algorithm>
#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {4, -2, 5, -1, 3, -6};
    std::sort(v.begin(), v.end(), [](int a, int b) {
        return std::abs(a) < std::abs(b);
    });
    for (auto x : v) {
        std::cout << x << " ";
    }
    // output: -1 3 4 -2 5 -6
    return 0;
}
/*
在这个例子中，我们使用一个匿名函数作为sort函数的第三个参数，该函数接受两个int类型的参数，分别表示vector中的两个元素a和b，比较它们的绝对值大小，返回a的绝对值是否小于b的绝对值。这样，sort函数就会按照元素的绝对值大小进行排序。
*/

内建函数对象的基础知识

内建函数对象的理解

STL内建了一些函数对象。在 STL中内建这些函数对象，是为了配合 STL 的算法，实现更加灵活和泛化的操作。
例如，假设需要对一个容器中的所有元素进行加1，一般就得用for循环，让每一个元素都用普通的运算符进行加1，而如果使用算术类函数对象plus，配合transform算法，就可以轻松完成。
另外，函数对象可以被编译器优化，因为函数对象可以被内联，所以在一些情况下，使用函数对象可以比使用普通函数或运算符更加高效。但在一些简单的场景下，使用函数对象可能会比直接使用运算符或函数略显繁琐，所以需要根据具体的情况来选择使用哪种方式。

内建函数对象分类

氛围算数类函数对象,关系运算类函数对象，逻辑运算类仿函数。
这些函数对象，用法和一般函数完全相同，当然我们还可以产生无名的临时对象来履行函数功能。

内建函数对象的头文件

使用内建函数对象，需要引入头文件 #include<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

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
struct add_two {
    int operator()(int x) const {
        return x + 2;
    }
};


int main() {
    vector<int> v{1, 2, 3, 4, 5};

    // 使用std::transform算法和std::plus函数对象，将v中的每个元素加1
	//执行代码时，std::transform算法对v中的每个元素调用plus<int>对象的operator()函数，并将该元素作为第一个参数和1作为第二个参数传递给operator()函数，然后将函数返回的结果存储在v中对应的位置。
    transform(v.begin(), v.end(), v.begin(), plus<int>());
    

    // 输出v中的元素
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

	//使用自定义的函数对象 `add_two`，并将其传递给 `std::transform` 算法作为参数。在 `std::transform` 中，每个元素都会被依次传递给 `add_two` 对象的 `operator()` 方法，该方法会将输入的值加 2 并返回。
	transform(v.begin(), v.end(), v.begin(), add_two());
	

    // 使用ransform算法和multiplies函数对象，将v中的每个元素乘2
    transform(v.begin(), v.end(), v.begin(), multiplies<int>());

    // 输出v中的元素
    for (auto it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";
    }
    cout <<endl;

    return 0;
}

适配器

适配器的理解

适配器可以用来改变函数对象的参数或返回值。以便更好地适应某些函数或算法的需求。
比如使用binder1st适配器或者binder2nd适配器，binder1st将二元函数对象的第一个参数绑定为一个固定值，而binder2nd将二元函数对象的第二个参数绑定为一个固定值。这样就可以将原本需要两个参数的函数对象适配成只需要一个参数的函数对象。
这样作的目的是因为，比如有些算法用一元函数对象作为参数传入，但是我们又得在这个算法中，用到某个二元函数对象，那么我们就可以用适配器，将二元函数对象改成1元函数对象。

适配器的使用注意事项

如果是使用stl内建的函数对象，则可以直接使用适配器，STL的许多内建函数对象已经继承了binary_function或者unary_function，所以我们可以直接使用适配器来改变这些函数对象的参数。

但是如果是我们自己写的函数对象，就得让类继承binary_function 或者 unary_function，否则编译器会报错。
这是因为们自己写的函数对象没有继承binary_function或者unary_function，编译器就无法推断其参数类型，只有在继承binary_function或者unary_function，编译器才能推断你写的函数对象的类型。
一元函数对象所在类继承public unary_function<参数1 ,返回值类型>
二元继承public binary_function<int,int,void>

常用适配器

  • binder1st和binder2nd：用于将一个二元函数对象适配成一个一元函数对象。
  • not1和not2：用于将一个一元或二元函数对象的返回值取反。
  • negate：用于将一个一元函数对象的返回值取负。
  • compose1和compose2：用于将两个一元或二元函数对象组合成一个新的函数对象。
  • identity：用于将一个元素作为函数对象的参数，并将其原样返回。

适配器的返回值

auto f1 = std::bind1st(MyFunc(), 10);
将第一个参数绑定为10，这句代码std::bind1st(MyFunc(), 10)的返回值是一个函数对象，该函数对象的第一个参数已经被绑定为10。

内建函数对象使用适配器的举例1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//假设有一个 vector<int> v，我们要将其中所有小于 5 的元素替换成 0，大于5的替换为1
#include <algorithm>
#include <functional>
#include <vector>
#include <iostream>
using namespace std;

int main() {
  vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

  transform(v.begin(), v.end(), v.begin(), bind2nd(less<int>(), 5));

  for (auto i : v) {
    cout << i << " ";
  }
  cout << endl;
//最终输出为0000111111
}

自己建立的函数对象使用视频举例1

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
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
//一元继承public unary_function<参数1 ,返回值类型>
//二元继承public  binary_function<int,int,void>
//`Print`继承自`binary_function<int, int, bool>`，它告诉编译器，这个函数对象接受两个int类型的参数，并返回一个bool类型的结果。现在我们再用`bind2nd`绑定第二个参数，编译就不会报错了。
class Print:public   binary_function<int, int, void>
{
	public:
		void operator()(int  a ,int  num)const
		{
			cout << a << " " << num << endl;
			cout << a +num<< endl;
		}
};
void  test()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	for_each(v.begin(),v.end(), bind2nd(Print(),200));


}

int main()
{
	test();
	return 0;
}

自己建立的函数对象使用视频举例2

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
class GreaterThenFive:public unary_function<int,bool>
{
	public:
	bool operator ()(int v) const
	{
		return v > 5;
	}
};
//2、取反适配器
void test02()
{
	vector <int> v;
	for (int i = 0; i < 10;i++)
	{

		v.push_back(i);
	}
		// vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterThenFive()); 返回第一个大于 5 的迭代器
	
	
	// vector<int>::iterator it = find_if(v.begin(), v.end(), not1(GreaterThenFive()));返回第一个小于等于 5 迭代器
	
	/自定义输入
	vector<int>::iterator it = find_if(v.begin(), v.end(), not1 ( bind2nd(greater<int>(),5)));
	if (it == v.end())
	{
		cout << "没找到" << endl;
	}
	else
	{
		cout << "找到" << *it << endl;
	}
	//排序 二元函数对象
	sort(v.begin(), v.end(), not2(less<int>()));
	for_each(v.begin(), v.end(), [](int val){cout << val << " "; });
}
//not1 对一元函数对象取反
//not2 对二元函数对象取反

算法的基础知识

算法的分类

[[1.01-STL容器-STL的概述(Av432064775,P1).mp4#t=11:03,11:33]]

质变算法：是指运算过程中会更改区间内的元素的内容。例如拷贝，替换，删除等等

非质变算法：是指运算过程中不会更改区间内的元素内容，例如查找、计数、遍 历、寻找极值等

所需头文件

#include<algorithm>