（Boolan） STL与泛型编程第一周笔记
1.源代码分布
标准库STL的文件位置，与所采用的编译器有关：
（1）Visual C++：...\include (例如 D:\Program Files (x86)\Microsoft Visual Studio 14.0\VC \include)
（2）GNU C++：...\4.9.2\inlcude
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容器的结构与分类
课件里面将容器的结构和分类讲得很清楚，具体如下图所示：
3.4 容器list
3.4.1 list
G2.9的list：
G4.9的list：
3.4.2 list的iterator
G2.9的iterator：
G4.9相较于G2.9：
模板参数只有一个（易理解）；
node结构有其parent；
node的成员的type较精确；
具体如下图所示：
1.C++标准库和STL
C++标准库以header files形式呈现：
（1）C++标准库的header files不带副档名（.h），例如#include
（2）新式C header files 不带副档名.h，例如#include
（3）旧式C header files （带有副档名.h）仍然可用，例如#include
（4）新式headers内的组件封装于namespace “std”
using namespace std；或者以 using std::cout;的形式
（5）旧式headers 内的组件不封装于namespace "std"
在标准库中，标准模板库STL（Standard Template Library），占据了标准库70%，80%以上的内容。
STL的核心思想是泛型编程（Generic Programming）。
重要资源：
网站：
书籍：
The C++ standard Library second edition；
STL 源码剖析
使用示例：
#include
#include
#include
#include
using namespace std;
int main()
{
int ia[6] = { 27, 210, 12,47, 109, 83 }；
vector> vi(ia, ia + 6);
cout << count_if(vi.begin(), vi.end(),
not1(bind2nd（less(), 40)));
return 0;
}
Paste_Image.png
3.容器的相关知识
3.1容器的结构与分类
容器按在内存中的存储结构分为三种：顺序容器（Sequence Container）、关联容器（Associative Container）、和无序容器（Unordered Container）。 其中的无序容器是C++ 11提出的，实际上无序容器也属于关联容器，使用哈希表构成。
Paste_Image.png
3.2顺序容器
顺序容器：它将单一类型元素聚集起来成为容器，然后根据位置来存储和访问这些元素。
标准库提供了一下几种顺序容器：array、vector、list、forward_list、slist、deque、stack和queue，他们的差别在于访问元素访问元素的方式， 以及添加或删除元素相关操作的运行代价。 array是C++11的新内容，功能比内置数组更加强大，可以以对象为单位存储数据，vector支持快速随机访问，list支持快速插入/删除，deque是一个双端队列， queue和stack在STL中都是基于deque来实现。
3.2.1顺序容器的常用操作
容器定义的操作非常少，只定义了构造函数、添加或删除元素的操作、设置容器长度的操作以及返回指向特殊元素的迭代器的操作。 其他一些有用的操作，如排序、查找，则不是由容器类型定义，而是由标准算法定义。
（1）begin和end成员
begin 和 end 操作产生指向容器内第一个元素和最后一个元素的下一位置的迭代器，这两个迭代器通常用于标记包含容器中所有元素的迭代器范围。
Paste_Image.png
（2）添加元素
Paste_Image.png
（3）大小操作
Paste_Image.png
（4）访问元素
Paste_Image.png
（5）删除元素
Paste_Image.png
（6）swap交换操作
swap 操作实现交换两个容器内所有元素的功能。 要交换的操作数必须是相同类型的容器，而且所存储的元素类型也必须相同。 调用了 swap 函数后，右操作数原来存储的元素被存放在左操作数中，反之亦然。 该操作不会删除或插入任何元素，而且保证在常量时间内实现交换。 由于容器内没有移动任何元素，因此迭代器不会失效。
根据课程举几个使用例子：
Paste_Image.png
Paste_Image.png
Paste_Image.png
作者获得授权，非商业转载请注明出处。
3.3关联容器
在STL中关联容器使用红黑树来实现，因为不是顺序结构，因而不能使用上面提到的push和pop函数，使用insert和erase函数来实现元素的插入删除操作。
关联容器支持通过键来高效地查找和读取元素，两个基本的关联容器类型是map和set。 map的元素以键-值（key-value）对的形式组织：键用于元素在map中的索引，而值则表示所存储和读取的数据。 set仅包含一个键，并有效地支持关于某个键是否存在的查询。 map可理解为字典，set可理解为一类元素的集合。
关联容器和顺序容器的本质差别在于：关联容器通过键（key）存储和读取元素，而顺序容器则通过元素在容器中的位置顺序存储和访问元素。
et 和 map 类型的对象所包含的元素都具有不同的键，不允许为同一个键添加第二个元素。 如果一个键必须对应多个实例，则需使用 multimap 或 multi set，这两种类型允许多个元素拥有相同的键。
根据课程举几个例子：
Paste_Image.png
3.4无序容器
严格意义上讲，无序容器也属于关联容器。
Paste_Image.png
Paste_Image.png
