C++从零开始（十一）：C++进阶（下）STL

🌟《C++从零开始》 系列，开始更新中…

C++从零开始

https://hwh.zone/p/62712

九、STL

STL 即“标准模板库”（ “Standard Template Library”） 的缩写， 是C++标准库的一部分，使用时不用单独安装，直接引入头文件即可。

比如：

# include <vector>  // 引入vector
# include <array>   // 引入array

STL发展历史重要时刻一览：

• 1987年：贝尔实验室Stepanov 进行C++泛型软件库的研究；
• 1992年：Alex Stepanov 正式提出 STL（Standard Template Library）；
• 1994年：STL 正式纳入 C++ 标准化进程之中，随者 C++ 标准的改进，STL 也不断做着相应演化；
• 1998年：ANSI/ISO C++ 标准正式定案，STL 正式成为C++ 标准库不可或缺的重要组成部分。

STL 几乎所有的代码都采用了模板类和模版函数的方式，由此提供了很好的代码重用机会。

STL从广义上讲分为三类：

• container（容器），使得我们可以直接使用不同的数据结构，如vector（底层是数组）、list（底层是链表）、map（底层是红黑树）等来组织数据。这为我们高效组织不同数据，提供了极大的方便。

• algorithm（算法），则方便了我们对容器（或数组）中的数据进行各种骚操作，如排序（sort）、查找（find）、合并（merge）等。STL算法提供了现成的接口（函数），可以快速实现上述操作。而且一般来说，STL的实现远比我们自身实现的算法要高效，尽量避免自己造轮子，直接使用STL中的接口函数更好。

• iterator（迭代器），提供了遍历不同容器（或数组）的元素时的统一访问方式。这得益于STL为每种容器类设计了一个内嵌的iterator类，不同的容器都有自己专属的iterator，因此访问不同容器中的数据可统一使用container<type>::iterator方式：

  vector<int> v {1,2,3,4,5};    // vector
  vector<int>::iterator t = v.begin();  // iterator
  
  array<int,5> arr {1,2,3,4,5}; // array
  array<int,5>::iterator t = arr.begin(); // iterator

  普通数组名也可视为一个指向首元素的迭代器：

  int* arr = new int[5]{1,2,3,4,5}; 
  *(arr++);    // 2, arr作为迭代器

  更妙的是，迭代器使得容器和算法的实现可以分开，必要时又可作为“粘合剂”将二者联系起来。

现在我们按：迭代器、容器、算法的顺序依次对STL进行详细介绍。

9.1 迭代器

正如前述，迭代器用于遍历容器（或数组）中存储的元素。

9.1.1 认识迭代器

容器迭代器：iterator

STL 标准库为每一种标准容器定义了迭代器，我们可以按照下面方式进行访问：

<容器类名>::iterator 

就像：

vector<int>::iterator;
array<int,5>::iterator;

这里的类成员<容器类名>::iterator 对于不同容器，返回的是不同功能的迭代器。

容器	底层数据结构	迭代器类型
array	数组	随机访问迭代器
vector	数组	随机访问迭代器
deque	数组	随机访问迭代器
list	双链表	双向迭代器
set / multiset / map / multimap	红黑树	双向迭代器
forward_list	单链表	正向迭代器
unordered_map / unordered_set / …	哈希表	正向迭代器
stack / queue	对基础容器list、deque等进行封装	不支持迭代器

上述三种迭代器解释如下：

以下p、q代表对应的迭代器。

• 输入、输出迭代器：比较特殊，它们不是把容器（或数组）当做操作对象，而是把输入流/输出流作为操作对象。

  • 输入迭代器：只读，一次传递 ，为输入迭代器预定义实现只有istream_iterator和istreambuf_iterator，用于从一个输入流中读取数据。其支持的操作符有 *p,++p,p++,p!=q,p == q ；
  • 输出迭代器：只写，一次传递 ，为输出迭代器的预定义实现只有ostream_iterator和ostreambuf_iterator，用于向一个输出流写数据。支持的操作符和输入迭代器一致。

• 正向迭代器：结合了输入、输出迭代器几乎所有的功能，支持正向遍历、取值、赋值及相关比较操作。

  操作	描述
  p++ 或 ++p	返回p后一个元素的迭代器
  *p	获取迭代器所指向元素的值
  p = p+1	赋值操作
  p == p+1	比较操作
  p != p+1	比较操作

• 双向迭代器：具有正向迭代器的全部功能，除此之外还可以向后移动，即--p或p-- 。

  额外操作（相比正向迭代器）	描述
  p-- 或 --p	返回p前一个元素的迭代器

• 随机访问迭代器：具有双向迭代器的全部功能，除此之外还可以随机遍历容器元素（显然，指针就是这么一个迭代器）。

  额外操作（相比双向迭代器）	描述
  p+=i	p 往后移动 i 个元素
  p-=i	p 往前移动 i 个元素
  p+i	返回 p 后面第 i 个元素的迭代器
  p-i	返回 p 前面第 i 个元素的迭代器
  p[i]	返回 p 后面第 i 个元素的引用

  此外，两个随机访问迭代器 p1、p2 ：

  • 可以用 <、>、<=、>= 运算符进行比较；
  • 表达式 p2-p1 也是有定义的，返回区间[p1,p2]的元素个数。

再思考不同容器对应的迭代器就很好理解了：

• 底层数据结构是数组的（array/vector/deque），具体随机访问的特性，自然最适合随机迭代器；
• 底层数据结构是双链表和红黑树的（list/set/map），无法随机访问，但可以前、后方向遍历，所以使用双向迭代器；
• 底层数据结构是单链表、哈希表的（forward_list/unordered_map / unordered_set），无法随机访问也无法正向遍历，最后只能使用正向迭代器。

stack / queue 为了维持特殊的数据访问规则“先进后出” / “先进先出”，不允许前/后/随机迭代器在这里使用，否则会破坏规则。

容器其它迭代器

每个容器类除了成员iterator还可能有其它的迭代器：

迭代器	使用格式
默认迭代器	<容器类名>::iterator
常量正向迭代器	<容器类名>::const_iterator
反向迭代器	<容器类名>::reverse_iterator
常量反向迭代器	<容器类名>::const_reverse_iterator

这些迭代器是对类成员iterator的进一步限制。

• 常量正向/反向迭代器：保留iterator的基本特性，但常量迭代器无法修改其指向的元素；

• 反向迭代器：保留iterator的基本特性，但iterator进行 ++ 操作时，迭代器会指向容器中的后一个元素；而反向迭代器进行 ++ 操作时，迭代器会指向容器中的前一个元素。

  操作	描述
  p++ 或 ++p	返回p前一个元素的迭代器

不过以上 4 种定义迭代器，并不是每个容器都全部拥有。

• 部分容器同时支持以上 4 种方式，比如 array、deque、vector；
• 而有些容器只支持部分，例如 forward_list 容器只支持正向迭代器，不支持反向迭代器。

以vector为例演示vector类中四种迭代器成员的使用。

同前，vector的iterator是随机迭代器，常量迭代器和反向迭代器只是对iterator的进一步限制，但也具有随机迭代器的基本特性。

#include <vector>
#include <iostream>

int main()
{
   vector<int> vec {1,2,3,4,5};
    
   // vector默认的是随机迭代器
   std::cout << "随机迭代器遍历：";
   vector<int>::iterator iter = vec.begin(); 
   iter[1] = 20;  // 随机迭代器特性[]
   for(; iter != vec.end() ; iter++)
         std::cout << *(iter) << " ";  // 1 20 3 4 5

   // 常量迭代器
   std::cout << "\n常量迭代器遍历：";
   vector<int>::const_iterator c_iter = vec.cbegin(); 
   // c_iter[1] = 20;  // error，只读

   // 注意，rbegin()/crbegin() 返回的是尾元素迭代器
   // 反向迭代器
   std::cout << "\n反向迭代器遍历：";
   vector<int>::reverse_iterator r_iter = vec.rbegin(); 
   for(; r_iter != vec.rend() ; r_iter++)
         std::cout << *(r_iter) << " ";  // 5 4 3 20 1
         
   // 常量反向迭代器
   std::cout << "\n常量反向迭代器遍历：";
   vector<int>::const_reverse_iterator cr_iter = vec.crbegin(); 
   // c_iter[1] = 20;  // error，只读
    
   return 0;
}

输出：

[root@roy-cpp test]# ./test.out 
随机迭代器遍历：1 20 3 4 5 
反向迭代器遍历：5 4 3 20 1 

实际编码中，可用auto关键字减少定义迭代器类型时的书写：

auto iter = vec.begin(); 

下文我们会默认采用这种书写方式。更多迭代器的使用示例会穿插在后文中。

9.1.2 迭代器和指针？

迭代器和指针表现得和指针极为类似，以至于我们会产生疑惑：迭代器是什么？它就是指针吗？

先说结论，迭代器不是指针，它只是指针的一层封装，在STL中实现为一个模板类。

为什么要进行这种封装？

这样可统一不同容器的指针操作。比如，array/list/…底层都是利用指针算术运算查找元素，但具体的行为不同，采用iterator可把底层指针操作抽象出来，根据容器不同的底层数据结构来实现不同的++、–等指针操作。

源码简单观察迭代器。

#include <vector>

int main()
{
   vector<int> vec {1,2,3,4,5};   
   vector<int>::iterator iter = vec.begin(); 
}

F12查看vector<int>::iterator定义：

• iterator定义在模板类vector中，是 __gnu_cxx::__normal_iterator<pointer, vector> 的别名，注意到模板参数pointer；
• __normal_iterator是linux中STL自定义的迭代器模板，而pointer是普通指针类型别名，这里是int* 。

继续进入__normal_iterator类中：

• _M_current 类型为_Iterator ，即为pointer（这里是int*），它是一个指针，指向底层数组首元素 。

类中还有迭代器的各种操作，以++操作为例：

可见迭代器确实只是对指针进行了一层封装，本质还是通过指针实现了各种操作。

9.2 容器

STL中的容器也是模板类，本质是封装了不同的基本数据结构（数组、链表等）的模板类。STL提供三种标准容器，分别是：

• 序列容器
• 排序容器
• 哈希容器

这三种容器主要特点如下。

容器种类	包含的具体容器	底层数据结构	特点
序列容器	vector 向量容器、list 列表容器以及 deque 双端队列容器	数组或链表	序列容器中的元素以线性方式存储，但元素不是排好序的
排序容器	set 集合容器、multiset 多重集合容器、map 映射容器以及 multimap 多重映射容器	红黑树	排序容器中的元素，以键值对形式存储，默认是按键值排序好的
哈希容器	unordered_set 哈希集合、unordered_multiset 哈希多重集合、unordered_map 哈希映射以及 unordered_multimap 哈希多重映射	哈希表	哈希容器中元素同样以键值对方式存储，但元素是未排序的，元素的位置由哈希函数确定

下面开始具体介绍。

9.2.1 序列式容器

本节主要探讨以下容器：

容器	底层数据结构	特点	迭代器类型
array	数组	大小固定、无法修改	随机迭代器
vector	数组	大小可变、只能尾部插入/删除	随机迭代器
deque	数组	大小可变、双向队列，头尾可高效插入/删除	随机迭代器
list	双链表	大小可变，双链表，头尾可高效插入/删除	双向迭代器
forward_list	单链表	大小可变，单链表，仅可在头部插入/删除	前向迭代器

它们最主要的区别，由底层数据结构决定。

array

array 容器底层数据结构是普通的静态数组，所以array大小是固定的，无法动态扩展。

array 容器以类模板的形式定义在 <array> 头文件，如下所示：

template<typename _Tp, std::size_t _Nm>
struct array

这里实际是使用模板结构体struct，但在C++中和class差别不大，可以视为类模板。

在 array<_Tp,_Nm> 模板中：

• _Tp，用于指明容器中元素数据类型；
• _Nm，用于指明容器的大小。

一个简单使用实例。

#include <iostream>
#include <array>

int main()
{
    array<int, 5> arr {10, 20, 30, 40, 50}; // 初始化
    auto first = arr.cbegin();
    auto last = arr.cend();
    while (first != last)
    {
        std::cout << *first << " ";
        ++first;
    }
    std::cout << "\n";
    return 0; 
}

输出：

底层实现

本节主要探讨以下问题：

• array底层数据结构？
• array迭代器结构？

我们前面说过array底层是一个容量大小固定的数组，它具体是什么样呢？

array<int, 5> arr{10, 20, 30, 40, 50};

F12查看array定义：

注意到上面红框处的代码：

typedef _GLIBCXX_STD_C::__array_traits<_Tp, _Nm> _AT_Type;
typename _AT_Type::_Type    _M_elems; // typename说明_AT_Type::_Type是一个类型

成员 _M_elems便是底层数组。要分析出_M_elems类型，首先要知道_AT_Type::_Type是什么意思。

• 注意到第一行代码，_AT_Type是__array_traits<_Tp, _Nm>的别名，查看__array_traits定义：

  template<typename _Tp, std::size_t _Nm>
  struct __array_traits
  {
     typedef _Tp _Type[_Nm]; // _Type是一个静态数组
  
     static constexpr _Tp&
     _S_ref(const _Type& __t, std::size_t __n) noexcept
     { return const_cast<_Tp&>(__t[__n]); }
  };

  所以：_AT_Type就是一个array萃取类，而_Type是它的成员，也就是一个静态数组，类型为_Tp[_Nm]。

回到_M_elems相关定义：

typename _AT_Type::_Type    _M_elems;

_M_elems真正面貌便呼之欲出，在这个例子中_Tp为int，_Nm为5 ，所以上述等价于：

int[5] _M_elems;

每个容器都会有对应的迭代器，array的迭代器是什么？

说出来你有点惊讶，array的迭代器就简单实现为指针。

• iterator 即为_Tp * ；
• const_iterator 即为const _Tp * 。

所以你会发现即使array的iterator 没有实现operator++函数 ，依旧可以这么使用：

array<int,3> arr{1,2,3};
auto iter = arr.begin();  // 等价于 int* iter = arr.begin(); 
iter++; // ok

因为此时就是对一个int*指针进行++操作。

array让我们可以灵活定义各种类型的数组，保证了安全性又几乎不损失效率。如果想使用静态数组（固定数组），array首选推荐使用。

成员函数

array具有众多的成员函数，方便我们对array进行各种操作。

我们先一睹为快。

• 迭代器相关

  成员函数	功能
  begin()	返回指向容器中第一个元素的正向迭代器
  end()	返回指向容器最后一个元素之后一个位置的正向迭代器
  rbegin()	返回指向最后一个元素的反向迭代器
  rend()	返回指向第一个元素之前一个位置的反向迭代器
  cbegin()	和 begin() 功能相同，只不过其返回的迭代器类型为常量正向迭代器
  cend()	和 end() 功能相同，只不过其返回的迭代器类型为常量正向迭代器
  crbegin()	和 rbegin() 功能相同，只不过其返回的迭代器类型为常量反向迭代器
  crend()	和 rend() 功能相同，只不过其返回的迭代器类型为常量反向迭代器

  • 注意，如果是 const 类型容器，返回的一定是常量正向迭代器，常量迭代器不能修改指向的元素；
  • begin() 和 end() 为C++11新增，操作对象还可以是数组。

包含使用的一些小例子

• 主要成员函数

  标粗部分是常用的函数。

  成员函数	功能
  size()	返回容器中当前元素的数量，其值始终等于初始化 array 类的第二个模板参数 N
  max_size()	返回容器可容纳元素的最大数量，其值始终等于初始化 array 类的第二个模板参数 N
  empty()	判断容器是否为空，和通过 size()==0 的判断条件功能相同，但其效率可能更快
  at(n)	返回容器中 n 位置处元素的引用，作用类似[]，但该函数还会检查 n 是否有效，无效会抛出 out_of_range 异常
  front()	返回容器中第一个元素的直接引用，该函数不适用于空的 array 容器
  back()	返回容器中最后一个元素的直接引用，该函数同样不适用于空的 array 容器
  data()	返回一个指向容器首个元素的指针，利用该指针可实现复制容器中所有元素等类似功能
  fill(val)	将 val 这个值赋值给容器中的每个元素
  array1.swap(array2)	交换 array1 和 array2 容器中的所有元素，但前提是它们具有相同的长度和类型。

由于这些函数都比较简单，所以就不举例说明啦。

vector

vector基本是平时最常用的容器之一，和 array 容器类似，底层数据结构都是数组，只不过array是静态数组大小固定，而vector底层是一个动态数组。

最让人欣慰的是，vector会动态扩展（但不会收缩）所占用的内存空间，即自动扩容，我们无需操心数组增长问题。

vector容器以类模板的形式定义在 <vector> 头文件，如下所示：

template<typename _Tp, 
		 typename _Alloc = std::allocator<_Tp> >
class vector : protected _Vector_base<_Tp, _Alloc>

在 vector<_Tp,_Alloc> 模板中：

• _Tp ，用于指明容器中元素数据类型；
• _Alloc ，内存分配器，默认采用二级配置器，一般不用我们关心。

简单使用示例：

#include <iostream>
#include <vector>

int main()
{
	// vector<int,std::allocator<int>> vec {1,2,3,4,5,6}; // 模板参数完整使用
	vector<int> vec {1,2,3,4,5,6};
    vec.push_back("7"); // 继续插入数据，vector自动扩容，程序员无需关心
    vec.push_back("8");
    vec.push_back("9");
    for (auto i = vec.begin(); i < vec.end(); i++) 
	{
        std::cout << *i << " ";
    }
    std::cout << "\n";
    return 0; 
}

可以看到，相比array，vector可以很方便的使用push_back等方法插入新数据。

输出：

[root@roy-cpp test]# ./test.out 
1 2 3 4 5 6 7 8 9

底层实现

在本节我们主要探讨以下问题：

• vector底层数据结构？
• vector底层迭代器如何实现？
• vector底层是如何进行初始化的？
• vector底层自动扩容机制过程和原理？

我们先了解下vector类继承结构及核心成员。

注意到，vector 继承了 _Vector_base ，_Vector_base专门负责vector的内存管理。

_Vector_base核心是内部类_Vector_impl ，它继承了_Tp_alloc_type 获得内存分配释放的功能。

_Vector_impl核心成员：

• M_start，_M_finish，_M_end_of_storage ：所有关于地址，容量大小等操作都需要用到这三个指针。

  

  • _M_start ，代表起始位置的指针
  • _M_finish ，代表已存储的元素的末尾位置
  • _M_end_of_storage， 代表整个vector空间的结束位置

• _M_allocate和_M_deallocate：分别分配和释放vector所用内存，vector只需要负责元素构造和析构。

  

  • _M_allocate，最终通过malloc实现内存分配；
  • _M_deallocate，通过free实现内存释放。

了解了vector类大致结构，再来依次回答节前的问题：

• vector底层数据结构？

  vector底层是一个动态数组，初始化时会让指针_M_start （_Tp*类型）会指向分配内存。

  

• vector迭代器如何实现？

  同前9.1.2节，在vector类中可找到iterator相关定义：

  typedef __gnu_cxx::__normal_iterator<pointer, vector> iterator;

  进入__normal_iterator类中：

  

  • 主要成员_M_current 类型为_Iterator ，即为pointer（这里是int*），它是一个指针，指向底层数组首元素 。

  类中还封装迭代器的各种操作，以++操作为例：

  

• vector是如何进行初始化的？

  vector<string> vec {"Hello", "World"};

  vector类在构造时分配初始数组内存。vector类支持多种构造函数，如普通构造函数、移动构造函数、拷贝构造函数等。

  以普通构造函数为例：

  /**
    *  @brief  初始化为n个__value值，如果没指定就使用该类型默认值
    *  @param  __n  The number of elements to initially create.
    *  @param  __a  An allocator.
  */
  explicit vector(size_type __n, const value_type& __value = value_type(),const allocator_type& __a = allocator_type())
   : _Base(__n, __a)
   { 
   	 _M_fill_initialize(__n, __value); // 初始化所有元素为__value
   }

  核心是调用了基类构造函数_Base(__n, __a) ：

  typedef _Vector_base<_Tp, _Alloc>			 _Base;

  在_Vector_base 查到其定义：

  

  关键函数_Vector_base::_M_create_storage实现为：

  

  • _M_allocate 最终就是通过_M_impl.allocate实现；
  • _M_impl.allocate 最终通过malloc实现内存分配。

  综上所述，vector通过构造函数初始化，最终调用malloc分配了底层数组内存空间。

• vector自动扩容机制实现的过程和原理？

  vec.push_back("7"); // 继续插入数据，vector自动扩容，程序员无需关心
  vec.push_back("8");
  vec.push_back("9");

  如下所示，左图代表扩容前的存储结构，右图是扩容后的存储结构。

  

  扩容条件：

  • size()函数返回的是已用空间大小，capacity()返回的是总空间大小，capacity()-size()则是剩余的可用空间大小；
  • 当size()和capacity()相等，说明vector目前的空间已被用完，如果再添加新元素，则会引起vector空间的动态增长。

  扩容过程：

  1. 重新分配一块两倍于原来大小的内存空间；
  2. 将原来的存储空间的元素，依次拷贝到新的2*capacity大小的存储空间之中。

成员函数

vector具有众多的成员函数，方便我们对vector进行各种操作。

我们先一睹为快。

• 迭代器相关

  同array。

  成员函数	功能
  begin()	返回指向容器中第一个元素的正向迭代器
  end()	返回指向容器最后一个元素之后一个位置的正向迭代器
  rbegin()	返回指向最后一个元素的反向迭代器
  rend()	返回指向第一个元素之前一个位置的反向迭代器
  cbegin()	和 begin() 功能相同，只不过其返回的迭代器类型为常量正向迭代器
  cend()	和 end() 功能相同，只不过其返回的迭代器类型为常量正向迭代器
  crbegin()	和 rbegin() 功能相同，只不过其返回的迭代器类型为常量反向迭代器
  crend()	和 rend() 功能相同，只不过其返回的迭代器类型为常量反向迭代器

  • 注意，如果是 const 类型容器，返回的一定是常量正向迭代器，常量迭代器不能修改指向的元素；
  • begin() 和 end() 为C++11新增，操作对象还可以是数组。

• 主要成员函数

  标粗部分是常用的函数。

  成员函数	功能
  size()	返回容器中当前元素的数量
  capacity()	返回当前容量
  reserve()	增加容器的容量
  max_size()	返回容器可容纳元素的最大数量
  empty()	判断容器是否为空，和通过 size()==0 的判断条件功能相同，但其效率可能更快
  at(n)	返回容器中 n 位置处元素的引用，作用类似[]，但该函数还会检查 n 是否有效，如果不是会抛出 out_of_range 异常
  front()	返回容器中第一个元素的直接引用
  back()	返回容器中最后一个元素的直接引用
  data()	返回一个指向容器首个元素的指针，利用该指针可实现复制容器中所有元素等类似功能
  swap()	交换两个容器的所有元素

  相比array独有的方法（可以尾部插入、删除元素等）：

  成员函数	功能
  push_back()	在容器的尾部添加一个元素
  pop_back()	移出容器尾部的元素
  emplace_back()	在容器的尾部添加一个元素
  erase()	移出一个元素或一段元素，返回指向删除元素的下一个元素的迭代器
  clear()	移出所有的元素，容器大小变为 0

关于删除vector空间释放有些小问题。

clear()、erase()方法均不会释放vector所占用的内存空间。

#include <iostream>
#include <vector>

int main() 
{
    vector<int> vec {1,2,3,4,5};
    std::cout<< vec.size() << std::endl;     // 5
    std::cout<< vec.capacity() << std::endl; // 5

    vec.erase(vec.begin(), vec.begin()+1);
    std::cout<< vec.size() << std::endl;     // 4
    std::cout<< vec.capacity() << std::endl; // 5 , capacity未改变

    vec.clear();
    std::cout<< vec.size() << std::endl;     // 0
    std::cout<< vec.capacity() << std::endl; // 5 , capacity未改变
}

因为vector内存占用空间只增不减：

• 分配了10,000个字节，然后erase掉后面9,999个，留下一个有效元素，但是内存占用仍为10,000个；
• 所有内存空间，在vector对象析构时才能被系统回收。

换句话说，clear()、erase()方法只是减少了vector的size大小，没有改变capacity。

我们可以借助swap方法彻底删除。

#include <iostream>
#include <vector>

int main() 
{
    vector<int> vec {1,2,3,4,5};
    vector<int>().swap(vec); // swap
    
    std::cout<< vec.size() << std::endl;     // 0
    std::cout<< vec.capacity() << std::endl; // 0，彻底删除
}

• vector<int>()使用默认构造函数建立临时vector对象，再在该临时对象上调用swap成员；
• swap调用之后原来vector占用的空间就等于一个默认构造的对象的大小，而临时对象就具有原来对象vec的大小；
• 临时对象随即被析构，其占用的空间（原来vec的空间）也被释放。

另一方面，会动态增长和缩小的容器，如deque，便没有上面烦扰：clear()、erase()方法删除元素后，其内存也随之缩减。

下节我们一起来认识下吧。

deque

vector 可以在尾部快速添加和移除元素，虽然理论上也可以在头部进行操作，但因为其底层是一个一维动态数组，因此无论是添加和移除元素都涉及到数组所有元素的移动，效率都奇差，因此STL相关头部操作的方法vector::push_front()都没有提供。

deque （双端队列）用于弥补 vector 的不足，在首尾两端都可以快速添加和删除，STL会提供头、尾插入、删除方法（vector头部操作效率低，STL只提供了尾部插入、删除相关方法），其直观形式表现如下：

不过这种“整体连续”是一种假象，deque底层实际实现为一个二维动态数组 。正式介绍其底层实现前，我们按老规矩先介绍容器上层封装和基本使用。

deque容器以类模板的形式定义在 <deque> 头文件，如下所示：

template<typename _Tp, 
	     typename _Alloc = std::allocator<_Tp> >
class deque : protected _Deque_base<_Tp, _Alloc>

在 deque<_Tp,_Alloc> 模板中：

• _Tp，用于指明容器中元素数据类型；
• _Alloc，内存分配器，默认采用二级配置器，一般不用我们关心。

简单使用实例。

#include <iostream>
#include <deque>

void printDeque(const deque<int>& d)
{
    std::cout<<"size = " << d.size() <<" : ";
    // deque没有`capacity`()函数
    for(auto first = d.begin(); first != d.end(); first++)
    	std::cout<<*first<<" ";
    std::cout<<"\n";    
}
int main()
{
	deque<int> d {1,2,3};
    d.push_back(4);
    d.push_front(0);
    printDeque(d);  // size = 5 : 0 1 2 3 4
    
    d.pop_back();
    d.pop_front();
    printDeque(d); // size = 3 : 1 2 3  
    
    return 0;
}

底层实现

本节我们主要探讨以下问题：

• deque底层数据结构及实现？
• deque底层迭代器如何定义？
• deque什么时候进行扩容？如何扩容？
• deque底层如何插入、删除一个数据？

我们先了解下deque类继承结构及核心成员（类似vector继承结构）。

注意到，deque继承了 _Deque_base ，_Deque_base专门负责vector的内存管理。

_Deque_base核心是内部类_Deque_impl ，它继承了_Tp_alloc_type 获得内存分配释放的功能。

template<typename _Tp, typename _Alloc>
class _Deque_base
{
  public:
      ...
  protected:
      typedef typename _Alloc::template rebind<_Tp>::other  _Tp_alloc_type;
  struct _Deque_impl: public _Tp_alloc_type
  {
      _Tp** _M_map;   // map数组，其中的每个元素都是一个指针（节点），指向一块缓冲区
      size_t _M_map_size;
      iterator _M_start;
      iterator _M_finish;

_Deque_impl核心成员：

• _M_map：二维动态数组map；

• _M_start，_M_finish：迭代器，start 迭代器记录着 map 数组中首个连续空间的信息，finish 迭代器记录着 map 数组中最后一个连续空间的信息。

  deque的begin() 和 end() 方法就是通过他们实现的：

  iterator begin() { return _M_start; }
  iterator end() { return _M_finish; }

好了，现在我们可以依次回答节前的问题。

我们先探讨第一个问题：deque底层数据结构及实现？

deque 容器用二维动态数组（数组名假设为 map）存储着各个连续空间的首地址 ，每个连续空间是等长的内存缓存区域（下图中的strat和finish对应上面的_M_start和_M_finish）。

所以第一个问题答案总结如下：deque底层数据结构就是一个二维数组_Tp** ，由_Deque_impl类负责相关内存分配。

最后补充一点deque类中_Map_pointer介绍。

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
class deque : protected _Deque_base<_Tp, _Alloc>
{
    typedef _Deque_base<_Tp, _Alloc>           _Base;
    typedef typename _Base::_Tp_alloc_type	 _Tp_alloc_type;
    public:
      ...
      typedef typename _Tp_alloc_type::pointer           pointer;
      ...
    protected:
      // _Map_pointer，一个二级指针，指向二维数组map
      typedef pointer*                           _Map_pointer;

_Map_pointer是一个二维指针类型。

_Map_pointer其实就是_Tp**：

容易知道，_Map_pointer 是_Deque_base<_Tp, _Alloc>::_Tp_alloc_type::pointer* 别名；

• 查看_Tp_alloc_type定义：

  class _Deque_base
  {
  	protected:
      // _Alloc是模板参数设置的分配器，_Tp是模板参数的类型
      // _Tp_alloc_type是空间配置器的类型
  	typedef typename _Alloc::template rebind<_Tp>::other  _Tp_alloc_type;

  _Tp_alloc_type 就是other的别名，经过一番艰难的求知，在三张图带你弄懂STL中内存分配器 中确定：other类型其实是allocator<_Tp1>这个类型，如果我们传参为int 那就是allocator<int> 。

• 查看pointer定义：

  

所以，最终pointer* 等价于__Tp** ，如果我们传入的类型为int，那就是int** 。

typedef pointer*   _Map_pointer;

继续第二个问题：deque迭代器如何定义？

前面我们说过，_M_start，_M_finish都是iterator类型：

typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;

查看_Deque_iterator定义：

template<typename _Tp, typename _Ref, typename _Ptr>
struct _Deque_iterator
{
      typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
      ...
      ...
      typedef _Tp**                           _Map_pointer;
      typedef _Deque_iterator                 _Self;

      _Tp* _M_cur;   // 可以看成是原生指针，表示当前的元素位置
      _Tp* _M_first; // 缓冲区开始处，可看成是第二维第一个元素的位置  
      _Tp* _M_last;  // 缓冲区末端的下一个位置，第二维的最后元素的下一个位置  
      _Map_pointer _M_node; // _M_node指向第一维  

相比deque的迭代器底层实现 ，vector中的迭代器就底层封装了一个光溜溜的_M_current指针， 简单了很多：

第三个问题：deque什么时候进行扩容？如何扩容？

放一张图：

deque何时及如何扩容一目了然：

• 扩容时机：map数组已满；
• 扩容方式：再申请一块更大的连续空间供 map 数组使用，将原有数据（很多指针）拷贝到新的 map 数组中，然后释放旧map数组的空间（不释放map数组中的指针指向的空间）。

最后一个问题：deque底层如何插入、删除一个数据？

如果是插入操作，需分三种情况讨论：在容器的尾部插入、在容器的首部插入、在容器的指定位置前插入元素。这里仅以在容器的尾部插入为例分析。

• 在容器的尾部插入

  此时，cur指向的是含有实际值的下一个位置，last表示最后一个实际值的下一个位置。

  push_back(const T& t)

  1. 找到finish绑定的缓冲区，如果缓存区还有空闲位置（start.cur!=start.last），则在cur位置插入元素，并更新cur++ ，否则转2；
  2. 没有空闲位置可以插入元素，则在finish.node（这是第一维）的后一个位置申请一个缓冲区（如果map满了，触发扩容），并将finish绑定到该新缓冲区，重复1中步骤插入元素。

删除操作类似，同样需要分三种情况：在容器的尾部删除、在容器的首部删除、在容器的指定位置前删除元素。这里仅以在容器的尾部删除为例分析。

• 在容器的尾部删除

  pop_back()

  1. 找到finish绑定的缓冲区，如果finish所绑定的缓冲区上有1个或多个元素，将最后一个有效元素析构即可destroy(–finish.cur)，否则转2；

  2. finish所绑定的缓冲区为空，即finish.cur==finish.first：

     • 先将该空缓冲区的空间释放掉deallocate_node(finish.first)；

     • 再将finish绑定到上一个map结点和缓冲区；

       finish.set_node(finish.node-1);
       finish.cur=finish.last-1;

     • 最后将最后一个元素析（也是当前要删除的元素）构destroy(finish.cur)。

  从这里也可以看出，相比vector，deque确实会动态释放内存，不会只增不减。

成员函数

deque具有众多的成员函数，方便我们对deque进行各种操作。

我们先一睹为快。

• 迭代器相关

  同array，vector。

  成员函数	功能
  begin()	返回指向容器中第一个元素的正向迭代器
  end()	返回指向容器最后一个元素之后一个位置的正向迭代器
  rbegin()	返回指向最后一个元素的反向迭代器
  rend()	返回指向第一个元素之前一个位置的反向迭代器
  cbegin()	和 begin() 功能相同，只不过其返回的迭代器类型为常量正向迭代器
  cend()	和 end() 功能相同，只不过其返回的迭代器类型为常量正向迭代器
  crbegin()	和 rbegin() 功能相同，只不过其返回的迭代器类型为常量反向迭代器
  crend()	和 rend() 功能相同，只不过其返回的迭代器类型为常量反向迭代器

  • 注意，如果是 const 类型容器，返回的一定是常量正向迭代器，常量迭代器不能修改指向的元素；
  • begin() 和 end() 为C++11新增，操作对象还可以是数组。

• 主要成员函数

  标粗部分是常用的函数。

  • 头、尾操作效率均高，所以会都提供push_front() 、push_front()等头、尾部等插入、删除方法。

  成员函数	功能
  size()	返回容器中当前元素的数量
  capacity	deque没有该方法，vector有
  reserve()	deque没有该方法，vector有
  max_size()	返回容器可容纳元素的最大数量
  empty()	判断容器是否为空，和通过 size()==0 的判断条件功能相同，但其效率可能更快
  at(n)	返回容器中 n 位置处元素的引用，作用类似[]，但该函数还会检查 n 是否有效，如果不是会抛出 out_of_range 异常
  front()	返回容器中第一个元素的直接引用
  back()	返回容器中最后一个元素的直接引用
  data()	deque没有该方法，vector有
  swap()	交换两个容器的所有元素

  相比array独有的方法（可以头、尾部插入、删除元素等）：

  成员函数	功能
  push_back()	在容器的尾部添加一个元素
  emplace_back()	在容器的尾部添加一个元素
  push_front()	在容器的头部添加一个元素
  emplace_front()	在容器头部生成一个元素
  erase()	移出一个元素或一段元素，返回指向删除元素的下一个元素的迭代器
  clear()	移出所有的元素，容器大小变为 0
  pop_back()	移出容器尾部的元素
  pop_front()	移除容器头部的元素

这些方法都比较简单，不过多介绍。

list

list容器的底层是用双向链表实现的，甚至一些 STL 版本中（比如 SGI STL），list 容器的底层实现使用的是双向循环链表。

• a）双向链表，b）循环链表

双链表相比数组有很多好处：

• 插入和删除操作效率高（但查找效率低），头、尾插入/删除操作也是，所以STL会都提供了push_front()、push_back()等头、尾部操作方法；
• 扩展方便；
• 内存空间不要求连续，可充分利用空间；
• …

这些也是list所具有的优点。另外一个好处可能现在有点难以理解（后文会解释）：

• 在vector中如果进行插入和删除操作会导致后续迭代器会失效，而在List中：插入不会导致迭代器失效；删除也只会使得当前迭代器失效，后续迭代器不会失效。

list容器以类模板的形式定义在 <list> 头文件，如下所示：

template<typename _Tp,
		 typename _Alloc = std::allocator<_Tp> >
class list : protected _List_base<_Tp, _Alloc>

在 list<_Tp,_Alloc> 模板中：

• _Tp，用于指明容器中元素数据类型；
• _Alloc，内存分配器，默认采用二级配置器，一般不用我们关心。

简单使用实例。

#include <iostream>
#include <list>

void printList(const list<int>& l)
{
    std::cout<<"size = " << l.size() <<" : ";
    // list没有`capacity`()函数
    for(auto first = l.begin(); first != l.end(); first++)
    	std::cout<<*first<<" ";
    std::cout<<"\n";    
}
int main()
{
	list<int> l {1,2,3};
    l.push_back(4);
    l.push_front(0);
    printList(l);  // size = 5 : 0 1 2 3 4
    
    l.pop_back();
    l.pop_front();
    printList(l);  // size = 3 : 1 2 3  
    
    return 0;
}

因为list不止是链表还是双向链表，所以我们头、尾都是可以插入/删除的。

底层实现

本节我们主要探讨以下问题：

• list底层数据结构及实现？
• list底层迭代器如何定义？
• list底层如何插入、删除一个数据？

我们先了解下list类继承结构及核心成员（类似vector、deque继承结构）。

注意到，list继承了 _List_base ，_List_base专门负责list的内存管理。

_List_base核心是内部类_List_impl ，它继承了_Tp_alloc_type 获得内存分配释放的功能。

template<typename _Tp, typename _Alloc>
class _List_base
{
  protected:
    typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
        _Node_alloc_type;
    typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;

    struct _List_impl: public _Node_alloc_type
    {
		__detail::_List_node_base _M_node;  // 头结点，不存储数据

        _List_impl(): _Node_alloc_type(), _M_node()
        { }

	    _List_impl(const _Node_alloc_type& __a): _Node_alloc_type(__a), 	_M_node()
	    { }
      ...
    }; // _List_impl
...

_List_impl核心成员：

• _M_node：list头结点，不存储数据

  

好了，现在我们可以依次回答节前的问题。

第一个问题：list底层数据结构及实现？

list底层是链表，头结点为_M_node。头节点是_List_node_base类型，不存储数据。

但数据结点是_List_node 类型，存储数据。

借助_M_node可以实现，list中几乎所有的成员函数。

第二个问题：list底层迭代器如何定义？

在list类中，找到iterator定义：

typedef _List_iterator<_Tp>             iterator;

其定义如下：

template<typename _Tp>
struct _List_iterator
{
    // 定义一堆别名
    typedef _List_iterator<_Tp>                _Self;
    typedef _List_node<_Tp>                    _Node;

    typedef ptrdiff_t                          difference_type;
    // list为一个双向链表，迭代器必须具备前移、后移的能力，所以提供了bidirectional iterator
    typedef std::bidirectional_iterator_tag    iterator_category;
    typedef _Tp                                value_type;
    typedef _Tp*                               pointer;
    typedef _Tp&                               reference;
     
    // 构造函数1：实例化头结点_M_node指针
    _List_iterator(): _M_node() { }   
    // 构造函数2：给定值实例化
     explicit _List_iterator(__detail::_List_node_base* __x): _M_node(__x) { }
    ...

继续看看具体_List_iterator相关函数。

• operator++ 的后置自增，将当前 _M_node 移动到 _M_node->_M_next 所在的位置，并返回移动之后的迭代器。

  // _Self 是_List_iterator<_Tp> 一个类型别名
  _Self& operator++()
  {
       _M_node = _M_node->_M_next;
       return *this;
  }

• operator--大同小异。

  _Self& operator--()
  {
  	_M_node = _M_node->_M_prev;
  	return *this;
  }

最后一个问题：list底层如何插入、删除一个数据？

大致应该就是链表的插入、删除相关操作。这里有机会再补上吧。

成员函数

list具有众多的成员函数，方便我们对list进行各种操作。

我们先一睹为快。

• 迭代器相关

  同array、vector，deque。

  成员函数	功能
  begin()	返回指向容器中第一个元素的正向迭代器
  end()	返回指向容器最后一个元素之后一个位置的正向迭代器
  rbegin()	返回指向最后一个元素的反向迭代器
  rend()	返回指向第一个元素之前一个位置的反向迭代器
  cbegin()	和 begin() 功能相同，只不过其返回的迭代器类型为常量正向迭代器
  cend()	和 end() 功能相同，只不过其返回的迭代器类型为常量正向迭代器
  crbegin()	和 rbegin() 功能相同，只不过其返回的迭代器类型为常量反向迭代器
  crend()	和 rend() 功能相同，只不过其返回的迭代器类型为常量反向迭代器

  • 注意，如果是 const 类型容器，返回的一定是常量正向迭代器，常量迭代器不能修改指向的元素；
  • begin() 和 end() 为C++11新增，操作对象还可以是数组。

• 主要成员函数

  标粗部分是常用的函数。

  • list底层是双链表，只有双向迭代器没有随机迭代器，一些随机迭代器才支持的方法，比如at(n)、[n]都是不支持的；

  • 头、尾操作效率均高，所以会提供push_front() 、push_back()等头、尾部等插入、删除方法。

    成员函数	功能
    size()	list没有，vector、deque有
    capacity	list、deque没有该方法，vector有
    reserve()	list、deque没有该方法，vector有
    max_size()	返回容器可容纳元素的最大数量
    empty()	判断容器是否为空，和通过 size()==0 的判断条件功能相同，但其效率可能更快
    at(n)	不支持
    front()	返回容器中第一个元素的直接引用
    back()	返回容器中最后一个元素的直接引用
    data()	list、deque没有该方法，vector有
    swap()	交换两个容器的所有元素

  相比array独有的方法（可以头、尾部插入、删除元素等）：

  成员函数	功能
  push_back()	在容器的尾部添加一个元素
  emplace_back()	在容器的尾部添加一个元素
  push_front()	在容器的头部添加一个元素
  emplace_front()	在容器头部生成一个元素
  erase()	移出一个元素或一段元素，返回指向删除元素的下一个元素的迭代器
  clear()	移出所有的元素，容器大小变为 0
  pop_back()	移出容器尾部的元素
  pop_front()	移除容器头部的元素

  相比deque新增（链表的一些操作方法）：

  成员函数	功能
  splice()	将一个 list 容器中的元素插入到另一个容器的指定位置
  remove(val)	删除容器中所有等于 val 的元素
  remove_if()	删除容器中满足条件的元素
  unique()	删除容器中相邻的重复元素，只保留一个
  merge()	合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的
  sort()	通过更改容器中元素的位置，将它们进行排序
  reverse()	反转容器中元素的顺序

新增的函数有点意思，合适的时候进行补充。

迭代器失效

分析“迭代器失效”这个问题前，我们先回忆一下各个容器的底层数据结构：

容器	底层数据结构	对应的迭代器类型
array、vector、deque	数组	随机访问迭代器
list、forward_list	链表	双向迭代器
set / multiset / map / multimap	红黑树	双向迭代器
stack / queue	list 和 deque 实现，封闭头部	不支持迭代器

好了，让我们正式开始吧。

看下面这段看似无害的代码：

#include <vector>

int main()
{
    vector<int> vec {1,2,3,4,5};
    for(auto it=vec.begin(); it != vec.end(); it++)
    {
        vec.erase(it);  // 迭代器失效
    }
    return 0;
}

执行时却发生了错误：

[root@roy-cpp test]# ./test.out 
Segmentation fault

这段代码对于list、vector、deque等容器都会出错（array例外，它没有erase()方法），究其原因就是出现迭代器失效。

1. 迭代器it 初始化指向了第一个元素，判断条件成立进入循环体；
2. 执行vec.erase(it)，it被删除；
3. 执行it++出错，it已失效无法递增。

得益于erase方法的返回值是下一个有效的 iterator，解决办法也很简单。

#include <vector>

int main()
{
    vector<int> vec {1,2,3,4,5};
    for(auto it=vec.begin(); it != vec.end(); )
    {
        it = vec.erase(it);  // 迭代器失效
        // it++;  // it已经是下一个迭代器了不用++
    }
    return 0;
}

或者：

⚠️ 关联容器：map、set、multimap、multiset等可以使用两种方式，但list、vector、deque无法使用下面这种方式，否则会出错（为啥？）。

#include <map>

int main()
{
    map<int,int> map1;
    map1.emplace(1,1);
    map1.emplace(2,2);
    for(auto it=map1.begin(); it != map1.end(); )
    {
        map1.erase(it++);  // 迭代器失效
    }
    return 0;
}

1. it++会复制一个it副本传递给erase() 函数；
2. it执行++操作；
3. 最后再执行erase()将 复制的it副本删除，它和it指向同一元素，所以最后it还是失效了。

迭代器失效总结如下：

• 如果底层数据结构是一维数组的（vector）
  • 插入操作：插入位置及之后的迭代器都失效，因为插入位置后的所有元素都需要移动；如果还触发了扩容，则所有迭代器都失效；
  • 删除操作：删除位置及之后的迭代器都失效，因为删除位置之后的元素都需移动；
• 如果底层数据结构是二维数组的（deque）
  • 插入操作：首部或者尾部插入不会使迭代器失效，因为不影响其它元素位置，中间插入会使得所有迭代器失效，因为所有元素都被影响要移动；
  • 删除操作：部或尾部删除元素只会使得被删除位置的迭代器失效，中间删除会使得所有迭代器失效，原因同上。
• 如果底层数据结构是链表的（list、forward_list）
  • 插入操作：节点无需移动，所有迭代器有效；
  • 删除操作：节点无需移动，仅删除的节点迭代器失效。
• 如果底层数据结构是红黑树的（set / multiset / map / multimap）
  • 插入操作：不影响其它节点，所有迭代器有效；
  • 删除操作：不影响其它节点，仅删除的节点迭代器失效。

forward_list

forward_list底层实现和list一样，都是链表，但是forward_list使用的是单链表，而list是双链表。

单链表相比双链表灵活性差了很多：

• 尾部插入、删除操作效率低；
• 只能前向遍历，不能反向遍历（因此forward_list只有前向迭代器，而且不会具有 rbegin()、rend() 之类的成员函数）；
• …

但是单链表空间利用利用率更高（node不用保存前向指针），而且遵循奥卡姆剃刀原则：“若无必要，勿增实体”——在诸多可以满足需求的结构中，选择影响范围最小的。

所以只要是 list 容器和 forward_list 容器都能实现的操作，应优先选择 forward_list 容器。

forward_list 容器以类模板的形式定义在 <forward_list > 头文件，如下所示：

template<typename _Tp, 
		 typename _Alloc = allocator<_Tp> >
class forward_list : private _Fwd_list_base<_Tp, _Alloc>

在 forward_list<_Tp,_Alloc> 模板中：

• _Tp，用于指明容器中元素数据类型；
• _Alloc，内存分配器，默认采用二级配置器，一般不用我们关心。

简单使用实例。

#include <iostream>
#include <forward_list>

void printList(const forward_list<int>& fl)
{
    // forward_list 没有size()方法
    // 用distance方法实现
    std::cout<<"size = " << std::distance(std::begin(fl), std::end(fl)) <<" : ";
    // forward_list 没有capacity()函数
    for(auto first = fl.begin(); first != fl.end(); first++)
    	std::cout<<*first<<" ";
    std::cout<<"\n";    
}
int main()
{
	forward_list<int> fl {1,2,3};
    // fl.emplace_front(4);  // 底层是单链表，不支持尾部相关操作的函数/迭代器
    fl.emplace_front(0); // 头部插入，尾部不行
    printList(fl);    // size = 4 : 0 1 2 3 
    
    fl.pop_front();   // 头部删除
    printList(fl);    // size = 3 : 1 2 3  
    
    return 0;
}

注意到：

• forward_list只能头部进行了插入等操作，不能在尾部；
• forward_list没有size方法，只能用distance方法实现。

底层实现

本节我们主要探讨以下问题：

• forward_list底层数据结构及实现？
• forward_list底层迭代器如何定义？
• forward_list底层如何插入、删除一个数据？

forward_list底层实现和list极为相似，这里直接给出关键答案。

• forward_list底层数据结构及实现？

  forward_list底层是但链表，头结点为_M_head。头节点是_Fwd_list_node_base类型，不存储数据。

  

• forward_list底层迭代器如何定义？

  没啥好说的，和list差不多。

  

• forward_list底层如何插入、删除一个数据？

  就是单链表相关的操作，有头结点操作比较统一。

成员函数

forward_list具有众多的成员函数，方便我们对forward_list进行各种操作。

我们先一睹为快。

• 迭代器相关

  和array、vector、deque，list不同，forward_list没有尾部相关迭代器函数。

  成员函数	功能
  begin()	返回指向容器中第一个元素的正向迭代器
  end()	返回指向容器最后一个元素之后一个位置的正向迭代器
  cbegin()	和 begin() 功能相同，只不过其返回的迭代器类型为常量正向迭代器
  cend()	和 end() 功能相同，只不过其返回的迭代器类型为常量正向迭代器

  • 注意，如果是 const 类型容器，返回的一定是常量正向迭代器，常量迭代器不能修改指向的元素；
  • begin() 和 end() 为C++11新增，操作对象还可以是数组。

• 主要成员函数

  标粗部分是常用的函数。

  • list、forward_list底层是链表，没有随机迭代器，一些随机迭代器才支持的方法，比如at(n)都是不支持的；
  • forward_list底层是单链表，只有头部操作效率高，所以尾部操作相关的方法push_back()等STL不提供；

  成员函数	功能
  size()	forward_list不支持，可用std::distance() 方法间接实现
  capacity	forward_list、list、deque没有该方法，vector有
  reserve()	forward_list、list、deque没有该方法，vector有
  max_size()	返回容器可容纳元素的最大数量
  empty()	判断容器是否为空，和通过 size()==0 的判断条件功能相同，但其效率可能更快
  at(n)	-
  front()	返回容器中第一个元素的直接引用
  data()	forward_list、list、deque没有该方法，vector有
  swap()	交换两个容器的所有元素

  相比array独有的方法（可以头部插入、删除元素等）：

  成员函数	功能
  push_front()	在容器的头部添加一个元素

| emplace_front() | 在容器头部生成一个元素 |
| erase() | 移出一个元素或一段元素，返回指向删除元素的下一个元素的迭代器 |
| clear() | 移出所有的元素，容器大小变为 0 |
| pop_front() | 移除容器头部的元素 |

相比deque新增（链表相关方法）：

成员函数	功能
splice()	将一个 forward_list容器中的元素插入到另一个容器的指定位置
remove(val)	删除容器中所有等于 val 的元素
remove_if()	删除容器中满足条件的元素
unique()	删除容器中相邻的重复元素，只保留一个
merge()	合并两个事先已排好序的 forward_list容器，并且合并之后的 forward_list容器依然是有序的
sort()	通过更改容器中元素的位置，将它们进行排序
reverse()	反转容器中元素的顺序

9.2.2 关联式容器

序列式容器元素是顺序存储的，而“关联式容器”是以键值对方式存储的，顾名思义每个元素都会和一个“键”相关联的。这种特性简单解释来说，就是查找到“键”就可以查找到相关元素。

在底层实现中，关联容器的“键值对”采用红黑树来存储，这使得可以很方便地实现排序，所以关联式容器的元素都会按照键值的大小做升序排序。

本节主要探讨以下容器：

除此之外，C++ 11 还新增了 4 种哈希容器，即 unordered_map、unordered_multimap 以及 unordered_set、unordered_multiset。严格来说，它们也属于关联式容器，但由于哈希容器底层采用的是哈希表，而不是红黑树，放在下节9.2.3讲解。

容器	底层数据结构	特点	迭代器类型
map	红黑树，下同	键必须唯一，会根据键大小默认升序排序	双向迭代器，下同
multimap		基本同map，但multimap 键可重复
set		键和值完全相同，键依旧唯一，默认升序
multiset		基本同set，但multiset 键可重复

pair

我们知道，关联式容器存储的是“键值对”形式的数据，即<key,value>形式。

C++STL专门提供了pair类模板，用来封装“键值对”这种形式的数据。

它被定义为：

template<class _T1, class _T2>
struct pair
{
      _T1 first;
      _T2 second;
      ...

使用起来也很简单：

#include <utility>
#include <string>       

int main()
{
    // 初始化
    pair<int,string> kv1{1,"一"};
    pair<int,string> kv2{2,"二"};

    // 修改  
    kv1.first = -1;
    kv1.second ="负一"; 

    // 比较:键值对完全相关返回true，否则false
    bool is_equal = kv1 == kv2 ? true : false;

    // swap交换键值对
    kv1.swap(kv2);
}

你还可以使用make_pair 来创建pair对象：

pair<int,string> kv3{make_pair(3, "三")};

后面我们会大量用到这种方式创建pair对象。

map

作为关联式容器的一种，map用 pair 类模板创建键值对，底层结构是红黑树而且还会根据各键值对的键的大小，进行升序排序。

map容器以类模板形式定义在 <map> 头文件，如下所示：

template <typename _Key, 
		  typename _Tp, 
          typename _Compare = std::less<_Key>,
          typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class map

在 map<_Key,_Tp,_Compare,_Alloc> 模板中：

• _Key，指定键的类型；
• _Tp，指定值的类型；
• _Compare：指定排序顺序，默认选用升序std::less<_Key>，也可以选用std::greater<_Key> 或者自定义排序规则；
• _Alloc，默认选用二级内存分配器。

特别的，关联式容器（如map）的键值key都是不能修改的，只能通过：先手动删除键值对，再插入，这种间接的方式修改。

假设关联容器允许修改键值的，因为其底层是红黑树：

1. 首先需要删除该键，然后调节平衡
2. 再插入修改后的键值，再调节平衡

如此一来，严重破坏了红黑树的结构，导致iterator失效，不知道应该指向之前的位置，还是指向改变后的位置。所以STL中将关联式容器的迭代器设置成const，不允许修改迭代器的值。

auto map1 = std::map<int,std::string> { std::make_pair(1,"一"),std::make_pair(2,"二")};

map1.find("two")->first  = 0; // error，不允许修改

一个简单使用实例。

#include<map>
#include<utility>
#include<iostream>
#include<string>   

void printMap(const map<int,string>& m)
{
    std::cout<<"size = " << m.size() <<" : ";
    // 打印键值对
    for(auto iter = m.begin(); iter != m.end(); iter++)
    	std::cout<<"<key="<< iter->first <<", value=" << iter->second << "> "; 
    std::cout<<"\n";    
}

int main()
{
    // make_pair
    map<int,std::string> map1 { std::make_pair(1,"一"),std::make_pair(2,"二")};
    map1[1]; // "一"
    map1[2]; // "二"
   
    // 插入
    map1.emplace(std::make_pair(0,"零"));
    map1.emplace(std::make_pair(4,"四"));
    printMap(map1);
    
    // 删除
    map1.erase(3);
    map1.erase(4);
    printMap(map1);
}

在本例中，map初始化还可以简化为：

map<int,std::string> map1 { {1,"一"},{2,"二"}};

输出（注意打印出来的顺序按key升序打印的）：

[root@roy-cpp test]# ./test.out 
size = 4 : <key=0, value=零> <key=1, value=一> <key=2, value=二> <key=4, value=四> 
size = 3 : <key=0, value=零> <key=1, value=一> <key=2, value=二> 

成员函数

map具有众多的成员函数，方便我们对map进行各种操作。

我们先一睹为快。

• 迭代器相关

  同array、vector，deque、list。

  成员函数	功能
  begin()	返回指向容器中第一个元素的正向迭代器
  end()	返回指向容器最后一个元素之后一个位置的正向迭代器
  rbegin()	返回指向最后一个元素的反向迭代器
  rend()	返回指向第一个元素之前一个位置的反向迭代器
  cbegin()	和 begin() 功能相同，只不过其返回的迭代器类型为常量正向迭代器
  cend()	和 end() 功能相同，只不过其返回的迭代器类型为常量正向迭代器
  crbegin()	和 rbegin() 功能相同，只不过其返回的迭代器类型为常量反向迭代器
  crend()	和 rend() 功能相同，只不过其返回的迭代器类型为常量反向迭代器

  • 注意，如果是 const 类型容器，返回的一定是常量正向迭代器，常量迭代器不能修改指向的元素；
  • begin() 和 end() 为C++11新增，操作对象还可以是数组。

• 主要成员函数

  标粗部分是常用的函数。

  • 关联容器虽然底层也是双向迭代器，不是随机迭代器，一些随机迭代器才支持的方法，比如at(n)、[n]是不支持的，但支持按键值查找at(key)、[key]方法；
  • 关联容器不能在指定位置上删除、插入元素，所以STL没有提供push_back()、push_front()之类头尾操作方法，而是使用emplace() 或insert()。

  成员函数	功能
  empty()	若容器为空，则返回 true；否则 false
  size()	返回当前 map 容器中存有键值对的个数
  max_size()	返回 map 容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同
  operator[key]	map容器重载了 [] 运算符，获取指定键的值，查找失败添加新的键值对
  at(key)	找到 map 容器中 key 键对应的值，查找失败引发 out_of_range 异常
  insert()	向 map 容器中插入键值对，如果key重复会覆盖
  erase()	删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对
  swap()	交换 2 个 map 容器中存储的键值对，这意味着，操作的 2 个键值对的类型必须相同。
  clear()	清空 map 容器中所有的键值对，即使 map 容器的 size() 为 0
  emplace()	基本同insert，但相比insert效率更高
  count(key)	在当前 map 容器中，查找键为 key 的键值对的个数并返回。注意，由于 map 容器中各键值对的键的值是唯一的，因此该函数的返回值最大为 1。

  相比序列容器，关联容器独有的一些函数：

  成员函数	功能
  find(key)	在 map 容器中查找键为 key 的键值对，找到返回对应迭代器（和at、[]不同，不是返回value），如果没找到返回和 end() 方法一样的迭代器
  lower_bound(key)	返回一个指向当前 map 容器中第一个大于或等于 key 的键值对的双向迭代器，如果没找到返回和 end() 方法一样的迭代器
  upper_bound(key)	类似上，不过返回的是第一个大于 key的（不包含等于）

简单对比下operator[key] 和at(key) 这两种查询key的方式。

注意到，operator[key] 如果没查找到key，还会直接给map插入当前未查找到的key。

#include<map>
#include<string> 
#include<iostream>
  
int main()
{
    // 空map
    map<int,std::string> map1 { };

    // at(key)
    // map1.at(1); // error程序终止，抛出异常
    
    // [key]
    map1[1];
    std::cout<< map1.begin()->first <<"," << map1.begin()->second << std::endl;
}

编译器自动初始化了value：如果是基本数据类型，则值为 0；如果是 string 类型，其值为 “”，即空字符串。

输出：

[root@roy-cpp test]# ./test.out 
1,""

底层实现

本节我们主要探讨以下问题：

• map底层数据结构及实现？
• map底层迭代器如何定义？
• map底层如何插入、删除一个数据？

本节只做简单分析。

map底层数据结构及实现？

前面我们说过，map底层是红黑树，可以在map代码中验证：

template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class map
{
  public:
    typedef _Key    key_type;
    typedef _Tp     mapped_type;
    typedef std::pair<const _Key, _Tp>     value_type;
    ...
  private:
    typedef typename _Alloc::template rebind<value_type>::other _Pair_alloc_type;
    // 红黑树模板类
    typedef _Rb_tree<key_type, value_type, _Select1st<value_type>, key_compare, _Pair_alloc_type> _Rep_type;  
   /// The actual tree structure.
   _Rep_type _M_t; // map底层的红黑树 
    ...

具体展开就是对红黑树的分析了，大致了解到这就行。

map底层迭代器如何定义？

map中迭代器使用的是红黑中的迭代器：

typedef typename _Rep_type::iterator   iterator;

enum _Rb_tree_color { _S_red = false, _S_black = true };
struct _Rb_tree_node_base
  {
    typedef _Rb_tree_node_base* _Base_ptr;
    typedef const _Rb_tree_node_base* _Const_Base_ptr;

    _Rb_tree_color	_M_color;
    _Base_ptr		_M_parent;  // 父指针
    _Base_ptr		_M_left;    // 左指针
    _Base_ptr		_M_right;   // 右指针

map底层如何插入、删除一个数据？

主要是红黑树相关删除、插入操作。

multimap

multimap 容器具有和 map 极为相似的特性：

• multimap 容器的类模板也定义在<map>头文件；
• 也按键值对方式存储数据，底层也是红黑树结构；
• 会根据键值升序排序元素；
• 成员函数大部分相同；
• 键值无法修改；
• …

主要的不同体现在：

• multimap 可以同时存储多个键相同的键值对；
• multimap 除了find(key)，不能使用at(key) 或 operator[key] 等直接按key获取value的方式（很好理解，multimap会存在多个重复的键）。

multimap 也定义在 <map> 头文件，如下所示：

template <typename _Key, 
		  typename _Tp, 
		  typename _Compare = std::less<_Key>,
		  typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class multimap 

在 multimap <_Key,_Tp,_Compare,_Alloc> 模板中：

• _Key，指定键的类型；
• _Tp，指定值的类型；
• _Compare：指定排序顺序，默认选用升序std::less<_Key>，也可以选用std::greater<_Key> 或者自定义排序规则；
• _Alloc，默认选用二级内存分配器。

一个简单使用实例（使用起来和map很相似）。

#include<map>
#include<utility>
#include<iostream>
#include<string>   

void printMMap(const multimap<int,string>& m)
{
    std::cout<<"size = " << m.size() <<" : ";
    // 打印键值对
    for(auto iter = m.begin(); iter != m.end(); iter++)
        std::cout<<"<key="<< iter->first <<", value=" << iter->second << "> "; 
    std::cout<<"\n";    
}

int main()
{
    // make_pair
    multimap<int,std::string> mmap1 { std::make_pair(1,"一"),std::make_pair(1,"壹")}; // 键值相同，都是1
    // map1[1] = "one"; // error，无法修改键值

    // 插入
    mmap1.emplace(std::make_pair(0,"零"));
    mmap1.emplace(std::make_pair(4,"四"));
    printMMap(mmap1);
    
    // 删除
    mmap1.erase(3);
    mmap1.erase(4);
    printMMap(mmap1);
}

输出（自动排序）：

[root@roy-cpp test]# ./test.out 
size = 4 : <key=0, value=零> <key=1, value=一> <key=1, value=壹> <key=4, value=四> 
size = 3 : <key=0, value=零> <key=1, value=一> <key=1, value=壹> 

关于成员函数

multimap的成员函数，除了不能使用at(key)、operator[key] ，基本和map一致，故不单列了。

set

map和set都是以红黑树作为底层数据结构，所以外部表现的也极为相似：

• 不允许出现键值重复；
• 所有的元素都会被自动排序；
• 不能通过迭代器来改变set的值，因为set的值就是键（关联容器的键值不允许修改）；
• 成员函数极为类似；
• …

主要区别在于：

• set容器存储的键值对（key-value）的key、value完全相同。在底层实现上，map底层区别也主要是修改红黑树存储的key、value保存一致；
• set容器除了find(key)，不能使用at(key) 或 operator[key]获取value ，虽然在底层实现上set的key等于value，但是不允许获取value。

对于第一个区别，我们查看set容器底层实现：

template<typename _Key, typename _Compare = std::less<_Key>,
typename _Alloc = std::allocator<_Key> >
class set
{
     ...
  public:
      typedef _Key     key_type;  
      typedef _Key     value_type; // 和key_type一样
     ...

  private:
      typedef typename _Alloc::template rebind<_Key>::other _Key_alloc_type;
      // 和map几乎一致
      // 唯一区别在于红黑树类模板参数key_type和value_type其实是一样的
      // 初始化时它们的值也一样
      typedef _Rb_tree<key_type, value_type, _Identity<value_type>,
		       key_compare, _Key_alloc_type> _Rep_type;
     _Rep_type _M_t;  // Red-black tree representing set.

可以看到，底层实现上key、value的类型、值都会被设置为一样。set 容器类模板的定义中，也仅提供第 1 个参数（_Key）用于设定存储数据的类型。

set 容器以类模板形式定义在 <set> 头文件，如下所示：

template<typename _Key, 
		 typename _Compare = std::less<_Key>,
         typename _Alloc = std::allocator<_Key> >loc = std::allocator<std::pair<const _Key, _Tp> > >
class set

在 set<_Key,_Compare,_Alloc> 模板中：

• _Key，指定键的类型；
• _Compare：指定排序顺序，默认选用升序std::less<_Key>，也可以选用std::greater<_Key> 或者自定义排序规则；
• _Alloc，默认选用二级内存分配器。

一个简单使用实例。

#include<set>
#include<utility>
#include<iostream>
#include<string>   

void printSet(const set<int>& s)
{
    std::cout<<"size = " << s.size() <<" : ";
    // 打印set键值
    for(auto iter = s.begin(); iter != s.end(); iter++)
    	std::cout<<"key="<<*iter<< " ";  //  iter->first set不允许使用
    std::cout<<"\n";    
}

int main()
{
    // 初始化
    set<int> set1 { 1,2,3,4 }; // 键值不能相同
    // set1[1];  // error，不能使用[key]或at(key)

    // 插入
    set1.emplace(0);
    set1.emplace(4);
    printSet(set1);
    
    // 删除
    set1.erase(3);
    set1.erase(4);
    printSet(set1);
}

输出：

[root@roy-cpp test]# ./test.out 
size = 5 : key=0 key=1 key=2 key=3 key=4 
size = 3 : key=0 key=1 key=2 

关于成员函数

set、multimap的成员函数，除了不能使用at(key)、operator[key] ，基本和map一致（底层实现上就非常相似），故不单列了。

multiset

multiset和map的主要区别在于：

• multiset可以存储相同的键值；

• multiset键值对相同；

• 除了map/unordered_map，multiset和set、multimap一样，也不能使用at(key) 或 operator[key]，但可以使用find(key) 。

multiset 也定义在 <set> 头文件，如下所示：

template <typename _Key,
		  typename _Compare = std::less<_Key>,
		  typename _Alloc = std::allocator<_Key> >
class multiset

在 multiset<_Key,_Compare,_Alloc> 模板中：

• _Key，指定键的类型；
• _Compare：指定排序顺序，默认选用升序std::less<_Key>，也可以选用std::greater<_Key> 或者自定义排序规则；
• _Alloc，默认选用二级内存分配器。

一个简单使用实例（使用起来和set很相似）。

#include<set>
#include<utility>
#include<iostream>
#include<string>   

void printMSet(const multiset<int>& ms)
{
    std::cout<<"size = " << ms.size() <<" : ";
    for(auto iter = ms.begin(); iter != ms.end(); iter++)
    	std::cout<<"key="<<*iter<< " ";  //  iter->first ，set、multiset不允许使用
    std::cout<<"\n";    
}

int main()
{
    // make_pair
    multiset<int> mset1 { 1,1,2,3 }; // 存在键值相同
    // mset1[1];  // error，不能使用[key]或at(key)
    
    // 插入
    mset1.emplace(0);
    mset1.emplace(4);
    printMSet(mset1);
    
    // 删除
    mset1.erase(3);
    mset1.erase(4);
    printMSet(mset1);
}

输出（自动排序）：

[root@roy-cpp test]# ./test.out 
size = 6 : key=0 key=1 key=1 key=2 key=3 key=4 
size = 4 : key=0 key=1 key=1 key=2 

关于成员函数

multimap、set、multiset的成员函数，除了不能使用at(key)、operator[key] ，基本和map一致（底层实现上就非常相似），故不单列了。

9.2.3 无序关联式容器

本节主要介绍以下容器：

容器	底层数据结构	特点	迭代器类型
unordered_map	哈希表，下同	键必须唯一，会根据键大小默认升序排序	前向迭代器，下同
unordered_multimap		基本同前，但unordered_multimap键可重复
unordered_set		键和值完全相同，键依旧唯一，默认升序
unordered_multiset		基本同前，但unordered_multiset键可重复

正如名字“unordered”所暗示的，这些关联式容器是无序的，它们不会像之前的map/set/multimap/multiset/等关联容器一样，自动按键值大小对存储的键值对进行排序。

为什么无序关联容器不会自动排序了？

这是因为“unordered”版本的关联式容器底层数据结构采用的是哈希表 而不是红黑树 ，哈希表结构不适合插入元素时进行排序。

哈希表（Hash table）是根据关键码值(Key value)而直接进行访问的数据结构。

例如， std::unordered_map在内存中的哈希表形式结构：

直观上来看：

• 哈希表是一个buckets数组（C++中使用vector实现）；
• 每个bucket是一个指针，指向它外挂的键值对链表（有时候我们用“bucket”指代外挂的链表）。

在哈希表查找指定key的value大致过程如下：

以 std::unordered_map 中 [key] 或 at(key) 查找过程为例。

1. 使用hash(key)函数进行哈希映射，得到一个key对应的哈希值；
2. 将哈希值和桶数量n 做哈希值 % n运算，元素结果即bucket的编号（下标），由此定位到具体的bucket上；
3. 遍历查找定位的bucket外挂的键值对链表，如果找到key返回对应value（find(key)方法返回对应迭代器），如果没找到抛出异常（find(key)方法返回迭代器unordered_map::end()）。

为什么要重新设计哈希表作为底层结构？

这涉及到红黑树和哈希表的数据结构特性：

• 查找、修改效率上：哈希表更快（哈希映射查找），常数级别O(1)，但哈希碰撞严重最坏O(n)；红黑树更慢（二叉树二分查找），但稳定O(logn)级别；
• 插入、删除效率上：哈希表更快，常数级别O(1)，红黑树更慢，但稳定O(logn)。

所以，选择哈希表作为底层结构的无序容器，增删查改效率通常是更好的。一般建议选择无序关联容器，除非你真的需要key有序。

unordered_map

unordered_map 容器和 map 容器一样：

• 以键值对（pair类型）的形式存储数据；
• 存储的各个键值对的键互不相同且不允许被修改。

但由于 unordered_map 容器底层采用的是哈希表存储结构，该结构本身不具有对数据的排序功能，所以此容器内部不会自行对存储的键值对进行排序。

unordered_map 容器以类模板形式定义在 <unordered_map> 头文件，如下所示：

template<class _Key, class _Tp,
	     class _Hash = hash<_Key>,
	     class _Pred = std::equal_to<_Key>,
	     class _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
class unordered_map : __check_copy_constructible<_Alloc>

在 unordered_map<_Key,_Tp,_Hash,_Pred,_Alloc> 模板中：

• _Key，指定键的类型；
• _Tp，指定值的类型；
• _Hash：指定要使用的哈希函数，默认选用hash<_Key>，不过默认哈希函数只适用于基本数据类型（包括 string 类型），而不适用于自定义的结构体或者类；
• _Pred：unordered_map不允许键值相等，而判断是否相等的规则，就由此参数指定；
• _Alloc，默认选用二级内存分配器。

使用简单举例。

和map的提供的上层函数接口基本一致，如emplace() 插入元素等。

#include<unordered_map>
#include<utility>
#include<iostream>
#include<string> 

void printUMap(const unordered_map<int,string>& m)
{
    std::cout<<"size = " << m.size() <<" : ";
    // 打印键值对
    for(auto iter = m.begin(); iter != m.end(); iter++)
    	std::cout<<"<key="<< iter->first <<", value=" << iter->second << "> "; 
    std::cout<<"\n";    
}
int main()
{
    unordered_map<int,std::string> umap1 { {1,"一"},{2,"二"}};
    umap1[1]; // "一"
    umap1[2]; // "二"
    // 插入
    umap1.emplace(std::make_pair(0,"零"));
    umap1.emplace(std::make_pair(4,"四"));
    printUMap(umap1);
    
    // 删除
    umap1.erase(3);
    umap1.erase(4);
    printUMap(umap1);
}

输出（未排序）：

[root@roy-cpp test]# ./test.out 
size = 4 : <key=4, value=四> <key=0, value=零> <key=2, value=二> <key=1, value=一> 
size = 3 : <key=0, value=零> <key=2, value=二> <key=1, value=一> 

成员函数

unordered_map 既可以看做是关联式容器，更属于自成一脉的无序容器。所以其成员函数可分为：

• 迭代器相关
• 基本方法
• 无序容器独有方法

我们先一睹为快。

• 迭代器相关

  无序容器只有前向迭代器，尾部操作相关迭代器和函数都没有。

  成员函数	功能
  begin()	返回指向容器中第一个元素的正向迭代器
  end()	返回指向容器最后一个元素之后一个位置的正向迭代器
  cbegin()	和 begin() 功能相同，只不过其返回的迭代器类型为常量正向迭代器
  cend()	和 end() 功能相同，只不过其返回的迭代器类型为常量正向迭代器

  • 注意，如果是 const 类型容器，返回的一定是常量正向迭代器，常量迭代器不能修改指向的元素；
  • begin() 和 end() 为C++11新增，操作对象还可以是数组。

• 基本方法（基本同map）

  标粗部分是常用的函数。

  • 无序关联容器虽然底层不是随机迭代器，一些随机迭代器才支持的方法，比如at(n)、[n]是不支持的，但支持按键值查找at(key)、[key]方法；
  • 关联容器不能在指定位置上删除、插入元素，所以STL没有提供push_back()、push_front()之类头尾操作方法，而是使用emplace() 或insert()。

  成员函数	功能
  empty()	若容器为空，则返回 true；否则 false
  size()	返回当前 unordered_map容器中存有键值对的个数
  max_size()	返回 unordered_map容器所能容纳键值对的最大个数，不同的操作系统，其返回值亦不相同
  operator[key]	map容器重载了 [] 运算符，获取指定键的值，查找失败添加新的键值对
  at(key)	找到 map 容器中 key 键对应的值，查找失败引发 out_of_range 异常
  insert()	向 map 容器中插入键值对，如果key重复会覆盖
  erase()	删除 map 容器指定位置、指定键（key）值或者指定区域内的键值对
  swap()	交换 2 个 map 容器中存储的键值对，这意味着，操作的 2 个键值对的类型必须相同。
  clear()	清空 map 容器中所有的键值对，即使 map 容器的 size() 为 0
  emplace()	基本同insert，但相比insert效率更高
  count(key)	在当前 map 容器中，查找键为 key 的键值对的个数并返回。注意，由于 map 容器中各键值对的键的值是唯一的，因此该函数的返回值最大为 1。

• 无序容器独有方法

  相比序列容器、有序容器，无序容器独有的一些哈希表相关方法：

  成员函数	功能
  bucket_count()	返回当前桶数量（一个线性链表代表一个桶）
  max_bucket_count()	返回最多可以使用多少桶
  bucket_size(n)	返回第 n 个桶中存储键值对的数量
  bucket(key)	返回以 key为键的键值对所在桶的编号
  load_factor()	返回 unordered_map 容器中当前的负载因子，即负载因子 = 容器存储的总键值对 / 桶数 ， load_factor() = size() / bucket_count()
  max_load_factor()	返回或者设置当前 unordered_map 容器的负载因子
  rehash(n)	将当前容器底层使用桶的数量设置为 n
  reserve()	将存储桶的数量（也就是 bucket_count() 方法的返回值）设置为至少容纳count个键值对（不超过最大负载因子）所需的数量，并重新整理容器
  hash_function()	返回当前容器使用的哈希函数对象

对于无序容器的独有方法进行测试。

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

void printUmapInfo(const unordered_map<string, string>& umap)
{  
    cout << "umap 初始桶数: " << umap.bucket_count() << endl;
    cout << "umap 最大可使用桶数: " << umap.max_bucket_count() << endl;
    cout << "umap 当前存在的键值对: " << umap.size() << endl;
    cout << "umap 初始负载因子: " << umap.load_factor() << endl;
    cout << "umap 最大负载因子: " << umap.max_load_factor() << endl;
    cout << "—————————————————————————————————————"  << endl;
}

int main()
{
    // 创建空 umap 容器
    unordered_map<string, string> umap;

    // 设置 umap 使用最适合存储 9 个键值对的桶数
    umap.reserve(9);
    printUmapInfo(umap);

    // 向 umap 容器添加 3 个键值对
    umap["name"] = "royhuang";
    umap["age"] = "25";
    umap["university"] = "chongqingU";
    printUmapInfo(umap);
    // 调用 bucket() 获取指定键值对位于桶的编号
    cout << "“age”存储在第：" << umap.bucket("age") <<"个桶"<< endl;

    // 自行计算某键值对位于哪个桶
    auto fn = umap.hash_function();
    cout << "hash(age)%n，计算“age”存储在第：" << fn("age") % (umap.bucket_count())  <<"个桶"<< endl;
    return 0;
}

输出：

[root@roy-cpp test]# ./test.out 
umap 初始桶数: 11
umap 最大可使用桶数: 576460752303423487
umap 当前存在的键值对: 0
umap 初始负载因子: 0
umap 最大负载因子: 1
—————————————————————————————————————
umap 初始桶数: 11
umap 最大可使用桶数: 576460752303423487
umap 当前存在的键值对: 3
umap 初始负载因子: 0.272727
umap 最大负载因子: 1
—————————————————————————————————————
“age”存储在第：5个桶
hash(age)%n，计算“age”存储在第：5个桶

底层实现

unordered_map底层实现主要就是哈希表：

具体逻辑暂略。

unordered_multimap

回忆map和multimap的区别：

map和multimap主要的不同体现在：

• multimap 可以同时存储多个键相同的键值对；
• multimap 除了find(key)，不能使用at(key) 或 operator[key] 等直接按key获取value的方式（很好理解，multimap会存在多个重复的键）。

multimap 也定义在 <map> 头文件，…

unordered_map和unordered_multimap的区别同上：

• unordered_multimap可以同时存储多个键相同的键值对；

• unordered_multimap除了find(key)，不能使用at(key) 或 operator[key] 等直接按key获取value的方式 。

unordered_multimap也定义在 <unordered_map> 头文件中，使用起来基本和unordered_map没差，不再重复介绍了。

unordered_set

回忆set和map的区别：

主要区别在于：

• set容器存储的键值对（key-value）的key、value完全相同。在底层实现上，map底层区别也主要是修改红黑树存储的key、value保存一致 ;
• set容器除了find(key)，不能使用at(key) 或 operator[key]获取value ，虽然在底层实现上set的key等于value，但是不允许获取value。

unordered_set和unordered_map的区别同上。

unordered_multiset

回忆multiset和map的区别：

multiset和map的主要区别在于：

• multiset可以存储相同的键值；

• multiset键值对相同；

• 除了map/unordered_map，multiset和set、multimap一样，也不能使用at(key) 或 operator[key]，但可以使用find(key) 。

unordered_map和unordered_multiset的区别同上。

9.2.4 容器适配器

本节主要介绍以下容器：

容器	底层数据结构	特点	迭代器类型
stack	（默认）deque	元素“先进后出”	无
queue	（默认）deque	元素“先进先出”	无
priority_queue	（默认）vector	元素“先进优先级高先出”	无

或许你和第一次接触“容器适配器”这个名词的我，都会感到纳闷：这词听起来有些古怪，它是什么意思呢？它也是容器吗？

“容器适配器”是什么意思？

在栈（stack）这种数据结构中，必须要满足“先进后出”这种特性。而我们之前的容器，如deque、list都无法满足这种特性。

但我们可以，比如对基础容器deque，进行一层封装：禁止头部进出只允许尾部进出，这样就适配了栈“先进后出”的特性。这种通过，封装某个序列式容器，并重新组合该容器中包含的成员函数来实现“需要的特性”的容器（必要时也可以自创新函数），就称为容器适配器。

所以，容器适配器自然也是容器。特别的，STL中的容器适配器，基础容器并不是固定的，还允许我们选择满足条件的基础容器。采用的底层基础容器不同，其执行效率也不尽相同，一般来说使用默认的就行。

stack

stack 栈适配器是一种单端开口的容器，该容器模拟的就是栈存储结构，只能在栈顶插入、删除。

下图展示了stack的简单使用。

stack 容器以类模板的形式定义在 <stack> 头文件，如下所示：

template<typename _Tp, typename _Sequence = deque<_Tp> >
class stack

在 stack<_Tp,_Sequence> 模板中：

• _Tp，用于指明容器中元素数据类型；
• _Sequence，指定底层使用的基础容器。

简单使用实例。

在这个例子中，我们没有使用默认的deque作为基础容器，而是使用list。

#include <iostream>
#include <stack>
#include <list>
using namespace std;
int main()
{
    // 构建 stack 容器适配器
    list<int> values{ 1, 2, 3 };  // 基础容器list
    stack<int, list<int>> my_stack(values);

    // 查看 my_stack 存储元素的个数
    cout << "size of my_stack: " << my_stack.size() << endl;
    my_stack.push(4);
    cout << "size of my_stack: " << my_stack.size() << endl;

    // 将 my_stack 中存储的元素依次弹栈，直到其为空
    while (!my_stack.empty())
    {  
        cout << my_stack.top() << endl;
        my_stack.pop();  // 将栈顶元素弹栈
    }
    return 0;
}

底层实现

stack底层就是封装了基础容器。

template<typename _Tp, typename _Sequence = deque<_Tp> >
class stack
{
	...
    protected:
    //  See queue::c for notes on this name.
    _Sequence c;  // 底层基础容器，模板参数指定
    ...

查看经典的stack::push()、stack::pop() 实现：

push(const value_type& __x)  // 引用
{ 
	c.push_back(std::move(__x));  // 就是基础容器的push_back方法
}

push(value_type&& __x)  // 右值引用
{ 
	c.push_back(std::move(__x)); 
}

pop()
{
	__glibcxx_requires_nonempty();
	c.pop_back();  // 基础容器的pop_back方法
}

确实主要还是借助基础容器的成员和方法实现。

成员函数

相比其它序列或关联式容器，stack 是一类存储机制简单、提供成员函数较少的容器。

• 特别的，容器适配器都没有迭代器，所以遍历元素：只能不断移除元素，去访问下一个元素。

成员函数	功能
empty()	当 stack 栈中没有元素时，该成员函数返回 true；反之，返回 false
size()	返回 stack 栈中存储元素的个数
top()	返回一个栈顶元素的引用，类型为 T&，如果栈为空，程序会报错。
push(const T& val)	先复制 val，再将 val 副本压入栈顶，这是通过调用底层容器的 push_back() 函数完成的
push(T&& obj)	以移动元素的方式将其压入栈顶，这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
pop()	弹出栈顶元素
emplace(arg…)	arg… 可以是一个参数，也可以是多个参数，但它们都只用于构造一个对象，并在栈顶直接生成该对象，作为新的栈顶元素
swap(stack & other_stack)	将两个 stack 适配器中的元素进行互换，需要注意的是，进行互换的 2 个 stack 适配器中存储的元素类型以及底层采用的基础容器类型，都必须相同

queue

和 stack 栈容器适配器不同，queue 容器适配器有 2 个开口，一个开口（尾部）专门用来加入元素，另一个开头（头部）专门用来移除元素。

这种存储结构最大的特点是，最先进入 queue 的元素，也可以最先从 queue 中出来，即“先进先出”。

下图展示了queue这种结构。

stack 容器以类模板的形式定义在 <stack> 头文件，如下所示：

template<typename _Tp, typename _Sequence = deque<_Tp> >
class stack

在 stack<_Tp,_Sequence> 模板中：

• _Tp，用于指明容器中元素数据类型；
• _Sequence，指定底层使用的基础容器。

简单使用实例。

#include <iostream>
#include <queue>
#include <list>
using namespace std;
int main()
{
    // 构建 stack 容器适配器
    list<int> values{ 1, 2, 3 };  // 基础容器list
    queue<int, list<int>> my_queue(values);

    // 查看 my_stack 存储元素的个数
    cout << "size of my_queue: " << my_queue.size() << endl;
    my_queue.push(4);
    cout << "size of my_queue: " << my_queue.size() << endl;

    // 将 my_stack 中存储的元素依次弹栈，直到其为空
    while (!my_queue.empty())
    {  
        cout << my_queue.front() << endl;
        //将栈顶元素弹栈
        my_queue.pop();
    }
    return 0;
}

输出：

[root@roy-cpp test]# ./test.out 
size of my_queue: 3
size of my_queue: 4
1
2
3
4

底层实现

同stack，queue底层就是封装了基础容器。

template<typename _Tp, typename _Sequence = deque<_Tp> >
class queue
{
	...
    protected:
    //  See queue::c for notes on this name.
    _Sequence c;  // 底层基础容器，模板参数指定
    ...

queue::push、queue::pop方法实现：

push(const value_type& __x)  // 引用
{ 
	c.push_back(std::move(__x));  // 就是基础容器的push_back方法
}

push(value_type&& __x)  // 右值引用
{ 
	c.push_back(std::move(__x)); 
}

pop()
{
	__glibcxx_requires_nonempty();
	c.pop_front();  // 基础容器的pop_front方法，stack这里是pop_back，所以是尾部弹出
}

成员函数

queue 容器适配器拥有stack 成员函数基本所有函数（除了top()、emplace()）。

• 特别的，容器适配器都没有迭代器，所以遍历元素：只能不断移除元素，去访问下一个元素。

成员函数	功能
empty()	当 queue中没有元素时，该成员函数返回 true；反之，返回 false
size()	返回 queue中存储元素的个数
top()	queue没有
push(const T& val)	先复制 val，再将 val 副本压入队尾，这是通过调用底层容器的 push_back() 函数完成的
push(T&& obj)	以移动元素的方式将其压入队尾，这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
pop()	弹出队头（第一个）元素
emplace(arg…)	queue没有
swap(queue & other_stack)	将两个 queue适配器中的元素进行互换，需要注意的是，进行互换的 2 个 queue适配器中存储的元素类型以及底层采用的基础容器类型，都必须相同

queue 独有的函数：

成员函数	功能
front()	返回 queue 中第一个元素的引用
back()	返回 queue 中最后一个元素的引用

priority_queue

priority_queue 容器适配器中元素的进出，遵循“先进优先级高的先出”原则。

那priority_queue 中元素优先级是如何评定？

每个 priority_queue 容器适配器在创建时，都制定了一种“排序规则”。根据此规则，该容器适配器中存储的元素就有了优先级高低之分。

比如这种“排序规则”，可以是：元素值从大到小或从小到大。

priority_queue中元素进出和queue有些不同：

• 进：不直接插到队尾，找到优先级最高的元素，并将其移动到队列的队头；
• 出：直接移出队头，然后找到当前优先级最高的元素，并将其移动到队头。

优先队列可以使用数组、二叉搜索树、链表和堆数据结构来实现。但是，最好的选择是堆数据结构，因为它有助于相对更快、更有效地实现优先级队列。

priority_queue容器以类模板的形式定义在 <queue> 头文件，如下所示：

 template<typename _Tp, 
		  typename _Sequence = vector<_Tp>,
	      typename _Compare  = less<typename_Sequence::value_type> >
class priority_queue

在 priority_queue<_Tp,_Sequence,_Compare> 模板中：

• _Tp，用于指明容器中元素数据类型；
• _Sequence，指定底层使用的基础容器；
• _Compare ，指定排序规则。

简单使用例子。

注意priority_queue的初始化有些不同。

#include <iostream>
#include <queue>
#include <deque>
#include <list>
using namespace std;
int main()
{
    // 构建 stack 容器适配器
    deque<int> values{ 5, 1, 3};  // 此时是无序的list
    // priority_queue<int, deque<int>> my_priority_queue(values); // error,不能使用这种方式初始化
    priority_queue<int, deque<int>> my_priority_queue{values.begin(),values.end()} ; // 初始化指定两个迭代器

    // 查看 my_priority_queue 存储元素的个数
    cout << "size of my_priority_queue: " << my_priority_queue.size() << endl;
    my_priority_queue.push(4);
    cout << "size of my_priority_queue: " << my_priority_queue.size() << endl;

    // 将 my_stack 中存储的元素依次弹栈，直到其为空
    while (!my_priority_queue.empty())
    {  
        cout << my_priority_queue.top() << endl; // 输出有序
        // 队头元素（最高优先级出栈）
        my_priority_queue.pop();
    }
    return 0;
}

输出（有序）：

[root@roy-cpp test]# ./test.out 
size of my_priority_queue: 3
size of my_priority_queue: 4
5
4
3
1

成员函数

priority_queue 拥有的成员函数和tack更像（基本一致）：

• 有top() 方法，没有queue独有的front() 或back() 方法；

• 特别的，容器适配器都没有迭代器，所以遍历元素：只能不断移除元素，去访问下一个元素。

成员函数	功能
empty()	当 stack 栈中没有元素时，该成员函数返回 true；反之，返回 false
size()	返回 stack 栈中存储元素的个数
top()	返回一个栈顶元素的引用，类型为 T&，如果栈为空，程序会报错。
push(const T& val)	先复制 val，再将 val 副本压入栈顶，这是通过调用底层容器的 push_back() 函数完成的
push(T&& obj)	以移动元素的方式将其压入栈顶，这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
pop()	弹出栈顶元素
emplace(arg…)	arg… 可以是一个参数，也可以是多个参数，但它们都只用于构造一个对象，并在栈顶直接生成该对象，作为新的栈顶元素
swap(stack & other_stack)	将两个 stack 适配器中的元素进行互换，需要注意的是，进行互换的 2 个 stack 适配器中存储的元素类型以及底层采用的基础容器类型，都必须相同

9.2.5 容器最佳实践

在本节我们从基本使用、底层实现、常用函数等方面介绍了众多容器，它们可分为：

1. 序列式容器：array、vector、deque、list 和 forward_list；
2. 关联式容器：map、multimap、set 和 multiset；
3. 无序关联式容器：unordered_map、unordered_multimap、unordered_set 和 unordered_multiset；
4. 容器适配器：stack、queue 和 priority_queue。

这么多容器，实际编码该选择哪一个呢？

回忆各个数据结构的特点。

	特点	对应容器	对应迭代器
数组	查找效率高且可随机查找、（除尾部）插入删除效率低	array/vector/deque	随机迭代器
链表	空间利用率高，插入删除效率高，查找较数组低	list/forwar_list	双向或前向迭代器
红黑树	在STL中存储键值对，增删查改效率均高，还会排序	map/set/…	双向迭代器
哈希表	在STL中存储键值对，不会排序，但比红黑树效率更高	unordered_map/ unordered_set/…	前向迭代器

首先，一般来说除非需要键值有序，在无序关联式容器/关联式容器中，优先考虑无序关联式容器。现在，我们再从时间效率角度 出发考虑各种容器的选择：

• 如果查找元素效率要求高 ：选择unordered_map/unordered_set或array/vector/deque
  • 如果数据可按键值对存储：选择unordered_map/unordered_set，O(1)常数级别查找键值；
  • 如果只能顺序存储 ：选择array/vector/deque
    • 如果存储的是静态数据：选array；
    • 如果存储的是动态数据：只在尾部增、删选vector；头、尾均需要增、删选deque。
• 如果插入、删除效率要求高：
  • 如果插入、删除位置有要求 ：list/forwar_list
    • 如果只在头部插入、删除数据：选forwar_list；
    • 如果头、尾均需插入、删除数据：选list。
  • 如果插入、删除位置没要求：选择unordered_map/unordered_set，O(lgn)级别复杂度。

至于stack、queue 和 priority_queue则一般是在你需要：“先进后出”、“先进先出”或“按优先级别出队”，这种特殊情况才考虑。

9.3 算法

STL提供了许多算法，供我们来对容器（或数组）中数据进行操作，通常可分两类：

• 会改变它们所应用的序列的算法
• 不改变它们所应用的序列的算法

可通过引入于<algorithm>头文件来使用：

#include <algorithm>

不过在本文中，主要还是按算法功能来进行介绍。而且本文不会对各种算法进行具体介绍，通常只是对常用算法进行简单概况。

为什么不详细介绍各类算法？

主要原因如下：

• 本文已经足够长（~3W字），每个算法详细介绍的话，篇幅长度难以估计把控；
• 一般情况下我们只需对大致函数功能有所了解就行，实际编码可查看具体的API接口，再深入理解即可。

另外，作者在实际工作中如果对一些算法有“踩坑和理解”，还会补充到本文中。

9.3.1 sort

C++ STL 标准库提供很多实用的排序函数，通过调用它们，我们可以很轻松地实现对普通数组或者容器中指定范围内的元素进行排序。

函数名	用法
sort (first, last)	对容器或普通数组中 [first, last) 范围内的元素进行排序，默认进行升序排序
stable_sort (first, last)	和 sort() 函数功能相似，不同之处在于，对于 [first, last) 范围内值相同的元素，该函数不会改变它们的相对位置
partial_sort (first, middle, last)	从 [first,last) 范围内，筛选出 muddle-first 个最小的元素并排序存放在 [first，middle) 区间中
partial_sort_copy (first, last, result_first, result_last)	从 [first, last) 范围内筛选出 result_last-result_first 个元素排序并存储到 [result_first, result_last) 指定的范围中
is_sorted (first, last)	检测 [first, last) 范围内是否已经排好序，默认检测是否按升序排序
is_sorted_until (first, last)	和 is_sorted() 函数功能类似，唯一的区别在于，如果 [first, last) 范围的元素没有排好序，则该函数会返回一个指向首个不遵循排序规则的元素的迭代器

9.3.2 merge

有些场景中，我们需要将 2 个有序序列合并为 1 个有序序列，这时就可以借助 merge() 实现。

函数名	用法
merge (first1, last1, first2, last2, result)	first1、last1、first2 以及 last2 都为输入迭代器，[first1, last1) 和 [first2, last2) 各用来指定一个有序序列；result 为输出迭代器，指定存储位置
merge (first1, last1, first2, last2, result, comp)	同上，不过多了comp 用于自定义排序规则

举例：

#include <iostream>     // std::cout
#include <algorithm>    // std::merge
#include <vector>       // std::vector
using namespace std;
int main()
{
    // first 和 second 数组中各存有 1 个有序序列
    int first[] = { 5,10,15,20,25 };
    int second[] = { 7,17,27,37,47,57 };
    // 用于存储新的有序序列
    vector<int> myvector(11);
    // 将 [first,first+5) 和 [second,second+6) 合并为 1 个有序序列，并存储到 myvector 容器中
    merge(first, first + 5, second, second + 6, myvector.begin());
    return 0;
}

9.3.3 find

find() 函数本质上是一个模板函数，用于在指定范围内查找和目标元素值相等的第一个元素。

函数名	用法
find(first, last, const T& val)	该函数会返回一个输入迭代器，first 和 last 为输入迭代器，[first, last) 用于指定该函数的查找范围；val 为要查找的目标元素。

其它的“find”函数：

• find_if() 或 find_not_if()， 和find唯一不同的是，前者需要明确指定要查找的元素的值，而后者则允许自定义查找规则；
• find_end() 或 search()，用于在序列 A 中查找序列 B， 最后一次或第一次出现的位置；
• find_first_of()：在 A 序列中查找和 B 序列中，和B中任意元素相匹配的第一个元素。

举例：

#include <iostream>     // std::cout
#include <algorithm>    // std::find
#include <vector>       // std::vector
using namespace std;
int main() 
{
    // find() 函数作用于普通数组
    char stl[] ="royhuang";
    // 调用 find() 查找第一个字符 'r'
    char * p = find(stl, stl + strlen(stl), 'r');
    // 判断是否查找成功
    if (p != stl + strlen(stl)) 
        cout << p << endl;
    
    // find() 函数作用于容器
    std::vector<int> myvector{ 10,20,30,40,50 };
    std::vector<int>::iterator it;
    it = find(myvector.begin(), myvector.end(), 30);
    if (it != myvector.end())
        cout << "查找成功：" << *it;
    return 0;
}

9.3.4 reverse

reverse函数可以反转一个容器中的元素。

函数名	用法
reverse(_first, last)	reverse函数反转的范围是[first,last)，不包括last指向的元素

简单实例。

#include <iostream>    
#include <algorithm>   
#include <vector>      
 
int main () 
{
    std::vector<int> myvector {1,2,3,4,5};
    std::reverse(myvector.begin(),myvector.end());    // 5 4 3 2 1
    return 0;
}

9.3.5 copy_n

copy_n() 算法，可以从源容器复制指定个数的元素到目标容器中。

函数名	用法
copy_n(source_first, size, target_start)	source_first 是指向源容器的起始位置的迭代器，size是要复制的元素总数， target_start是目标容器的开始迭代器

简单实例。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main()
{
    int arr[] = { 10, 20, 30, 40, 50 };
    vector<int> v1(5);
    // 复制arr中5个元素到v1中
    copy_n(arr, 5, v1.begin());
 
    return 0;
}

9.3.6 fill和fill_n

fill() 和 fill_n() 算法提供了一种为元素序列填入指定值的简单方式，fill() 会填充整个序列； fill_n() 则以给定的迭代器为起始位置，为指定个数的元素设置值。

函数名	用法
fill(first, last, value)	给容器在位置[first,last)，填充指定值value
fill_n(first, 10, value)	从指定位置first开始，填充n个value

9.4 总结

本文是《C++从零开始之C++篇》最后一篇博客，因此除了STL总结部分，还特意补充了《C++篇》的总结。

9.4.1 STL总结

在这篇博客中，作者主要从：STL迭代器、STL容器、STL算法对STL进行了全面介绍，其中STL容器是重点阐述内容。

• 迭代器：本质是指针的一层封装，具体实现为模板类，每个容器都有自己的迭代器类。迭代器主要功能是，提供了统一访问各种容器的方式，同时也使得算法和容器得于解耦，必要时可以作为“粘合剂”将二者联系起来。
• 容器：容器用来组织存储数据，具体实现也是模板类，本质是对数组、链表、红黑树、哈希表等基本数据结构的封装。最后作者还对实践中各种容器的选择，进行了简单总结。
• 算法：STL中提供了大量的算法供我们使用，具体实现是模板函数。理论上如果能使用STL中算法就尽量使用，本文主要对：sort、merge、find、reverse、copy_n、fill等常用算法进行了简略介绍。

不过在本文成型中，也发现了一些不足：

• 博文过长~3W字，放在一篇文章中显得过长，不利于阅读；
• 作者水平有限，对STL底层分析及STL算法等尚缺乏相关知识或经验，写作中难免部分描述不清。

针对上述问题或未发现的一些问题，后期作者会尽量进行完善，并将更新记录同步在文后。

9.4.2 C++总结

在重庆今天这个让人有点昏昏欲睡的下午，STL篇终于完结，不禁舒了一口气，长达2.7w的总结既是《C++篇》最后一篇博客，也应该是目前我写的最长的一篇博客。

也终于可以回过神来，做一个小结。

时间回到~3个月前，大约是11.20号，也就是9月结束找工作痛快玩了2个月后，我感到空虚过于无所事事，开始折腾起了自己的网站。在个人网站总结完自己实习和秋招笔记后，也萌发了学习C++的想法——主要是想到自己在腾讯实习从Java转到C++的痛苦经历，就还是在工作前提前学习一遍C++吧（菜是原罪）。

于是便有了《C++从零开始》 这个系列。

这是我第一次尝试写框架这么大的系列文章（光C++篇已经~13W+字），整个系列完成估计至少有40W字。当然字数多少并不重要，在这个过程中学习到很多，比如明确了一个很重要的原则：“写的文章不是给自己看的笔记，而是给别人看的博客”。秉着这个原则，每篇博客写完，我都会代入一个“旁观者”视角，自己读几遍，看逻辑是否清晰、文章是否有错误等。所以，每篇博客甚至整个系列其实一直在完善中。但限于自己的水平，错误和描述不清晰的地方依旧不少，比如每次我自己重读时依旧能发现（好消息是越来越少了）。

whatever，相信不断进步&完善，总能达到满意的效果。

《C++从零开始》 接下来将主要专注于Linux/C++开发方面的知识，所以接下来的内容分为两大篇章：

• 《C++从零开始之Linux/C++系统编程》
• 《C++从零开始之网络编程》

和《C++从零开始之C++》互为《C++从零开始》的三部曲。

敬请期待！

更新记录

2022-02-19：更新笔记

1. 第一次更新

参考资料

---

1. 1.嗨课网-STL教程：https://haicoder.net/stl/stl-data-structure.html ↩
2. 2.迭代器（iterator）和指针（pointer）区别在哪？https://www.zhihu.com/question/54047747 ↩
3. 3.STL 源码剖析：https://www.kancloud.cn/digest/stl-sources/ ↩
4. 4.C++ STL: 容器vector源码分析：https://blog.csdn.net/Z_Stand/article/details/106866871 ↩
5. 5.stl源码分析之vector：https://www.cnblogs.com/coderkian/p/3888429.html ↩
6. 6.Priority Queue - Insertion, Deletion and Implementation in C++ ↩