STL使用常见的容器序列式容器string结构char* size capacity扩容机制不同编译器不同VS1.5 倍扩容GCC2 倍扩容clear清空有效字符(不改变空间大小)resize(n,c),有效字符改为n个,扩大空间时并把多出空间置为creserve(n)预留空间到n个,nsize时不改变空间大小模拟实现vector结构由三个迭代器组成(随机访问迭代器)templateclassTclassvector{public:// 迭代器原生指针typedefT*iterator;private:iterator _start;// 空间头iterator _finish;// 有效数据尾iterator _endofstorage;// 可用空间尾};扩容倍数:VS1.5倍,gcc2倍过程:单独申请一块连续空间把原有数据拷贝到新空间释放原有空间扩容会导致迭代器失效:空间地址完全变了list迭代器(双向迭代器)只能±-,不能n,-n,[]每次插入或者删除一个元素就配置或者释放一个空间原有的迭代器不会失效只需要一个指向node节点的指针即可deque迭代器(随机访问迭代器)deque 是分段连续的双端队列包含T*_cur;// 当前指向的元素T*_first;// 当前缓冲区的头T*_last;// 当前缓冲区的尾T**_map;// 指向中控 map 的指针底层是 分段连续的空间不是一整块数组)扩容高效迭代器不会失效关联式容器map/set底层红黑树平衡二叉搜索树特点key 有序中序遍历有序key 不可重复插入 / 删除 / 查找 O(logN)迭代器双向迭代器 / --区别set只有 keymapkey valuepair迭代器失效插入不会失效删除只有被删节点迭代器失效其他都有效unordered_map/unordered_set底层哈希表拉链法 / 开链法特点key 无序key 不可重复插入 / 删除 / 查找 O (1) 平均迭代器单向 / 向前迭代器区别unordered_set只有 keyunordered_mapkey value迭代器失效插入触发 rehash 扩容全部迭代器失效删除只有被删迭代器失效容器适配器stack底层用deque维护queue底层用deque维护priority_queue底层用vector维护向上向下调整算法迭代器迭代器失效问题序列式容器vector/deque插入和删除元素之后迭代器会失效erase会返回下一个有效的迭代器关联式容器map/set删除后当前元素的迭代器失效只需要在删除前记录一下下一个元素的迭代器即可为什么要有迭代器借助迭代器可以在不清楚对象内部表示的情况下按照一种顺序访问每一个元素迭代器不是指针但是可以像指针一样进行元素访问是对于原生指针的封装简单来说是可以在不暴露内部结构的前提下循环遍历元素的效果常见的算法find线性查找元素find(起始迭代器, 结束迭代器, 目标值)reverse将迭代器范围内的元素原地反转。reverse(起始迭代器, 结束迭代器)sort对迭代器范围内的元素原地排序默认升序。sort(起始迭代器, 结束迭代器, 比较函数/仿函数/lambda)swap交换两个对象或容器的内容。swap(a, b)lower_bound/upper_bound二分查找要求序列有序lower_bound(起始迭代器, 结束迭代器, 目标值)在升序序列中找第一个 ≥ 目标值的位置。lower_bound(起始迭代器, 结束迭代器, 目标值)在升序序列中找第一个 目标值的位置。next_permutation生成下一个字典序排列存在下一个排列返回 true并修改序列为下一个排列。不存在下一个排列已是最后一个排列返回 false并将序列重置为第一个排列升序。next_permutation(起始迭代器, 结束迭代器)…原理六大组件容器多种数据结构容器就是一种模板类算法算法是一种模板函数迭代器进行容器和算法之间的粘合剂泛型指针也是模板类适配器一种用来修饰容器或仿函数或迭代器接口的东西仿函数行为类似函数可以作为算法的策略重载了()空间配置器一个实现了动态空间配置管理释放的模板类