上篇文章的容器只提到了栈(stack
),它是一种十分简单的容器,并不算什么强大的容器,功能很少。
上篇文章仅仅是入门时的小打小闹罢了。本篇文章将会想你介绍更多的、功能强大的 STL 容器,能够让你见识到 STL 的真正实力。
本文适用人群:对面向对象编程语言有了解的人,有 C++ 基础更佳。
如果你还对此不了解,请移步上篇的入门文章。
通用方法
下面的通用方法,如无特殊说明,是所有 STL 容器均具有的,请务必记住哦(只有下面三个)。意味着所有的 STL 容器都能使用它们。
这里以 c 作为容器名举例。
如无特殊说明,STL 容器都是有迭代器的。如果你对这两个都不了解,请阅读上篇文章。
如无特殊说明,STL 容器都是能够使用 algorithm 提供的算法函数的。例如:
更多 algorithm 用法请参考 cplusplus.com。
基本容器
这些容器都是自己手写也比较好实现的,利用 STL 可以偷懒。
队列与栈
关于栈的介绍,请移步上文。
队列(queue)
队列是先进先出的,就像现实生活中的队伍一样,队首的人处理完成事情之后会离开(pop)并轮到下一个。
需要的头文件
注意:所有 STL 容器都是在 std 命名空间内的,所以想要省事请加上 using namespace std;
。为了简洁,后面的文章将省略这行,但是实际写代码不要忘记这行哦。
声明与定义
注意:以后的所有容器将默认为 char
类型,你可以根据实际情况进行改动,这里只是作为例子。
方法
还有两个 C++11 新增方法,emplace
与 swap
,可参考前篇文章对它们的简单介绍。
双端队列(deque)
顾名思义,双端队列两头都可以进出,兼有栈和队列的特性。
需要的头文件
声明与定义
方法
更多方法参见 cplusplus.com。本文章只介绍常见的。
链表(list)
经典数据结构——双向链表。可以 O(1) 快速插入和和删除某个元素,O(n) 遍历元素。
需要的头文件
声明与定义
方法
更多方法参见 cplusplus。本文章只介绍常见的。
其他
下面这些不常用,感兴趣的读者可自行搜索相关资料。
数组(array)
和普通定长数组一样,没什么特别之处,不怎么常用。
单向链表(forward list)
比起双向链表,唯一的优点也许只有内存占用小了吧。因为是单向,所以不提供反向迭代器。
有点意思的容器
这里的容器都是看起来简单,却实际却又没那么简单的容器。
向量 / 动态数组(vector)
动态数组,顾名思义,长度是动态的。可以像数组一样 O(1) 下标访问,就像普通数组一样。
需要的头文件
声明与定义
构造器
构造器是初始化一个容器时用的,它会在容器创建时自动执行。在声明时这样写即可使用构造器。
方法
字符串(string)
功能强大的字符串类,字符串处理题好帮手。
需要的头文件
声明与定义
构造器
输入输出方式
使用 C++ 的输入输出流。
方法
字符串提供的方法有太多了。这里分了几组。
访问方法
拼接方法
此外,string
也可以按照字典序进行大小比较,直接用 <
或 >
比较即可。
在使用 sort
排序 string
数组时,默认就是按照字典序从小到大排序了。
增删
转换
查找
截取
C++11 的转换方法
更多方法参见 cplusplus.com
其他
元组(tuple)
和数组差不多,就是没有固定类型,里面的可以同时存储不同类型的数据。
看起来很高级的容器
这里的容器具有一定的特殊功能,自己手写可不好写哦。
优先队列(priority queue)
优先队列会自动在插入时将元素排好顺序,即堆(heap)这种数据结构。默认顶部为最大的值,即大根堆。
需要的头文件
声明与构造
为方便起见,从这里开始声明和构造器就合一起了。
方法
只有通用的和下面的三个,不多。
映射(map)
了解过 Python 的同学应该都知道,Python 有字典(dict)这个类,可以通过一个键访问到对应的值。JavaScript 也有类似的类型:对象(object),其他语言或许有也哈希表(hash table)。
就拿 Python 举例来说,定义一个像这样表示三个人成绩的字典
如果想要根据人名获得对应的成绩,那只需要
只需要提供键(key):'xiaoming'
,就能得到它对应的值(value):89
。
STL 的 map 容器提供的便是这种功能。map 有两种:
- map:底层实现是红黑树,是按照插入顺序严格有序的,因此访问也慢一些(O(logn))。
- unordered_map:(C++11 才有的)底层实现是哈希表,无需,访问也更快(O(1))。
需要的头文件
声明与定义
注意:由于这两种 map 基本用法都一样,所以下面都以 map 来举例。
遍历
map 内部存储的元素类型是 pair。
像上面定义的例子,grades
里的元素是 pair<string, int>
。
可以理解成,grades
里的元素的是这样的结构体:
如何遍历 map 呢?就像下面这样:
方法
集合(set)
数学上的集合是不能出现重复值的,set 容器也是一样的。不过与数学上集合的无序性不同的是,set 容器内部是有序的(默认从小到大排序)。相对地还有个 unordered_set(C++11 才有的),它是无序的,因此速度也比有序的 set 更快。之前也写过关于它的文章。
需要的头文件
声明与定义
构造器
为方便起见,下面都以 set 为例。
方法
其他
multiset
允许有重复值的集合,跟优先队列很像,不知道有什么用呢。
bitset
说是集合,却没有集合的特性,就当它是个存储位(bit)的数组吧。每一个元素都是一位,支持位运算。
比起 bool
数组来说,这东西更省空间,要对位进行精确操作可以用它。之前写过关于它的文章。
太长不看版
文章太长了一头雾水?STL 容器看起来很多,但其内核都是相通的。
现代编辑器都拥有完善的代码补全,所以你不用担心方法名能不能记住,你只需要知道这些方法是做什么的就可以了,以及,以上容器的拼写。
这里再列下它们的名字吧。
中英文名字 | 头文件 | 作用 |
---|
栈(stack) | stack | 先进后出 |
队列(queue) | queue | 先进先出 |
双端队列(deque) | deque | 兼有栈和队列特性 |
链表(list) | list | 双向链表 |
向量(vector) | vector | 动态数组 |
字符串(string) | string | 比 char* 更好用的字符串 |
优先队列(priority_queue) | queue | 堆,内部有序 |
映射(map) | map | 构造键到值的映射 |
集合(set) | set | 不允许重复值,内部有序 |
如果想看详细用法就点击目录吧。注意,要先看通用方法哦。
参考资料:cplusplus.com