本文介绍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); }方法二函数里开辟同样大小空间再使用函数交换两空间指针vectorT operator (vectorT v) { swap(v); return *this; } void swap(vectorT 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 等C11 引入。底层是桶数组 开链法一个指针数组每个桶挂一条链表或红黑树冲突严重时自动切换。查找时先算 hash(key) % bucket_count 定位桶再在链表里线性搜索。平均复杂度 O(1)但最坏 O(n)——所有元素哈希到同一个桶时退化成链表。负载因子size / bucket_count超过阈值默认 1.0时触发 rehash分配更大的桶数组把所有节点重新哈希到新桶里。