STLSTLStandard Template Library标准模板库C 标准库一部分基于模板实现复用数据结构与算法代码STL 六大组件容器 container各类数据结构存放数据vector、list、map…算法 algorithm通用算法排序、查找、拷贝等迭代器 iterator容器和算法之间的桥梁类似指针用来遍历容器元素仿函数 functor重载()的类行为像函数给算法提供自定义策略适配器 adapter包装其他组件修改接口stack、queue 就是容器适配器空间配置器 allocator负责内存空间分配、释放、管理组件交互关系容器依靠空间配置器申请内存算法通过迭代器访问容器里的数据仿函数给算法提供自定义策略适配器用来修饰容器 / 仿函数 / 迭代器接口三大核心组件三大核心容器、算法、迭代器容器分为序列式容器和关联式容器序列式容器元素位置由插入顺序决定元素是有序排列但值不一定有序1vector、deque、list、forward_list关联式容器容器内部自带排序规则元素位置由元素值 / 键值决定自动有序1map、set、multimap、multiset算法分为质变算法、非质变算法质变算法运算过程修改容器区间内元素内容1例copy、replace、sort非质变算法运算不会修改元素只做查找、统计、遍历1例find、count、for_each只读版本迭代器迭代器是算法访问容器的统一接口不同容器迭代器能力不同双向迭代器支持、--可以向前、向后遍历不支持随机跳跃1list、map、set 的迭代器随机访问迭代器继承双向迭代器能力额外支持n、-n、[]可以直接跳跃访问元素1vector、deque 的迭代器三大组件关系总结容器负责存储数据并对外提供迭代器算法通过迭代器间接操作容器里面的元素算法本身不依赖具体容器STL 工作机制核心原理1STL 的核心思想容器负责存数据并且对外提供迭代器begin ()、end ()算法不直接访问容器只通过迭代器区间[begin, end)来遍历、操作元素2[begin, end) 左闭右开区间begin 指向第一个元素end 指向最后一个元素的下一个位置end 位置不存储有效数据//模拟数组容器 template class T class MyArray { public: //迭代器把原生指针T* 别名叫做iterator typedef T* iterator; MyArray() { mCapacity 10; //容量 总空间大小 mSize 10; // 有效元素个数 p new T[mCapacity]; //开辟堆内存 for (int i 0; i mCapacity; i) { p[i] i 1; //初始化1,2,3,4....10 } } //begin:返回起始迭代器指向第一个元素 T* begin() { return p; } //end,返回结束迭代器指向末尾下一个位置无有效数据 T* end() { return p mSize; } public: T* p;// 堆数组首地址 int mCapacity; //容量 int mSize; //有效数据数量 }; //算法打印区间元素不依赖MyArray这个容器 //只要求传入一对迭代器 [begin,end] template class T void printArray(T begin, T end) { for (; begin ! end; begin) { cout *begin ; //解引用迭代器拿到元素 } cout endl; } void test1() { MyArrayint arr; //获取迭代器 MyArrayint::iterator begin arr.begin(); MyArrayint::iterator end arr.end(); printArray(begin, end); }重点迭代器本质1迭代器是容器对外暴露的访问接口2对于 list、map迭代器不是原生指针但是用法和指针一样支持*解引用、容器和算法解耦STL 最核心的设计1容器只负责管理内存、存放数据提供begin()和end()拿到迭代器2算法不关心底层是什么容器只接收一对迭代器区间[begin,end)3算法和容器完全分离这就是 STL 的精髓左闭右开区间[begin, end)1begin有效第一个元素2end尾后迭代器不是有效元素是判断循环终止条件3循环条件begin ! endtypedef T* iterator;作用1给指针起别名iterator模仿 STL 标准写法2使用时MyArrayint::iterator和vectorint::iterator写法一模一样STL中的hello world核心vector 容器四种用法存放基础数据类型 int存放自定义类对象存放自定义类指针容器嵌套容器vectorvectorintvector 存放内置数据类型void MyPrint(int val) { cout val ; } void test1() { vectorintv; v.push_back(10); v.push_back(20); v.push_back(30); v.push_back(40); v.push_back(50); vectorint::iterator begin v.begin(); vectorint::iterator end v.end(); //for_each : 遍历算法,接收迭代区间回调函数 for_each(begin, end, MyPrint); cout endl; }for_each 底层伪代码void _For_each(_InIt _First, _InIt _Last, _Fn1 _Func) { for (; _First ! _Last; _First) _Func(*_First); }1for_each 会不断移动迭代器取出元素传给回调函数vector 存放自定义对象重点vectorMaker存放的是对象副本push_back 的时候会拷贝临时对象存入容器class Maker { public : string name; int age; Maker(string name, int age) { this-name name; this-age age; } }; //重载 运算符 支持cout 打印Maker对象 ostream operator(ostream out, Maker m) { out Name: m.name Age: m.age endl; return out; } void test2() { vectorMakerv; //会调用Maker构造函数创建临时对象存入容器拷贝 v.push_back(Maker(悟空, 18)); v.push_back(Maker(小林, 19)); v.push_back(Maker(贝吉塔, 25)); v.push_back(Maker(龟仙人, 21)); v.push_back(Maker(短笛, 29)); vectorMaker::iterator begin v.begin(); vectorMaker::iterator end v.end(); while (begin ! end) { cout (*begin); //*begin 取出Maker对象 begin; } }vector 存放对象指针vectorMaker*class Maker { public : string name; int age; Maker(string name, int age) { this-name name; this-age age; } }; //重载 运算符 支持cout 打印Maker对象 ostream operator(ostream out, Maker m) { out Name: m.name Age: m.age endl; return out; } void test3() { vectorMaker*v; //在堆区创建对象 Maker* m1 new Maker(悟空, 18); Maker* m2 new Maker(小林, 19); Maker* m3 new Maker(贝吉塔, 25); Maker* m4 new Maker(龟仙人, 21); Maker* m5 new Maker(短笛, 29); v.push_back(m1); v.push_back(m2); v.push_back(m3); v.push_back(m4); v.push_back(m5); vectorMaker*::iterator begin v.begin(); vectorMaker*::iterator end v.end(); while (begin ! end) { //*begin 得到的的是Maker*指针 用-访问 cout (*begin)-name (*begin)-age endl; begin; } //堆内存必须手动释放 delete m1; delete m2; delete m3; delete m4; delete m5; }区分1vectorMaker存对象容器销毁自动销毁对象不需要手动 delete2vectorMaker*存指针容器只保存地址不会释放堆上的对象必须手动 delete否则内存泄漏容器嵌套容器vectorvectorint二维数组效果//容器嵌套相当于二维数组 void test4() { vector vectorintvs; vectorintv1; vectorintv2; vectorintv3; vectorintv4; vectorintv5; for (int i 0; i 5; i) { v1.push_back(i 10); v2.push_back(i 10); v3.push_back(i 10); v4.push_back(i 10); v5.push_back(i 10); } vs.push_back(v1); vs.push_back(v2); vs.push_back(v3); vs.push_back(v4); vs.push_back(v5); vectorvectorint::iterator beginvs.begin(); vectorvectorint::iterator end vs.end(); while (begin ! end) { // *begin 得到内层 vectorint vectorint::iterator sbegin (*begin).begin(); vectorint::iterator send (*begin).end(); while (sbegin ! send) { cout *sbegin ; sbegin; } cout endl; begin; } }外层迭代器遍历外层容器解引用*begin拿到内层容器再取内层迭代器遍历