（Boolan） STL与泛型编程第二周笔记
各容器测试(使用方法类似，需要根据上图结构，来选择不同场景使用（可根据容器名查询使用方法）)：
使用容器array: 内存连续
使用容器vector: 内存连续，扩大需要移动, 内存扩大 2部
使用容器list: 内存动态，双向循环链表
使用容器forward_list:内存动态，单向链表 在尾结点插入和删除
使用容器slist: 内存动态，单向链表 在头结点插入和删除
使用容器deque: 双向队列
使用容器stack: 栈是一种容器适配器，后入先出
使用容器queue: 队列
使用容器multiset: 可重复，不使用[]
使用容器multimap:可重复，不使用[]
使用容器unordered_multiset: 可重复，不使用[] （c++ 11新的容器其内部不再采用红黑树实现，而是采用了hash表，加速了检索速度。 ）
使用容器unordered_multimap: 可重复，不使用[] （c++11新的容器其内部不再采用红黑树实现，而是采用了hash表，加速了检索速度。 ）
使用容器set: 不可重复，可使用[]
使用容器map:不可重复，可使用[]
使用容器unordered_set: 不可重复，可使用[]（c++ 11新的容器其内部不再采用红黑树实现，而是采用了hash表，加速了检索速度。 ）
使用容器unordered_map: 不可重复，可使用[]（c++11新的容器其内部不再采用红黑树实现，而是采用了hash表，加速了检索速度。 ）
使用分配器allocator:*分配器
00 源代码分布
标准库STL的文件位置，与所采用的编译器有关：
（1）Visual C++：...\include (例如 D:\Program Files (x86)\Microsoft Visual Studio 14.0\VC \include)
（2）GNU C++：...\4.9.2\inlcude
容器list
1.1 list
G2.9的list：
G4.9的list：
1.2 list的用法
#include
#include
#include
#include
using namespace std;
//创建一个list容器的实例LISTINT
typedef list LISTINT;
//创建一个list容器的实例LISTCHAR
typedef list LISTCHAR;
void main()
{
//用list容器处理整型数据
//用LISTINT创建一个名为listOne的list对象
LISTINT listOne;
//声明i为迭代器
LISTINT::iterator i;
//从前面向listOne容器中添加数据
listOne.push_front (2);
listOne.push_front (1);
//从后面向listOne容器中添加数据
listOne.push_back (3);
listOne.push_back (4);
//从前向后显示listOne中的数据
cout<<"listOne.begin()--- listOne.end():"<
for (i = listOne.begin(); i != listOne.end(); ++i)
cout << *i << " ";
cout << endl;
//从后向后显示listOne中的数据
LISTINT::reverse_iterator ir;
cout<<"listOne.rbegin()---listOne.rend():"<
for (ir =listOne.rbegin(); ir!=listOne.rend();ir++) {
cout << *ir << " ";
}
cout << endl;
//使用STL的accumulate(累加)算法
int result = accumulate(listOne.begin(), listOne.end(),0);
cout<<"Sum="<
cout<<"------------------"<
//--------------------------
//用list容器处理字符型数据
//--------------------------
//用LISTCHAR创建一个名为listOne的list对象
LISTCHAR listTwo;
//声明i为迭代器
LISTCHAR::iterator j;
//从前面向listTwo容器中添加数据
listTwo.push_front ('A');
listTwo.push_front ('B');
//从后面向listTwo容器中添加数据
listTwo.push_back ('x');
listTwo.push_back ('y');
//从前向后显示listTwo中的数据
cout<<"listTwo.begin()---listTwo.end():"<
for (j = listTwo.begin(); j != listTwo.end(); ++j)
cout << char(*j) << " ";
cout << endl;
//使用STL的max_element算法求listTwo中的最大元素并显示
j=max_element(listTwo.begin(),listTwo.end());
cout << "The maximum element in listTwo is: "<
}
1.3 list的iterator
G2.9的iterator：
Paste_Image.png
G4.9相较于G2.9
模板参数只有一个（易理解）；
node结构有其parent；
node的成员的type较精确；
2.OOP（Object-Oriented programming） VS GP（Generic programming）
OOP企图将datas和methods关联在一起
这里的list不能使用::sort()排序，这是因为::sort()算法设计中的Iterator必须是RandomAccessIterator，而list并不是一个连续空间， 在内存中它是由指针一个一个串起来，不能使用指针加法减法。 因此list不能使用::sort()排序。
GP却是将datas和methods分开来，两者之间通过迭代器联系在一起。
两者分开的优点：
（1）Containers和Algorithms团队可各自闭门造车，其间以Iterator沟通即可；
（2）Algorithms通过Iterators确定操作范围 ，并通过Iterators取用Container元素。
补充：
所有的algorithms，最终设计元素本身的操作，无非就是比大小。 比如说重新定义max函数，根据字符长度来比大小，我们就必须重写一个比较函数。
3.源代码阅读
基础：
（1）Operator Overloading 操作符重载
（2）Templates 模板
3.1操作符重载、模板、特化和偏特化
这部分内容在之前额课程中已经讲过，不再赘述。
3.2分配器
分配器（Allocator）是容器管理内存的工具，在容器申请内存空间上起作用。
分配器在底层实现上通过operator new()和operator delete()来完成内存分配和释放，而operator new()和operator delete()实际上是通过调用malloc() 和free()函数来实现操作。
operator new()和operator delete()的源代码如下：
3.2.1 VC6的allocator
VC6所附的标准库，其allocator实现如下（）
3.2.2 BC5的allocator
BC5所附的标准库，其allocator实现如下（）
3.2.3 G2.9的allocator
G2.9所附的标准库，其allocator实现如下（）
3.2.4 G4.9的allocator
G4.9所附的标准库，其allocator实现如下：
由以上各编译器中allocator的源代码可以看出，无论是VC、BC还是GNU的版本中分配器实际上是通过operator new和operator delete来调用malloc和free来管理内存。
但是在GNU2.9中，容器实际使用的并非是allocator，而是alloc，如下图所示。
alooc的最终实现内存管理也是通过malloc和free，但是可以避免其他额外开销，比如cookie，实现过程如下：
（1）设计了16条链表，每条链表负责某种特定大小的区块， 比如第0条链表负责8个字节大小的区块，第1条负责16个字节，以此类推，即（标号数+1）*8；
（2）容器的元素大小都会调整到8的倍数，比如50的会调整到56，然后交给第6条链表负责；
（3）分配器查看链条有没有挂内存块，如果没有，向操作系统要内存，得到的内存块除了头尾有cookie，中间的每一小块内存都不带cookie；
实现过程示意图如下图所示：
在GNU4.9版本以后，分配器也直接调用了operator new来分配内存，之前2.9中的alloc放入了extention allocators中，也就是__pool_alloc，如下图所示：
3.3容器的结构与分类
课件里面将容器的结构和分类讲得很清楚，具体如下图所示：
