C++标准库
- C++ Standard Library(C++标准库)
- Standard Template Library（STL，标准模板库）
C++标准库>STL，除了对六大类型的封装之外，C++标准库还封装了其他一些东西。
STL六大部件
- 容器 Containers
- 分配器 Allocators
- 算法 Algorithms
- 迭代器 Iterators
- 适配器 Adapters
- 仿函数 Functors
程序=算法+数据结构。数据结构也就是这里的容器，因为容易不需要管内存分配的事情，所以分配器负责这部分。另一部分实现了算法。但是算法不是在容器的类里面的，所以要对容器进行操作需要使用迭代器。另外对类进行加减的行为称为仿函数。适配器可以对容器、迭代器、仿函数进行转换。
问题：
一个程序里面可以用两个using namespace吗？
GP vs. OOP
C++标准库的主要思想并不是OOP（继承关系不是很复杂），而是GP。 OOP是将data和method联系在一起，而GP却是将data和method分开来。它用全局的函数，通过迭代器进行沟通。这样的好处是，containers和algorithm可以分别开发。list容器中有sort函数，而vector和deque没有sort函数，需要使用全局的排序函数。全局的排序函数有对指针直接进行加减乘除的操作，而list是链表，不能这样对指针进行加减乘除。
操作符重载 & 模板是标准库的基础。
模板分为：类模板，函数模板，成员模板。
模板还分为泛化，全特化和偏特化。
容器
分类：
- Sequence Containers
- Assosiative Containers(主要用于查找，主要用红黑树实现set/map)
- Unordered Container(实际还是一种Assoiative Containers, C++11, 用hashtable实现，开链法)
这个图展示了各种容器之间的基层与衍生层的关系，这里的衍生并非继承，而是复合。
蓝色的框里展示的是一个对象的大小，不包含数据。
Sequence Containers
array
array的实现比vector更简单，它的具体实现如下图：
array的data就是 _M_instance[_Nm ? _Nm : 1],类型是value_type，就是传入的第一个模板参数。
vector
vector是前开后闭的。
vector只有一个push_back()，因为如果从前面插入的话，后面所有的元素都要挪动位置。
增长的速度是2倍2倍地增长。先从另外一个地方找一个两倍大的空间，然后把原来的都搬过来，所以成长的速度比较慢。可以使用size()和capacity()来看当前的实际大小和分配的空间大小。
vector 的具体实现有三个指针：start, finish, end_of_storage
下面这个图展示了vector的成员变量和一些函数。
因为vector是连续存储，所以vector的迭代器实际上是指针。
list
首先看List类，包括一个link_type的node，link_type是个list_node*，也就是个指针，所以list包括了一个指针，所以大小为4(G2.9). 然后看list_node包括两个指针，prev和next和数据data，这两个指针指向void*，这意味着这两个指针在使用的时候需要类型转换。后面的版本会改进。
所有的线性容器，除了array之外都是前闭后开的，后开的意思就是最后一个元素不是数据元素。为了实现这个，会加一个空白结点（图中灰色结点）。
list 的 iterator
为了实现iterator像指针一样，必须要对操作符进行重载。主要是对++,–,*,->的重载。这里拿++举例。
因为++i和i++都是单目运算操作符，因此编译器并没有办法区分，因此设计了两个不同的函数，一个是前++operator++()，一个是后++operator++(int)。
先来看图下面的前++，这个函数取当前节点的next指针，然后返回这个指针。
而后++，self tmp = *this这句并不会唤起operator*这个函数，而是会唤起拷贝构造函数，*this被解释为拷贝构造函数的参数。如图中深蓝箭头1所指的函数。 然后再进行++，返回tmp。
另外注意这两个函数的返回值。参考int的++操作，由于C++不允许对整数进行两次后++，即i++++是错误的，所以后++返回的不是一个引用，而前++返回引用，可以多次连续++。
另外，对于*和->的重载如下：
T& operator*() const
{return (*node).data;}
T* operator->() const
{return &(operator*());}
对于*，就是解引用，*it就是指一个object，所以返回的是data, 而对于->实际上是指针调用，所以返回的是data的指针。
G4.9
改进：
- 模板参数只有一个
- node在结构有parent
- node的成员type比较精确（指针指向自己）
但是G4.9的继承关系比较复杂。
G4.9版本的结构基本上是一个容器继承一个基类，这个容器有一个指针指向impl实现，这个实现public继承allocator。变得复杂是为了一个OO的目标，一个class里面有一个指针表现实现手法，这种模型叫做handle-body。但是侯捷认为不应该是public继承，因为这表示“是一个”，但是impl并不是allocator。
在2.9版是一个指针指向空白结点，到4.9是这个结构直接包括了两个指针，所以size变成了8.
max_size()是如何计算的？
list自身也有sort函数，全局也有sort函数，用容器自身的排序函数会比较快。
forward list
只提供push_front()为什么？这个不也是个list吗？不是动态增长的吗？
slist:(不属于标准库，但是用法和forward list相同)
deque
deque可以向前或者向后扩充。
deque每次扩充都扩充一个buffer，如图所示，向后扩充如果不够，就分配一个buffer，同理向前扩充也一样。deque中间控制的地方是个vector，这个vector聪明的地方在于，如果现在buffer满了，那么在扩充之后它会保持原来的元素在buffer中间，这样便于向两边扩展。
deque的iterator包括四个指针，当指针指向buffer的最后一个元素，再加加时，指针应该指向下一个buffer的第一个元素，所以有一个node指针，指向中控中心。另外还有两个iterator，也就是start和finish，分别是这个容器的头和尾。
deque的成员有一个指针map_pointer，一个size，两个迭代器start,finish，其中每个包括四个指针，所以deque的大小为442+4+4=40.
deque的模板默认参数有一个缓冲区大小默认为0，有一个计算缓冲区大小的函数__deque_buf_size，如果不为0，则设定为n，如果为0，设定为默认大小。
deque的insert函数需要判断插入的元素距离头比较近还是距离尾比较近，因为它需要移动其他元素并且可以双向移动。
deque如何模拟连续空间？都是deque iterator的功劳。
这是一些基本操作：
其中-的重载：
首先计算这里面有几个buffer，乘以buffer_size，然后再加上头和尾的元素。
- 对++和–的重载：
对++的重载有两个，一个是前++，一个是后++。首先检查加了之后有没有到达缓冲区尾端，如果到达就跳到下一个节点的起点。其中set_node函数就是跳到下一个缓冲区，包括重新设置first和last指针。
对–的重载也有两个。–首先检查当前是不是在缓冲区的起点，如果是的话就跳到前一个缓冲区的末端。
另外deque还有+=和+的操作。其中+就是调用+=。
+=的逻辑是这样的：首先计算出来要跳到的位置offset，如果offset在当前buffer的区域，直接跳。否则计算需要跳几个缓冲区，切换到正确的缓冲区再跳到元素的位置。
而-=直接调用+=(-n)就可以。
stack/queue
stack:push_back,pop_back
queue:push_back,pop_front
实际上deque已经包含了stack和queue，所以也叫做adapter.
stack和queue都不允许遍历，也不提供iterator
因为stack和queue是先进先出/先进后出，所以不提供iterator，这样就会破坏stack/queue的特性。
stack和queue可以选择list或者deque作为底层结构，不可以选择map/set。
stack可以选择vector作为底层结构，但是queue不可以，因为queue调用pop的时候需要调用vector的pop_front，但是vector没有这个函数。
Assosiative Containers
关联式容器的底层实现是红黑树和hashtable。
红黑树
红黑树是平衡二叉搜索树中经常被使用的一种。平衡二叉搜索树的特征：排列规则有利于search和insert，并且保持适度平衡。
红黑树按照正常规则遍历(++)便能够获得排序状态。红黑树从最左边的结点开始遍历，遍历到最右边的结点。另外红黑树有个头结点，是个空结点，便于操作。
虽然红黑树提供iterator，但是我们不应该用iterator来改变元素的值，这样会破坏红黑树的结构。
红黑树有两种插入：insert_unique和insert_equal，前一种不允许key重复，后一种允许。
红黑树的模板参数包括五个：
- key 的类型
- value (key+data)的类型
- keyOfValue key应该如何得到
- Compare 元素如何比大小
- alloc
参数：
node_account, 结点数量,4
header，指向红黑树的结点,4
Compare，可能是仿函数，大小应该是0，创造出来的对象大小是1
rb_tree<int,int,identity
,less ,alloc> myTree;
这是一个堆红黑树的使用。
其中identity是gnu C的一个仿函数，返回元素本身，less是标准库的一个比大小的函数。
template <class T>
struct identity:public unary_function<T,T>
{
const T& operator()(const T& x) const { return x; }
}
struct less:public binary_function<T,T,bool>
{
bool operator()(const T& x,const T&y) const
return { x<y; }
}
问题：红黑树和AVT有什么区别？
set/multiset
set/mulitset以红黑树为底层结构，key和value合二为一。
set调用insert_unique()，multiset调用insert_equal()。
set的底层实现实际上就是一颗红黑树，看上图可以看到从set的声明到set的模板参数到树的参数的转换。
但是我们无法使用set/multiset的iterator改变元素值，这是怎么实现的呢？看源码，set中定义了一个iterator,是const_iterator类型，这就保证了不允许改元素的值。
查找速度非常快。
map/multimap
和set不同的地方是，map把key和data包成一个包，keyOfValue是select1st。之前的set是把iterator变成const，这里是把key变成const。
insert(pair<long,string>(i,buf));
map在插入的时候可以使用c[i]=string(buf)，但是multimap不可以。
[]的作用是返回下标对应的元素值，如果不存在，则用默认值创建然后返回。源代码可以看对[]的重载，首先利用lower bound进行查找，如果有这个元素，就返回下标，否则就返回适合这个元素插入的位置，然后执行insert()函数。
hashtable
bucket_count()可能比元素多，因为有的篮子可能是空的。当元素>=篮子数，篮子就会扩充，把元素重新打散。打散的方式就是把篮子*2附近的质数，所有的元素都要重新计算一遍。
hashtable的模板参数：
- hash 1
- equals 1
- get_key 1
- bukets 12
- num_elements 4
hashtable的iterator必须能够从当前节点回到buckets，所以有一个指针ht指向hashtable本身。
hashtable的应用：
hashtable<const char*,
const char*,
hash<const char*>,
identity<const char*>,
eqstr,
alloc>
ht(50,hash<const char*>(),eqstr());
ht.insert_unique("kiwi");
ht.insert_unique("apple");
struct eqstr{bool operator()(const char*s1, s2)const
{ return strcmp(s1,s2)==0; }}
为什么这里不用strcmp呢？因为strcmp返回值是-1,0,1，不是返回bool，所以必须加一层外套。
在gnuC中，有一个结构体struct hash{}; 还有hash
决定每个元素落在哪个篮子里最终都是调用bkt_num_key这个函数，返回hash(key)%n，其中这里的hash不是上面的struct hash，而是hasher的hash。
hasher这里的hash是做什么用的？
unordered multiset/multimap
实际上unordered_(multi)list/set就是之前的hash_(multi)list/set，使用方法和slist一样，#include<ext/slist>。
分配器 allocators
尽量使用容器而不要使用分配器，因为分配器不像malloc和free，它还内存的时候还要指定特定的字节。
operator new() 和 malloc()
所有的获取空间追究到底层都是malloc()。
malloc会生成一个(五彩内存分配图)。
VC6 的 allocator
allocator->operator new->malloc。
VC6的allocator只是以operator new 和operator delete 完成allocate()和deallocate()，没有任何特殊设计。
在delete的时候，需要指定要回收多少字节。
BC5 的 allocator
BC5的allocator只是以operator new 和operator delete 完成allocate()和deallocate()，没有任何特殊设计。
比VC6贴心的是第二个参数VC6需要给一个指针，而BC5第二个参数给了默认值。
GCC2.9 的 allocator
GCC2.9的allocator只是以operator new 和operator delete 完成allocate()和deallocate()，没有任何特殊设计。
但是这个allocator并不是容器所使用的，源代码中使用的是alloc。
当分配的内存比较小的时候，用malloc比较浪费空间，因为它还需要申请空间记录其他信息，其中cookie记录的是这块空间的大小，用于指针回收的时候知道要回收多少。
alloc的结构如图，它一共分为16块，0号存储8个字节的，1号存储16个字节的，以此类推。当下面没有分配内存时才调用一次malloc。
具体需要看内存管理。
G4.9 的 allocator
G4.9 -> std::allocator -> new_allocator -> allocate -> operator new
在G4.9中没有用上面那个特殊设计的alloc，而是沿用了之前的分配器。但是alloc还在。
G4.9 有很多extension allcoators，其中__pool_alloc就是G2.9的alloc。
vector<string,__gnu_cxx::__pool_alloc<string>> vec;
真是源码面前无秘密啊。
迭代器
traits的作用
traits能够萃取出一个类型的特征，有iterator traits, type traits, pointer traits等等。
iterator需要遵循的原则（特性）
迭代器是算法和容器之间的桥梁。算法在对容器操作的时候需要知道容器的一些性质，比如rotate这个函数，调用了iterator_category()（判断这个容器是能++/–/+i），difference type()（两个iterator之间的距离用什么类型表现，比如unsigned integer范围2^32）, value type()（iterator本身指向的是什么数据类型）。
associated type:
- category
- difference type
- value type
- reference type
- pointer type
当算法提问的时候，可以直接提问：I::iterator_category
但是当iterator不是一个class的时候不可以这么调用，比如指针，是一个iterator（指针是退化的iterator，iterator是泛化的pointer），但是不是class，所以这时候需要用traits来萃取pointer的特征，来回答算法的提问。traits是一个中间层，他能够区分它所获得的iterator是class还是pointer。用偏特化可以实现。
当算法提问的时候，问iterator_traits。
如果I是class，那么进入1，如果是pointer to T就进入2，如果是pointer to const T，就进入3.
但是当I是pointer to const T的时候，value_type是T而不是const T。因为value_type的主要目的是声明变量，而一个无法被复制的变量没有用，所以iterator的value_type不应该加const。
不同容器的迭代器类型
迭代器共有5中iterator category:
- input_iterator_tag
- output_iterator_tag
- forward_iterator_tag: public input_iterator_tag
- bidirectional_iterator_tag: public forward_iterator_tag
- random_access_iterator_tag: public bidirectional_iterator tag
对于sequence containers来说：
array, vector, deque是random_access_iterator_tag
list是bidirectional_iterator_tag
forward_list是forward_iterator_tag
对于Associative containers：
(multi)set/map 是bidirectional_iterator
unordered_(multi)set/map 要看vector下面是用的单向链表还是双向链表来判断。
下面是用程序测试各种容器的iterator类型的代码：
另外还可以使用cout<<"typeid(itr).name()="<<typeid(itr).name()<<endl;来打印出各种容器的iterator_category的typeid。打印出的typeid在前面输出的前后会加一些东西，这是由编译器的具体实现决定的。
调用函数display_category，利用traits::iterator_category来询问迭代器的类型。
为什么这个类型不用12345的数字来表示，而用一个结构体呢？
看上面的程序就可以知道，用结构体能写的更规范。另外一个原因是，参考算法那部分的distance例子，这里只设计了两个函数，分别针对random_access_iterator和input_iterator，当有比如forward_iterator的时候，由于它继承了input_iterator，所以它是一种input_iterator，所以会调用input_iterator对应的函数。
算法
STL中的算法是什么？
从语言层面上来讲，STL除了算法是function template之外，其他都是class template。template<typename Iterator> Algorithm(Iterator it1, Iterator it2,(typename Cmp)){...}
算法看不到容器，所以它需要的一切信息都必须从Iterator中获得，Iterator必须能够回答算法的所有提问，才能搭配算法的所有操作。
迭代器对算法的影响
算法的效率和迭代器的类型有很大的关系。
举个例子来说，加入有一个函数distance()用于计算两个迭代器之间的距离。由于random_access_iterator和其他iterator不一样，它只需要用两个指针相减就可以了，而其他迭代器需要遍历两个迭代器，并且用n来计数。注意这里调用的是category()临时对象。同时返回值是difference_type。对于100万条数据来说，这两种函数的效率可见一斑。
同理advance函数也有相同的结构，这个函数的作用是向前进。假如是random_access，就直接+=n，如果是双向，判断n的正负，如果是单向，就while (n--) ++i;.
再举一个例子，copy这个函数。从下面可以看到这个函数对于不同情况的分类有多么精细。首先判断copy的对象是不是const char*/wchar_t，如果是的话，就调用memmove()，这个函数是底层的拷贝函数，速度非常快。如果不是的话，再判断是不是指针 const T*，如果是的话，判断有没有重要的拷贝复制，如果没有的话，调用 memmove()，如果有的话，调用__copy_d()，对于不是指针的iterator来说，判断是不是random、_access类型，是的话调用__copy_d()，不是的话以iterator是否相等来决定for-loop函数。这个函数和__copy_d()相比较慢。另外，判断拷贝复制是不是重要主要看这个类里面有没有指针，如果没有指针，那么拷贝赋值函数可以直接用底层函数赋值，如果有指针就需要调用拷贝复制了。
这一部分叫做type_traits。
但是算法源码中对iterator_category没有强制，而是“暗示”。比如
template <class RandomAccessIterator>
inline void sort(...){...}