顺序容器概述
顺序容器(sequential container):为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值,而是与元素加入容器时的位置相对应。
顺序容器类型
| 容器类型 | 介绍 | | —- | —- | |
vector
| 可变大小数组。支持快速随机访问。在尾部之外的位置插入或删除元素可能很慢。 | |deque
| 双端队列。支持快速随机访问。在头尾位置插入/删除速度很快。 | |list
| 双向链表。只支持双向顺序访问。在list
中任何位置进行插入/删除操作速度都很快。 | |forward_list
| 单向链表。只支持单向顺序访问。在链表任何位置进行插入/删除操作速度都很快。 | |array
| 固定大小数组。支持快速随机访问。不能添加或者删除元素。 | |string
| 与vector
相似的容器,但专门用于保存字符。随机访问块。在尾部插入/删除速度快。 |除了固定大小的
array
外,其他容器都提供高效、灵活的内存管理。forward_list
和array
是新C++标准增加的类型。- 通常使用
vector
是最好的选择,除非你有很好的理由选择其他容器。 - 新标准库的容器比旧版的快得多。
容器操作
类型
| 操作 | 解释 | | —- | —- | |iterator
| 此容器类型的迭代器类型 | |const_iterator
| 可以读取元素但不能修改元素的迭代器类型 | |size_type
| 无符号整数类型,足够保存此种容器类型最大可能的大小 | |difference_type
| 带符号整数类型,足够保存两个迭代器之间的距离 | |value_type
| 元素类型 | |reference
| 元素的左值类型;和value_type &
含义相同 | |const_reference
| 元素的const
左值类型,即const value_type &
|
构造函数
操作 | 解释 |
---|---|
C c; |
默认构造函数,构造空容器 |
C c1(c2); 或C c1 = c2; |
构造c2 的拷贝c1 |
C c(b, e) |
构造c ,将迭代器b 和e 指定范围内的所有元素拷贝到c |
C c(a, b, c...) |
列表初始化c |
C c(n) |
只支持顺序容器,且不包括array ,包含n 个元素,这些元素进行了值初始化 |
C c(n, t) |
包含n 个初始值为t 的元素 |
- 只有顺序容器的构造函数才接受大小参数,关联容器并不支持。
array
具有固定大小。- 和其他容器不同,默认构造的
array
是非空的。 - 直接复制:将一个容器复制给另一个容器时,类型必须匹配:容器类型和元素类型都必须相同。
使用迭代器复制:不要求容器类型相同,容器内的元素类型也可以不同。
赋值和
swap
| 操作 | 解释 | | —- | —- | |
c1 = c2;
| 将c1
中的元素替换成c2
中的元素 | |c1 = {a, b, c...}
| 将c1
中的元素替换成列表中的元素(不适用于array
) | |c1.swap(c2)
| 交换c1
和c2
的元素 | |swap(c1, c2)
| 等价于c1.swap(c2)
| |c.assign(b, e)
| 将c
中的元素替换成迭代器b
和e
表示范围中的元素,b
和e
不能指向c
中的元素 | |c.assign(il)
| 将c
中的元素替换成初始化列表il
中的元素 | |c.assign(n, r)
| 将c
中的元素替换为n
个值是t
的元素 |使用非成员版本的
swap
是一个好习惯。assign
操作不适用于关联容器和array
大小
| 操作 | 解释 | | —- | —- | |c.size()
|c
中元素的数目(不支持forward_list
) | |c.max_size()
|c
中可保存的最大元素数目 | |c.empty()
| 若c
中存储了元素,返回false
,否则返回true
|
添加元素
操作 | 解释 |
---|---|
c.push_back(t) |
在c 尾部创建一个值为t 的元素,返回void |
c.emplace_back(args) |
同上 |
c.push_front(t) |
在c 头部创建一个值为t 的元素,返回void |
c.emplace_front(args) |
同上 |
c.insert(p, t) |
在迭代器p 指向的元素之前创建一个值是t 的元素,返回指向新元素的迭代器 |
c.emplace(p, args) |
同上 |
c.inset(p, n, t) |
在迭代器p 指向的元素之前插入n 个值为t 的元素,返回指向第一个新元素的迭代器;如果n 是0,则返回p |
c.insert(p, b, e) |
将迭代器b 和e 范围内的元素,插入到p 指向的元素之前;如果范围为空,则返回p |
c.insert(p, il) |
il 是一个花括号包围中的元素值列表,将其插入到p 指向的元素之前;如果il 是空,则返回p |
- 因为这些操作会改变大小,因此不适用于
array
。 forward_list
有自己专有版本的insert
和emplace
。forward_list
不支持push_back
和emplace_back
。- 当我们用一个对象去初始化容器或者将对象插入到容器时,实际上放入的是对象的拷贝。
emplace
开头的函数是新标准引入的,这些操作是构造而不是拷贝元素。-
访问元素
| 操作 | 解释 | | —- | —- | |
c.back()
| 返回c
中尾元素的引用。若c
为空,函数行为未定义 | |c.front()
| 返回c
中头元素的引用。若c
为空,函数行为未定义 | |c[n]
| 返回c
中下标是n
的元素的引用,n
时候一个无符号证书。若n>=c.size()
,则函数行为未定义 | |c.at(n)
| 返回下标为n
的元素引用。如果下标越界,则抛出out_of_range
异常 | 访问成员函数返回的是引用。
at
和下标操作只适用于string
、vector
、deque
、array
。back
不适用于forward_list
。-
删除元素
| 操作 | 解释 | | —- | —- | |
c.pop_back()
| 删除c
中尾元素,若c
为空,则函数行为未定义。函数返回void
| |c.pop_front()
| 删除c
中首元素,若c
为空,则函数行为未定义。函数返回void
| |c.erase(p)
| 删除迭代器p
指向的元素,返回一个指向被删除元素之后的元素的迭代器,若p
本身是尾后迭代器,则函数行为未定义 | |c.erase(b, e)
| 删除迭代器b
和e
范围内的元素,返回指向最后一个被删元素之后元素的迭代器,若e
本身就是尾后迭代器,则返回尾后迭代器 | |c.clear()
| 删除c
中所有元素,返回void
| 会改变容器大小,不适用于
array
。forward_list
有特殊版本的erase
forward_list
不支持pop_back
-
特殊的forwad_list操作
链表在删除元素时需要修改前置节点的内容,双向链表会前驱的指针,但是单向链表没有保存,因此需要增加获取前置节点的方法。
forward_list
定义了before_begin
,即首前(off-the-begining)迭代器,允许我们再在首元素之前添加或删除元素。 | 操作 | 解释 | | —- | —- | |lst.before_begin()
| 返回指向链表首元素之前不存在的元素的迭代器,此迭代器不能解引用。 | |lst.cbefore_begin()
| 同上,但是返回的是常量迭代器。 | |lst.insert_after(p, t)
| 在迭代器p
之后插入元素。t
是一个对象 | |lst.insert_after(p, n, t)
| 在迭代器p
之后插入元素。t
是一个对象,n
是数量。若n
是0则函数行为未定义 | |lst.insert_after(p, b, e)
| 在迭代器p
之后插入元素。由迭代器b
和e
指定范围。 | |lst.insert_after(p, il)
| 在迭代器p
之后插入元素。由il
指定初始化列表。 | |emplace_after(p, args)
| 使用args
在p
之后的位置,创建一个元素,返回一个指向这个新元素的迭代器。若p
为尾后迭代器,则函数行为未定义。 | |lst.erase_after(p)
| 删除p
指向位置之后的元素,返回一个指向被删元素之后的元素的迭代器,若p
指向lst
的尾元素或者是一个尾后迭代器,则函数行为未定义。 | |lst.erase_after(b, e)
| 类似上面,删除对象换成从b
到e
指定的范围。 |
改变容器大小
操作 | 解释 |
---|---|
c.resize(n) |
调整c 的大小为n 个元素,若n<c.size() ,则多出的元素被丢弃。若必须添加新元素,对新元素进行值初始化 |
c.resize(n, t) |
调整c 的大小为n 个元素,任何新添加的元素都初始化为值t |
获取迭代器
操作 | 解释 |
---|---|
c.begin() , c.end() |
返回指向c 的首元素和尾元素之后位置的迭代器 |
c.cbegin() , c.cend() |
返回const_iterator |
- 以
c
开头的版本是C++11新标准引入的 -
反向容器的额外成员
| 操作 | 解释 | | —- | —- | |
reverse_iterator
| 按逆序寻址元素的迭代器 | |const_reverse_iterator
| 不能修改元素的逆序迭代器 | |c.rbegin()
,c.rend()
| 返回指向c
的尾元素和首元素之前位置的迭代器 | |c.crbegin()
,c.crend()
| 返回const_reverse_iterator
| -
迭代器
迭代器范围:
begin
到end
,即第一个元素到最后一个元素的后面一个位置。- 左闭合区间:
[begin, end)
左闭合范围蕴含的编程设定:
在向容器添加元素后:
- 如果容器是
vector
或string
,且存储空间被重新分配,则指向容器的迭代器、指针、引用都会失效。 - 对于
deque
,插入到除首尾位置之外的任何位置都会导致指向容器的迭代器、指针、引用失效。如果在首尾位置添加元素,迭代器会失效,但指向存在元素的引用和指针不会失效。 - 对于
list
和forward_list
,指向容器的迭代器、指针和引用依然有效。
- 如果容器是
在从一个容器中删除元素后:
元素类型必须支持赋值运算;
- 元素类型的对象必须可以复制。
除了输入输出标准库类型外,其他所有标准库类型都是有效的容器元素类型。
vector对象是如何增长的
vector
和string
在内存中是连续保存的,如果原先分配的内存位置已经使用完,则需要重新分配新空间,将已有元素从就位置移动到新空间中,然后添加新元素。管理容量的成员函数
| 操作 | 解释 | | —- | —- | |
c.shrink_to_fit()
| 将capacity()
减少到和size()
相同大小 | |c.capacity()
| 不重新分配内存空间的话,c
可以保存多少个元素 | |c.reverse(n)
| 分配至少能容纳n
个元素的内存空间 |shrink_to_fit
只适用于vector
、string
和deque
capacity
和reverse
只适用于vector
和string
。额外的string操作
构造string的其他方法
| 操作 | 解释 | | —- | —- | |
string s(cp, n)
|s
是cp
指向的数组中前n
个字符的拷贝,此数组 | |string s(s2, pos2)
|s
是string s2
从下标pos2
开始的字符的拷贝。若pos2 > s2.size()
,则构造函数的行为未定义。 | |string s(s2, pos2, len2)
|s
是string s2
从下标pos2
开始的len2
个字符的拷贝。 |-
substr操作
| 操作 | 解释 | | —- | —- | |
s.substr(pos, n)
| 返回一个string
,包含s
中从pos
开始的n
个字符的拷贝。pos
的默认值是0,n
的默认值是s.size() - pos
,即拷贝从pos
开始的所有字符。 |
改变string的其他方法
操作 | 解释 |
---|---|
s.insert(pos, args) |
在pos 之前插入args 指定的字符。pos 可以使是下标或者迭代器。接受下标的版本返回指向s 的引用;接受迭代器的版本返回指向第一个插入字符的迭代器。 |
s.erase(pos, len) |
删除从pos 开始的len 个字符,如果len 被省略,则删除后面所有字符,返回指向s 的引用。 |
s.assign(args) |
将s 中的字符替换成args 指定的字符。返回一个指向s 的引用。 |
s.append(args) |
将args 指定的字符追加到s ,返回一个指向s 的引用。 |
s.replace(range, args) |
删除s 中范围range 中的字符,替换成args 指定的字符。返回一个指向s 的引用。 |
string搜索操作
string
类提供了6个不同的搜索函数,每个函数都有4个重载版本。- 每个搜索操作都返回一个
string::size_type
值,表示匹配发生位置的下标。如果搜索失败则返回一个名为string::npos
的static
成员(类型是string::size_type
,初始化值是-1,也就是string
最大的可能大小)。 | 搜索操作 | 解释 | | —- | —- | |s.find(args)
| 查找s
中args
第一次出现的位置 | |s.rfind(args)
| 查找s
中args
最后一次出现的位置 | |s.find_first_of(args)
| 在s
中查找args
中任何一个字符第一次出现的位置 | |s.find_last_of(args)
| 在s
中查找args
中任何一个字符最后一次出现的位置 | |s.find_first_not_of(args)
| 在s
中查找第一个不在args
中的字符 | |s.find_first_not_of(args)
| 在s
中查找最后一个不在args
中的字符 |
args必须是一下的形式之一:
args 形式 |
解释 |
---|---|
c, pos |
从s 中位置pos 开始查找字符c 。pos 默认是0 |
s2, pos |
从s 中位置pos 开始查找字符串s 。pos 默认是0 |
cp, pos |
从s 中位置pos 开始查找指针cp 指向的以空字符结尾的C风格字符串。pos 默认是0 |
cp, pos, n |
从s 中位置pos 开始查找指针cp 指向的前n 个字符。pos 和n 无默认值。 |
s.compare的几种参数形式
逻辑类似于C标准库的strcmp
函数,根据s
是等于、大于还是小于参数指定的字符串,s.compare
返回0、正数或负数。
参数形式 | 解释 |
---|---|
s2 |
比较s 和s2 |
pos1, n1, s2 |
比较s 从pos1 开始的n1 个字符和s2 |
pos1, n1, s2, pos2, n2 |
比较s 从pos1 开始的n1 个字符和s2 |
cp |
比较s 和cp 指向的以空字符结尾的字符数组 |
pos1, n1, cp |
比较s 从pos1 开始的n1 个字符和cp 指向的以空字符结尾的字符数组 |
pos1, n1, cp, n2 |
比较s 从pos1 开始的n1 个字符和cp 指向的地址开始n2 个字符 |
string和数值转换
转换 | 解释 |
---|---|
to_string(val) |
一组重载函数,返回数值val 的string 表示。val 可以使任何算术类型。对每个浮点类型和int 或更大的整型,都有相应版本的to_string() 。和往常一样,小整型会被提升。 |
stoi(s, p, b) |
返回s 起始子串(表示整数内容)的数值,p 是s 中第一个非数值字符的下标,默认是0,b 是转换所用的基数。返回int |
stol(s, p, b) |
返回long |
stoul(s, p, b) |
返回unsigned long |
stoll(s, p, b) |
返回long long |
stoull(s, p, b) |
返回unsigned long long |
stof(s, p) |
返回s 起始子串(表示浮点数内容)的数值,p 是s 中第一个非数值字符的下标,默认是0。返回float |
stod(s, p) |
返回double |
stold(s, p) |
返回long double |
容器适配器(adapter)
- 适配器是使一事物的行为类似于另一事物的行为的一种机制,例如
stack
可以使任何一种顺序容器以栈的方式工作。 - 初始化
deque<int> deq; stack<int> stk(deq);
从deq
拷贝元素到stk
。 - 创建适配器时,指定一个顺序容器,可以覆盖默认的基础容器:
stack<string, vector<string> > str_stk;
。适配器的通用操作和类型
| 操作 | 解释 | | —- | —- | |size_type
| 一种类型,须以保存当前类型的最大对象的大小 | |value_type
| 元素类型 | |container_type
| 实现适配器的底层容器类型 | |A a;
| 创建一个名为a
的空适配器 | |A a(c)
| 创建一个名为a
的适配器,带有容器c
的一个拷贝 | | 关系运算符 | 每个适配器都支持所有关系运算符:==
、!=
、<
、<=
、>
、>=
这些运算符返回底层容器的比较结果 | |a.empty()
| 若a
包含任何元素,返回false
;否则返回true
| |a.size()
| 返回a
中的元素数目 | |swap(a, b)
| 交换a
和b
的内容,a
和b
必须有相同类型,包括底层容器类型也必须相同 | |a.swap(b)
| 同上 |
stack
操作 | 解释 |
---|---|
s.pop() |
删除栈顶元素,不返回。 |
s.push(item) |
创建一个新元素,压入栈顶,该元素通过拷贝或移动item 而来 |
s.emplace(args) |
同上,但元素由args 来构造。 |
s.top() |
返回栈顶元素,不删除。 |
- 定义在
stack
头文件中。 stack
默认基于deque
实现,也可以在list
或vector
之上实现。queue和priority_queue
| 操作 | 解释 | | —- | —- | |
q.pop()
| 删除队首元素,但不返回。 | |q.front()
| 返回队首元素的值,不删除。 | |q.back()
| 返回队尾元素的值,不删除。只适用于queue
| |q.top()
| 返回具有最高优先级的元素值,不删除。 | |q.push(item)
| 在队尾压入一个新元素。 | |q.emplace(args)
| |定义在
queue
头文件中。queue
默认基于deque
实现,priority_queue
默认基于vector
实现。queue
可以在list
或vector
之上实现,priority_queue
也可以用deque
实现。