)
本文介绍c++标准模板库（STL）
一、STL的组成
STL提供了一套通用模板类和函数，主要包含三个部分：
容器：比如vector、list、map，用来存储和管理数据
算法：比如sort、find，用来对容器里的数据进行各种操作
迭代器：充当容器与算法之间的“胶水”，让算法能通用化的访问容器的数据
二、深拷贝
在了解STL前，我们需要了解什么是深拷贝构造。
1、为什么需要深拷贝
编译器自动生成的默认拷贝构造是逐字节复制，如果对象里有指针，那么浅拷贝只会复制指针本身，而不是复制指针指向的内存。
结果就是：两个对象指向同一块空间。一旦一个对象被销毁，另一个指针就会变成野指针。
2、如何深拷贝
方法一：
//深拷贝 string(const string& s) :_str(new char[strlen(s._str)+1])//浅拷贝：_str(s._str);//两种拷贝的区别就在于是否开辟空间 { strcpy(_str, s._str); }方法二：
函数里开辟同样大小空间，再使用函数交换两空间指针
vector<T>& operator =(vector<T> v) { swap(v); return *this; } void swap(vector<T>& v) { ::swap(start, v.start); ::swap(finish, v.finish); ::swap(endofstorage, v.endofstorage); }三、迭代器
1、迭代器的底层实际是只读指针
例：string迭代器的使用
string::iterator it = s1.begin(); while (it != s1.end()) { *it -= 1; ++it; }迭代器提供了标准化遍历方法，让遍历容器不再需要关心容器底层数据结构。
2、迭代器失效
erase(),insert()在调用后，迭代器会失效
原因：
迭代器指向的地址仍然有效，但该地址上存储的元素已经不是原来的元素了。例如 vector 删除中间元素后，后续元素整体前移，原迭代器指向的位置被新元素填充。
迭代器失效后有可能正常运行，也可能崩溃报错：
例如，vector在增容时，会开辟一块新的内存空间，原来的空间上的数据会被拷贝到新空间，旧空间销毁，旧的迭代器此时指向旧空间指针，迭代器变成了野指针！但是如果是删除或者增加，迭代器本身还是有效的，但是由于更改位置之后的迭代器所指元素已经改变，视为失效。
四、容器
容器：容纳数据的数据结构
第一种：连续内存结构
代表是 vector 和 string。底层就是一块连续的堆内存，用三个指针管理：start（起始）、finish（当前末尾）、end_of_storage（容量末尾）。迭代器就是原生指针 T*，++it 就是指针加一，*it 就是解引用。
它的优势是缓存友好——CPU 预取器能猜到你要访问下一块内存，所以遍历速度极快。劣势是扩容代价大：容量不够时要分配新内存、搬移所有元素、释放旧内存，这个过程是 O(n)。 deque 也属于这一类，但它不是单一连续块，而是"分段连续"：一个中控数组（指针数组），每个指针指向一块固定大小的缓冲区。
这样它能在头部和尾部都做到 O(1) 插入，代价是迭代器不能是简单指针，必须封装成包含"当前缓冲区指针 + 缓冲区内偏移"的结构体，++it 时要判断是否跨越缓冲区边界。
第二种：节点式链表结构
代表是 list（双向链表）和 forward_list（单向链表）。每个元素独立分配在堆上，节点之间通过指针链接。迭代器是对 Node* 的轻量包装，++it 本质是 node = node->next。
它的优势是插入删除 O(1)——只需要改指针链接，不动其他节点的内存。劣势是遍历慢：节点散落在堆的各个角落，Cache Miss 率极高，实际遍历速度可能比 vector 慢一个数量级。
第三种：平衡二叉搜索树
代表是 map、set、multimap、multiset。底层是红黑树，每个节点包含 key、value、左子指针、右子指针、父指针、颜色标记。迭代器遍历本质是树的中序遍历——先递归左子树，再访问当前节点，再递归右子树，所以遍历结果是有序的。
红黑树不追求绝对平衡（像 AVL 树那样），而是通过"红黑规则"保证最长路径不超过最短路径的两倍。这样插入删除时的旋转次数比 AVL 少，写入性能更好，查询性能略差但仍在 O(log n)。
第四种：哈希表
代表是 unordered_map、unordered_set 等（C++11 引入）。底层是桶数组 + 开链法：一个指针数组，每个桶挂一条链表（或红黑树，冲突严重时自动切换）。查找时先算 hash(key) % bucket_count 定位桶，再在链表里线性搜索。
平均复杂度 O(1)，但最坏 O(n)——所有元素哈希到同一个桶时退化成链表。负载因子（size / bucket_count）超过阈值（默认 1.0）时触发 rehash：分配更大的桶数组，把所有节点重新哈希到新桶里。
