C++_顺序容器

顺序容器

容器：一组对象的集合。
顺序容器：元素的位置顺序由“加入容器的位置”决定，不依赖元素值。

例如：

• vector：像可变数组
• list：像链表
• deque：双端队列

顺序容器类型

容器	特点
vector	可变大小数组；支持快速随机访问；尾部插入快；中间/头部插入删除慢
deque	双端队列；支持快速随机访问；头尾插入删除都快
list	双向链表；不支持随机访问；任意位置插入删除快
forward_list	单向链表；只支持单向遍历；任意位置插入删除快
array	固定大小数组；支持快速随机访问；大小不可变
string	存字符的顺序容器；与 vector<char> 类似，但专门处理字符串

如何选容器

复习时可先这样记：

• 默认首选：vector
• 需要头部频繁插入/删除：deque
• 需要中间频繁插入/删除：list / forward_list
• 大小固定：array
• 保存字符序列：string

容器中可以放容器

vector<vector<string>> lines;

即：容器元素类型也可以是另一个容器。

容器的通用操作

容器的类型成员

类型成员	含义
iterator	迭代器类型
const_iterator	只读迭代器类型
size_type	无符号整数类型，表示大小
difference_type	带符号整数类型，表示两个迭代器距离
value_type	元素类型
reference	value_type&
const_reference	const value_type&

容器的定义和初始化

默认构造

C c;

• 创建空容器
• array 例外：创建后元素存在，只是大小固定

---

拷贝构造 / 拷贝初始化

C c1(c2);
C c1 = c2;

要求：

• c1 和 c2 类型相同
• 若是 array，大小也必须相同

---

列表初始化

C c{a, b, c};
C c = {a, b, c};

要求：

• 元素类型兼容
• array 中元素个数不能超过数组大小

---

范围初始化

C c(b, e);

含义：

• 用迭代器 [b, e) 指定范围初始化

注意：

• array 不支持
• 范围是左闭右开：包含 b，不包含 e

---

指定大小的构造

只有顺序容器（不含 array）支持按大小构造：

C seq(n);      // n 个值初始化元素
C seq(n, t);   // n 个值为 t 的元素

注意：

• string 不按这一规则理解为一般顺序容器构造，单独记更好

赋值和 swap

赋值

c1 = c2;
c1 = {a, b, c};

作用：

• 用右侧内容替换左侧内容

注意：

• array 不支持用初始化列表赋值
• 赋值后，原来指向左侧容器元素的迭代器/引用/指针通常失效

assign

assign 主要用于顺序容器（不适用于关联容器和 array）：

seq.assign(b, e);
seq.assign({a, b, c});
seq.assign(n, t);

作用：

• 用新内容整体替换原容器内容

swap

swap(c1, c2);
c1.swap(c2);

作用：

• 交换两个同类型容器的内容
• 通常比拷贝赋值快

注意：

• 大多数容器中，swap 不会移动元素本身
• 但不同容器关于迭代器/引用是否失效有细节差异，复习时先记：
• swap 通常比赋值更安全、更高效
• array 和 string 要单独小心

计算大小

操作	含义
c.size()	元素个数
c.max_size()	理论最大可容纳元素个数
c.empty()	是否为空

注意：

• forward_list 不支持 size()

添加与删除元素

这些操作都会改变容器大小：

• array 不支持
• 各容器支持的接口不完全相同

通用操作：

操作	含义
c.insert(args)	插入元素
c.emplace(args)	原地构造元素
c.erase(args)	删除元素
c.clear()	删除所有元素

push 和 emplace 的区别

c.push_back(obj);      // 放入一个已有对象
c.emplace_back(args);  // 直接用参数构造对象

一般理解：

• push_back：放对象进去
• emplace_back：在容器里直接创建对象

获取迭代器

操作	含义
c.begin(), c.end()	首元素 / 尾后位置
c.cbegin(), c.cend()	const 迭代器

反向迭代器

forward_list 不支持反向迭代器。

操作	含义
c.rbegin(), c.rend()	从尾到头遍历
c.crbegin(), c.crend()	const 反向迭代器

迭代器

迭代器可看作“泛化的指针”。

基本操作：

• 解引用：*it
• 递增：++it
• 比较：it != end

例如：

for (auto it = v.begin(); it != v.end(); ++it)
    cout << *it << " ";

迭代器支持能力不同

• 所有容器迭代器都支持：*it、++it
• forward_list 不支持 --
• 只有 string、vector、deque、array 的迭代器支持算术运算（如 it + n）

迭代器范围

标准写法：

[b, e)

表示：

• 从 b 开始
• 到 e 之前结束
• e 不指向最后一个元素，而是尾后位置

要求：

• b 和 e 必须属于同一个容器
• e 可以等于 b
• 不能在循环中越过 end()

顺序容器的添加操作

尾部添加

c.push_back(t);
c.emplace_back(args);

适用：

• vector
• deque
• list
• string

不适用：

• forward_list
• array

头部添加

c.push_front(t);
c.emplace_front(args);

适用：

• deque
• list
• forward_list（用自己的特殊接口更常见）

不适用：

• vector
• string
• array

任意位置插入

c.insert(p, t);
c.emplace(p, args);
c.insert(p, n, t);
c.insert(p, b, e);
c.insert(p, {a, b, c});

说明：

• 在迭代器 p 指向元素之前插入

插入的失效问题

尤其注意：

• 向 vector / string 插入元素，可能导致重新分配内存
• 一旦重新分配，原来的迭代器、引用、指针都可能失效

复习时先记：

对 vector / string / deque 做插入删除后，原迭代器可能失效，要谨慎。

访问元素

操作	含义
c.front()	首元素引用
c.back()	尾元素引用
c[n]	下标访问
c.at(n)	带越界检查的下标访问

支持情况

• front()：大多数顺序容器支持
• back()：forward_list 不支持
• [] 和 at()：只适用于
• vector
• deque
• string
• array

[] 和 at() 的区别

v[100];    // 越界：未定义行为
v.at(100); // 越界：抛出 out_of_range 异常

复习结论：

• []：快，但不检查越界
• at()：安全，会检查越界

删除元素

操作	含义
c.pop_back()	删除尾元素
c.pop_front()	删除首元素
c.erase(p)	删除 p 指向元素
c.erase(b, e)	删除 [b, e)
c.clear()	清空容器

注意：

• array 不支持
• forward_list 不支持 pop_back
• vector / string 不支持 pop_front

erase 返回值

it = c.erase(it);

erase 返回：

• 被删元素之后的位置

这在边遍历边删除时特别重要。

删除导致迭代器失效

复习时重点记：

• vector / string 删除某位置元素后，该位置及之后的迭代器、引用、指针可能失效
• deque 删除中间元素时影响更大
• list / forward_list 插入删除通常更稳定

forward_list 的特殊操作

forward_list 是单向链表，没有“前驱”信息，因此接口特殊。

首前位置

lst.before_begin();
lst.cbefore_begin();

含义：

• 返回“首元素之前”的位置
• 这个位置不能解引用

在某位置之后插入

lst.insert_after(p, t);
lst.emplace_after(p, args);
lst.insert_after(p, n, t);
lst.insert_after(p, b, e);

注意：

• 是在 p 之后插入，不是之前

删除某位置之后的元素

lst.erase_after(p);
lst.erase_after(b, e);

改变容器大小：resize

array 不支持 resize

c.resize(n);
c.resize(n, t);

作用：

• 若 n 更小：删掉多余元素
• 若 n 更大：补新元素
• resize(n)：值初始化
• resize(n, t)：用 t 初始化

注意：

• 扩容时，vector / string / deque 的迭代器可能失效

容器操作与迭代器失效

这是顺序容器中的重点难点。

会导致失效的典型操作

• insert
• erase
• push_back
• push_front
• resize
• assign

复习时先记的规律

对 vector / string

• 一旦重新分配内存，全部迭代器/引用/指针可能失效
• 删除元素后，删除位置及之后的也可能失效

对 deque

• 头尾插入删除相对常见
• 中间插入删除影响大

对 list / forward_list

• 插入删除通常不会让其他位置迭代器失效
• 但被删元素本身的迭代器一定失效

vector 是如何增长的

vector 内部通常预留一段连续内存。

当空间不够时：

• 分配更大的新内存
• 把旧元素搬过去
• 释放旧内存

很多实现会采用成倍增长策略，以减少频繁扩容。

管理容量

适用于 vector / string 的常见操作：

操作	含义
c.capacity()	当前不重新分配内存最多能放多少元素
c.reserve(n)	预留至少 n 个元素的空间
c.shrink_to_fit()	请求把容量缩到接近当前大小

说明：

• reserve 不改变元素个数
• size() 是“已有多少元素”
• capacity() 是“最多还能装到哪一步而不扩容”

例如：

vector<int> v;
v.reserve(100); // 预留空间，但 size 仍可能是 0

string 的额外操作

string 虽然像顺序容器，但还提供了大量字符串专用操作。

string 的构造

string s(cp, n);          // cp 前 n 个字符
string s(s2, pos2);       // 从 s2[pos2] 开始到末尾
string s(s2, pos2, len2); // 从 s2[pos2] 开始取 len2 个字符

substr

s.substr(pos, n);

含义：

• 从 pos 开始取 n 个字符
• 若省略 n，则取到末尾

例如：

string s = "hello";
s.substr(1, 3); // "ell"

修改 string

操作	含义
s.insert(...)	插入字符/字符串
s.erase(...)	删除字符
s.assign(...)	替换整个字符串内容
s.append(...)	追加内容
s.replace(...)	替换某一段内容

string 的搜索操作

若搜索失败，返回 string::npos

操作	含义
s.find(args)	第一次出现的位置
s.rfind(args)	最后一次出现的位置
s.find_first_of(args)	第一次出现“args 中任一字符”的位置
s.find_last_of(args)	最后一次出现“args 中任一字符”的位置
s.find_first_not_of(args)	第一个不在 args 中的字符位置
s.find_last_not_of(args)	最后一个不在 args 中的字符位置

例如：

string s = "ab2c3";
s.find_first_of("0123456789"); // 找到第一个数字

string::compare

compare 用于比较字符串，返回：

• < 0：左边小
• == 0：相等
• > 0：左边大

例如：

s1.compare(s2);

还支持比较子串、C 风格字符串等。

复习时先记最常用版本即可：

s.compare(s2)

字符串与数值转换

数值转字符串

to_string(val)

例如：

string s = to_string(123);

字符串转数值

整数转换：

stoi(s)
stol(s)
stoll(s)
stoul(s)
stoull(s)

浮点数转换：

stof(s)
stod(s)
stold(s)

带额外参数的形式：

stoi(s, &p, base);

含义：

• p：记录第一个未转换字符的位置
• base：进制，默认 10

异常

若不能转换：

• 抛出 invalid_argument

若数值超范围：

• 抛出 out_of_range

容器适配器

标准库定义了 3 个常见容器适配器：

• stack
• queue
• priority_queue

适配器：把已有容器包装成另一种“行为模式”。

例如：

• 用 deque 包装成“栈”
• 用 deque 包装成“队列”

适配器的通用操作

操作	含义
A a;	空适配器
A a(c);	用底层容器 c 初始化
a.empty()	是否为空
a.size()	元素个数
swap(a, b)	交换内容

类型成员：

• size_type
• value_type
• container_type

stack

头文件：

#include <stack>

默认底层容器通常是 deque。

特点：

• 后进先出（LIFO）

常用操作：

操作	含义
s.push(x)	压栈
s.emplace(args)	原地构造后压栈
s.pop()	弹出栈顶，不返回值
s.top()	访问栈顶元素
s.empty()	判空
s.size()	元素个数

注意：

• pop() 只删除，不返回元素

queue

头文件：

#include <queue>

默认底层容器通常是 deque。

特点：

• 先进先出（FIFO）

常用操作：

操作	含义
q.push(x)	入队
q.emplace(args)	原地构造入队
q.pop()	出队，不返回值
q.front()	队首元素
q.back()	队尾元素
q.empty()	判空
q.size()	元素个数

注意：

• queue 的 pop() 也不返回值

priority_queue

也定义在：

#include <queue>

默认底层容器通常是 vector。

特点：

• 每次取出的都是优先级最高的元素
• 默认通常是“大顶堆”效果：最大元素优先

常用操作：

操作	含义
q.push(x)	插入元素
q.emplace(args)	原地构造插入
q.pop()	删除最高优先级元素，不返回值
q.top()	访问最高优先级元素
q.empty()	判空
q.size()	元素个数

注意：

• priority_queue 没有 front() / back()
• 只有 top()

易错点总结

vector 是默认首选顺序容器

除非有明确理由，否则通常先用 vector

array 大小固定，不能增删元素

forward_list 不支持：

• size()
• back()
• push_back()
• pop_back()
• 反向迭代器

vector / string / deque 插入删除后，迭代器可能失效

尤其是 vector 扩容时，原迭代器几乎都不能再用

erase 常返回“下一个合法位置”

边删边遍历时常写：

it = c.erase(it);

[] 不检查越界，at() 会检查

reserve() 只改容量，不改大小

v.reserve(100); // size 不变

stack / queue / priority_queue 的 pop() 都不返回元素

要先 top() 或 front() 再 pop()

queue 是 FIFO，stack 是 LIFO

priority_queue 默认取最大元素

小结

顺序容器重点掌握：

1. 各容器特点与适用场景
2. 增删改查接口
3. 迭代器与范围 [begin, end)
4. 迭代器失效
5. vector 的容量管理
6. string 的额外操作
7. 适配器：stack / queue / priority_queue