C++ ：1、STL 的容器概述、array容器详解、迭代器初步分析_C

一、STL的容器类介绍

0、铺垫

之前分析了模板的语法，我们接下来学习 STL 的使用。

对 STL 的使用的核心就是对容器类的使用。
在 c++ 当中一切皆对象，所以容器也是一个类。

1、何为容器

顾名思义，容器就是盛放东西的东西，这里被盛放的一般是数据对象，用来盛放的是容器类。
- 如何盛放数据，肯定是通过函数来进行管理。
- 容器类的成员函数，就是对容器当中的数据进行 *** 作。
计算机中一切皆是数据，数据存储只能在内存中，而容器类是用做容器的内存的管理方法。
容器类的内核就是：数据结构 + 算法
C语言语法内置的数组和结构体，就是语言源生支持的容器。
- C 语言严格来说并不算是容器，因为 C 语言没有提供很多算法。
- C 语言当中只有 string、stdio 等等一些基础算法，不提供排序算法等高级的算法。
C++容器通过类库方式提供，容器类库被模板技术泛化后，就是STL容器了。
- 泛化就是可以存放不同的数据类型。

2、STL有哪些容器类

序列容器。

元素在容器中的位置同元素的值无关，即容器不是排序的（类似于C数组）。

包括array、vector、deque、list、forward_list 等几个。
- 补充：序列容器的排序方式，是按照元素的存放顺序，来挨个排放的，与元素本身的值没有关系。
  
  （对比排序容器）
排序容器。

数据插入时即自动按照值从小到大排列好。

包括set、multiset、map、mutilmap等。
- 补充：用户只管进行存放，容器类的内部会替我们自动将元素进行排序。
哈希容器。

哈希容器中的元素是未排序的，元素的位置由哈希函数确定，即遵守一定规则的对式存储。

包括unordered_set、unordered_map、hash_set、hash_multiset、hash_map、hash_multimap等
- key：配置项
- value：配置值
- 距离：描述长方形：长(key)= 29(value) ，宽(key)=10(value)

3、容器类如何学习

容器类就是STL的核心，STL其他技术点都围绕容器类开展
可见STL的本质：其实就是一套模板技术泛化类型的C++基本数据结构和算法类库。
本课程会集中细致讲几个STL序列容器array、vector等，其他容器类似情况就简略讲过了
第一层为学会使用stl容器，第二层为能合理使用stl容器，第三层为理解stl背后设计，第四层为自己能写新的stl容器。
- 合理使用stl容器：我们要清楚哪一个容器适合我们当前的场景。
  
  哪一个的效率更高（array、list 的抉择）（代表成为一个成熟的c++ 工程师了）
- 理解stl背后设计：（大牛级别的人物了）

二、容器类 array 1、array 的介绍

1、array的特性

array是定长、同类型多元素、内存中连续排布的一种容器
- 定长：在初始化之后，他的大小就确定了，不能进行动态更改。
array其实就是C语言数组的C++ template封装，从而可以让适用于不同类型的数据结构。

2、array的学习方法

参考文档：https://zh.cppreference.com/w/cpp/container/array
挨个理解文档相关所有元素，并写代码验证

3、查看 array 的原型：

class T：模板类型，（模板定义的时候，typename 和 class 的作用是一样的）。
std::size_t N：模板数值。

（size_t 本质就是一个 int，通过 typedef 来进行定义）

template<class T, std::size_t N>
    class array;

4、array的构造和初始化

和C数组兼容的初始化方式
需要C++11或以上标准来支持
支持默认的拷贝构造

注意：

( ) ：小括号默认会调用对应类的构造函数。

（容易类不可以这样进行初始化，因为C++无法提供无数个构造函数来匹配）
{ }：综括号，并不会调用对应的构造函数，属于聚合初始化。

int main(void)
{
	array<int, 3> a1;					// 定义了但是未初始化，猜测值应该是随机的
	
//  array a2(1, 3, 5);			// 不支持这样的语法，C++无法提供无数个构造函数来匹配
	array<int, 3> a2{1, 3, 5};			// 综括号：可以，属于聚合初始化
	
    array<int, 3> a3 = {1, 3, 5};		// 初始化赋值，和a2效果一样
	array<int, 3> a4 = a3;				// 拷贝构造
	return 0;
}

2、array 的成员函数

1、array的元素访问

operator[] 实现的C数组式访问：
本质：这个运算符 [] 是 array 当中一个成员函数，C++ 内部帮我们进行了重载，让我们使用更加方便。
运算符重载 == 成员函数。

int main(void)
{
	array<int, 3> a{1, 3, 5};		// 可以，属于聚合初始化
	
    a[0] = 4;
	a[1] = 6;
	cout << "a[0] = " << a[0] << endl;			// a.operator[](0)
	cout << "a[1] = " << a[1] << endl;
	cout << "a[2] = " << a[2] << endl;
    return 0;
}

at 方法：也是一个成员函数

int main(void)
{
	array<int, 3> a{1, 3, 5};		// 可以，属于聚合初始化

	a.at(3) = 4;		
	a.at(0) = 4;
    
	cout << "a[0] = " << a.at(0) << endl;
	return 0;
}

注意：上面两种方法会涉及一个问题：可能越界访问。

front 和 back 方法返回第1个和最后1个元素

	cout << "a.front = " << a.front() << endl;	// 1
	cout << "a.back = " << a.back() << endl;	// 5

data 返回真实存储内存中首元素的首地址（返回一个指针）
通过结果，我们也可以验证 array 内部的值是挨着排布的。

	int *p = a.data();
	cout << "a.data = " << p << ", *p = " << *p++ << endl;
	cout << "a.data = " << p << ", *p = " << *p++ << endl;
	cout << "a.data = " << p << ", *p = " << *p++ << endl;

如果 array 的元素访问越界了，那么编译时没问题，但是运行时会抛出异常：

2、array的容量设置和获取

容量设置只能在定义时一次设定，且必须设定，设定后再不能改
empty：如果为空，则返回1。

如果不为空，则返回1。
size：取决于和初始化的时候，传入 N。
max_size：代表该容器的最大容量。
- array：size == max_size，因为 array 的大小在初始化的时候必须确定。
- vector：size != max_size ，vector 是动态可变的，所以 max_size 就是最大的数值。

int main(void)
{
	array<int, 3> a{1, 3, 5};		// 可以，属于聚合初始化
	array<int, 0> b;

	cout << "b.empty = " << b.empty() << endl;
	cout << "a.size = " << a.size() << endl;
	cout << "a.max_size = " << a.max_size() << endl;
}

3、 *** 作：这两个函数没有写案例，比较简单。

fill：将 array 里面的所有元素，都填充为统一的值。
swap：将两个 array 当中元素的值，进行交换。

（array 的地址不会变换，只是 value 进行交换）

3、array 的非成员函数

普通非成员函数：只能访问 array 当中 public 的成员变量。

（1）operator: 运算符重载函数

operator==：判断两个数组个数是否相同以及每个元素是否相同。
!= < <= > >= ：具体比较规程：https://zh.cppreference.com/w/cpp/container/array/operator_cmp

	array<int, 3> a{1, 7, 5};		// 可以，属于聚合初始化
	array<int, 3> b{1, 4, 6};
	bool flag = (a == b);
	bool flag = (a < b);
	cout << "flag = " << flag << endl;

（2）get：https://zh.cppreference.com/w/cpp/container/array/get

可以获取某个元素的值
可以设置某个元素的值，因为他的返回值是一个引用，所以可以设置。

（3）swap：https://zh.cppreference.com/w/cpp/container/array/swap2

进行交换

（4）to_array：（具体细节）https://zh.cppreference.com/w/cpp/container/array/to_array

将 C 语言的一个数组，转换为一个 C++ 的数组

	int b[3] = {1, 4, 7};
	array<int, 3> a = to_array<int, 3>(b);
	cout << "a[0] = " << a[0] << endl;			// a.operator[](0)
	cout << "a[1] = " << a[1] << endl;
	cout << "a[2] = " << a[2] << endl;

4、array 辅助类

参考文档：https://zh.cppreference.com/w/cpp/container/array

拓展：分析一下 pair 和 tupe 的关系

参考文档：https://zh.cppreference.com/w/cpp

std::pair 是类模板，提供在一个单元存储两个相异类型对象的途径。
pair 是 std::tuple 的拥有两个元素的特殊情况。

----------> （总结：tuple 是pair 的升级版本）
元组的功能：就是类似于一个结构体，里面可以有不同类型的参数。

（1）辅助类：tuple_size ：https://zh.cppreference.com/w/cpp/utility/pair/tuple_size

我们在写功能函数的时候，不知道对方传过来的 array 的容量到底多大，可以使用这个函数。
使用情况：test 函数先完成， main 函数后完成，所以需要 test 需要获取size 的大小。

分析使用过程：

std::tuple_size：先将这个类实例化，在这个类实例化的过程当中，value这个静态成员变量会被填充。
std::tuple_size::value：本质就是使用 tuple_size 当中的 value 属性。

（value 是一个静态成员变量）
- 这段代码的返回值其实就是 value 变量。

好处：这种方式是在编译器编译的时候进行确定，所以使代码在运行的时候，效率就会高一点。

#include 
#include 
#include 
 
template<class T>
void test(T t)
{
    int a[std::tuple_size<T>::value]; // 可用于编译时
    std::cout << std::tuple_size<T>::value << '\n'; // 或运行时
}
 
int main()
{
    std::array<int, 4> a{0, 1, 2, 3};
    test(a);								// 输出 4
    test(std::make_tuple(1, 2, 3.14));		// 输出 3
    test(std::make_pair(1, 3.14));			// 输出 2
}

（2）辅助类：tuple_element

作用：获取 array 元素的类型
using T：相当于 typedef ，声明一个新的类型。
std::tuple_element<0, decltype(data)>::type：返回 tuple_element<0, decltype(data)> 实例化类当中的 type 成员变量。
std::is_same::value ：返回 std::is_same，实例化类之后，当中的 value 变量。
const auto const_data = data：本质是 “ = ” 运算符的重载，会调用对应的拷贝构造函数。

#include 
#include 
#include 
#include 
 
int main()
{
   // 定义 array 并获取位于位置 0 的元素类型
   std::array<int, 10> data {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
   using T = std::tuple_element<0, decltype(data)>::type; // int
 
   std::cout << std::boolalpha;							  // 让s cout 输出 true，而不是 1
   std::cout << std::is_same<T, int>::value << '\n';		// true
 
   const auto const_data = data;
   using CT = std::tuple_element<0, decltype(const_data)>::type; // const int
 
   // tuple_element 的结果取决于仿 tuple 类型的 cv 限定
   std::cout << std::is_same<T, CT>::value << '\n';				// false, 因为 int 和 const int 类型不相同
   std::cout << std::is_same<CT, const int>::value << '\n';		// true
}

（3）被取代的 make_array

这个并没有被归入到辅助类当中，而是放到了页面的最下面。

因为这个还不成熟，属于一个实验的阶段：

后面被移除掉了，因为有一个 to_array，所以他的功能和 to_array 的功能类似。

三、array 迭代器

每个容器的迭代器可能不一样，我们可以通过查阅手册，来最终确定有哪些的迭代器

3.1 迭代器的引入

（1）迭代器是干什么的

铺垫：STL其他技术点都围绕容器类开展，所以 STL 的核心就是容器类。

迭代：就是能通过移动来遍历处理的一种机制。
- 遍历：只移动一次（从头到尾就一次）
- 迭代：来来回回一直移动（走到中间，可能还要回去）
C 语言当中的迭代器：用指针 *p++ 方式，指针变量就是遍历迭代器。

（就是将指针想象成一个机器，++ 是机器的 *** 作）
- 数组可以通过 *p++ 来进行迭代。
  
  （因为数组的元素相同）
- 结构体就不可以通过 *p++ 来进行迭代了。

（2）关于迭代器的分析

每种容器理论上都可以被遍历，不存在不能被遍历的容器。
每种容器的遍历实现都可能不同，要结合容器和元素的特点来具体实现。
迭代器内部原理肯定是通过指针 *** 作（地址运算）来实现。
迭代器就是C++为我们设计的一个高层次的“指针”，高层指针是面向容器中的元素的。
- 高层次指针：就可以解决结构体当中元素类型不相同的问题。
- 高层次指针：*iterator++ 当中 ++ 的最小单位是容器当中的元素，并不是指针的类型。

（3）C++实际是这么设计迭代器的

所有的迭代器有一个共同基类（接口），规定了迭代器的基本行为规范接口。
- 基本行为规范接口：所有的迭代器共同支持的 *** 作。
每个容器类中均包含了一个专属化迭代器成员变量，这个专属化迭代器专门针对该容器的特点实现了迭代器应该有的所有接口。
需要遍历某STL容器时，只需要直接调出该容器的这个迭代器成员变量直接用即可，固定名字为 iterator。

（4）典型的迭代器用法

代码实战，用迭代器来实现遍历array。
begin() 和 end() 方法是得到容器遍历的开始和结尾的套路化方法。
begin() 和 end() 返回的是 array 类当中 iterator 类型。
array 和 array 是两个不同的类。

（使用了模板的技术，让我们看起来好像是一个类）

int main(void)
{
	array a{1, 7, 5};		// 可以，属于聚合初始化
	
	array::iterator iter;	// iterator 是 array 当中的一个内部类， iter 是迭代器定义的对象
	
	for (iter = a.begin(); iter != a.end(); iter++)
	{
		cout << "*iter = " << *iter << endl;
	}
	
/*	
	for (p=第1个元素; p!=最后一个元素; p++)
	{
		*p就是每一个元素
	}
*/
	return 0;
}

总结：迭代器使用本质：就是一个指针。

3.2 迭代器的几个细节问题

1、const与非const

(1)begin 和 end 返回可读可写的迭代器，而 cbegin 和 cend 返回const的只读迭代器

(2)代码验证迭代器的读写权限

分析：iterator 其实分为两种类型：

iterator ：可读可写，这个对应 begin 和 end
const_iterator：只能读，这个对应 cbegin 和 cend

array<int, 3>::iterator iter;				// 可读、可写的迭代器
	iter = a.begin();
	iter = a.end();

array<int, 3>::const_iterator iter;			// 只能读的迭代器
	iter = a.cbegin();
	iter = a.cend;

/*********************************************特殊情况*******************************************************/
// 编译器会报错：因为代码企图将 a.cbegin() 的使用范围变大，（只读--->可读可写）
array<int, 3>::iterator iter;	
	iter = a.cbegin();
	iter = a.cend();
// 编译器不会报错：因为发生了隐式类型转换，当使用范围缩小，是可以发生饮食类型转换的
// 将 a.begin() 的使用范围缩小（可读可写 ---> 只读）
array<int, 3>::const_iterator iter;			// 只能读的迭代器
	iter = a.begin();
	iter = a.end;

另外一个取巧的办法：auto，让编译器进行推断

注意：因为在 for 循环当中定义了局部变量，所以他的作用域只能在 for 循环当中。

当程序跳出 for 循环，就不可以使用了。

	array<int, 3> a{1, 7, 5};		// 可以，属于聚合初始化
	for (auto iter=a.rbegin(); iter!=a.rend(); iter++)
	{
		cout << "*iter = " << *iter << endl;
	}

2、begin和end的半开半闭区间

(1)begin返回第0个元素的迭代器（类似于C数组的首元素首地址指针）

(2)end指向的不是末尾元素的迭代器，而是末尾元素的（实际不存在的）下一个元素的迭代器

(3)前闭后开区间，经常记做 [begin end)，这样设计是为了写循环遍历时方便

// 这样的设计
for (auto iter=a.begin(); iter!=a.end(); iter++)

// 为什么不使用 < ?
    如果使用 "<" 的话，我们就又的重载这个运算符，实现起来很麻烦。

3、正向和逆向迭代器

(1)rbegin 和 rend 返回逆向迭代器（reverse）

(2)逆向迭代器的 begin是最末尾元素，而end是第0个元素去（实际不存在的）前面1个元素的迭代器

(3)逆向迭代器++是向前移动，而–是向后移动。

关键：逆向的时候，还可以使用 ++ ，来实现。

（就像是开车挂倒挡，给油门会向后面走）

	array<int, 3> a{1, 7, 5};		// 可以，属于聚合初始化
	for (auto iter=a.rbegin(); iter!=a.rend(); iter++)
	{
		cout << "*iter = " << *iter << endl;		// 输出： 5、 7、 1
	}

4、迭代器越界会怎么样

(1)和数组越界类似，编译时不审查，运行时会崩溃

(2)不管是正向还是逆向迭代器，++不到end，–不到 begin，就不会越界。

越界情况：

逆向迭代器使用的时候，iter--,iter 器就会向右边走，访问肯定会越界。
但是编译不会报错，运行的时候会段错误。

	array<int, 3> a{1, 7, 5};		// 可以，属于聚合初始化
	for (auto iter=a.rbegin(); iter!=a.rend(); iter--)
	{
		cout << "*iter = " << *iter << endl;		// 输出： 5、 7、 1
	}

3.3 不同类型的迭代器

1、C++17前共有5种迭代器

（1）InputIterator，输入迭代器。

（或者叫做只读只读迭代器好一点）

只能从容器内读出而不能向容器内写入，
只能单次读出（读出过一次后不保证再次 *** 作仍然可以，想想流输入输出）
- 类似于串口接受缓冲区，串口的接受缓冲区只能读取，我们只能单次读取一个，再次读的话就是读取下一个了。
- 串口的接受缓冲器区：看作是一个容器，读取串口的 *** 作：看作是一个输入迭代器。
只能 ++ 走，不能–走（就是单向的），
不能保证第二次遍历容器时，顺序不变，输入迭代器适用于单通只读型算法。

（2）OutputIterator，输出迭代器。

用于将信息传输给容器（修改容器中元素的值），但是不能读取。

（显示器就是只能写不能读的设备，可用输出容器来表示它）
只能++走不能–走（就是单向的）
输出迭代器适用于单通只写型算法。

（3）ForwardIterator，前向迭代器。

只能 ++ 走不能 – 走（就是单向的）

前向迭代器是一个更大的概念，里面包含输出迭代器、输入迭代器。

（4）BidirectionalIterator，双向迭代器。

**既能 ++ 也可以 – **，双向移动。

array<int, 3> a{1, 7, 5};		// 可以，属于聚合初始化
for (auto iter=a.rbegin(); iter!=a.rend(); iter--)

array<int, 3> a{1, 7, 5};		// 可以，属于聚合初始化
for (auto iter=a.rend(); iter!=a.rbegin(); iter--)

（5）RandomAccessIterator，随机访问迭代器。

能双向移动，并且可以单次跨越多个元素移动。

iter+2：就代表了可以随机访问

array<int, 3> a{1, 7, 5};		// 可以，属于聚合初始化
for (auto iter=a.rbegin(); iter!=a.rend(); iter+2)

2、C++17新增1种迭代器

contiguousIterator,连续迭代器。

所指向的逻辑相邻元素也在内存中物理上相邻。
数组的迭代器就属于连续迭代器、链表的迭代器就不属于连续迭代器。

3、STL的6种迭代器总结

每种迭代器更应该被看作是具有某些预定义特征（或者满足某接口要求）的一个迭代器的实现。
这些迭代器彼此之间有功能重叠，譬如随机访问迭代器可由双向迭代器扩展而来，详见文档
为何定义多种迭代器？是为了适配容器特性和泛型算法，后面会看到。
- 数组的迭代器：双向迭代器 + 随机迭代器 + 连续迭代器

4、C++20的新迭代器

C++20中重新实现了基于concept的新的迭代器体系
原有的模板都被加了前缀Legecy，但很长时间仍然可用，甚至还是主流
基于concept的新迭代器主要在类型约束和模板特化方面做了优化
C++20目前还刚开始，可以先不管，先学好原有的，后面再扩展去学C++20新特性

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/578804.html

C++ ：1、STL 的容器概述、array容器详解、迭代器初步分析

发表评论

评论列表（0条）