sequence containers,其中的元素都可序(ordered),但未必有序(sorted)。
串行容器包括vector,heap,priority_queue,list,slist,deque,stack,queue。其实string也可以算一个串行容器,和vector还很像。不过string使用copy-on-write技术,vector使用预留容量和深拷贝。
vector在<vector>中定义,list是双向链表,在<list>中定义,deque是双端队列,在<deque>中定义。
slist是sgi的扩展,不属于标准的一部分,不过单向链表却很有用。
注:c++11已经提供了单向链表forward_list。
queue和priority_queue在<queue>中定义,stack在<stack>中定义,它们已在前边介绍过。
heap以算法形式呈现,也已在前边介绍过。
所以,这里介绍的串行容器有:vector,list,deque,slist。
container | description |
---|---|
vector | 动态数组,可作为c++内置数组的替代型态,vector有如同数组一样的访问方式,例如使用下标(subscript)运算符,并记得自己的长度信息(size),您也可以使用对象的方式来访问vector(push、pop)。vector可在常量时间内完成在vector末尾插入/移除元素,但在vector中间或开头插入/移除元素,则需要消耗线性时间。 |
list | list容器的每个元素中存储着上一个元素和下一个元素的地址(指针),因此是一个双向链接的链表。与vector相比,其元素的访问速度较慢,而在已知元素位置的情况下,插入和删除速度较快。 |
deque | 可看做为能在常量时间内完成向开头或结尾插入或删除元素的vector,但是修改之后,其迭代器的有效性就无法得到保障。 |
slist | 单向链表,相比list并做出了一些优化,比如insert_after(),erase_after() |