STL库基本组成

STL组成 含义
容器 封装数据结构的模板类，如vector向量容器、list列表等
算法 许多被设计成模板的数据结构算法在命名空间中定义，大部分包含在algorithm头文件中，少部分位于numeric头文件
迭代器 在C++STL中，对容器中数据的读和写，是通过迭代器完成的
函数对象 一个将运算符重载为成员函数的类叫函数对象类，这个类的对象就是函数对象
适配器 可以使一个类的接口（模板的参数适配成用户指定的形式，让本来不能在一起工作的两个类工作在一起
内存分配器 为容器类模板提供自定义的内存申请和释放功能

C++标准中，STL头文件被组织为13个：

  • iterator：定义了一些迭代器模板
  • functional：定义一些函数对象类型和支持函数对象的功能
  • vector：类似数组，需要所有元素为统一类型，定义vector容器和vector对象的操作
  • deque：封装双端队列，定义deque容器和deque对象操作
  • list：封装列表，定义list容器和list对象操作
  • queue：封装队列（只有一端可操作，有点栈的感觉，但先进先出），定义queue容器和queue对象操作
  • stack：封装堆栈，定义stack容器和stack对象操作
  • set：封装二叉树（红黑树），定义set对象和set对象操作
  • map：封装加权二叉树（红黑树），定义map对象和map对象操作
  • algorithm：定义多种算法，例如升降序排序、查找之类的
  • numeric：定义了基础性的数值算法
  • memory
  • utility

STL容器

STL容器就是封装了数据结构的模板类的集合，提有三类标准容器：序列容器、排序容器和哈希容器，后两类有时也统称关联容器。

容器种类 功能
序列容器 主要包括vector向量容器、list列表容器以及deque双端队列容器。元素在容器中的位置同元素值无关，插入元素时指定在什么位置，元素就位于什么位置。
排序容器 包括set集合容器、multiset多重集合容器、map映射容器、multimap多重映射容器。元素默认从小到大排列，插入元素时同样插入到合适的位置，所以在查找时具有非常好的性能。
哈希容器 包括4 种关联式容器，分别是 unordered_set 哈希集合、unordered_multiset 哈希多重集合、unordered_map 哈希映射以及 unordered_multimap 哈希多重映射。容器中的元素是未排序的，位置由哈希函数决定。【c++11的编译器下才能使用，VS支持，gcc/g++编译器是不支持的】

序列容器

以线性排列来存储数据，且不进行排序的容器，有如下几种：

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

注：虽然stack< T >和queue< T >本质上也是序列容器，但都是在deque的基础上改造的，更习惯称为容器适配器

关联式容器

关联式容器，包括 map、multimap、set 以及 multiset 这 4 种容器，在存储元素时会为每个元素在配备一个键，整体以键值对的方式存储到容器中。相比序列式容器，关联式容器可以通过键值直接找到对应的元素，而无需遍历整个容器。另外，关联式容器在存储元素，默认会根据各元素键值的大小做升序排序。

相比其它类型容器，关联式容器查找、访问、插入和删除指定元素的效率更高。


STL迭代器

迭代器和c++的指针非常相似，可以是任何需要的类型，通过迭代器可以指向容器中的某个元素，也可以执行读写操作。

迭代器的功能强弱决定了容器是否支持STL的某种算法。

常用迭代器按功能强弱分为输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器。

【其中输入/输出迭代器不是把数组和容器当做操作对象，而是将输入/输出流作为对象，较为特殊。】

已知p是一个前向迭代器，则p支持++p，p++，*p操作，可以被复制或赋值，可以用==和！=运算符进行比较，且两个正向迭代器可以相互赋值

具有正向迭代器的所有功能，同时具有–p或p–的操作（即一次向后移动一个位置）

具有双向迭代器的全部功能，可以用<、>、<=、>=运算符比较，且p2-p1有意义，为p2指向元素和p1指向元素的序号差

当i为整型变量或常量时：

  • p+=i：往后移动i个元素
  • p-=i：往前移动i个元素
  • p+i：返回p后面第i个元素的迭代器
  • p-i：返回p前面第i个元素的迭代器
  • p[i]：返回p后面第i个元素的引用
容器 对应迭代器类型
array 随机访问迭代器
vector 随机访问迭代器
deque 随机访问迭代器
list 双向迭代器
set/multiset 双向迭代器
map/multimap 双向迭代器
forward_list 前向迭代器
unordered_map/unordered_multimap 前向迭代器
unordered_set/unordered_multiset 前向迭代器
stack 不支持迭代器
queue 不支持迭代器

注：容器适配器stack和queue没有迭代器，其本身具有一些成员函数，用于对元素进行访问


迭代器定义方式

定义方式 格式
正向迭代器 ::iterator 迭代器名;
常量正向迭代器 ::const_iterator 迭代器名;
反向迭代器（反向迭代器适配器） ::reverse_iterator 迭代器名;
常量反向迭代器 ::const_reverse_iterator 迭代器名;

注意事项：

  • 读取迭代器指向的元素使用和指针一样的方法：*迭代器名
  • 反向迭代器和正向迭代器：正向迭代器使用p++时，迭代器指向容器中后一个元素，而反向迭代器使用p++时，迭代器指向前一个元素
  • 常量迭代器和非常量迭代器：常量迭代器同c++中const声明是几乎一样的，所以只有通过非常量迭代器才能修改其指向的元素
  • 如容器array、deque、vector同时支持4种，但并不是每个容器都适用以上4种定义迭代器的方式，如forward_list只支持正向迭代器而不支持反向迭代器

以下为范例1：

#include<iostream>
#include<vector>				//需要引入vector头文件
using namespace std;
int main()
{
	vector<int> v{ 1,2,3,4,5,6 };			//v被初始化为有5个元素
	cout << "第1次遍历v" << endl;
	for (int i = 0; i < v.size(); i++)			//可以通过v.size()的方式得到元素个数
	{
		cout << v[i] << " ";				//可以像普通数组一样使用vector容器
	}
	cout << endl << "第2次遍历v" << endl;
	vector<int>::iterator i;
	for (i = v.begin(); i ！= v.end(); i++)		//能用v.begin()和v.end()的方式获得首末元素的地址
	{
		cout << *i << " ";					//可以用*迭代器名的方式获取元素值
	}
	cout << endl << "第3次遍历v" << endl;
	i = v.begin();
	while (i < v.end())					//实现间隔一个元素输出
	{
		cout << *i << " ";
		i += 2;					//随机访问迭代器支持“+=整型”的操作
	}
	    cout<<endl;
	return 0;
}

以上运行结果为：

第1次遍历v
1 2 3 4 5 6
第2次遍历v
1 2 3 4 5 6
第3次遍历v
1 3 5

注：VisualStudio在调试时不会检查迭代器越界问题，但运行时系统会弹窗报错”cannot seek vector iterator after end”


以下为范例2：

#include<iostream>
#include<list>
using namespace std;

//创建一个 v list容器
list<int> v;
//创建一个常量正向迭代器，同样，list也支持其他三种定义迭代器的方式。
list<int>::const_iterator i;

以下代码合法：

for(i = v.begin(); i != v.end(); ++i)
    cout << *i;

以下代码不合法，因为list是双向迭代器，不支持用”<”比较：

for(i = v.begin(); i < v.end(); ++i)
    cout << *i;

以下代码不合法，因为list是双向迭代器，不支持用下标随机访问比较：

for(int i=0; i<v.size(); ++i)
    cout << v[i];