C++ STL 容器详解：序列、关联与适配器

概述

本文详细介绍 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; // 输出所有 Alice 的电话

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()` 转二进制字符串

四、特殊功能

位统计：count() 返回置位（1）的数量。

std::bitset<8> bs(0b10101010);
bs.count(); // 返回 4

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&&)，分配与源相同大小的存储，并拷贝/移动元素。

析构函数 ~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; // 元素级加法：{6, 7, 8, 9}
    std::cout << va.sum() << std::endl; // 输出 30
    va.resize(2); // 变为 {6, 7}
    return 0;
}

此示例展示基本运算和 resize。

表格：常见成员函数总结

函数	描述	返回类型	注意事项
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，元素应用

概述

序列容器

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; // 输出所有 Alice 的电话

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()` 转二进制字符串

四、特殊功能

位统计：count() 返回置位（1）的数量。

std::bitset<8> bs(0b10101010);
bs.count(); // 返回 4

std::valarray 详细说明

概述

关键点

设计目的：专为高效数值数组操作设计，支持元素级运算、切片和间接访问，但不提供标准迭代器（如 vector）。
优化特性：操作可能返回代理对象以减少临时对象，支持并行化和循环优化，但实际实现中优化程度有限。
内存管理：元素连续存储在动态分配的数组中，默认构造函数不分配内存，其他构造函数根据大小分配；resize 可改变大小，可能导致重新分配。
限制：模板参数 T 需为数值类型（如算术类型或 std::complex）；不支持自定义分配器。
争议与使用：虽标准但使用较少，常被 vector 或其他库取代；研究表明其性能优化在现代编译器中未充分实现，但适合简单数值任务。

基本用法

优势与注意事项

优势在于内置数学函数（如 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&&)，分配与源相同大小的存储，并拷贝/移动元素。

析构函数 ~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; // 元素级加法：{6, 7, 8, 9}
    std::cout << va.sum() << std::endl; // 输出 30
    va.resize(2); // 变为 {6, 7}
    return 0;
}

此示例展示基本运算和 resize。

表格：常见成员函数总结

函数	描述	返回类型	注意事项
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，元素应用