本周课程主要内容分为：STL体系结构基础介绍、容器之分类与各种测试和分配器之测试，其中容器之分类与各种测试是本周课程的重点难点。
1、STL体系结构基础介绍
6大部件
STL：标准模板库，属于标准库的一部分，包含6大部件，彼此可以组合套用。
1、容器（Containers）：各种数据结构，如：vector、list、deque、set、map。用来存放数据。从实现的角度来看，STL容器是一种class template。
2、算法（algorithms）：各种常用算法，如：sort、search、copy、erase。从实现的角度来看，STL算法是一种function template。
3、迭代器（iterators）：容器与算法之间的胶合剂，是所谓的“泛型指针”。共有五种类型，以及其他衍生变化。从实现的角度来看，迭代器是一种将operator*、operator->、operator++、operator- -等指针相关操作进行重载的class template。所有STL容器都有自己专属的迭代器，只有容器本身才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。
4、仿函数（functors）：行为类似函数，可作为算法的某种策略（policy）。从实现的角度来看，仿函数是一种重载了operator（）的class或class template。一般的函数指针也可视为狭义的仿函数。
5、配接器（adapters）；一种用来修饰容器、仿函数、迭代器接口的东西。例如：STL提供的queue和stack，虽然看似容器，但其实只能算是一种容器配接器，因为它们的底部完全借助deque，所有操作都由底层的deque供应。改变functors接口者，称为function adapter；改变Container接口者，称为container adapter；改变iterator接口者，称为iterator adapter。
6、配置器（allocators）：负责空间配置与管理。从实现的角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的class template。
6大部件关系
STL6大部件之间的关系：container（容器）通过allocator（配置器）取得数据储存空间，algorithm（算法）通过iterator（迭代器）存取container（容器）内容，functor（仿函数）可以协助algorithm（算法）完成不同的策略变化，adapter（配接器）可以修饰或套接functor（仿函数）。
2、容器之分类与各种测试
2.1 课堂知识
（1）容器结构与分类
STL容器主要分为序列式和关联式。
（2）各类容器
主要包括array、vector、list、deque、set、map、multiset、multimap、unordered_set、unordered_map、unordered_multiset、unordered_multimap等容器，介绍各种容器的测试程序，测试内容包括元素大小、容器内存大小、查找元素所需时间等。
（3）总结
将上述内容进行总结如下：
a、序列式容器放入元素用c.push_back()或者c.push_front()，关联式容器放入元素用c.insert()；
b、对于元素扩充：容器array不能扩充，容器vector2倍扩充，容器list依次扩充，容器deque每次扩充一个buffet；
c、两种查找方法：全局查找::find()，在全局中循序查找，花费时间较短；调用容器sort再查找，花费时间较长，因为大部分时间花在sort上；
d、clock()得到运行到此刻的时间，两次用韵该函数可以得到某一步或某几步程序所花费的时间；
e、容器set和map中放入元素不能重复，但是由于set中key就是value，map中key和value组成一个pair，因此1000000个元素中value是重复的，key不重复，导致set.size不是1000000，而map.size是1000000；
f、编程小技巧：
2.2 课后补充学习
1、顺序性容器
（1）vector
vector是一种动态数组，在内存中具有连续的存储空间，支持快速随机访问。由于具有连续的存储空间，所以在插入和删除操作方面，效率比较慢。vector有多个构造函数，默认的构造函数是构造一个初始长度为0的内存空间，且分配的内存空间是以2的倍数动态增长的，即内存空间增长是按照20,21,22,23.....增长的，在push_back的过程中，若发现分配的内存空间不足，则重新分配一段连续的内存空间，其大小是现在连续空间的2倍，再将原先空间中的元素复制到新的空间中，性能消耗比较大，尤其是当元素是非内部数据时(非内部数据往往构造及拷贝构造函数相当复杂)。vector的另一个常见的问题就是clear操作。clear函数只是把vector的size清为零，但vector中的元素在内存中并没有消除，所以在使用vector的过程中会发现内存消耗会越来越多，导致内存泄露，现在经常用的方法是swap函数来进行解决： vector V;
V.push_back(1); V.push_back(2);V.push_back(1); V.push_back(2);
vector().swap(V); 或者 V.swap(vector());
利用swap函数，和临时对象交换，使V对象的内存为临时对象的内存，而临时对象的内存为V对象的内存。交换以后，临时对象消失，释放内存。
（2）deque
deque和vector类似，支持快速随机访问。二者最大的区别在于，vector只能在末端插入数据，而deque支持双端插入数据。deque的内存空间分布是小片的连续，小片间用链表相连，实际上内部有一个map的指针。deque空间的重新分配要比vector快，重新分配空间后，原有的元素是不需要拷贝的。
（3）list
list是一个双向链表，因此它的内存空间是可以不连续的，通过指针来进行数据的访问，这使list的随机存储变得非常低效，因此list没有提供[]操作符的重载。但list可以很好地支持任意地方的插入和删除，只需移动相应的指针即可。
（4）在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应遵循下面的原则：
1) 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector；
2) 如果你需要大量的插入和删除，而不关心随即存取，则应使用list；
3) 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque。
2、关联容器
（1）map
map是一种关联容器，该容器用唯一的关键字来映射相应的值，即具有key-value功能。map内部自建一棵红黑树（一种自平衡二叉树），这棵树具有数据自动排序的功能，所以在map内部所有的数据都是有序的，以二叉树的形式进行组织。这是map的模板：
template < class Key, class T, class Compare= less, class Allocator=allocator< pair > > class map;
从模板中我们可以看出，再构造map时，是按照一定的顺序进行的。map的插入和删除效率比其他序列的容器高，因为对关联容器来说，不需要做内存的拷贝和移动，只是指针的移动。由于map的每个数据对应红黑树上的一个节点，这个节点在不保存你的数据时，是占用16个字节的，一个父节点指针，左右孩子指针，还有一个枚举值（标示红黑色），所以map的其中的一个缺点就是比较占用内存空间。
（2）set
set也是一种关联性容器，它同map一样，底层使用红黑树实现，插入删除操作时仅仅移动指针即可，不涉及内存的移动和拷贝，所以效率比较高。set中的元素都是唯一的，而且默认情况下会对元素进行升序排列。所以在set中，不能直接改变元素值，因为那样会打乱原本正确的顺序，要改变元素值必须先删除旧元素，再插入新元素。不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取。set模板原型：
template , class Alloc=STL_DEFAULT_ALLOCATOR(Key) > class set;
set支持集合的交(set_intersection)、差(set_difference)、并(set_union)及对称差(set_symmetric_difference) 等一些集合上的操作。
3、容器适配器
（1）queue
queue是一个队列，实现先进先出功能，queue不是标准的STL容器，却以标准的STL容器为基础。queue是在deque的基础上封装的。之所以选择deque而不选择vector是因为deque在删除元素的时候释放空间，同时在重新申请空间的时候无需拷贝所有元素。其模板为：
template < TYPENAME _Sequence="deque<_TP" typeneam _Tp,> > class queue;
（2）stack
stack是实现先进后出的功能，和queue一样，也是内部封装了deque，这也是为啥称为容器适配器的原因吧（纯属猜测）。自己不直接维护被控序列的模板类，而是它存储的容器对象来为它实现所有的功能。stack的源代码原理和实现方式均跟queue相同。
3、分配器之测试
分配器一般搭配在容器中自动使用，可以直接使用分配器，但是没有必要，因为会造成多方面的负担。
做自己的分配器的一些注意事项：
1.需要有自己的一些类型定义比如pointer
2.需要做自己的allocate和deallocate
3.一定要有rebind实现，如果不理解，请看一下标准库里面的list，set等的实现，很容易的。
网友评论