【数据结构】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. 插入操作‌

‌3. 删除操作‌

‌4. 关键特性‌

• ‌内存策略‌：
  • 扩容：指数增长（避免频繁重分配）
  • 不自动缩容：erase不释放内存
• ‌迭代器失效‌：
  • 扩容或中间插入/删除导致迭代器失效

‌性能对比‌：

手动释放：

v.shrink_to_fit();// 请求释放多余内存vector<int>().swap(v);// 强制释放所有内存

std::deque 核心知识点总结

一、基础概念与特性

1. ‌容器类型‌
   C++ STL 中的‌双端队列‌（double-ended queue）
2. ‌访问特性‌
   支持‌随机访问‌（通过 operator[] 或 at()）
3. ‌动态扩展‌
   两端插入/删除操作高效，时间复杂度为 ‌O(1)‌
4. ‌底层实现‌
   基于‌分段连续存储‌结构（多个固定大小的数组块 + 中央控制块）

二、内存管理机制

‌内存布局示例‌：

三、核心操作特性

四、模板参数

template<classT,// 元素类型classAllocator= std::allocator<T>// 分配器类型>classdeque;

std::list 核心知识点总结

一、基础概念与特性

1. ‌容器类型‌
   C++ STL 中的‌双向链表‌容器
2. ‌存储结构‌
   每个元素存储在独立的节点中，节点包含：
   • 数据值
   • 前驱节点指针
   • 后继节点指针
3. ‌迭代器特性‌
   支持‌双向迭代器‌（可前向/后向遍历）

二、内存管理机制

‌节点结构示例‌：

三、核心操作特性

四、特殊成员函数

1. ‌链表拼接‌
   splice()：将其他链表的元素移动到当前链表（O(1)时间复杂度）
   // 将other链表的全部元素移动到当前链表末尾
   mylist.splice(mylist.end(), otherlist);

std::forward_list 核心知识点总结

一、基础概念与特性

1. ‌单向链表结构‌
   C++11 引入的‌单向链表‌容器，每个节点包含数据值和指向下一节点的指针
2. ‌最小化内存开销‌
   相比 std::list 节省内存（每个节点少一个指针）
3. ‌迭代器特性‌
   仅支持‌前向迭代器‌（不可反向遍历）

二、内存管理机制

‌节点结构示例‌：

三、核心操作特性

四、特殊成员函数

1. ‌首前迭代器‌
   before_begin()：返回首元素前的虚拟节点迭代器（用于首元素操作）
   auto it = flist.before_begin();
   flist.insert_after(it, 42); // 在链表头插入

std::array 核心知识点总结

一、基础概念与特性

1. ‌固定大小数组容器‌
   C++11 引入的‌静态连续数组‌容器，封装原生数组
2. ‌内存分配方式‌
   元素在‌栈内存‌或‌全局/静态存储区‌分配（与原生数组相同）
3. ‌零额外开销‌
   相比原生数组，不增加任何空间或时间开销（编译期确定大小）

二、模板参数与声明

template<classT,// 元素类型 std::size_t N // 数组固定大小>classarray;

关联容器（基于键值存储，允许快速查找）
‌有序关联容器‌（元素按键排序）：

std::set 核心知识点总结

一、基础概念与特性

1. ‌有序关联容器‌
   存储‌唯一键值‌（无重复元素）并自动按键排序
2. ‌红黑树实现‌
   基于‌红黑树‌（自平衡二叉搜索树）实现，保证操作效率
3. ‌自动排序机制‌
   元素始终‌按键升序排列‌（默认std::less<Key>）

二、内存管理机制

‌节点结构示例‌：

三、核心操作特性

四、模板参数

template<classKey,// 元素类型（必须支持严格弱序比较）classCompare= std::less<Key>,// 比较器（默认升序）classAllocator= std::allocator<Key>// 内存分配器>classset;

std::multiset 核心知识点总结

一、基础概念与特性

1. ‌有序关联容器‌
   存储‌可重复键值‌的集合，元素自动按键排序
   set是多了判断是否重复
2. ‌红黑树实现‌
   基于‌红黑树‌（自平衡二叉搜索树）实现
3. ‌自动排序机制‌
   元素始终‌按键升序排列‌（默认std::less<Key>）

二、内存管理机制

‌节点结构示例‌：

三、核心操作特性

四、模板参数

template<classKey,// 元素类型（必须支持严格弱序比较）classCompare= std::less<Key>,// 比较器（默认升序）classAllocator= std::allocator<Key>// 内存分配器>classmultiset;

std::map 核心知识点总结

一、基础概念与特性

1. ‌容器类型‌
   C++ STL 中的‌有序关联容器‌，存储键值对（key-value pairs）
2. ‌排序特性‌
   元素始终‌按键（key）自动排序‌（默认升序）
3. ‌键唯一性‌
   每个键在 std::map 中‌唯一‌（不允许重复键）
4. ‌底层实现‌
   基于‌红黑树‌（自平衡二叉搜索树）实现，保证操作效率

二、内存管理机制

示例节点结构（简化）：

三、核心操作特性

四、模板参数与自定义

template<classKey,// 键类型（必须支持严格弱序比较）classT,// 值类型classCompare= std::less<Key>,// 比较器（默认升序）classAllocator= std::allocator<std::pair<const Key, T>>// 内存分配器>classmap;

std::multimap 核心知识点总结

一、基础概念与特性

1. ‌有序关联容器‌
   存储‌可重复键值对‌（允许相同键对应多个值）
2. ‌红黑树实现‌
   基于‌红黑树‌（自平衡二叉搜索树）实现
3. ‌自动排序机制‌
   元素始终‌按键升序排列‌（默认std::less<Key>）

二、内存管理机制

‌节点结构示例‌：

三、与 std::map 的关键区别

四、核心操作特性

五、特殊成员函数

1. ‌键值范围访问‌
   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 核心知识点总结

一、基础概念与特性

1. ‌无序关联容器‌
   C++11 引入的‌哈希集合‌，存储‌唯一键值‌（无重复元素）
   相比unordered_map 仅存key 且不支持【】访问
2. ‌哈希表实现‌
   基于‌哈希表‌（链地址法或开放寻址法）实现
3. ‌无序存储‌
   元素存储顺序‌不固定‌，取决于哈希函数和桶分布

二、内存管理机制

‌典型节点结构‌（链地址法）：

三、核心操作特性

四、模板参数

template<classKey,// 键类型classHash= std::hash<Key>,// 哈希函数对象classKeyEqual= std::equal_to<Key>,// 键相等比较器classAllocator= std::allocator<Key>// 分配器>classunordered_set;

std::unordered_multiset 核心知识点总结

一、基础概念与特性

1. ‌无序关联容器‌
   存储‌可重复键值‌的集合，元素顺序由哈希函数决定
2. ‌哈希表实现‌
   基于‌链式哈希表‌实现（数组 + 链表冲突解决）
3. ‌快速查找特性‌
   平均时间复杂度 O(1)，最坏情况 O(n)

二、内存管理机制

‌节点结构‌：

三、核心操作特性

四、模板参数

template<classKey,// 键类型classHash= std::hash<Key>,// 哈希函数对象classKeyEqual= std::equal_to<Key>,// 键相等比较器classAllocator= std::allocator<Key>// 分配器>classunordered_multiset;

std::unordered_map：哈希实现的键值对映射（键唯一）

哈希表核心知识点总结

一、基础结构

1. ‌数组槽位‌
   • 哈希表的第一维是数组结构，称为"槽"(slots)或"桶"(buckets)
   • 每个槽存储键值对或冲突处理结构（链表/树的头节点）

二、容量机制

1. ‌初始容量‌
   • 创建时指定（如 Java HashMap 默认 16，Go map 默认 8）
   • 未指定时采用语言/库默认值
2. ‌动态扩容‌
   • 触发条件：元素数量 > 当前容量 × 负载因子（通常 0.5-0.75）
   • 扩容策略：
     • ‌倍增策略‌：容量翻倍（如 16 → 32），保持 2 的幂
     • ‌质数策略‌：取大于 2 倍容量的最小质数
   • 扩容后需‌重新哈希‌所有元素

三、内存分配机制

四、冲突处理策略

1. ‌链表法‌
   • 每个槽位维护链表结构存储冲突元素
   • 插入新键必分配节点内存
2. ‌开放寻址法‌
   • 所有元素直接存储在数组槽位中
   • 通过线性探测/二次探测解决冲突
   • 插入新键通常不分配额外内存

std::unordered_multimap 核心知识点总结

一、基础概念与特性

1. ‌无序关联容器‌
   C++11 引入的‌哈希键值对容器‌，允许‌重复键值‌（同键可对应多个值）
2. ‌哈希表实现‌
   基于‌链式哈希表‌实现（数组 + 链表冲突解决）
3. ‌无序存储特性‌
   元素顺序由‌哈希函数‌决定，遍历时无固定顺序

二、内存管理机制

‌节点结构‌：

三、核心操作特性

四、模板参数

template<classKey,// 键类型classT,// 值类型classHash= std::hash<Key>,// 哈希函数对象classKeyEqual= std::equal_to<Key>,// 键相等比较器classAllocator= std::allocator<std::pair<const Key, T>>// 分配器>classunordered_multimap;

容器适配器（基于其他容器封装）

std::stack 核心知识点总结

一、基础概念与特性

1. ‌容器适配器‌
   C++ STL 中的‌栈结构容器适配器‌，提供后进先出（LIFO）操作接口
2. ‌底层容器依赖‌
   基于其他序列容器实现（默认使用 std::deque）
3. ‌受限访问‌
   仅允许在栈顶进行插入和删除操作

二、内存管理机制

当使用默认 std::deque 时：内存分段存储在固定大小块中动态扩容时分配新内存块不释放已分配的内存块直到对象销毁

三、核心操作接口

四、模板参数与自定义

template<classT,// 元素类型classContainer= std::deque<T>// 底层容器类型>classstack;

std::queue 核心知识点总结

一、基础概念与特性

1. ‌容器适配器‌
   C++ STL 中的‌队列结构容器适配器‌，提供先进先出（FIFO）操作接口
2. ‌底层容器依赖‌
   基于其他序列容器实现（默认使用 std::deque）
3. ‌受限访问‌
   仅允许在队尾插入元素，队头删除元素

二、内存管理机制

当使用默认 std::deque 时：内存分段存储在固定大小块中动态扩容时分配新内存块不释放已分配的内存块直到对象销毁

三、核心操作接口

四、模板参数与自定义

template<classT,// 元素类型classContainer= std::deque<T>// 底层容器类型>classqueue;

std::priority_queue 核心知识点总结

一、基础概念与特性

1. ‌容器适配器‌
   C++ STL 中的‌优先级队列‌容器适配器，提供基于优先级的元素访问
2. ‌堆结构实现‌
   底层实现为‌二叉堆‌数据结构（默认最大堆）
3. ‌访问特性‌
   • 仅能访问堆顶元素（优先级最高元素）
   • 不支持随机访问或迭代器遍历

二、内存管理机制

‌内存布局示例‌（最大堆）：

三、核心操作接口

四、模板参数与自定义

template<classT,// 元素类型classContainer= std::vector<T>,// 底层容器classCompare= std::less<typenameContainer::value_type>// 比较器>classpriority_queue;

std::bitset 核心知识点总结

一、基础概念与特性

1. ‌固定大小位集合‌
   C++ STL 提供的‌固定长度位数组‌容器，用于高效处理二进制标志位
2. ‌编译时确定大小‌
   大小 N 在编译时指定，无法运行时动态改变
3. ‌内存高效存储‌
   每个位仅占 1 bit 空间，无额外内存开销

二、内存管理机制

‌示例‌：
std::bitset<64> 在 64 位系统占用 8 字节（64/8=1 word）
std::bitset<65> 在 64 位系统占用 16 字节（65/64≈2 words）

三、核心操作接口

四、特殊功能

‌位统计‌
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 会使指针/引用失效；操作假设无别名以优化，但需小心使用。

std::valarray 详细说明

引言

std::valarray 是 C++ 标准库（头文件 <valarray>）中的类模板，用于表示数值数组并支持高效的元素级数学操作。它允许元素 wise 的算术运算、逻辑运算和各种下标操作，包括切片（slice）和间接访问（indirect）。 该类设计时考虑了无别名假设，类似于 C 语言的 restrict 关键字，从而允许编译器优化，如循环融合。 表达式如 v1 = a * v2 + v3; 可被优化为单次循环遍历。一些实现（如 GNU libstdc++ 和 LLVM libc++）内部使用表达式模板，但进一步优化较少见。 valarray 适合数值计算，但实际使用中常被 std::vector 或第三方库（如 Eigen）替代，因为其优化潜力在现代编译器中未完全实现。

valarray 的模板参数 T 必须满足 NumericType 要求，通常为算术类型、指针或类似 std::complex 的类。 它不支持标准容器接口（如迭代器），但 C++11 引入了 std::begin 和 std::end 的重载。

成员类型

• value_type：T，即存储元素的类型。

构造函数

std::valarray 提供多种构造函数，用于创建空数组或初始化数组：

• 默认构造函数：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。

非成员函数

• 交换（C++11）：std::swap(std::valarray)。
• 迭代器（C++11）：std::begin、std::end，返回指向开始/结束的指针。
• 二元运算符：operator+ 等，元素级应用，返回新 valarray。
• 比较运算符：operator== 等，元素级比较，返回 bool valarray。
• 数学函数：abs、exp、log、pow、sqrt、sin、cos 等，元素级应用，返回新 valarray。

运算符

• 一元：成员函数形式，对元素应用。
• 复合赋值：成员函数，修改自身。
• 二元：非成员，元素级运算，支持 valarray 与 valarray 或 scalar。
• 比较：非成员，返回 bool valarray。

内存分配与管理

std::valarray 的元素存储在连续的动态分配数组中，类似于 std::vector 但无完整迭代器支持。 默认构造函数不分配内存。 其他构造函数根据指定大小在堆上分配连续块，并初始化元素。 resize 操作可能导致重新分配：若新大小大于当前，分配更多空间并初始化新增元素；若小于，销毁多余元素并可能释放内存。 实现可能使用 copy-on-write 或 copy-on-reference 优化以减少拷贝。 无自定义分配器支持；resize 或赋值失效所有指针/引用。 一些实现（如 Microsoft）提供非标准 free() 以释放存储。

辅助类与高级特性

• 切片与子数组：使用 std::slice、std::gslice、slice_array、gslice_array、mask_array、indirect_array 支持子集操作。
• 模板参数推导（C++17）：支持从初始化列表等推导 T。
• 并行化潜力：设计允许操作并行执行，但依赖实现。

示例

#include<valarray>#include<iostream>intmain(){ 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}return0;}

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

表格：常见成员函数总结

表格：运算符支持