各容器测试(使用方法类似，需要根据上图结构，来选择不同场景使用（可根据容器名查询使用方法）)：
使用容器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 <iostream>
#include <list>
#include <numeric>
#include <algorithm>
using namespace std;
//创建一个list容器的实例LISTINT
typedef list<int> LISTINT;
//创建一个list容器的实例LISTCHAR
typedef list<int> 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():"<<endl;
for (i = listOne.begin(); i != listOne.end(); ++i)
cout << *i << " ";
cout << endl;
//从后向后显示listOne中的数据
LISTINT::reverse_iterator ir;
cout<<"listOne.rbegin()---listOne.rend():"<<endl;
for (ir =listOne.rbegin(); ir!=listOne.rend();ir++) {
cout << *ir << " ";
}
cout << endl;
//使用STL的accumulate(累加)算法
int result = accumulate(listOne.begin(), listOne.end(),0);
cout<<"Sum="<<result<<endl;
cout<<"------------------"<<endl;
//--------------------------
//用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():"<<endl;
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: "<<char(*j)<<endl;
}
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实现如下（<xmemory>）
3.2.2 BC5的allocator
BC5所附的标准库，其allocator实现如下（<memory.stl>）
3.2.3 G2.9的allocator
G2.9所附的标准库，其allocator实现如下（<defalloc.h>）
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容器的结构与分类
课件里面将容器的结构和分类讲得很清楚，具体如下图所示：
网友评论