STL是一套功能强大的C++模板类,属于C++标准库的一部分,提供了通用的模板类和函数。本质上就是借助模板把常用的数据结构和算法都实现了一遍。
基本组成
通常认为STL是由容器、算法、迭代器、函数对象、容器适配器、内存分配器六部分组成,其中后边四部分是为前边两部分服务。
容器
容器分为三类,分别是序列容器、排序容器和哈希容器,其中后两类容器有时也统称为关联容器。
容器种类 | 包含的容器 | 含义 |
---|---|---|
序列容器 | vector向量容器、list列表容器、deque双端队列容器 | 序列容器的意思的是元素在容器中的位置和元素本身的值没有关系 |
排序容器 | set集合容器、multiset多重集合容器、map映射容器、multimap多重映射容器 | 排序容器中的元素默认是有小到大排序好的,在插入元素时,元素也会插入到合适的位置。因此关联容器在查找时有很好的性能 |
哈希容器 | uordered_set哈希集合、unordered_multiset哈希多重集合、unordered_map哈希映射、unordered_multimap哈希多重映射 | 这四种关联式容器是在c++11时新加入的。和排序容器不同,哈希容器中的元素是未排序的。元素的位置由哈希函数确定 |
序列式容器
通过线性排列的方式来组织数据就是所谓的序列式容器,且序列式容器只不过是对一类容器的统称,并不具体指某个具体的容器,序列式容器大致包括以下几种:
- array
(数组容器):array是C++本身就提供的一种容器,array在建立之后,长度就是固定的,不能增加或删除,只能改变其中某个元素的值。 - vector
(向量容器):用来存放T类型的数据,是一个长度可变的序列容器。vector在尾部增加或删除元素的效率最高,其他位置插入或者删除的效率较差。 - deque
(双端队列容器):和vector非常相似。但是deque在插入和删除元素时会更加高效。 - list
(链表容器):长度可变的序列,以双向链表的形式来组织数据,在list中的任何地方都可以高效的插入删除数据,但是访问容器中任意元素的速度要比上述三种序列都要慢,因为链表的特性决定了元素必须从第一个或最后一个元素开始访问。 - forward_list
(正向链表容器):和list非常类似,只不过它是以单链表的形式来组织元素,内部的元素只能从第一个元素开始访问。 除此之外,其实stack
和queue 本质上也属于序列式容器,只不过它们都是在deque容器的基础上改头换面而成,因此更习惯上称它们为容器适配器
关联式容器
关联式容器说白了就是键值对的形式来组织和储存数据。如果已知目标元素的键值,就可以直接通过该键找到目标元素,而不需像序列式容器一样再遍历整个容器。使用关联式容器存储的数据,默认会根据各元素的键值大小做升序排列。并且STL在实现该类型容器时,选择了使用「红黑树」这种数据结构来组织和存储各个键值对。
关联式容器对比序列式容器,优点就是关联式容器可以快速查找、读取或者删除所存储的元素。同时,关联式容器插入元素的效率也比序列式容器要高。
STL标准库提供了四种关联式容器,分别是:
- map:定义在
- set:定义在
头文件中,set容器中各个元素键和值完全相同,且元素的值不能重复。该容器会根据各个元素的键的大小进行升序排列 - multimap:也定义在
- multiset:定义在
中,和set不同的是,multiset容器中存储的键值也是可以重复的。 C++11还新增了四种哈希容器,分别是unordered_map、unordered_multimap、unordered_set和unordered_multiset严格来说也算关联式容器,但由于哈希容器底层采用的是哈希表而不是红黑树,因此划在哈希容器中
哈希容器
哈希容器又被称为无序关联式容器,C++11新加入的。和关联式容器的共同点是也是以键值对的形式来存储管理元素,不同在于关联式容器是默认升序的方式来存储数据,哈希容器则不是。哈希容器的特性就是查找性能很好,但是遍历效率不行。无序容器有以下几种:
- unordered_map:储存键值类型的数据,键值不允许重复,且该容器中存储的键值对是无序的。
- unordered_multimap:同unorder_map相比,unordered_multimap允许重复。
- unordered_set:不再以键值对的形式存储数据,而是直接存储数据元素本身(也可以理解为键值相等),不允许重复,存储是无序的。
unordered_multiset:和unoerdered_set相比,unordered_multiset允许重复。
总结
可以看到,哈希容器只不过就是在关联式容器前加了个unordered_来表示无序。使用哈希容器的好处就是可以提高查找效率。实际场景中使用时,如果涉及大量遍历容器的操作,那就应该使用关联式容器,反之,如果更多的操作是通过键来获取对应的值就应该使用无序的哈希容器。根据使用场景灵活使用就可以。
容器适配器
容器适配器是一个封装了序列容器的类模板,因为在一般序列容器的基础上提供了一些不同的功能。之所以称为适配器类,是因为可以通过适配容器现有接口来提供不同的功能,即通过某个序列式容器,并重新组合该容器中包含的成员函数,使其满足特定场景的需要。以stack举例,默认就是在deque的基础上封装来的。
容器适配器类包括以下几种:stack
:一个封装了deque 容器的适配器类模板,实现了一个LIFO(后入先出)的压入栈,stack 模板定义在头文件stack中。 - queue
:也是封装了deque 容器的适配类模板,实现了一个FIFO的队列,定义在 中。 priority_queue
:一个封装了vector 容器的适配器类模板,默认实现的事一个会对元素排序,保证最大元素总在队列最前面的队列。定义在 中。这里的排序是通过堆来实现的。 迭代器
不同种类的容器的内部结构不尽相同,结构各异,但是本质上都是用来存储大量数据的。所以在获取数据的方式上也是类似的。既然类似,则可以用泛型的技术来将它们设计成为适合所有容器的通用算法,将容器和数据分离开来,因此该技术需要一个承载,不仅能够对容器进行所需的数据操作,还要能隐藏容器的内部差异。于是,迭代器就诞生了,迭代器的用法与指针类似,通过迭代器,可以指向容器中的某个元素,还可以进行读写操作。
STL的标准库中,无论是序列式容器还是关联式容器或者哈希容器都只能通过该类容器模板提供的迭代器。迭代器的类型大致可以分为五种,分别是输入迭代器、输出迭代器、前向迭代器、双向迭代器以及随机访问迭代器。前向迭代器:假设p是一个前向迭代器,则p支持++p,p++,*p操作,还可以被复制或者赋值。
- 双向迭代器:具有正向迭代器的全部功能,除次之外,还能—p和p—
- 随机访问迭代器:具有双向迭代器的所有功能,除次之外还能再跳转指定位,比如p += i。随机访问器还可以使用运算符来比较。
以下是不同容器指定使用的迭代器类型:
容器 | 对应的迭代器类型 |
---|---|
array | 随机访问迭代器 |
vector | 随机访问迭代器 |
deque | 随机访问迭代器 |
list | 双向迭代器 |
set / multiset | 双向迭代器 |
map / multimap | 双向迭代器 |
forward_list | 前向迭代器 |
unordered_map / unordered_multimap | 前向迭代器 |
unordered_set / unordered_multiset | 前向迭代器 |
stack | 不支持迭代器 |
queue | 不支持迭代器 |
定义方式
虽然容器不同,迭代器的类型也不同,但是这些迭代器的定义方式都是统一的,只有四种,这也体现了它们的「通用」属性。
代器定义方式 | 具体格式 |
---|---|
正向迭代器 | 容器类名::iterator 迭代器名; |
常量正向迭代器 | 容器类名::const_iterator 迭代器名; |
反向迭代器 | 容器类名::reverse_iterator 迭代器名; |
常量反向迭代器 | 容器类名::const_reverse_iterator 迭代器名; |
迭代器适配器
上述所说的这几种迭代器都是最基本的,有些场景中并不适合。比如要逆序输出list中的所有元素,list模板提供的是双向迭代器,那么逆序打印的实现步骤就应该是:
#include <iostream>
#include <list>
using namespace std;
int main()
{
std::list<int> values{1,2,3,4,5};
//找到遍历的开头位置和结尾位置
std::list<int>::iterator begin = --values.end();
std::list<int>::iterator end = --values.begin();
//开始遍历
while (begin != end)
{
cout << *begin << " ";
--begin;
}
return 0;
}
ok看起来很简单,就是进行一下减减的操作,那所有支持双向迭代器或者随机访问迭代器的容器岂不是就可以用泛型的思想来做出一个模板来实现?是的,这就是迭代器适配器。
参考文章