跳到主要内容C++ STL 容器详解：序列、关联与适配器 | 极客日志C++算法
C++ STL 容器详解：序列、关联与适配器
本文详细介绍了 C++ STL 标准模板库中的各类容器。涵盖序列容器（如 vector、deque、list）、关联容器（如 set、map、unordered_map）及容器适配器（如 stack、queue）。内容包含各容器的底层内存结构、时间复杂度分析、核心操作特性及模板参数说明，帮助开发者根据场景选择合适的数据结构。
概述
本文详细介绍 C++ 标准模板库（STL）中的各类容器，涵盖序列容器、关联容器及容器适配器。内容包含各容器的底层内存结构、时间复杂度分析、核心操作特性及模板参数说明。
序列容器
- std::vector：动态数组，支持快速随机访问。
- std::deque：双端队列，支持高效的首尾插入/删除。
- std::list：双向链表，支持高效插入/删除。
- std::forward_list：单向链表（C++11 引入），内存开销更小。
- std::array：固定大小数组（C++11 引入），编译时确定大小。
关联容器
有序关联容器
std::set
std::multiset：允许多个相同键的集合。std::map：键值对映射，键唯一。std::multimap：允许多个相同键的映射。无序关联容器（C++11 引入，基于哈希表）
- std::unordered_set：哈希实现的唯一键集合。
- std::unordered_multiset：哈希实现的可重复键集合。
- std::unordered_map：哈希实现的键值对映射（键唯一）。
- std::unordered_multimap：哈希实现的可重复键映射。
容器适配器
- std::stack：栈（LIFO 后进先出），默认基于 deque。
- std::queue：队列（FIFO 先进先出），默认基于 deque。
- std::priority_queue：优先队列，元素按优先级排序，默认基于 vector。
其他容器
- std::bitset：固定大小位集，用于位操作。
- std::valarray：数值数组，优化数值计算（较少使用）。
std::vector 数据结构与内存管理
1. 底层结构
- 连续内存块：元素在内存中紧密排列。
- 三指针逻辑（典型实现）：
begin_ptr → 内存起始位置size_ptr → 当前元素末尾（size()）capacity_ptr → 内存块末尾（capacity()）
2. 插入操作
| 场景 | 操作步骤 | 时间复杂度 |
|---|
| 尾部空间充足 | 1. 在 size_ptr 处构造元素
2. size_ptr 后移 | O(1) |
| 空间不足需扩容 | 1. 分配新内存（容量：GCC×2 / MSVC×1.5）
2. 迁移数据（优先移动语义）
3. 释放旧内存 | 均摊 O(1) |
| 中间插入 | 1. 移动后续元素腾出空间
2. 构造新元素 | O(n) |
3. 删除操作
| 类型 | 操作步骤 | 时间复杂度 |
|---|
| 尾部删除 | 1. 销毁末尾元素
2. size_ptr 前移 | O(1) |
| 中间删除 | 1. 销毁目标元素
2. 向前移动后续元素覆盖空隙 | O(n) |
4. 关键特性
- 内存策略：
- 扩容：指数增长（避免频繁重分配）
- 不自动缩容：
erase 不释放内存
- 迭代器失效：
| 操作 | 复杂度 | 适用性 |
|---|
| 随机访问 | O(1) | ★★★★★ |
| 尾部操作 | 均摊 O(1) | ★★★★★ |
| 中间操作 | O(n) | ★☆☆☆☆ |
v.shrink_to_fit();
std::vector<int>().swap(v);
std::deque 核心知识点总结
一、基础概念与特性
- 容器类型：C++ STL 中的双端队列（double-ended queue）。
- 访问特性：支持随机访问（通过
operator[] 或 at()）。
- 动态扩展：两端插入/删除操作高效，时间复杂度为 O(1)。
- 底层实现：基于分段连续存储结构（多个固定大小的数组块 + 中央控制块）。
二、内存管理机制
| 特性 | 说明 |
|---|
| 默认分配器 | std::allocator<T> |
| 分段存储结构 | 由多个固定大小的数组块组成（典型块大小 512 bytes - 4KB） |
| 中央控制映射器 | 维护指向所有块的指针数组（动态扩容时重新分配） |
| 内存分配策略 | 插入时：两端直接使用预留空间或分配新块；中间移动元素 |
| 扩容机制 | 中央指针数组满时重新分配（通常翻倍） |
| 非连续内存 | 元素物理存储非连续，但逻辑连续 |
三、核心操作特性
| 操作 | 时间复杂度 | 说明 |
|---|
| 头尾插入/删除 | O(1) | push_front()/pop_front() push_back()/pop_back() |
| 随机访问 | O(1) | operator[] 或 at() 直接访问元素 |
| 中间插入/删除 | O(n) | insert()/erase() 需移动元素 |
| 迭代器操作 | O(1) | 支持随机访问迭代器（++, --, +n 等） |
四、模板参数
template<class T, class Allocator = std::allocator<T>>
class deque;
std::list 核心知识点总结
一、基础概念与特性
- 容器类型：C++ STL 中的双向链表容器。
- 存储结构：每个元素存储在独立的节点中，节点包含数据值、前驱节点指针、后继节点指针。
- 迭代器特性：支持双向迭代器（可前向/后向遍历）。
二、内存管理机制
| 特性 | 说明 |
|---|
| 默认分配器 | std::allocator<T> |
| 节点内存分配 | 每个元素独立分配内存（包含数据 + 两个指针） |
| 分配触发时机 | push_back/push_front/insert 时分配新节点 |
| 内存释放时机 | pop_back/pop_front/erase 时立即释放节点 |
| 内存碎片 | 高频插入删除可能产生内存碎片 |
| 连续内存 | ❌ 元素在内存中非连续存储 |
三、核心操作特性
| 操作 | 时间复杂度 | 说明 |
|---|
| 头尾插入/删除 | O(1) | push_front()/pop_front() push_back()/pop_back() |
| 任意位置插入 | O(1) | insert(iterator_pos, value)（只需修改相邻节点指针） |
| 任意位置删除 | O(1) | erase(iterator_pos)（只需修改相邻节点指针） |
| 元素查找 | O(n) | 必须从头/尾开始遍历 |
| 迭代器稳定性 | ✅ 稳定 | 插入/删除操作不会使其他迭代器失效（除被删除元素的迭代器） |
四、特殊成员函数
- 链表拼接：
splice()：将其他链表的元素移动到当前链表（O(1) 时间复杂度）。
mylist.splice(mylist.end(), otherlist);
std::forward_list 核心知识点总结
一、基础概念与特性
- 单向链表结构：C++11 引入的单向链表容器，每个节点包含数据值和指向下一节点的指针。
- 最小化内存开销：相比
std::list 节省内存（每个节点少一个指针）。
- 迭代器特性：仅支持前向迭代器（不可反向遍历）。
二、内存管理机制
| 特性 | 说明 |
|---|
| 默认分配器 | std::allocator<T> |
| 节点结构 | { data, next_ptr }（仅含数据域和单向指针） |
| 内存分配 | 插入操作时动态分配新节点（如 push_front, insert_after） |
| 内存释放 | 删除操作立即释放节点内存（如 pop_front, erase_after） |
| 内存碎片 | 高频插入删除可能产生碎片（但比 std::list 碎片少 25%） |
三、核心操作特性
| 操作 | 时间复杂度 | 说明 |
|---|
| 头部插入 | O(1) | push_front() 在链表头插入新元素 |
| 指定位置后插入 | O(1) | insert_after(pos) 在迭代器 pos 后插入元素 |
| 头部删除 | O(1) | pop_front() 删除首元素 |
| 指定位置后删除 | O(1) | erase_after(pos) 删除 pos 后元素 |
| 元素查找 | O(n) | 必须从头节点开始顺序遍历 |
| 迭代器稳定性 | ✅ 稳定 | 插入/删除操作不影响其他迭代器（除被删元素的迭代器） |
四、特殊成员函数
- 首前迭代器：
before_begin()：返回首元素前的虚拟节点迭代器（用于首元素操作）。
auto it = flist.before_begin();
flist.insert_after(it, 42);
std::array 核心知识点总结
一、基础概念与特性
- 固定大小数组容器：C++11 引入的静态连续数组容器，封装原生数组。
- 内存分配方式：元素在栈内存或全局/静态存储区分配（与原生数组相同）。
- 零额外开销：相比原生数组，不增加任何空间或时间开销（编译期确定大小）。
二、模板参数与声明
template<class T, std::size_t N>
class array;
std::set 核心知识点总结
一、基础概念与特性
- 有序关联容器：存储唯一键值（无重复元素）并自动按键排序。
- 红黑树实现：基于红黑树（自平衡二叉搜索树）实现，保证操作效率。
- 自动排序机制：元素始终按键升序排列（默认
std::less<Key>）。
二、内存管理机制
| 特性 | 说明 |
|---|
| 默认分配器 | std::allocator<Key> |
| 节点内存分配 | 每个元素独立分配内存（含数据 + 父/子指针 + 颜色标志） |
| 分配触发时机 | insert() 操作时动态分配新节点 |
| 内存释放时机 | erase() 操作时立即释放节点内存 |
| 内存布局 | 树形结构存储，节点间非连续内存 |
三、核心操作特性
| 操作 | 时间复杂度 | 说明 |
|---|
| 插入元素 | O(log n) | insert(key) 或 emplace(args) |
| 删除元素 | O(log n) | erase(key) 或 erase(iterator) |
| 查找元素 | O(log n) | find(key)/contains(key)（C++20） |
| 范围查询 | O(log n) | lower_bound()/upper_bound() 实现高效范围扫描 |
| 迭代器稳定性 | ✅ 稳定 | 插入/删除操作不影响其他迭代器（除被删元素的迭代器） |
四、模板参数
template<class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key>>
class set;
std::multiset 核心知识点总结
一、基础概念与特性
- 有序关联容器：存储可重复键值的集合，元素自动按键排序。
- 红黑树实现：基于红黑树（自平衡二叉搜索树）实现。
- 自动排序机制：元素始终按键升序排列（默认
std::less<Key>）。
二、内存管理机制
| 特性 | 说明 |
|---|
| 默认分配器 | std::allocator<Key> |
| 节点结构 | 每个节点包含：键值数据、父/子节点指针、红黑树颜色标志 |
| 内存分配 | insert() 操作时动态分配新节点 |
| 内存释放 | erase() 操作时立即释放节点内存 |
| 内存布局 | 树形结构存储，节点间非连续内存 |
| 内存占用 | 每个节点额外开销约 3 指针 + 1 bool（通常 16-32 字节） |
三、核心操作特性
| 操作 | 时间复杂度 | 说明 |
|---|
| 插入元素 | O(log n) | insert(key) 可重复插入相同键值 |
| 删除元素 | O(log n) | erase(key) 删除所有匹配键值；erase(iterator) 删除指定元素 |
| 元素计数 | O(log n) | count(key) 返回匹配键值的元素数量 |
| 范围查询 | O(log n) | equal_range(key) 获取相同键值元素的范围迭代器对 |
| 迭代器稳定性 | ✅ 稳定 | 插入/删除操作不影响其他迭代器 |
四、模板参数
template<class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key>>
class multiset;
std::map 核心知识点总结
一、基础概念与特性
- 容器类型：C++ STL 中的有序关联容器，存储键值对（key-value pairs）。
- 排序特性：元素始终按键（key）自动排序（默认升序）。
- 键唯一性：每个键在
std::map 中唯一（不允许重复键）。
- 底层实现：基于红黑树（自平衡二叉搜索树）实现，保证操作效率。
二、内存管理机制
| 特性 | 说明 |
|---|
| 默认分配器 | std::allocator<std::pair<const Key, T>> |
| 内存分配方式 | 动态分配（堆内存），每个节点独立分配 |
| 分配触发时机 | 插入新元素时为键值对分配内存；删除时释放对应内存 |
| 内存布局 | 树形结构存储，每个节点包含：父/子指针、颜色标志、键值对数据 |
| 连续内存 | ❌ 元素在内存中非连续存储，迭代器遍历可能产生缓存未命中 |
三、核心操作特性
| 操作 | 时间复杂度 | 说明 |
|---|
| 插入 | O(log n) | insert() 或 emplace() 添加新元素 |
| 查找 | O(log n) | find()/count()/contains()（C++20） |
| 删除 | O(log n) | erase() 移除指定键或迭代器位置元素 |
| 访问 | O(log n) | operator[] 访问或创建元素；at() 边界检查访问 |
| 范围查询 | O(log n) | lower_bound()/upper_bound() 实现高效范围扫描 |
四、模板参数与自定义
template<class Key, class T, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<const Key, T>>>
class map;
std::multimap 核心知识点总结
一、基础概念与特性
- 有序关联容器：存储可重复键值对（允许相同键对应多个值）。
- 红黑树实现：基于红黑树（自平衡二叉搜索树）实现。
- 自动排序机制：元素始终按键升序排列（默认
std::less<Key>）。
二、内存管理机制
| 特性 | 说明 |
|---|
| 默认分配器 | std::allocator<std::pair<const Key, T>> |
| 节点结构 | 每个节点包含：键值对数据、父/子节点指针、红黑树颜色标志 |
| 内存分配 | insert() 操作时动态分配新节点 |
| 内存释放 | erase() 操作时立即释放节点内存 |
| 内存布局 | 树形结构存储，节点间非连续内存 |
三、与 std::map 的关键区别
| 特性 | std::multimap | std::map |
|---|
| 键唯一性 | ❌ 允许重复键 | ✅ 键必须唯一 |
| 插入行为 | 总是成功（不覆盖） | 键存在时插入失败或覆盖值 |
| operator[] | ❌ 不支持 | ✅ 支持（自动创建键） |
| 查找返回值 | 返回匹配键的范围迭代器 | 返回单个元素迭代器 |
| 典型应用场景 | 一对多关系（如电话簿同名条目） | 键值唯一映射（如 ID 映射） |
四、核心操作特性
| 操作 | 时间复杂度 | 说明 |
|---|
| 插入元素 | O(log n) | insert({key, value}) 可重复插入相同键值对 |
| 删除元素 | O(log n) | erase(key) 删除所有匹配键值；erase(iterator) 删除指定元素 |
| 键值查找 | O(log n) | find(key) 返回首个匹配键值的迭代器 |
| 范围查询 | O(log n) | equal_range(key) 获取相同键值的迭代器范围 |
| 元素计数 | O(log n) | count(key) 返回匹配键值的元素数量 |
五、特殊成员函数
- 键值范围访问：
equal_range(key)：获取相同键值的迭代器范围。
auto [first, last] = phonebook.equal_range("Alice");
for (auto it = first; it != last; ++it)
std::cout << it->second;
std::unordered_set 核心知识点总结
一、基础概念与特性
- 无序关联容器：C++11 引入的哈希集合，存储唯一键值（无重复元素）。
- 哈希表实现：基于哈希表（链地址法或开放寻址法）实现。
- 无序存储：元素存储顺序不固定，取决于哈希函数和桶分布。
二、内存管理机制
| 特性 | 说明 |
|---|
| 默认分配器 | std::allocator<Key> |
| 桶数组结构 | 维护动态数组存储桶指针（桶即链表头节点或开放寻址槽位） |
| 节点内存分配 | 插入时动态分配节点（含键值 + 链表指针） |
| 扩容机制 | 当负载因子（元素数/桶数）超过阈值（默认 1.0）时：1. 桶数组翻倍扩容 2. 所有元素重新哈希到新桶 |
| 内存释放 | erase() 立即释放节点内存；桶数组在对象销毁时释放 |
三、核心操作特性
| 操作 | 平均复杂度 | 最坏复杂度 | 说明 |
|---|
| 插入元素 | O(1) | O(n) | insert(key) 或 emplace(args) |
| 删除元素 | O(1) | O(n) | erase(key) 或 erase(iterator) |
| 查找元素 | O(1) | O(n) | find(key)/contains(key)（C++20） |
| 迭代器稳定性 | ❌ 不稳定 | - | 扩容操作使所有迭代器失效 |
四、模板参数
template<class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator<Key>>
class unordered_set;
std::unordered_multiset 核心知识点总结
一、基础概念与特性
- 无序关联容器：存储可重复键值的集合，元素顺序由哈希函数决定。
- 哈希表实现：基于链式哈希表实现（数组 + 链表冲突解决）。
- 快速查找特性：平均时间复杂度 O(1)，最坏情况 O(n)。
二、内存管理机制
| 特性 | 说明 |
|---|
| 默认分配器 | std::allocator<Key> |
| 桶数组结构 | 动态数组存储桶指针（初始大小由实现定义） |
| 节点内存分配 | 每个元素独立分配节点（含键值 + 链表指针） |
| 动态扩容 | 当负载因子 (元素数/桶数) > max_load_factor()（默认 1.0）时：桶数组扩容（通常翻倍）、重新哈希所有元素 |
| 内存释放 | erase() 立即释放节点内存；桶数组在对象销毁时释放 |
三、核心操作特性
| 操作 | 平均复杂度 | 最坏复杂度 | 说明 |
|---|
| 插入元素 | O(1) | O(n) | insert(key) 允许重复插入相同键值 |
| 删除元素 | O(1) | O(n) | erase(key) 删除所有匹配键值；erase(iterator) 删除指定元素 |
| 元素计数 | O(n) | O(n) | count(key) 返回匹配键值的元素数量 |
| 范围查询 | O(n) | O(n) | equal_range(key) 获取相同键值元素的范围迭代器对 |
四、模板参数
template<class Key, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator<Key>>
class unordered_multiset;
std::unordered_map 核心知识点总结
一、基础结构
- 数组槽位：哈希表的第一维是数组结构，称为"槽"(slots) 或"桶"(buckets)。每个槽存储键值对或冲突处理结构（链表/树的头节点）。
二、容量机制
- 初始容量：创建时指定（如 Java HashMap 默认 16，Go map 默认 8）。未指定时采用语言/库默认值。
- 动态扩容：
- 触发条件：元素数量 >
当前容量 × 负载因子（通常 0.5-0.75）
- 扩容策略：倍增策略（容量翻倍，如 16 → 32，保持 2 的幂）；质数策略（取大于 2 倍容量的最小质数）
- 扩容后需重新哈希所有元素
三、内存分配机制
| 场景 | 内存分配行为 |
|---|
| 首次初始化 | ✅ 分配初始数组内存 |
| 触发扩容时 | ✅ 分配新数组内存 |
| 链表法插入新键 | ✅ 分配节点内存 |
| 开放寻址法插入新键 | ❌ 使用预分配槽位 |
| 更新已存在键的值 | ❌ 不分配新内存 |
四、冲突处理策略
- 链表法：每个槽位维护链表结构存储冲突元素。插入新键必分配节点内存。
- 开放寻址法：所有元素直接存储在数组槽位中。通过线性探测/二次探测解决冲突。插入新键通常不分配额外内存。
std::unordered_multimap 核心知识点总结
一、基础概念与特性
- 无序关联容器：C++11 引入的哈希键值对容器，允许重复键值（同键可对应多个值）。
- 哈希表实现：基于链式哈希表实现（数组 + 链表冲突解决）。
- 无序存储特性：元素顺序由哈希函数决定，遍历时无固定顺序。
二、内存管理机制
| 特性 | 说明 |
|---|
| 默认分配器 | std::allocator<std::pair<const Key, T>> |
| 桶数组结构 | 动态数组存储桶指针（初始大小由实现定义） |
| 节点内存分配 | 插入时动态分配节点（含键值对 + 链表指针） |
| 动态扩容 | 当负载因子 (元素数/桶数) > max_load_factor()（默认 1.0）时：1. 桶数组扩容（通常翻倍）2. 所有元素重新哈希到新桶 |
| 内存释放 | erase() 立即释放节点内存；桶数组在对象销毁时释放 |
三、核心操作特性
| 操作 | 平均复杂度 | 最坏复杂度 | 说明 |
|---|
| 插入元素 | O(1) | O(n) | insert({key, value}) 允许重复键值对插入 |
| 删除元素 | O(1) | O(n) | erase(key) 删除所有匹配键值；erase(iterator) 删除指定元素 |
| 键值查找 | O(1) | O(n) | find(key) 返回首个匹配键值的迭代器 |
| 范围查询 | O(1) | O(n) | equal_range(key) 获取相同键值的迭代器范围 |
| 迭代器稳定性 | ❌ 不稳定 | - | 扩容操作使所有迭代器失效 |
四、模板参数
template<class Key, class T, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>, class Allocator = std::allocator<std::pair<const Key, T>>>
class unordered_multimap;
std::stack 核心知识点总结
一、基础概念与特性
- 容器适配器：C++ STL 中的栈结构容器适配器，提供后进先出（LIFO）操作接口。
- 底层容器依赖：基于其他序列容器实现（默认使用
std::deque）。
- 受限访问：仅允许在栈顶进行插入和删除操作。
二、内存管理机制
| 特性 | 说明 |
|---|
| 底层容器决定内存 | 内存管理完全由底层容器（如 std::deque）负责 |
| 默认底层容器 | std::deque（分段连续存储，动态扩容） |
| 内存分配行为 | 遵循底层容器的分配策略：push() 可能触发扩容；pop() 释放元素内存 |
| 无独立内存管理 | 作为适配器不直接管理内存，完全依赖底层容器实现 |
三、核心操作接口
| 操作 | 时间复杂度 | 说明 |
|---|
| 入栈 | O(1) | push(value) 在栈顶插入元素 |
| 出栈 | O(1) | pop() 移除栈顶元素（不返回值） |
| 访问栈顶 | O(1) | top() 返回栈顶元素引用（空栈调用导致未定义行为） |
| 容量查询 | O(1) | size() 返回元素数量 empty() 判断是否为空 |
四、模板参数与自定义
template<class T, class Container = std::deque<T>>
class stack;
std::queue 核心知识点总结
一、基础概念与特性
- 容器适配器：C++ STL 中的队列结构容器适配器，提供先进先出（FIFO）操作接口。
- 底层容器依赖：基于其他序列容器实现（默认使用
std::deque）。
- 受限访问：仅允许在队尾插入元素，队头删除元素。
二、内存管理机制
| 特性 | 说明 |
|---|
| 底层容器决定内存 | 内存管理完全由底层容器（如 std::deque）负责 |
| 默认底层容器 | std::deque（分段连续存储，动态扩容） |
| 内存分配行为 | 遵循底层容器的分配策略：push() 可能触发扩容；pop() 释放元素内存 |
| 无独立内存管理 | 作为适配器不直接管理内存，完全依赖底层容器实现 |
三、核心操作接口
| 操作 | 时间复杂度 | 说明 |
|---|
| 入队 | O(1) | push(value) 在队尾插入元素 |
| 出队 | O(1) | pop() 移除队头元素（不返回值） |
| 访问队头 | O(1) | front() 返回队头元素引用（空队列调用导致未定义行为） |
| 访问队尾 | O(1) | back() 返回队尾元素引用 |
| 容量查询 | O(1) | size() 返回元素数量 empty() 判断是否为空 |
四、模板参数与自定义
template<class T, class Container = std::deque<T>>
class queue;
std::priority_queue 核心知识点总结
一、基础概念与特性
- 容器适配器：C++ STL 中的优先级队列容器适配器，提供基于优先级的元素访问。
- 堆结构实现：底层实现为二叉堆数据结构（默认最大堆）。
- 访问特性：仅能访问堆顶元素（优先级最高元素），不支持随机访问或迭代器遍历。
二、内存管理机制
| 特性 | 说明 |
|---|
| 底层容器决定内存 | 内存管理由底层容器（默认 std::vector）负责 |
| 堆结构特性 | 元素以完全二叉树形式存储，满足堆序性质 |
| 内存分配行为 | 遵循底层容器的分配策略：push() 可能触发扩容；pop() 释放元素内存 |
| 默认容器 | std::vector（连续内存存储，支持高效随机访问） |
| 扩容机制 | 当底层 vector 容量不足时：1. 分配新内存 2. 迁移元素并重建堆 |
三、核心操作接口
| 操作 | 时间复杂度 | 说明 |
|---|
| 插入元素 | O(log n) | push(value) 插入元素并调整堆结构 |
| 删除堆顶 | O(log n) | pop() 移除堆顶元素并调整堆结构 |
| 访问堆顶 | O(1) | top() 返回堆顶元素引用（空队列调用导致未定义行为） |
| 容量查询 | O(1) | size() 返回元素数量 empty() 判断是否为空 |
四、模板参数与自定义
template<class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type>>
class priority_queue;
std::bitset 核心知识点总结
一、基础概念与特性
- 固定大小位集合：C++ STL 提供的固定长度位数组容器，用于高效处理二进制标志位。
- 编译时确定大小：大小
N 在编译时指定，无法运行时动态改变。
- 内存高效存储：每个位仅占 1 bit 空间，无额外内存开销。
二、内存管理机制
| 特性 | 说明 |
|---|
| 内存分配位置 | 栈内存（或作为成员变量时随对象分配） |
| 内存布局 | 连续内存块存储，按机器字长（word）分组 |
| 内存计算 | 总内存 = ceil(N / (sizeof(WordType) * CHAR_BIT)) * sizeof(WordType) |
| 无动态内存 | 不涉及堆内存分配，无析构释放操作 |
示例：std::bitset<64> 在 64 位系统占用 8 字节（64/8=1 word）；std::bitset<65> 在 64 位系统占用 16 字节（65/64≈2 words）。
三、核心操作接口
| 操作 | 说明 |
|---|
| 位访问 | operator[] 访问特定位；test(pos) 带边界检查访问 |
| 位设置 | set(pos) 置位；reset(pos) 清零；flip(pos) 翻转 |
| 批量操作 | set() 全置位；reset() 全清零；flip() 全翻转 |
| 位运算 | 支持 &, ` |
| 转换操作 | to_ulong()/to_ullong() 转整数；to_string() 转二进制字符串 |
四、特殊功能
std::bitset<8> bs(0b10101010);
bs.count();
std::valarray 详细说明
概述
std::valarray 是 C++ 标准库中的一个类模板，用于表示和操作数值数组，支持元素级数学运算和各种下标访问方式。它旨在优化数值计算，避免别名问题，并允许编译器进行循环融合等优化。
关键点
- 设计目的：专为高效数值数组操作设计，支持元素级运算、切片和间接访问，但不提供标准迭代器（如 vector）。
- 优化特性：操作可能返回代理对象以减少临时对象，支持并行化和循环优化，但实际实现中优化程度有限。
- 内存管理：元素连续存储在动态分配的数组中，默认构造函数不分配内存，其他构造函数根据大小分配；resize 可改变大小，可能导致重新分配。
- 限制：模板参数 T 需为数值类型（如算术类型或 std::complex）；不支持自定义分配器。
- 争议与使用：虽标准但使用较少，常被 vector 或其他库取代；研究表明其性能优化在现代编译器中未充分实现，但适合简单数值任务。
基本用法
std::valarray 的实例化如 std::valarray<double> va(5);，创建大小为 5 的数组，所有元素默认初始化。支持如 va += 2.0; 的元素级运算，返回新 valarray 或修改原对象。
优势与注意事项
优势在于内置数学函数（如 sum、min）和运算符重载，便于数值代码编写。注意：resize 会使指针/引用失效；操作假设无别名以优化，但需小心使用。
构造函数
- 默认构造函数：
valarray()，创建空数组（大小 0），不分配内存。
- 大小指定：
valarray(size_t count)，分配 count 个元素，每个元素值初始化（默认构造）。
- 值初始化：
valarray(const T& val, size_t count)，分配 count 个元素，每个拷贝自 val。
- 数组拷贝：
valarray(const T* ptr, size_t count)，从 ptr 指向的数组拷贝 count 个元素。
- 初始化列表（C++11）：
valarray(initializer_list<T> ilist)，从列表初始化，大小为列表长度。
- 拷贝/移动构造函数：
valarray(const valarray&) 和 valarray(valarray&&)，分配与源相同大小的存储，并拷贝/移动元素。
成员函数
- 赋值：
operator=，赋值内容，可能导致重新分配。
- 访问：
operator[]，返回元素引用、切片（slice_array）或掩码子数组（mask_array）。
- 一元运算符：
operator+、operator-、operator~、operator!，对每个元素应用，返回新 valarray。
- 复合赋值：
operator+= 等，对每个元素应用，返回 *this。
- 交换：
swap，常数时间交换内容，不失效引用。
- 大小：
size，返回元素数。
- 调整大小：
resize(size_t new_size) 或 resize(size_t new_size, const T& val)，改变大小；若增大，新增元素默认/值初始化；若缩小，销毁多余元素；失效指针/引用。
- 聚合：
sum、min、max，计算总和、最小/最大值。
- 移位：
shift（零填充移位）、cshift（循环移位）。
- 应用函数：
apply，对每个元素应用指定函数，返回新 valarray。
示例
#include <valarray>
#include <iostream>
int main() {
std::valarray<int> va = {1, 2, 3, 4};
va += 5;
std::cout << va.sum() << std::endl;
va.resize(2);
return 0;
}
表格：常见成员函数总结
| 函数 | 描述 | 返回类型 | 注意事项 |
|---|
| size | 返回元素数 | size_t | 常量时间 |
| resize | 改变大小 | void | 可能失效引用 |
| sum | 元素总和 | T | 假设 T 支持 + |
| min/max | 最小/最大 | T | 假设 T 支持 < |
| apply | 应用函数 | valarray | 返回新数组 |
| shift/cshift | 移位 | valarray | shift 零填充，cshift 循环 |
| swap | 交换 | void | 常数时间，不失效引用 |
表格：运算符支持
| 类型 | 示例 | 行为 |
|---|
| 一元 | +va, -va | 新 valarray，元素应用 |
| 二元 | va1 + va2 | 新 valarray，元素级 |
| 复合 | va += scalar | 修改 va |
| 比较 | va1 == va2 | bool valarray，元素级 |
| 数学 | std::sin(va) | 新 valarray，元素应用 |
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown 转 HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
- HTML 转 Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
