STL初级

先说明一下为什么要单独把STL作为一个博客来写，本来是打算直接在CPP里面写STL，但是后来发现这个领域的知识点过于庞大，同时因为需要参考的资料较多所以单独整理相关知识点；

主要参考https://www.bilibili.com/video/BV1et411b73Z?p=185&vd_source=276d55048634a5b508b1b53a1ecd56b3
《STL源码剖析》

C语言中文网C++ STL标准库基础 (biancheng.net)

黑马教程文档https://www.aliyundrive.com/s/6see7VR7KGR

初级篇的话就简单的结合代码以及文档敲一下熟悉一下，之后高级篇详细参考《STL源码剖析》进行学习

绪论（一）

● 长久以来，软件界一直希望建立一种可重复利用的东西
● C++的面向对象和泛型编程（泛型编程主要基于模板技术实现）思想，目的就是复用性的提升
● 大多情况下，数据结构和算法都未能有一套标准,导致被迫从事大量重复工作
● 为了建立数据结构和算法的一套标准,诞生了STL

1.模板

之前在C++的笔记里面稍微学习了一下模板，但是相关知识点并不是特别扎实，因为STL就是基于C++的模板所以介绍一下模板相关概念；

  • 模板的概念可以类比生活中PPT模板等，不可以直接使用，仅仅只是一个框架；
  • 模板的通用并不是指万能的通用，其通用性会受到一定的制约；
  • C++的泛型编程依赖的技术就是模板技术，C++提供两种模板机制：函数模板和类模板

1.1 函数模板

（1）简介

函数模板作用：建立一个通用函数，其函数返回值类型和形参类型可以不具体制定，用一个虚拟的类型来代表（注意这之后我们就简单的认为函数模板和模板函数指的是同一个概念不再仔细区分）

  • 格式
1
2
3
4
5
6
template<typename T>
函数声明或定义

//template  ---  声明创建模板
//typename  --- 表面其后面的符号是一种数据类型，可以用class代替
//T    ---   通用的数据类型，名称可以替换，通常为大写字母
  • 示例
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
//交换整型函数
void swapInt(int& a, int& b) {
	int temp = a;
	a = b;
	b = temp;
}

//交换浮点型函数
void swapDouble(double& a, double& b) {
	double temp = a;
	a = b;
	b = temp;
}

//利用模板提供通用的交换函数
template<typename T>
void mySwap(T& a, T& b)
{
	T temp = a;
	a = b;
	b = temp;
}

//调用模板函数
//第一种方式，自动类型推导---自动类型推导，必须推导出一致的数据类型T,才可以使用，比如a是int，b是char则导致T类型不同失败
mySwap(a, b);	
//第二种方式，显示指定类型---推荐，因为可以自己确定通用类型T
mySwap<int>(a, b);

注意：无论是第一种调用方式还是第二种调用方式，模板函数必须要确定出T的数据类型，才可以使用

普通函数和模板函数的区别：

  • 普通函数调用时可以发生自动类型转换（隐式类型转换）
  • 函数模板调用时，如果利用自动类型推导，不会发生隐式类型转换
  • 如果利用显示指定类型的方式，可以发生隐式类型转换

普通函数和模板函数调用规则：

  • 如果函数模板和普通函数都可以实现，优先调用普通函数
  • 可以通过空模板参数列表来强制调用函数模板
  • 函数模板也可以发生重载
  • 如果函数模板可以产生更好的匹配,优先调用函数模板

综上，既然提供了函数模板，最好就不要提供普通函数，否则容易出现二义性

（2）模板重载

前面我们说过函数模板尽管概念上是通用的，但实际上还是会受到一些制约，比如上面的mySwap()函数模板，假如a和b都是数组则失效（因为数组不可以直接进行等号赋值）；

为了解决上述问题，C++提供了针对模板的重载，可以为这些特定的类型提供具体化的模板；

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
//普通函数模板
template<class T>
bool myCompare(T& a, T& b)
{
	if (a == b)
	{
		return true;
	}
	else
	{
		return false;
	}
}


//具体化，显示具体化的原型和定义以template<>开头，并通过名称来指出类型
//具体化优先于常规模板
template<> bool myCompare(Person &p1, Person &p2)
{
	if ( p1.m_Name  == p2.m_Name && p1.m_Age == p2.m_Age)
	{
		return true;
	}
	else
	{
		return false;
	}
}

1.2 类模板

（1）简介

类模板作用：建立一个通用类，类中的成员数据类型可以不具体制定，用一个虚拟的类型来代表；

  • 格式
1
2
3
4
5
6
template<typename T>
类

//template  ---  声明创建模板
//typename  --- 表面其后面的符号是一种数据类型，可以用class代替
//T    ---   通用的数据类型，名称可以替换，通常为大写字母

类模板和函数模板语法相似，在声明模板template后面加类定义，称为类模板

  • 示例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//类模板
template<class NameType, class AgeType> 
class Person
{
public:
	Person(NameType name, AgeType age)
	{
		this->mName = name;
		this->mAge = age;
	}
	void showPerson()
	{
		cout << "name: " << this->mName << " age: " << this->mAge << endl;
	}
public:
	NameType mName;
	AgeType mAge;
};

类模板与函数模板的区别：

  • 类模板没有自动类型推导的使用方式；

  • 类模板在模板参数列表中可以有默认参数；

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
//类模板定义
template<class NameType, class AgeType = int> //类模板中的模板参数列表可以有默认参数
class Person
{
public:
	Person(NameType name, AgeType age)
	{
		this->mName = name;
		this->mAge = age;
	}
	void showPerson()
	{
		cout << "name: " << this->mName << " age: " << this->mAge << endl;
	}
public:
	NameType mName;
	AgeType mAge;
};

//1.类模板没有自动类型推导的使用方式
void test01()
{
	// Person p("孙悟空", 1000); // 错误，类模板使用时候，不可以用自动类型推导
	Person <string ,int>p("孙悟空", 1000); //必须使用显示指定类型的方式，使用类模板
	p.showPerson();
}

//2.类模板在模板参数列表中可以有默认参数，也就意味着显式指定类型只需要指定没有设置默认参数的那个参数的数据类型
void test02()
{
	Person <string> p("猪八戒", 999); //类模板中的模板参数列表可以指定默认参数
	p.showPerson();
}

（2）继承

当类模板碰到继承时，需要注意以下几点：

  • 当子类继承的父类是一个类模板时，子类在声明的时候，要指定出父类中T的类型；
  • 如果不指定，编译器无法给子类分配内存；
  • 如果想灵活指定出父类中T的类型，子类也需变为类模板；
1
2
3
4
5
6
7
8
9
10
11
//当子类继承的父类是一个类模板时，子类在声明的时候，要指定出父类中T的类型
template<class T>
class Base
{
	T m;
};

//class Son:public Base  //错误，c++编译需要给子类分配内存，必须知道父类中T的类型才可以向下继承
class Son :public Base<int> //必须指定一个类型
{
};
1
2
3
4
5
6
7
8
9
10
11
//类模板继承类模板 ,可以用T2指定父类中的T类型
template<class T>
class Base
{
	T m;
};

template<class T1, class T2>
class Son2 :public Base<T2>
{
};

2.STL基本概念

● STL(Standard Template Library,标准模板库)
● STL 从广义上分为: 1.容器(container) 2.算法(algorithm) 3.迭代器(iterator)
● 容器和算法之间通过迭代器进行无缝连接。
● STL 几乎所有的代码都采用了模板类或者模板函数
● C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。例如，vector 的底层为顺序表（数组），list 的底层为双向链表，deque 的底层为循环队列，set 的底层为红黑树，hash_set 的底层为哈希表。

下面使用一个直观的案例解释STL和常规C++编程的区别；

我们需要定义一个长度可变的数组，使用在堆空间动态申请内存的方法创建一个动态数组并扩容

1
2
3
4
5
6
7
8
9
10
//定义一个动态数组，名称为p，初始长度为n
int *p = new int[n];
//当数组p存储空间不够需要扩容时，按照如下步骤进行
//1.新申请一个较大的内存空间
int temp = new int[m];
//2.将原内存空间的数据全部复制到新申请的内存空间中
memecpy(temp,p,sizeof(int)*n);
//3.将原堆空间释放
delete [] p;
p = temp;

借助STL库完成相同操作

1
2
3
4
5
6
7
8
9
10
11
12
//定义 a 数组，当前数组长度为 0，但和普通数组不同的是，此数组 a 可以根据存储数据的数量自动变长。
vector <int> a; 
//向数组 a 中添加 10 个元素，数值0~9
for (int i = 0; i < 10 ; i++)
    a.push_back(i)
//还可以手动调整数组 a 的大小，这里调整为100
a.resize(100);
a[90] = 100;
//还可以直接删除数组 a 中所有的元素，此时 a 的长度变为 0
a.clear();
//重新调整 a 的大小为 20，并存储 20 个值为 -1 的元素
a.resize(20, -1)

3.STL六大组件

前面四部分组件是为了后面两部分组件服务的

  1. 容器：各种数据结构，如vector、list、deque、set、map等,用来存放数据。
  2. 算法：各种常用的算法，如sort、find、copy、for_each等
  3. 迭代器：扮演了容器与算法之间的胶合剂。
  4. 仿函数：行为类似函数，可作为算法的某种策略。
  5. 适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。
  6. 空间配置器：负责空间的配置与管理。

我们通过下面这个表格展示STL六大组件之间的关系和作用

3.1 容器

容器：置物之所也(这里提到的容器，本质上就是封装有数据结构的模板类，例如 list、vector、set、map 等)
STL容器就是将运用最广泛的一些数据结构实现出来，常用的数据结构：数组, 链表,树, 栈, 队列, 集合, 映射表等
这些容器分为序列式容器和关联式容器两种:
● 序列式容器:序列式容器中的每个元素均有固定的位置。
● 关联式容器:排序容器和哈希容器都属于这一类，通常是二叉树结构，各元素之间没有严格的物理上的顺序关系

3.2 算法

算法：问题之解法也

有限的步骤，解决逻辑或数学上的问题，这一门学科称为算法(Algorithms)——STL中用函数封装算法，函数是具体算法的实现（STL中封装算法的函数一般都是模板函数，可用于多种容器，算法通过迭代器对容器做操作）

算法分为:质变算法和非质变算法。

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

3.3 迭代器

C++ 中，数组就是容器，数组的迭代器就是指针，而且是随机访问迭代器；

迭代器：容器和算法之间的中介，简单来说就是迭代器是一个通用的用于遍历各种容器的一套抽象代码；

迭代器提供了一种方法，使之能够依序寻访某个容器所含的各个元素（简单来说就是遍历容器中存储的元素），而又无需暴露该容器的内部表示方式，从而以统一的界面向算法传送数据；

每个容器都有自己专属的迭代器，不同容器的迭代器也不同，其功能强弱也有所不同。容器的迭代器的功能强弱，决定了该容器是否支持 STL 中的某种算法（迭代器决定了容器能够使用的算法）；

迭代器使用非常类似于指针，初学阶段我们可以先理解迭代器为指针，关于为什么C++有指针还需要迭代器可以参考(19条消息) STL中迭代器的作用，有指针为何还要迭代器_子木呀的博客-CSDN博客_有指针为何还要迭代器；

常用的容器中迭代器种类为前向迭代器、双向迭代器和随机访问迭代器（迭代器概念源自于 C/C++ 中原生指针的一般化推广）

(1) 前向迭代器（forward iterator）

假设 p 是一个前向迭代器，则 p 支持 ++p，p++，*p 操作，还可以被复制或赋值，可以用 == 和 != 运算符进行比较。此外，两个正向迭代器可以互相赋值。

(2) 双向迭代器（bidirectional iterator）

双向迭代器具有正向迭代器的全部功能，除此之外，若 p 是一个双向迭代器，则还可以进行 --p 或者 p-- 操作（即一次向后移动一个位置）。

(3) 随机访问迭代器（random access iterator）

随机访问迭代器具有双向迭代器的全部功能。除此之外，假设 p 是一个随机访问迭代器，i 是一个整型变量或常量，则 p 还支持以下操作：

    • p+=i：使得 p 往后移动 i 个元素。
    • p-=i：使得 p 往前移动 i 个元素。
    • p+i：返回 p 后面第 i 个元素的迭代器。
    • p-i：返回 p 前面第 i 个元素的迭代器。
    • p[i]：返回 p 后面第 i 个元素的引用。

  • 不同容器指定使用的迭代器类型

  • 尽管不同容器对应着不同类别的迭代器，但这些迭代器有着较为统一的定义方式（注意是迭代器的定义方式！而不能决定迭代器的类型（迭代器的类型是容器已经规定好了的），容器通过这些方式/某些方式可以定义属于自己的迭代器。通过不同的方式定义的容器的迭代器会有不同的附加属性，当然容器的迭代器本身因为属于不同种类所以也会自带属性；而实际上容器也包含了一些与迭代器相关的成员函数，因此可以不用手动定义迭代器而使用某个成员函数的返回值作为迭代器使用

    通过以上几种方式定义的迭代器，就可以读取它指向的元素，*迭代器名就表示迭代器指向的元素（这一点和指针很相似）

    • 对正向迭代器进行 ++ 操作时，迭代器会指向容器中的后一个元素；

    • 对反向迭代器进行 ++ 操作时，迭代器会指向容器中的前一个元素；

    • 通过非常量迭代器能修改其指向的元素；

    • 以上 4 种定义迭代器的方式，并不是每个容器都适用。有一部分容器同时支持以上 4 种方式，比如 array、deque、vector；而有些容器只支持其中部分的定义方式，例如 forward_list 容器只支持定义正向迭代器，不支持定义反向迭代器

序列式容器（二）

所谓STL序列式容器，即以线性排列来存储某一指定类型（例如 int、double 等）的数据，其共同的特点是不会对存储的元素进行排序，元素排列的顺序取决于存储它们的顺序

需要注意的是，序列容器只是一类容器的统称，并不指具体的某个容器。主要包含以下几类容器：

  1. array< T,N>（数组容器）：表示可以存储 N 个 T 类型的元素，是 C++ 本身提供的一种容器。此类容器一旦建立，其长度就是固定不变的，这意味着不能增加或删除元素，只能改变某个元素的值；
  2. vector< T>（向量容器）：用来存放 T 类型的元素，是一个长度可变的序列容器，即在存储空间不足时，会自动申请更多的内存。使用此容器，在尾部增加或删除元素的效率最高（时间复杂度为 O(1) 常数阶），在其它位置插入或删除元素效率较差（时间复杂度为 O(n) 线性阶，其中 n 为容器中元素的个数）；
  3. deque< T>（双端队列容器）：和 vector 非常相似，区别在于使用该容器不仅尾部插入和删除元素高效，在头部插入或删除元素也同样高效，时间复杂度都是 O(1) 常数阶，但是在容器中某一位置处插入或删除元素，时间复杂度为 O(n) 线性阶；
  4. list< T>（链表容器）：是一个长度可变的、由 T 类型元素组成的序列，它以双向链表的形式组织元素，在这个序列的任何地方都可以高效地增加或删除元素（时间复杂度都为常数阶 O(1)），但访问容器中任意元素的速度要比前三种容器慢，这是因为 list< T> 必须从第一个元素或最后一个元素开始访问（这是链表的通病），需要沿着链表移动，直到到达想要的元素。
  5. forward_list< T>（正向链表容器）：和 list 容器非常类似，只不过它以单链表的形式组织元素，它内部的元素只能从第一个元素开始访问，是一类比链表容器快、更节省内存的容器。

1.array容器

array 容器就是在 C++ 普通数组的基础上，添加了一些成员函数和全局函数。在使用上，它比普通数组更安全（原因后续会讲），且效率并没有因此变差；

和其它容器不同，array 容器的大小是固定的，无法动态的扩展或收缩，这也就意味着，在使用该容器的过程无法借由增加或移除元素而改变其大小，它只允许访问或者替换存储的元素；

  • 类模板形式定义
1
2
3
4
namespace std{
    template <typename T, size_t N>
    class array;
}

array<T,N> 类模板中，T 用于指明容器中的存储的具体数据类型，N 用于指明容器的大小，需要注意的是，这里的 N 必须是常量，不能用变量表示

1.1 创建array容器

1
2
//创建具有 10 个 double 类型元素的 array 容器
std::array<double, 10> values;
1
2
//创建具有 10 个 double 类型元素的 array 容器，且将所有的元素初始化为 0 或者和默认元素类型等效的值
std::array<double, 10> values {};
1
2
3
//创建array容器的过程中直接赋值初始化
std::array<double, 10> values {0.5,1.0,1.5,,2.0};
//这里只初始化了前 4 个元素，剩余的元素都会被初始化为 0.0

1.2 array容器成员函数

1.3 array随机访问迭代器

疑问：当迭代器指向容器中的一个特定元素时，它们不会保留任何关于容器本身的信息，所以我们无法从迭代器中判断它是指向 array 容器还是指向 vector 容器（这个有点难理解，因为指针的话其实是可以根据其指针类型判断它属于哪个数据类型，迭代器在定义的时候也使用了容器类名参与定义的，为什么这里就说不保留容器的细节了呢？）

在 array 容器的模板类中和随机访问迭代器相关的成员函数有

以上函数在实际使用时，其返回值类型都可以使用 auto 关键字代替，编译器可以自行判断出该迭代器的类型

（1）array 容器模板类中的 begin() 和 end() 成员函数返回的都是正向迭代器，它们分别指向「首元素」和「尾元素+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
//在循环中显式地使用迭代器来初始化 values 容器的值
#include <iostream>
//需要引入 array 头文件
#include <array>
using namespace std;

int main()
{	//创建values容器
    array<int, 5>values;
    int h = 1;
    //设置迭代器（注意这里不需要我们手动再使用容器类名::iterator 迭代器名这种方式去定义迭代器，因为使用begin()方法返回的就是一个迭代器用一个变量接收即可）
    auto first = values.begin();
    auto last = values.end();
    //初始化 values 容器为{1,2,3,4,5}
    while (first != last)
    {
        *first = h;
        ++first;
        h++;
    }
   //重定位迭代器，用于接下来遍历输出容器中的元素
    first = values.begin();
    while (first != last)
    {
        cout << *first << " ";
        ++first;
    }
    return 0; 
}

（2）array 模板类还提供了 cbegin() 和 cend() 成员函数，它们和 begin()/end() 唯一不同的是，前者返回的是 const 类型的正向迭代器，这就意味着，有 cbegin() 和 cend() 成员函数返回的迭代器，可以用来遍历容器内的元素，也可以访问元素，但是不能对所存储的元素进行修改；

（3）array 模板类中还提供了 rbegin()/rend() 和 crbegin()/crend() 成员函数，它们每对都可以分别得到指向最后一个元素和第一个元素的前一个位置的随机访问迭代器，又称它们为反向迭代器；

需要注意的是，在使用反向迭代器进行 ++ 或 – 运算时，++ 指的是迭代器向左移动一位，– 指的是迭代器向右移动一位，即这两个运算符的功能也“互换”了；

（4）crbegin()/crend() 组合和 rbegin()/crend() 组合的功能唯一的区别在于，前者返回的迭代器为 const 类型，即不能用来修改容器中的元素，除此之外在使用上和后者完全相同；

1.4 array容器访问元素

当 array 容器创建完成之后，最常做的操作就是获取其中的元素，甚至有时还会通过循环结构获取多个元素；

我们当然可以通过迭代器简单方便的无视数据结构访问array容器中的元素，但是假如我们依赖于array容器的数据结构访问其中的元素，有下面这些方法；

（1）直接访问

可以通过容器名[]的方式直接访问和使用容器中的元素，这和 C++ 标准数组访问元素的方式相同

1
values[4] = values[3] + 2.O*values[1];

使用如上这样方式，由于没有做任何边界检查，所以即便使用越界的索引值去访问或存储元素，也不会被检测到;

（2）at()成员函数

为了能够有效地避免越界访问的情况，可以使用 array 容器提供的 at() 成员函数

1
values.at (4) = values.at(3) + 2.O*values.at(1);

这行代码和前一行语句实现的功能相同，其次当传给 at() 的索引是一个越界值时，程序会抛出 std::out_of_range 异常。因此当需要访问容器中某个指定元素时，建议大家使用 at()，除非确定索引没有越界。

（3）get< n >模板函数

c++中的<>代表C++模板

get< n > 模板函数，它是一个辅助函数，能够获取到容器的第 n 个元素

1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <array>
#include <string>
using namespace std;
int main()
{
    array<string, 5> words{ "one","two","three","four","five" };
    cout << get<3>(words) << endl; // Output words[3]也就是字符串"four"
    //cout << get<6>(words) << std::endl; //越界，会发生编译错误
    return 0;
}

该模板函数中，参数的实参必须是一个在编译时可以确定的常量表达式，所以它不能是一个循环变量。也就是说，它只能访问模板参数指定的元素，编译器在编译时会对它进行检查。

（4）data成员函数

data() 成员函数，通过调用该函数可以得到指向容器首个元素的指针，通过该指针，我们可以获得容器中的各个元素

1
2
3
4
5
6
7
8
9
#include <iostream>
#include <array>
using namespace std;
int main()
{
    array<int, 5> words{1,2,3,4,5};
    cout << *( words.data()+1);//输出结果为2
    return 0;
}

上面介绍的都是访问array容器中的单个元素，下面我们介绍访问array容器多个元素的方法

（5）for循环

使用size() 函数返回容器中元素的个数，进而实现for循环；

1
2
3
4
5
double total = 0;
for(size_t i = 0 ; i < values.size() ; ++i)
{
    total += values[i];
}

size() 函数的存在，为 array 容器提供了标准数组所没有的优势，即能够知道它包含多少元素（普通数组是没有size()函数的，而sizeof()函数用于获取对象所占内存空间的大小，length()函数只能用于获取字符串的长度）

2.vector容器

vector容器和 array 容器非常类似，都可以看做是对C++普通数组的“升级版”。不同之处在于，array 实现的是静态数组（容量固定的数组），而 vector 实现的是一个动态数组，即可以进行元素的插入和删除，在此过程中，vector 会动态调整所占用的内存空间，整个过程无需人工干预。

vector 常被称为向量容器，因为该容器擅长在尾部插入或删除元素，在常量时间内就可以完成，时间复杂度为O(1)；而对于在容器头部或者中部插入或删除元素，则花费时间要长一些（移动元素需要耗费时间），时间复杂度为线性阶O(n)。

2.1 创建vector容器

（1）创建存储 double 类型元素的一个 vector 容器

1
std::vector<double> values;

注意，这是一个空的 vector 容器，因为容器中没有元素，所以没有为其分配空间。当添加第一个元素（比如使用 push_back() 函数）时，vector 会自动分配内存

（2）在创建的同时指定初始值以及元素个数

1
2
//2.在创建的同时指定初始值以及元素个数，创建一个含有 8 个素数的 vector 容器
std::vector<int> primes {2, 3, 5, 7, 11, 13, 17, 19};

（3）在创建 vector 容器时，也可以指定元素个数

1
2
//3.在创建 vector 容器时，也可以指定元素个数为20，它们的默认初始值都为 0
std::vector<double> values(20);

注意，圆括号 () 和大括号 {} 是有区别的，前者（例如 (20) ）表示元素的个数，而后者（例如 {20} ） 则表示 vector 容器中只有一个元素 20

1
2
//如果不想用 0 作为默认值，也可以指定一个其它值，这 20 个元素的值都是 1.0
std::vector<double> values(20, 1.0);

注意，值得一提的是，圆括号 () 中的 2 个参数，既可以是常量，也可以用变量来表示

1
2
3
int num=20;
double value =1.0;
std::vector<double> values(num, value);

（4）通过存储元素类型相同的其它 vector 容器，也可以创建新的 vector 容器

1
2
std::vector<char>value1(5, 'c');
std::vector<char>value2(value1);

如果不想复制其它容器中所有的元素，可以用一对指针或者迭代器来指定初始值的范围

1
2
3
4
5
int array[]={1,2,3};
std::vector<int>values(array, array+2);//values 将保存{1,2}

std::vector<int>value1{1,2,3,4,5};	//value1将保存{1,2,3,4,5}
std::vector<int>value2(std::begin(value1),std::begin(value1)+3);//value2保存{1,2,3}

2.2 vector容器成员函数

2.3 vector随机访问迭代器

vector 模板类提供的操作迭代器的成员函数和 array 容器一样

以上函数在实际使用时，其返回值类型都可以使用 auto 关键字代替，编译器可以自行判断出该迭代器的类型

（1）首先来看 begin() 和 end() 成员函数，它们分别用于指向「首元素」和「尾元素+1」 的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
//需要引入 vector 头文件
#include <vector>
using namespace std;
int main()
{	//创建values容器
    vector<int>values{1,2,3,4,5};
    //创建first迭代器和end迭代器
    auto first = values.begin();
    auto end = values.end();
    //遍历输出values容器中的元素
    while (first != end)
    {
        cout << *first << " ";
        ++first;
    }
    return 0;
}

（2）cbegin()/cend() 成员函数和 begin()/end() 唯一不同的是，前者返回的是 const 类型的正向迭代器，这就意味着，由 cbegin() 和 cend() 成员函数返回的迭代器，可以用来遍历容器内的元素，也可以访问元素，但是不能对所存储的元素进行修改；

（3）vector 模板类中还提供了 rbegin() 和 rend() 成员函数，分别表示指向最后一个元素和第一个元素前一个位置的随机访问迭代器，又称它们为反向迭代器；

在使用反向迭代器进行 ++ 或 – 运算时，++ 指的是迭代器向左移动一位，– 指的是迭代器向右移动一位，即这两个运算符的功能也“互换”了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//反向迭代器用于以逆序的方式遍历容器中的元素
#include <iostream>
//需要引入 vector 头文件
#include <vector>
using namespace std;
int main()
{
    vector<int>values{1,2,3,4,5};
    //first迭代器指向最后一个元素
    auto first = values.rbegin();
    //end迭代器指向第一个元素的前一个位置
    auto end = values.rend();
    while (first != end)
    {
        cout << *first << " ";
        ++first;//实际上指的是first迭代器向左移动一位
    }
    return 0;
}
//输出结果为5 4 3 2 1

（4）crbegin()/crend() 组合和 rbegin()/crend() 组合唯一的区别在于，前者返回的迭代器为 const 类型，即不能用来修改容器中的元素，除此之外在使用上和后者完全相同

vector迭代器的特点：

  • 与array 容器不同，vector 容器可以随着存储元素的增加，自行申请更多的存储空间。因此，在创建 vector 对象时，我们可以直接创建一个空的 vector 容器，并不会影响后续使用该容器；

  • vector 容器在申请更多内存的同时，容器中的所有元素可能会被复制或移动到新的内存地址，这会导致之前创建的迭代器失效。为了保险起见，每当 vector 容器的容量发生变化时，我们都要对之前创建的迭代器重新初始化一遍；

2.4 vector容器访问元素

（1）直接访问

vector 容器可以向普通数组那样访问存储的元素，甚至对指定下标处的元素进行修改

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> values{1,2,3,4,5};
    //获取容器中首个元素
    cout << values[0] << endl;
    //修改容器中下标为 0 的元素的值
    values[0] = values[1] + values[2] + values[3] + values[4];
    cout << values[0] << endl;
    return 0;
}

使用容器名[n]这种获取元素的方式，需要确保下标 n 的值不会超过容器的容量（可以通过 capacity() 成员函数获取），否则会发生越界访问的错误。幸运的是，和 array 容器一样，vector 容器也提供了 at() 成员函数，当传给 at() 的索引会造成越界时，会抛出std::out_of_range异常；

（2）at()成员函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> values{1,2,3,4,5};
    //获取容器中首个元素
    cout << values.at(0) << endl;
    //修改容器中下标为 0 的元素的值
    values.at(0) = values.at(1) + values.at(2) + values.at(3) + values.at(4);
    cout << values.at(0) << endl;
    //下面这条语句会发生 out_of_range 异常，因为越界了
    //cout << values.at(5) << endl;
    return 0;
}

（3）front()和back()成员函数

vector 容器还提供了 2 个成员函数，即 front() 和 back()，它们分别返回 vector 容器中第一个和最后一个元素的引用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> values{1,2,3,4,5};
    cout << "values 首元素为：" << values.front() << endl;
    cout << "values 尾元素为：" << values.back() << endl;
    //修改首元素
    values.front() = 10;
    cout <<"values 新的首元素为：" << values.front() << endl;
    //修改尾元素
    values.back() = 20;
    cout << "values 新的尾元素为：" << values.back() << endl;
    return 0;
}

（4）data()成员函数

vector 容器还提供了 data() 成员函数，该函数的功能是返回指向容器中首个元素的指针

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> values{1,2,3,4,5};
    //输出容器中第 3 个元素的值
    cout << *(values.data() + 2) << endl;
    //修改容器中第 2 个元素的值
    *(values.data() + 1) = 10;
    cout << *(values.data() + 1) << endl;
    return 0;
}

下面介绍访问vector容器中的多个元素

（5）for循环

1
2
3
4
5
6
7
8
9
10
11
12
13
//借助 size() 成员函数，该函数可以返回 vector 容器中实际存储的元素个数
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> values{1,2,3,4,5};
    //使用for循环从下标 0 一直遍历到 size()-1 处
    for (int i = 0; i < values.size(); i++) {
        cout << values[i] << " ";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
//使用 vector 迭代器遍历 vector 容器，以 begin()/end() 为例
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> values{1,2,3,4,5};
    for (auto first = values.begin(); first < values.end(); ++first) {
        cout << *first << " ";
    }
    return 0;
}

2.5 vector容器更新元素

向 vector 容器中添加元素的唯一方式就是使用它的成员函数，如果不调用成员函数，非成员函数既不能添加也不能删除元素，这意味着使用迭代器是不能更新vector容器中的元素的（迭代器只适合遍历容器）；

（1）添加元素

push_back()成员函数，该成员函数的功能是在 vector 容器尾部添加一个元素；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> values{};
    //向 values 容器尾部添加一个元素，但由于当前 values 容器是空的，因此新添加的元素 1 成为了容器中首个元素
    values.push_back(1);
    //在现有元素 1 的后面，添加元素 2
    values.push_back(2);
    for (int i = 0; i < values.size(); i++) {
        cout << values[i] << " ";
    }
    return 0;
}

emplace_back()成员函数，其功能和 push_back() 相同，都是在 vector 容器的尾部添加一个元素；

既然emplace_back()和push_back()功能相同为什么还要保留呢？emplace_back() 和 push_back() 的区别，就在于底层实现的机制不同（其实大部分功能相同的函数存在的意义都是和底层实现机制导致应用场景不同）：

  • push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；

  • emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程；

emplace_back() 的执行效率比 push_back() 高。因此，在实际使用时，建议大家优先选用 emplace_back();

如果程序要兼顾之前的版本，还是应该使用 push_back();

（2）插入元素

insert()成员函数，在 vector 容器的指定位置插入一个或多个元素；

insert()成员函数的语法形式有多种

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 <array> 
using namespace std;
int main()
{
    //创建demo容器
    std::vector<int> demo{1,2};
    //第一种格式用法
    demo.insert(demo.begin() + 1, 3);//{1,3,2}
    //第二种格式用法
    demo.insert(demo.end(), 2, 5);//{1,3,2,5,5}
    //第三种格式用法
    std::array<int,3>test{ 7,8,9 };
    demo.insert(demo.end(), test.begin(), test.end());//{1,3,2,5,5,7,8,9}
    //第四种格式用法
    demo.insert(demo.end(), { 10,11 });//{1,3,2,5,5,7,8,9,10,11}
    for (int i = 0; i < demo.size(); i++) {
        cout << demo[i] << " ";
    }
    return 0;
}

emplace()成员函数，用于在 vector 容器指定位置之前插入一个新的元素，emplace() 每次只能插入一个元素，而不是多个；

  • 格式
1
2
iterator emplace (const_iterator pos , arg1 , arg2);
//pos 为指定插入位置的迭代器；arg表示与新插入元素的构造函数相对应的多个参数；该函数会返回表示新插入元素位置的迭代器

  • 通过 insert() 函数向 vector 容器中插入 testDemo 类对象，需要调用类的构造函数和移动构造函数（或拷贝构造函数）；

  • 通过 emplace() 函数实现同样的功能，只需要调用构造函数即可，简单来说就是 emplace() 在插入元素时，是在容器的指定位置直接构造元素，而不是先单独生成，再将其复制（或移动）到容器中，因此其效率更高；

（3）删除元素

删除vector容器的元素可以并不仅限于使用vector模板类提供的成员函数，还可以借助一些全局函数；

具体函数的使用方法这里不再赘述，感兴趣可以查看资料；

3.deque容器

deque 是 double-ended queue 的缩写，又称双端队列容器；

deque 容器和 vecotr 容器有很多相似之处，比如：

  • deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为O(1)），而不擅长在序列中间添加或删除元素。
  • deque 容器也可以根据需要修改自身的容量和大小。

3.1 创建deque容器

（1）创建一个没有任何元素的空 deque 容器

1
std::deque<int> d;

空的 deque 容器在创建之后可以做添加或删除元素的操作；

（2）创建一个具有 n 个元素的 deque 容器，其中每个元素都采用对应类型的默认值

1
2
//创建一个具有 10 个元素（默认都为 0）的 deque 容器
std::deque<int> d(10);

（3）创建一个具有 n 个元素的 deque 容器，并为每个元素都指定初始值

1
2
//创建一个包含 10 个元素（值都为 5）的 deque 容器
std::deque<int> d(10, 5)

（4）在已有 deque 容器的情况下，可以通过拷贝该容器创建一个新的 deque 容器

1
2
std::deque<int> d1(5);
std::deque<int> d2(d1);

注意，采用此方式，必须保证新旧容器存储的元素类型一致；

（5）通过拷贝其他类型容器中指定区域内的元素（也可以是普通数组），可以创建一个新容器

1
2
3
4
5
6
7
//拷贝普通数组，创建deque容器
int a[] = { 1,2,3,4,5 };
std::deque<int>d(a, a + 5);

//拷贝其他类型容器，适用于所有类型的容器
std::array<int, 5>arr{ 11,12,13,14,15 };
std::deque<int>d(arr.begin()+2, arr.end());//拷贝arr容器中的{13,14,15}

3.2 deque容器成员函数

3.3 deque随机访问迭代器

deque 模板类提供了表 1 所示这些成员函数，通过调用这些函数，可以获得表示不同含义的随机访问迭代器

鉴于之前在array和vector中已经介绍了这些成员函数的作用和用法，这里就不再赘述；

注意事项：

  • 迭代器的功能是遍历容器，在遍历的同时可以访问（甚至修改）容器中的元素，但迭代器不能用来初始化空的 deque 容器（这一点和vector容器不一样，vector只能通过成员函数更新元素）；
  • 对于空的 deque 容器来说，可以通过 push_back()、push_front() 或者 resize() 成员函数实现向（空）deque 容器中添加元素；
  • 当向 deque 容器添加元素时，deque 容器会申请更多的内存空间，同时其包含的所有元素可能会被复制或移动到新的内存地址（原来占用的内存会释放），这会导致之前创建的迭代器失效，因此在对容器做添加元素的操作之后，如果仍需要使用之前以创建好的迭代器，为了保险起见，一定要重新生成迭代器；

3.4 deque容器访问元素

（1）直接访问

1
2
deque<int>d{ 1,2,3,4 };
cout << d[1] << endl;

（2）at()成员函数

与vector容器相同

（3）front()和back()成员函数

与vector容器相同

（4）while循环

1
2
3
4
5
6
7
8
9
deque<int> d{ 1,2,3,4,5 };
   //从元素 2 开始遍历
   auto first = d.begin() + 1;
   //遍历至 5 结束（不包括 5）
   auto end = d.end() - 1;
   while (first < end) {
       cout << *first << " ";
       ++first;
   }

3.5 deque容器更新元素

4.list容器

list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。这意味着，list 容器中的元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中

list 容器中各个元素的前后顺序是靠指针来维系的，每个元素都配备了 2 个指针，分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为 null，因为它前面没有元素；同样，尾部元素的后向指针也总为 null；

基于上述存储结构，list 容器具有一些其它容器（array、vector 和 deque）所不具备的优势，即它可以在序列已知的任何位置快速插入或删除元素（时间复杂度为O(1)）。并且在 list 容器中移动元素，也比其它容器的效率高；

使用 list 容器的缺点是，它不能像 array 和 vector 那样，通过位置直接访问元素，它不支持容器对象名[]这种语法格式，正确的做法是从容器中第一个元素或最后一个元素开始遍历容器，直到找到该位置（本质上就是链表和数组的区别）

4.1 创建list容器

（1）创建一个没有任何元素的空 list 容器

1
std::list<int> values;

和空 array 容器不同，空的 list 容器在创建之后仍可以添加元素，因此创建 list 容器的方式很常用

（2）创建一个包含 n 个元素的 list 容器

1
2
// 创建values 容器，其中包含 10 个元素，每个元素的值都为相应类型的默认值（int类型的默认值为 0）
std::list<int> values(10);

（3）创建一个包含 n 个元素的 list 容器，并为每个元素指定初始值

1
std::list<int> values(10, 5);

（4）在已有 list 容器的情况下，通过拷贝该容器可以创建新的 list 容器

1
2
std::list<int> value1(10);
std::list<int> value2(value1);

（5）通过拷贝其他类型容器（或者普通数组）中指定区域内的元素，可以创建新的 list 容器

1
2
3
4
5
6
//拷贝普通数组，创建list容器
int a[] = { 1,2,3,4,5 };
std::list<int> values(a, a+5);
//拷贝其它类型的容器，创建 list 容器
std::array<int, 5>arr{ 11,12,13,14,15 };
std::list<int>values(arr.begin()+2, arr.end());//拷贝arr容器中的{13,14,15}

4.2 list容器成员函数

4.3 list双向迭代器

list 模板类提供了如表 1 所示的这些迭代器函数

前面章节已经详细介绍了 array、vector、deque 容器的迭代器，和它们相比，list 容器迭代器最大的不同在于，其配备的迭代器类型为双向迭代器，而不再是随机访问迭代器。

这意味着，假设 p1 和 p2 都是双向迭代器，则它们支持使用 ++p1、 p1++、 p1–、 p1++、 *p1、 p1==p2 以及 p1!=p2 运算符，但不支持以下操作（其中 i 为整数）：

  • p1[i]：不能通过下标访问 list 容器中指定位置处的元素。
  • p1-=i、 p1+=i、 p1+i 、p1-i：双向迭代器 p1 不支持使用 -=、+=、+、- 运算符。
  • p1<p2、 p1>p2、 p1<=p2、 p1>=p2：双向迭代器 p1、p2 不支持使用 <、 >、 <=、 >= 比较运算符。

list 容器在进行插入（insert()）、接合（splice()）等操作时，都不会造成原有的 list 迭代器失效，甚至进行删除操作，而只有指向被删除元素的迭代器失效，其他迭代器不受任何影响；

4.4 list容器访问元素

  • list 容器不支持随机访问，未提供下标操作符 [] 和 at() 成员函数，也没有提供 data() 成员函数；
  • 访问 list 容器中存储元素的方式很有限，即要么使用 front() 和 back() 成员函数，要么使用 list 容器迭代器；

（1）front()和back()成员函数

与vector相同

（2）list双向迭代器

1
2
3
4
5
6
7
8
9
const std::list<int> mylist{1,2,3,4,5};
auto it = mylist.begin();
cout << *it << " ";
++it;
while (it!=mylist.end())
{
    cout << *it << " ";
    ++it;  
}

对于非 const 类型的 list 容器，迭代器不仅可以访问容器中的元素，也可以对指定元素的值进行修改；

4.5 list容器更新元素

list 模板类中，与“添加或插入新元素”相关的成员方法有如下几个：

  • push_front()：向 list 容器首个元素前添加新元素；
  • push_back()：向 list 容器最后一个元素后添加新元素；
  • emplace_front()：在容器首个元素前直接生成新的元素；
  • emplace_back()：在容器最后一个元素后直接生成新的元素；
  • emplace()：在容器的指定位置直接生成新的元素；
  • insert()：在指定位置插入新元素；
  • splice()：将其他 list 容器存储的多个元素添加到当前 list 容器的指定位置处；

对 list 容器存储的元素执行删除操作，需要借助该容器模板类提供的成员函数，list 模板类提供了大量用来实现此操作的成员函数

关联式容器（三）

经过上面对序列式容器的学习，我发现其实大多数的方法都是类似的，我们没必要去书写或者记忆这些网上都可以轻松查阅的知识点，所以这之后的笔记我可能就只会写一些重要的知识点而不会再写函数怎么用或者函数的意义；

前面大概说过，STL中的容器分为序列式容器和关联式容器，无论是哪种序列式容器，其存储的都是元素值（C++基本/复合数据类型），而关联式容器除了会存储元素值以外还会为各个元素配置一个键，功能是在使用关联式容器的过程中，如果已知目标元素的键的值，则直接通过该键就可以找到目标元素，而无需再通过遍历整个容器的方式；

同时序列式容器的元素默认未经过排序，而关联式容器存储的元素默认会根据元素的键值大小做升序排序；

总结：关联式容器具备上述特性是因为其底层是使用红黑树这种数据结构组织和存储各个键值对；

STL提供了如下四种关联式容器：

因为关联式容器存储的是“键值对”形式的数据，而“键值对”数据类型并不是普通数据类型，STL提供了标准的pair类模板，将两个C++元素构造成一个元素<first,second>，pair 类模板定义在<utility>头文件中；

1.map容器

map 容器存储的都是 pair 对象，也就是用 pair 类模板创建的键值对。其中，各个键值对的键和值可以是任意数据类型，包括C++基本数据类型（int、double 等）、使用结构体或类自定义的类型；

默认情况下，在使用 map 容器存储多个键值对时，该容器会自动根据各键值对的键的大小，按照既定的规则进行排序（当然可以使用其他内置排序规则或自定义排序规则）；

使用 map 容器存储的各个键值对，键key既不能重复也不能被修改（这里的不能修改是指正常情况下不能被修改，使用非常规手段还是可以修改的）

map 容器的模板定义如下：

1
2
3
4
5
template < class Key,                                     // 指定键（key）的类型
           class T,                                       // 指定值（value）的类型
           class Compare = less<Key>,                     // 指定排序规则
           class Alloc = allocator<pair<const Key,T> >    // 指定分配器对象的类型
           > class map;

2.multimap容器

multimap 容器具有和 map 相同的特性，即 multimap 容器也用于存储 pair<const K, T> 类型的键值对（其中 K 表示键的类型，T 表示值的类型），其中各个键值对的键的值不能做修改；并且，该容器也会自行根据键的大小对存储的所有键值对做排序操作。和 map 容器的区别在于，multimap 容器中可以同时存储多个键相同的键值对；

multimap 容器类模板的定义如下：

1
2
3
4
5
template < class Key,                                   // 指定键（key）的类型
           class T,                                     // 指定值（value）的类型
           class Compare = less<Key>,                   // 指定排序规则
           class Alloc = allocator<pair<const Key,T> >  // 指定分配器对象的类型
           > class multimap;

3.set容器

与map、multimap 容器不同，使用 set 容器存储的各个键值对，要求键 key 和值 value 必须相等

1
2
{<'a', 1>, <'b', 2>, <'c', 3>}
{<'a', 'a'>, <'b', 'b'>, <'c', 'c'>}

对于 set 容器来说，只能存储第 2 组键值对，而无法存储第一组键值对；

基于 set 容器的这种特性，当使用 set 容器存储键值对时，只需要为其提供各键值对中的 value 值（也就是 key 的值）即可。仍以存储上面第 2 组键值对为例，只需要为 set 容器提供 {‘a’,’b’,’c’} 该容器即可成功将它们存储起来；

set 容器的类模板定义如下：

1
2
3
4
template < class T,                        // 键 key 和值 value 的类型---键和值完全相同，也就意味着它们的类型相同
           class Compare = less<T>,        // 指定 set 容器内部的排序规则
           class Alloc = allocator<T>      // 指定分配器对象的类型
           > class set;

set 容器具有以下几个特性：

  • 不再以键值对的方式存储数据，因为 set 容器专门用于存储键和值相等的键值对，因此该容器中真正存储的是各个键值对的值（value）；
  • set 容器在存储数据时，会根据各元素值的大小对存储的元素进行排序（默认做升序排序）；
  • 存储到 set 容器中的元素，虽然其类型没有明确用 const 修饰，但正常情况下它们的值是无法被修改的；
  • set 容器存储的元素必须互不相等；

4.multiset容器

multiset 容器遵循 set 容器的前 3 个特性，仅在第 4 条特性上有差异。和 set 容器不同的是，multiset 容器可以存储多个值相同的元素。

multiset 容器类模板的定义如下所示：

1
2
3
4
template < class T,                        // 存储元素的类型
           class Compare = less<T>,        // 指定容器内部的排序规则
           class Alloc = allocator<T> >    // 指定分配器对象的类型
           > class multiset;

5.无序关联式容器

无序关联式容器，又称哈希容器。和关联式容器一样，此类容器存储的也是键值对元素；不同之处在于，关联式容器默认情况下会对存储的元素做升序排序，而无序关联式容器不会：

  • 关联式容器的底层实现采用的树存储结构，更确切的说是红黑树结构；
  • 无序容器的底层实现采用的是哈希表的存储结构；

和其它类容器相比，无序关联式容器擅长通过指定键查找对应的值，而遍历容器中存储元素的效率不如关联式容器；

以上 4 种无序容器的名称，仅是在前面所学的 4 种关联式容器名称的基础上，添加了 “unordered_”。如果读者已经学完了 map、multimap、set 和 multiset 容器不难发现，以 map 和 unordered_map 为例，其实它们仅有一个区别，即 map 容器内存会对存储的键值对进行排序，而 unordered_map 不会——即在已提供有 4 种关联式容器的基础上，又新增了各自的“unordered”版本（无序版本、哈希版本），提高了查找指定元素的效率；

  • 实际场景中如果涉及大量遍历容器的操作，建议首选关联式容器；
  • 如果更多的操作是通过键获取对应的值，则应首选无序容器；
  • 和关联式容器相比，无序容器擅长通过指定键查找对应的值（平均时间复杂度为 O(1)）；但对于使用迭代器遍历容器中存储的元素，无序容器的执行效率则不如关联式容器；

容器适配器（四）

容器适配器是一个封装了序列容器的类模板（容器适配器本质上还是容器），它在一般序列容器的基础上提供了一些不同的功能。之所以称作适配器类，是因为它可以通过适配 容器现有的接口 来提供不同的功能；

容器适配器的底层实现和模板 A、B 的关系是完全相同的，即通过封装某个序列式容器，并重新组合该容器中包含的成员函数，使其满足某些特定场景的需要；

STL 提供了 3 种容器适配器，分别为 stack 栈适配器、queue 队列适配器以及 priority_queue 优先权队列适配器。其中，各适配器所使用的默认基础容器以及可供用户选择的基础容器如下：

  1. stack：是一个封装了 deque 容器的适配器类模板，默认实现的是一个后入先出（Last-In-First-Out，LIFO）的压入栈。stack 模板定义在头文件 stack 中；
  2. queue：是一个封装了 deque 容器的适配器类模板，默认实现的是一个先入先出（First-In-First-Out，LIFO）的队列。可以为它指定一个符合确定条件的基础容器。queue 模板定义在头文件 queue 中；
  3. priority_queue：是一个封装了 vector 容器的适配器类模板，默认实现的是一个会对元素排序，从而保证最大元素总在队列最前面的队列。priority_queue 模板定义在头文件 queue 中；

简单的理解容器适配器就是利用已有的基础容器进行拆分重组形成新的容器，新的容器具备更加高级的功能（先入先出的队列，先入后出的栈等）

1.stack容器适配器

stack 栈适配器是一种单端开口的容器，实际上该容器模拟的就是栈存储结构，即无论是向里存数据还是从中取数据，都只能从这一个开口实现操作（先入后出）

2.queue容器适配器

queue 容器适配器有 2 个开口，其中一个开口专门用来输入数据，另一个专门用来输出数据（先入先出）

3.priority_queue容器适配器

此容器适配器存储元素只能“从一端进（称为队尾），从另一端出（称为队头）”，且每次只能访问 priority_queue 中位于队头的元素；

Howerver，priority_queue 容器适配器中元素的取，遵循的并不是 “First in,First out”（先入先出）原则，而是优先级最大的元素最先出队列；

每个 priority_queue 容器适配器在创建时，都制定了一种排序规则，根据此规则，该容器适配器中存储的元素就有了优先级高低之分（假设当前有一个 priority_queue 容器适配器，其制定的排序规则是按照元素值从大到小进行排序，根据此规则，自然是 priority_queue 中值最大的元素的优先级最高）；

priority_queue 容器适配器为了保证每次从队头移除的都是当前优先级最高的元素，每当有新元素进入，它都会根据既定的排序规则找到优先级最高的元素，并将其移动到队列的队头；同样，当 priority_queue 从队头移除出一个元素之后，它也会再找到当前优先级最高的元素，并将其移动到队头。

priority_queue 容器适配器“First in，Largest out”的特性，和它底层采用堆结构存储数据是分不开的（通常我们所说的堆的数据结构是指二叉树，堆的特点是根节点的值最小(或最大),且根节点的两个树也是一个堆，由于堆的这个特性,常用来实现优先队列）；

priority_queue 容器适配器的定义如下：

1
2
3
4
5
6
template <typename T,					   //指定存储元素的具体类型
        typename Container=std::vector<T>,	//指定 priority_queue 底层使用的基础容器，默认使用 vector 容
        typename Compare=std::less<T> >		//指定容器中评定元素优先级所遵循的排序规则
class priority_queue{
    //......
}

迭代器适配器（五）

迭代器适配器，其本质也是一个模板类，比较特殊的是，该模板类是借助以上 5 种基础迭代器实现的。换句话说，迭代器适配器模板类的内部实现，是通过对之前介绍过的 5 种基础迭代器拥有的成员方法进行整合、修改，甚至为了实现某些功能（比如逆序遍历）还会添加一些新的成员方法，使用迭代器适配器的过程中，其本质就是在操作某种基础迭代器；

STL中有四类迭代器适配器：

1.反向迭代器

反向迭代器适配器（reverse_iterator），可简称为反向迭代器或逆向迭代器，常用来对容器进行反向遍历，即从容器中存储的最后一个元素开始，一直遍历到第一个元素；

反向迭代器底层可以选用双向迭代器或者随机访问迭代器作为其基础迭代器。不仅如此，通过对 ++（递增）和 –（递减）运算符进行重载，使得：

  • 当反向迭代器执行 ++ 运算时，底层的基础迭代器实则在执行 – 操作，意味着反向迭代器在反向遍历容器；
  • 当反向迭代器执行 – 运算时，底层的基础迭代器实则在执行 ++ 操作，意味着反向迭代器在正向遍历容器

2.插入迭代器

插入迭代器适配器（insert_iterator），简称插入迭代器或者插入器，其功能就是向指定容器中插入元素。值得一提的是，根据插入位置的不同，C++ STL 标准库提供了 3 种插入迭代器：

常用算法（六）

算法主要是由头文件<algorithm> <functional> <numeric>组成：

  • <algorithm>是所有STL头文件中最大的一个，范围涉及到比较、 交换、查找、遍历操作、复制、修改等等；
  • <numeric>体积很小，只包括几个在序列上面进行简单数学运算的模板函数；
  • <functional>定义了一些模板类,用以声明函数对象；

1.常用遍历算法

1.1 for_each()

函数功能：遍历容器

  • 函数原型
1
2
3
4
5
6
for_each(iterator beg, iterator end, _func);  

// 遍历算法 遍历容器元素
// beg 开始迭代器
// end 结束迭代器
// _func 函数或者函数对象
  • 举例
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
#include <algorithm>
#include <vector>

//普通函数
void print01(int val) 
{
	cout << val << " ";
}
//函数对象
class print02 
{
 public:
	void operator()(int val) 
	{
		cout << val << " ";
	}
};

//for_each算法基本用法
void test01() {
	vector<int> v;
	for (int i = 0; i < 10; i++) 
	{
		v.push_back(i);
	}

	//遍历算法
	for_each(v.begin(), v.end(), print01);
	cout << endl;

	for_each(v.begin(), v.end(), print02());
	cout << endl;
}

1.2 transform()

函数功能：将一个容器搬运到另一个容器中

  • 函数原型
1
2
3
4
5
6
* `transform(iterator beg1, iterator end1, iterator beg2, _func);`

//beg1 源容器开始迭代器
//end1 源容器结束迭代器
//beg2 目标容器开始迭代器
//_func 函数或者函数对象
  • 举例
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<vector>
#include<algorithm>
//常用遍历算法  搬运 transform
class TransForm
{
public:
	int operator(int val)
	{
		return val;
	}

};


void test01()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	vector<int>vTarget; //目标容器
	vTarget.resize(v.size()); // 目标容器需要提前开辟空间
	transform(v.begin(), v.end(), vTarget.begin(), TransForm());
	
}

2.常用查找算法

2.1 find()

功能：查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()

  • 函数原型：
1
2
3
4
5
find(iterator beg, iterator end, value);  
// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
// beg 开始迭代器
// end 结束迭代器
// value 查找的元素
  • 举例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <algorithm>
#include <vector>
#include <string>
void test01() {

	vector<int> v;
	for (int i = 0; i < 10; i++) {
		v.push_back(i + 1);
	}
	//查找容器中是否有 5 这个元素
	vector<int>::iterator it = find(v.begin(), v.end(), 5);
	if (it == v.end()) 
	{
		cout << "没有找到!" << endl;
	}
	else 
	{
		cout << "找到:" << *it << endl;
	}
}

2.2 find_if()

按条件查找元素

  • 函数原型
1
2
3
4
5
6
find_if(iterator beg, iterator end, _Pred);  

// 按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置
// beg 开始迭代器
// end 结束迭代器
// _Pred 函数或者谓词（返回bool类型的仿函数）
  • 举例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <algorithm>
#include <vector>
#include <string>
void test01() {

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

	vector<int>::iterator it = find_if(v.begin(), v.end(), GreaterFive());
	if (it == v.end()) {
		cout << "没有找到!" << endl;
	}
	else {
		cout << "找到大于5的数字:" << *it << endl;
	}
}

2.3 adjacent_find()

查找相邻重复元素

  • 函数原型
1
2
3
4
5
adjacent_find(iterator beg, iterator end);  

// 查找相邻重复元素,返回相邻元素的第一个位置的迭代器
// beg 开始迭代器
// end 结束迭代器
  • 举例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <vector>
void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(5);
	v.push_back(2);
	v.push_back(4);
	v.push_back(4);
	v.push_back(3);

	//查找相邻重复元素
	vector<int>::iterator it = adjacent_find(v.begin(), v.end());
	if (it == v.end()) {
		cout << "找不到!" << endl;
	}
	else {
		cout << "找到相邻重复元素为:" << *it << endl;
	}
}

二分查找，查找指定元素是否存在

  • 函数原型
1
2
3
4
5
6
bool binary_search(iterator beg, iterator end, value);  
//查找指定元素，查到 返回true  否则false
// 注意: 在无序序列中不可用
// beg 开始迭代器
// end 结束迭代器
// value 查找的元素
  • 举例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <algorithm>
#include <vector>

void test01()
{
	vector<int>v;
	for (int i = 0; i < 10; i++)
	{
		v.push_back(i);
	}
	//二分查找
	bool ret = binary_search(v.begin(), v.end(),2);
	if (ret)
	{
		cout << "找到了" << endl;
	}
	else
	{
		cout << "未找到" << endl;
	}
}

二分查找法查找效率很高，值得注意的是查找的容器中元素必须的有序序列

3.常用统计算法

3.1 count()

统计元素个数

  • 函数原型
1
2
3
4
5
6
count(iterator beg, iterator end, value);  

// 统计元素出现次数
// beg 开始迭代器
// end 结束迭代器
// value 统计的元素
  • 举例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <algorithm>
#include <vector>

//内置数据类型
void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(4);
	v.push_back(5);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);
	int num = count(v.begin(), v.end(), 4);
	cout << "4的个数为： " << num << endl;
}

3.2 count_if

按照条件统计元素个数

  • 函数原型
1
2
3
4
5
6
count_if(iterator beg, iterator end, _Pred);  

// 按条件统计元素出现次数
// beg 开始迭代器
// end 结束迭代器
// _Pred 谓词
  • 举例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//内置数据类型
void test01()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(4);
	v.push_back(5);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);
	int num = count_if(v.begin(), v.end(), Greater4());
	cout << "大于4的个数为： " << num << endl;
}

按值统计用count，按条件统计用count_if

4.常用排序算法

4.1 sort()

对容器内部的元素进行排序

  • 函数原型
1
2
3
4
5
6
sort(iterator beg, iterator end, _Pred);  

// 对容器内部的元素进行排序
//  beg    开始迭代器
//  end    结束迭代器
// _Pred  谓词
  • 举例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void test01() {
	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	//sort默认从小到大排序
	sort(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;

	//从大到小排序
	sort(v.begin(), v.end(), greater<int>());
	for_each(v.begin(), v.end(), myPrint);
	cout << endl;
}

4.2 random_shuffle()

指定范围内的元素随机调整次序

  • 函数原型
1
2
3
4
5
random_shuffle(iterator beg, iterator end);  

// 指定范围内的元素随机调整次序
// beg 开始迭代器
// end 结束迭代器
  • 举例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void test01()
{
	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(), myPrint());
	cout << endl;

	//打乱顺序
	random_shuffle(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

4.3 merge()

将两个容器的元素合并到另一个容器中

  • 函数原型
1
2
3
4
5
6
7
8
9
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);  

// 容器元素合并，并存储到另一容器中
// 注意: 两个容器必须是有序的
// beg1   容器1开始迭代器
// end1   容器1结束迭代器
// beg2   容器2开始迭代器
// end2   容器2结束迭代器
// dest    目标容器开始迭代器
  • 举例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void test01()
{
	vector<int> v1;
	vector<int> v2;
	for (int i = 0; i < 10 ; i++) 
    {
		v1.push_back(i);
		v2.push_back(i + 1);
	}

	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(), myPrint());
	cout << endl;
}

4.4 reverse()

将容器内的元素反转

  • 函数原型
1
2
3
4
5
reverse(iterator beg, iterator end);  

// 反转指定范围的元素
// beg 开始迭代器
// end 结束迭代器
  • 举例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void test01()
{
	vector<int> v;
	v.push_back(10);
	v.push_back(30);
	v.push_back(50);
	v.push_back(20);
	v.push_back(40);

	cout << "反转前： " << endl;
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;

	cout << "反转后： " << endl;

	reverse(v.begin(), v.end());
	for_each(v.begin(), v.end(), myPrint());
	cout << endl;
}

其他算法如拷贝替换算法、算术生成算法、集合算法等具体可以查阅资料学习；

自学课程
#后端开发 #编程语言
STL初级
https://gintoki-jpg.github.io/2022/07/08/CPP_STL初级/
作者
杨再俨
发布于
2022年7月8日
许可协议