3. containers (容器)

实现各种数据结构容器。头文件: <vector>, <list>, <deque>, <array>, <forward_list>, <map>, <set>, <unordered_map>, <unordered_set>, <stack>, <queue>, <priority_queue> 等。

3.1 序列容器 — vector

头文件: <vector>

---

template <class T, class Allocator = allocator<T>> class vector

动态数组，连续存储，支持随机访问。

• 输入: T — 元素类型; Allocator — 分配器
• 输出: vector 对象
• 注意: 插入/删除中间元素为 O(N); 尾插均摊 O(1)

---

vector()

默认构造函数。

• 输入: 无
• 输出: 空 vector
• 注意: 不分配内存

---

explicit vector(size_type n)

构造包含 n 个默认构造元素的 vector。

• 输入: n — 元素个数
• 输出: 包含 n 个 T() 的 vector
• 注意: 要求 T 默认可构造

---

vector(size_type n, const value_type& value)

构造包含 n 个 value 的 vector。

• 输入: n — 个数; value — 填充值
• 输出: 包含 n 个 value 的 vector

---

vector(InputIterator first, InputIterator last)

从迭代器范围构造。

• 输入: first, last — 输入迭代器范围
• 输出: 包含范围内元素的 vector

---

vector(const vector& x)

拷贝构造函数。

• 输入: x — 源 vector
• 输出: 深拷贝

---

vector(vector&& x) noexcept

移动构造函数。

• 输入: x — 源 vector（右值）
• 输出: 转移所有权
• 注意: 分配器允许时 noexcept

---

~vector()

析构函数。

• 输入: 无
• 输出: 无
• 注意: 析构所有元素并释放内存

---

vector& operator=(const vector& x)

拷贝赋值。

• 输入: x — 源 vector
• 输出: *this

---

vector& operator=(vector&& x) noexcept

移动赋值。

• 输入: x — 源 vector（右值）
• 输出: *this

---

void assign(size_type n, const value_type& u)

重新赋值为 n 个 u。

• 输入: n — 个数; u — 值
• 输出: void

---

allocator_type get_allocator() const noexcept

获取分配器。

• 输入: 无
• 输出: allocator_type — 分配器副本

---

iterator begin() noexcept / const_iterator begin() const noexcept

返回起始迭代器。

• 输入: 无
• 输出: 指向首元素的迭代器

---

iterator end() noexcept / const_iterator end() const noexcept

返回尾后迭代器。

• 输入: 无
• 输出: 指向末尾之后位置的迭代器

---

reverse_iterator rbegin() noexcept

返回反向起始迭代器。

• 输入: 无
• 输出: 指向末元素的反向迭代器

---

const_iterator cbegin() const noexcept

返回 const 起始迭代器。

• 输入: 无
• 输出: const_iterator
• 注意: C++11 引入

---

size_type size() const noexcept

返回元素数量。

• 输入: 无
• 输出: size_type — 元素个数

---

size_type max_size() const noexcept

返回最大可容纳元素数。

• 输入: 无
• 输出: size_type — 最大数量

---

size_type capacity() const noexcept

返回当前容量。

• 输入: 无
• 输出: size_type — 不重新分配可容纳的元素数

---

bool empty() const noexcept

检查是否为空。

• 输入: 无
• 输出: bool — 空返回 true

---

void reserve(size_type n)

预留至少容纳 n 个元素的容量。

• 输入: n — 容量要求
• 输出: void
• 注意: 若 n > capacity() 则重新分配; 不构造元素

---

void shrink_to_fit()

请求缩减容量以适应大小。

• 输入: 无
• 输出: void
• 注意: 请求而非强制; 是否执行取决于实现

---

reference operator[](size_type n)

索引访问（无边界检查）。

• 输入: n — 索引
• 输出: reference — 元素引用
• 注意: 不检查越界，越界行为未定义

---

reference at(size_type n)

安全索引访问。

• 输入: n — 索引
• 输出: reference — 元素引用
• 注意: 越界抛出 out_of_range 异常

---

reference front() / const_reference front() const

返回首元素引用。

• 输入: 无
• 输出: 首元素引用
• 注意: 空 vector 调用行为未定义

---

reference back() / const_reference back() const

返回末元素引用。

• 输入: 无
• 输出: 末元素引用

---

value_type* data() noexcept

返回指向底层数组的指针。

• 输入: 无
• 输出: T* — 底层数组指针
• 注意: 空 vector 可能返回 nullptr

---

void push_back(const value_type& x)

尾部添加元素（拷贝）。

• 输入: x — 要添加的元素
• 输出: void
• 注意: 若容量不足则重新分配

---

void push_back(value_type&& x)

尾部添加元素（移动）。

• 输入: x — 要添加的元素（右值）
• 输出: void

---

template <class... Args> reference emplace_back(Args&&... args)

原地构造并尾部添加元素。

• 输入: args... — 构造参数
• 输出: reference — 新元素的引用
• 注意: 比 push_back 更高效

---

void pop_back()

移除尾部元素。

• 输入: 无
• 输出: void
• 注意: 空 vector 调用行为未定义

---

template <class... Args> iterator emplace(const_iterator position, Args&&... args)

在指定位置原地构造元素。

• 输入: position — 插入位置; args... — 构造参数
• 输出: iterator — 指向新元素的迭代器

---

iterator insert(const_iterator position, const value_type& x)

在指定位置插入元素。

• 输入: position — 插入位置; x — 元素
• 输出: iterator — 指向新元素的迭代器
• 注意: 可能使所有迭代器失效

---

iterator erase(const_iterator position)

删除指定位置的元素。

• 输入: position — 要删除的位置
• 输出: iterator — 被删除元素之后的迭代器
• 注意: 使 position 及之后迭代器失效

---

iterator erase(const_iterator first, const_iterator last)

删除范围内的元素。

• 输入: first, last — 要删除的范围
• 输出: iterator — last 删除后对应的新位置

---

void swap(vector&) noexcept

交换两个 vector。

• 输入: 另一个 vector 引用
• 输出: void
• 注意: 分配器支持时 noexcept

---

void clear() noexcept

清空所有元素。

• 输入: 无
• 输出: void
• 注意: 不释放内存

---

void resize(size_type sz)

调整大小。

• 输入: sz — 新大小
• 输出: void
• 注意: 扩大时新增元素默认构造，缩小时截断

---

void resize(size_type sz, const value_type& c)

调整大小并用 c 填充新增元素。

• 输入: sz — 新大小; c — 填充值
• 输出: void

---

3.2 序列容器 — list

头文件: <list>

---

template <class T, class Allocator = allocator<T>> class list

双向链表。

• 输入: T — 元素类型; Allocator — 分配器
• 输出: list 对象
• 注意: 插入/删除为 O(1)，不支持随机访问

---

void push_front(const value_type& x)

头部添加元素。

• 输入: x — 元素
• 输出: void
• 注意: vector 没有此操作

---

void pop_front()

移除头部元素。

• 输入: 无
• 输出: void

---

void splice(const_iterator position, list& x)

将另一个 list 的所有元素移动到当前 list 的指定位置。

• 输入: position — 插入位置; x — 源 list
• 输出: void
• 注意: 不拷贝/移动元素，仅调整指针; 操作后 x 为空

---

void remove(const value_type& value)

删除所有等于 value 的元素。

• 输入: value — 要删除的值
• 输出: void

---

void unique()

删除连续的重复元素。

• 输入: 无
• 输出: void
• 注意: 只删除相邻重复，通常先排序

---

void merge(list& x)

合并两个已排序的 list。

• 输入: x — 另一个已排序的 list
• 输出: void
• 注意: 操作后 x 为空; 要求两个 list 已排序

---

void sort()

对 list 排序。

• 输入: 无
• 输出: void
• 注意: 使用归并排序，稳定排序; 避免 vector 的全量迭代器失效问题

---

void reverse() noexcept

反转 list。

• 输入: 无
• 输出: void

---

3.3 序列容器 — deque

头文件: <deque>

---

template <class T, class Allocator = allocator<T>> class deque

双端队列。

• 输入: T — 元素类型; Allocator — 分配器
• 输出: deque 对象
• 注意: 支持两端 O(1) 插入/删除; 非连续存储但支持随机访问

---

void push_front(const value_type& x)

头部添加元素。

• 输入: x — 元素
• 输出: void
• 注意: 均摊 O(1)

---

void pop_front()

移除头部元素。

• 输入: 无
• 输出: void

---

3.4 序列容器 — array

头文件: <array>

---

template <class T, size_t N> struct array

固定大小数组。

• 输入: T — 元素类型; N — 大小
• 输出: array 对象
• 注意: 大小固定，在栈上分配; 支持所有容器操作

---

void fill(const value_type& u)

用值填充整个数组。

• 输入: u — 填充值
• 输出: void

---

void swap(array& other) noexcept

交换两个同类型同大小的 array。

• 输入: other — 另一个 array
• 输出: void

---

constexpr size_type size() const noexcept

返回数组大小。

• 输入: 无
• 输出: size_type — 大小 N
• 注意: 编译期常量

---

T& at(size_type n)

安全索引访问。

• 输入: n — 索引
• 输出: T& — 元素引用
• 注意: 越界抛出 out_of_range

---

T& operator[](size_type n)

索引访问（无检查）。

• 输入: n — 索引
• 输出: T& — 元素引用

---

T& front() / T& back()

首/末元素访问。

• 输入: 无
• 输出: T&

---

T* data() noexcept

获取底层数组指针。

• 输入: 无
• 输出: T* — 指向内部数组的指针

---

std::get<size_t I>(array<T, N>& a)

编译期索引访问。

• 输入: a — array 引用
• 输出: T& — 第 I 个元素
• 注意: 越界编译错误

---

3.5 序列容器 — forward_list

头文件: <forward_list>

---

template <class T, class Allocator = allocator<T>> class forward_list

单向链表。

• 输入: T — 元素类型; Allocator — 分配器
• 输出: forward_list 对象
• 注意: 仅支持正向遍历; 内存占用比 list 小

---

void push_front(const value_type& x)

头部添加元素。

• 输入: x — 元素
• 输出: void

---

iterator insert_after(const_iterator position, const value_type& x)

在指定位置之后插入元素。

• 输入: position — 位置; x — 元素
• 输出: iterator — 指向新元素
• 注意: 单向链表只能在前驱位置之后插入

---

iterator erase_after(const_iterator position)

删除指定位置之后的元素。

• 输入: position — 位置
• 输出: iterator — 被删除元素之后的迭代器

---

void splice_after(const_iterator position, forward_list& other)

将另一个 forward_list 拼接到指定位置之后。

• 输入: position — 位置; other — 源列表
• 输出: void

---

3.6 关联容器 — map

头文件: <map>

---

template <class Key, class T, class Compare = less<Key>, class Allocator = allocator<pair<const Key, T>>> class map

有序键值对容器。

• 输入: Key — 键类型; T — 值类型; Compare — 比较器; Allocator — 分配器
• 输出: map 对象
• 注意: 基于红黑树实现; 按键排序; 键唯一

---

pair<iterator, bool> insert(const value_type& x)

插入元素。

• 输入: x — 键值对
• 输出: pair — iterator 指向元素，bool 表示是否插入成功
• 注意: 键已存在则返回 false

---

iterator find(const key_type& x)

查找键。

• 输入: x — 键
• 输出: iterator — 指向元素的迭代器，未找到返回 end()

---

size_type count(const key_type& x) const

统计键出现次数。

• 输入: x — 键
• 输出: size_type — 0 或 1

---

iterator lower_bound(const key_type& x)

返回第一个不小于 x 的键的位置。

• 输入: x — 键
• 输出: iterator

---

iterator upper_bound(const key_type& x)

返回第一个大于 x 的键的位置。

• 输入: x — 键
• 输出: iterator

---

pair<iterator, iterator> equal_range(const key_type& x)

返回等于 x 的键的范围。

• 输入: x — 键
• 输出: pair<iterator, iterator> — 范围

---

T& operator[](const key_type& k)

访问或插入键对应的值。

• 输入: k — 键
• 输出: T& — 值引用
• 注意: 键不存在时会默认构造插入

---

T& at(const key_type& k)

安全访问键对应的值。

• 输入: k — 键
• 输出: T& — 值引用
• 注意: 键不存在时抛出 out_of_range

---

template <class... Args> pair<iterator, bool> emplace(Args&&... args)

原地构造并插入。

• 输入: args... — 构造 pair 的参数
• 输出: pair<iterator, bool> — 同 insert

---

void erase(iterator position)

删除指定位置的元素。

• 输入: position — 位置
• 输出: void

---

size_type erase(const key_type& x)

删除指定键的元素。

• 输入: x — 键
• 输出: size_type — 删除数量（0 或 1）

---

3.7 关联容器 — set

头文件: <set>

---

template <class Key, class Compare = less<Key>, class Allocator = allocator<Key>> class set

有序唯一键集合。

• 输入: Key — 键类型; Compare — 比较器; Allocator — 分配器
• 输出: set 对象
• 注意: 键即值，基于红黑树实现

---

pair<iterator, bool> insert(const value_type& x)

插入元素。

• 输入: x — 键
• 输出: pair<iterator, bool> — 同 map

---

iterator find(const key_type& x) const

查找键。

• 输入: x — 键
• 输出: iterator — 未找到返回 end()

---

size_type count(const key_type& x) const

统计键出现次数。

• 输入: x — 键
• 输出: size_type — 0 或 1

---

3.8 关联容器 — multimap / multiset

头文件: <map> / <set>

---

class multimap

有序多键值对容器。

• 输入: 同 map
• 输出: multimap 对象
• 注意: 允许重复键; insert 总是成功

---

class multiset

有序多键集合。

• 输入: 同 set
• 输出: multiset 对象
• 注意: 允许重复键

---

3.9 无序关联容器

头文件: <unordered_map>, <unordered_set>

---

template <class Key, class T, class Hash = hash<Key>, class KeyEqual = equal_to<Key>, class Allocator = allocator<pair<const Key, T>>> class unordered_map

哈希表实现的键值对容器。

• 输入: Key — 键类型; T — 值类型; Hash — 哈希函数; KeyEqual — 相等比较
• 输出: unordered_map 对象
• 注意: 平均 O(1) 查找/插入/删除; 元素无序

---

float load_factor() const

返回当前负载因子。

• 输入: 无
• 输出: float — size()/bucket_count()

---

float max_load_factor() const

返回最大负载因子。

• 输入: 无
• 输出: float — 默认通常为 1.0

---

void max_load_factor(float z)

设置最大负载因子。

• 输入: z — 新的最大负载因子
• 输出: void
• 注意: 设置后若当前负载因子超过新值，可能触发 rehash

---

void rehash(size_type n)

设置桶数量为至少 n。

• 输入: n — 桶数量
• 输出: void
• 注意: 使所有迭代器失效

---

void reserve(size_type n)

预留至少容纳 n 个元素的桶数。

• 输入: n — 元素数量
• 输出: void
• 注意: 等同于 rehash(ceil(n / max_load_factor()))

---

hasher hash_function() const

返回哈希函数对象。

• 输入: 无
• 输出: hasher — 哈希函数

---

key_equal key_eq() const

返回键相等比较函数。

• 输入: 无
• 输出: key_equal — 比较函数

---

3.10 容器适配器

头文件: <stack>, <queue>, <priority_queue>

---

template <class T, class Container = deque<T>> class stack

栈（LIFO）。

• 输入: T — 元素类型; Container — 底层容器
• 输出: stack 对象
• 注意: 默认基于 deque; 也可用 vector 或 list

---

bool empty() const

检查是否为空。

• 输入: 无
• 输出: bool

---

size_type size() const

返回元素数量。

• 输入: 无
• 输出: size_type

---

value_type& top()

返回栈顶元素。

• 输入: 无
• 输出: value_type&

---

void push(const value_type& x)

压栈。

• 输入: x — 元素
• 输出: void

---

void pop()

出栈。

• 输入: 无
• 输出: void
• 注意: 不返回值

---

void swap(stack& other) noexcept

交换两个栈。

• 输入: other — 另一个栈
• 输出: void

---

template <class T, class Container = deque<T>> class queue

队列（FIFO）。

• 输入: T — 元素类型; Container — 底层容器
• 输出: queue 对象
• 注意: 默认基于 deque

---

value_type& front()

返回队首元素。

• 输入: 无
• 输出: value_type&

---

value_type& back()

返回队尾元素。

• 输入: 无
• 输出: value_type&

---

void push(const value_type& x)

入队。

• 输入: x — 元素
• 输出: void

---

void pop()

出队。

• 输入: 无
• 输出: void

---

template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type>> class priority_queue

优先队列。

• 输入: T — 元素类型; Container — 底层容器; Compare — 比较器
• 输出: priority_queue 对象
• 注意: 默认基于 vector 和堆; 最大元素在顶部

---

const_reference top() const

返回顶部（最大）元素。

• 输入: 无
• 输出: const_reference

---

void push(const value_type& x)

插入元素。

• 输入: x — 元素
• 输出: void

---

void pop()

移除顶部元素。

• 输入: 无
• 输出: void

---