声明：

  • 1、本博文主要整理自《C++ Primer》和《STL 源码剖析》这两本经典书籍。同时，也参考了网络中不少优秀博客，对这些博客的作者表示感谢。
  • 2、由于博主能力有限，对于一些容器的用法可能尚未进行深入研究。因此，本博文若有错误和不足之处，欢迎大家批评指正。
  • 3、本博文仅作学术交流只用，无任何其他用途。

言归正传，下面开始介绍 C++ 中的 STL 容器。

1、容器的概念

Standard Template Library，标准模板库。
所谓 STL 容器，就是将最常用的一些数据结构实现出来。常用的数据结构不外乎数组 array、链表 list、树 tree、堆栈 stack、队列 queue、散列表 hash table、集合 set、映射表 map 等，根据“数据在容器中的排列”特性，这些数据结构可分为序列式和关联式两种。因此，容器大概也分为序列式容器和关联式容器两种。
20160824224201474.png

2、迭代器简介

我们在使用容器的时候，迭代器是一个不可分割的部分。迭代器在 STL 中用来将算法和容器联系起来，起着一种胶着剂的作用。迭代器是一种检查容器内元素并遍历元素的数据类型。迭代器是一种行为类似指针的对象，它提供类似指针的功能，对容器的内容进行走访，而指针的各种行为中最常见也最重要的便是“内容提领”和“成员访问”。因此，迭代器最重要的编程工作就是对 operator*和 operator-> 进行重载工作。

1、容器的迭代器类型

几乎 STL 提供的所有算法都是通过迭代器存取元素序列进行工作的，每一个容器都定义了其本身所专有的迭代器类型，用以存取容器中的元素，如 vector：

vector<int>::iterator iter;  // 将iter声明为int类型的向量迭代器

这条语句定义了一个名为 iter 的变量，它的数据类型是由 vector 定义的 iterator 类型。每个标准库容器类型都定义了一个名为 iterator 的成员，这里的 iterator 与迭代器的实际类型相同。术语迭代器通常指的是概念上的迭代器，而术语迭代器类型则是有容器定义的具体的 iterator 的类型，如 vector。
常见的迭代器类型主要有：迭代器类型 iterator、元素的只读迭代器类型 const_iterator、按逆序寻址元素的迭代器 reverse_iterator、元素的只读逆序迭代器 const_reverse_iterator。

2、迭代器的 begin 和 end 操作

vector<int>::iterator iter = vec.begin();

begin 返回的迭代器指向容器内第一个元素，end 返回的迭代器指向容器内“最后一个元素的下一个位置”，end 操作返回的迭代器并不指向 vector 中任何实际的元素，它只是起到一个哨兵的作用，表示我们已经处理完 vector 中的所有元素。
rbegin 返回一个逆序迭代器，它指向容器的最后一个元素，rend 返回一个逆序的迭代器，它指向容器的第一个元素前面的位置。

3、迭代器的自增和解引用

迭代器类型可使用解引用操作符（*操作符）来访问迭代器所指向的元素，解引用操作符返回迭代器当前所指向的元素。但是，不能对 end 操作返回的迭代器进行解引用。迭代器也可以使用自增操作符向前移动迭代器指向容器中下一个元素，这在形式上与 int 型对象的自增操作类似。
20160824224404757.png

关系操作符只适用于 vector 和 deque 容器，这是因为只有这两种容器为其元素提供快速、随机的访问。它们确保可根据元素位置直接有效地访问指定的容器元素。这两种容器都支持通过元素的位置实现随机访问，因此它们的迭代器可以有效地实现算术和关系运算。
C++ 语言使用一对迭代器来标记迭代器的范围。迭代器范围：[first, last)是一个左闭合区间，表示范围从 first 开始，到 last 结束，但不包括 last，即 last 指向容器内最后一个元素的下一个元素。注意：如果 first 不等于 last，则对 first 反复做自增运算必须能够到达 last；否则，即 last 位于 first 之前，则将发生未定义行为。迭代器范围使用左闭合的意义：因为这样可以统一表示空集，就无需特别处理。当 first 和 last 相等时，迭代器的范围是空。

4、各容器支持的迭代器类别

只有顺序容器和关联容器支持迭代器遍历，各容器支持的迭代器的类别如下：
20160824224455366.png