C++ STL 容器体系与内存管理深度解析

关联容器

关联容器基于键值存储，允许快速查找。分为有序和无序两类。

有序关联容器（红黑树实现）

包括 std::set, std::multiset, std::map, std::multimap。底层均为自平衡二叉搜索树（红黑树）。

• 特性：元素按键排序，操作复杂度为 O(log n)。
• 迭代器稳定：插入删除不影响其他迭代器。
• 区别：set/map 键唯一，multiset/multimap 允许重复键。map 支持 operator[] 自动创建键，而 multimap 不支持。

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

无序关联容器（哈希表实现）

C++11 引入，包括 unordered_set, unordered_map 等。基于哈希表，平均时间复杂度 O(1)。

• 机制：维护桶数组，负载因子超过阈值时触发扩容（重新哈希）。
• 风险：扩容会导致所有迭代器失效。最坏情况下（哈希冲突严重）退化为 O(n)。
• 模板参数：需指定哈希函数对象和键相等比较器。

template<class Key,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator<Key>>
class unordered_map;

容器适配器

适配器基于其他容器封装，限制接口以满足特定数据结构需求。

std::stack & std::queue

• Stack：后进先出（LIFO），默认底层容器为 deque。
• Queue：先进先出（FIFO），默认底层容器为 deque。
• 内存管理：完全依赖底层容器，无独立内存管理逻辑。

std::priority_queue

基于堆结构（默认最大堆），底层通常为 vector。

• 特性：仅能访问优先级最高元素（堆顶），不支持随机访问。
• 操作：插入和删除堆顶均为 O(log n)。

其他容器

std::bitset

固定大小位集，用于位操作。

• 内存：按机器字长分组存储，极度节省空间。
• 操作：支持位运算、置位、清零及统计置位数量 (count)。

std::valarray

专为数值计算设计的数组，支持元素级数学运算。

• 优化：设计时考虑无别名假设，便于编译器优化循环融合。
• 局限：不支持自定义分配器，现代编译器对其优化潜力未完全实现，常被 vector 替代。

#include <valarray>
#include <iostream>

int main() {
    std::valarray<int> va = {1, 2, 3, 4};
    va += 5; // 元素级加法
    std::cout << va.sum() << std::endl; // 输出 30
    return 0;
}