hashtable：
   SGI STL的hashtable是用的开链法完成的。用一个vector储存一系列的指针，指向一个节点元素链表的头（节点元素自身维护了一个list）。
   节点定义：

   迭代器摘要（没有--操作，没有逆向迭代器）：

   hashtable以质数来设计表格大小，预先计算好了28个质数，大约都是两倍的关系递增，查询28个质数中，“最接近且大于元素数目”的数字作为vector的长度，如果需要重新分配，则分配下一个质数长度的vector。
   hashtable设计的容量和buckets vector的大小一样。因此如果数目超过了，就需要重新建立：新建一个temp，将原来hashtable中的元素一个一个切割出来插入到新的temp的适当位置，全部插完后交换hashtable和temp。同时释放temp的内存。
   同样，hashtable的插入操作也分为insert_unique和insert_equal,分别代表不允许重复和允许重复插入。下面是不允许重复插入操作的具体实现。

 

   hashtable有一些无法处理的型别，除非用户为那些型别写了相应的hash function。

hash_set/hash_map：
   此两个跟set/map相比较，只是插入的元素不会自动排序。其他使用方式完全一致，而操作基本全部由hashtable完成。

hash_mulitset/hash_multimap:
   和multiset/multimap比较，也只是插入元素不会自动排序。      摘要:    关联式容器：观念上类似关联式数据库（实际上简单很多），每个元素都有一个键值和一个实值，当元素插入到关联容器中时，容器内部结构（RB-tree或者hash-table）依照键值将其插入到适当的位置。   AVL tree： 一种二叉搜索树。任何节点的左右子树高度最多相差1。 如果插入后平衡被破坏，则分为以下情况： 1、 插入点...  阅读全文 4、stack
   stack是一种先进先出的数据结构。只能在栈顶操作。它以底层容器完成所有的操作，因此是一个adapter（配接器）。
   stack还有一个特性就是没有迭代器：因为只能在栈顶进行操作，所以不必要定义迭代器，也不能遍历。

5、queue
   和stack基本一致。

6、Heap
   Heap在STL中不是实际组件，只是priority的助手。
   binary heap：一种完全二叉树。可以用数组表示。如果数组的第一个元素保留（设为无穷大或者无穷西欧啊），从第二个元素开始储存，则有：对于i处的节点，其子节点必定位于2i和2i+1处，其父节点位于i/2处。（SGI STL中没有用到这个方法，因此取值方法有所改变）
   heap操作：
      push_heap：在heap中插入一个新值的时候，先把它插入到最后面（树中最下面一排的最后一个）。然后将它和父节点进行比较，如果其键值大于父节点的，就交换位置，如此一直上溯。
      pop_heap：在heap中删除最大值的时候(其实是将最大值元素交换到heap的尾部，然后--size)。先进行交换，然后对交换后的数组进行从上往下的调整：如果子节点中最大的键值大于父节点的键值，就将他们两个交换，然后继续往下进行。
      ajust_heap：上述调整方法。
（SGI STL使用的方法：先不进行交换，而是将父节点设为空洞，然后将空洞下层到符合的底层，再将前堆尾元素在空洞位置进行一次push_heap）
   sort_heap：进行N次pop_heap，就完成了一次堆排序。
   make_heap：因为所有的叶子节点都不需要调整，所以从N/2处往上进行调整。

7、priority_queue
   priority_queue是一个带有权值观念的队列，因此取出元素的时候只能取出权值最大的元素。
   priority_queue完全以底层容器为根据（缺省为vector），加上heap处理规则实现。

8、slist
   slist是一个单向链表。（SGI中有实现，但是并不在STL容器中）
   因为slist是单向的，因此对于获得slist的链表尾端需要进行一次完整的遍历，因而push_back操作十分费时，没有提供。
   slist特点：节点和迭代器设计运用了继承关系，比list要复杂。
（为什么要用继承？）      摘要:    所谓序列式容器：其中的元素都可序但是不一定有序。   1、vector   vector的实现技术，关键在于对其大小的控制以及重新配置时的数据移动效率。   vector的迭代器实际上是普通指针。vector内部有3个iterator：start，finish，end_of...  阅读全文

  1.迭代器

  迭代器提供了一种方法，使之能够依序巡访某个容器的各个元素，而无需暴露容器的内部。

    STL的中心思想是容器和算法分开，最后再用迭代器将两者完美的融合到一起。而迭代器是实现中最关键的部分。

  迭代器是一种行为类似指针的对象，因此它必不可少的就是对operator*和operator ->的重载。可以参考auto_ptr。

 

 

  2.traits技法（重点）

  在effective C++中，条款47介绍到了traits技术。它的思想是通过提取出来某些类型的特性，然后根据它的特性进行某些操作。

  一种方法是通过内嵌类来表示类型的特性，然后在进行操作的时候进行判断，然而这种方法却不能对内置类型使用。因为我们不可能向内置类型加入内嵌类以表示它的特性。

  另一种方法表示如下（在别人blog里面看到一个类似例子，自己写了一下）：

 

 

这种方式通过把类的traits信息放到类的外部，从而可以通过偏特化将内置类型的traits融入进去。

 

 在STL中，迭代器对应的traits类为iterator_traits

为了能够表示内置类型如int *, const int *等的特性，所以要设计相应的特化版本。下例是I*的特化。

 

 

 

从此可以看出，在设计迭代器的时候一定要提供五个内嵌的相应型别。以利于traits萃取。STL提供了一个iterators class供人继承，可以保证其符合规范。

 

 

3. __type_traits

这个是SGI内部的，不在STL标准内。用来萃取性别的特性。
先定义两个空结构体，用来标识true和false。

__type_traits内则定义一些typedefs，其值为__true_type或者__false_type

 

空间配置器的标准接口(根据STL规范)

 

 

——————————————————————————————————————

SGI STL 的配置器与众不同， 名称是alloc而不是allocator， 而且不接受任何参数。

 

 

但是通常都是使用默认的空间配置器，而SGI STL已经为每一个容器都指定了缺省的空间配置器。所以使用的时候无太大区别。

 

 

————————————————————————————————————————

SGI空间配置器分析：

C++的new操作符和delete操作符进行内存配置时，new：先配置内存，然后构造对象。delete：先析构对象，然后释放内存。SGI STL将内存配置、释放内存与构造、析构分开。前者由<stl_alloc.h>中的allocate()和deallocate()负责，后者由<stl_construct.h>中的construct()和destroy()负责。 这两个头文件包含于<memory>中（STL标准规定，配置器定义在memory中）。同时<memory>还包含了一个文件<stl_unitialized.h>，定义了一些全局函数用来填充、复制大块内存数据。

 

1.构造和析构。

构造：

 

PS：placement new运算，并不分配内存，而是将已分配的内存调用构造函数来进行初始化。

析构：

析构函数第一个版本接受一个指针，将指针所指之物删除，可以直接调用析构函数。而第二个版本，接受两个迭代器，将其之间的所有对象全部析构。由于我们不知道这个范围的大小，有时候范围很大而每个对象的析构不是必要的，就会造成浪费。因此需要进行一个判断，根据得到的结果来判断是否需要析构它（判断用到了traits方法）。

下面是最终的析构调用情况，其中__false_type和__ture_type是两个空的struct，只用于标识，使其通过函数重载在编译的时候确定调用哪一个版本。

 

 

 同时这个析构函数对char*和wchar_t*有特化版本:将不调用他们的析构函数。（这是没有必要调用析构函数的例子么？）

2. 空间的配置和释放： std::alloc

std::alloc为了效率，设计了双层级配置器，第一级直接使用C的malloc()和free()。第二级则视配置区块的大小选择配置器，如果区块大，则直接调用第一级，如果区块过小，则采用memory pool 整理的方法。

SGI将其简单的包装了一个接口，simple_alloc类。使其符合STL规格。而在使用的时候全部使用的simple_alloc接口（缺省使用）。

 

第一级配置器：

调用malloc()和realloc()，如果配置不成功，则调用oom_malloc(), oom_realloc()（PS：oom= out of memory）。在oom_XXX的处理时，通过不断调用“内存不足处理例程”，期望在某次调用之后能够分配到。设计“内存不足处理例程”是客户端的责任。（effective C++ 对new-handler的行为有一个条款，还没认真看）

第二级配置器：

由于太多小额的区块会造成内存的碎片，同时也会带来额外的负担，因此通过第二级配置器的分配，适当的将小额内存分配出去。当区块小（<128bytes）的时候，采用内存池管理。第二级配置器维护了16个free-lists，各自管理从8~128bytes的小额区块，每一个区块以8bytes递增（将每一个小额的区块需求上调至8的倍数，以便管理）。每一次需要时候就将适当的内存从free-lists中间拔出来。客户释放后就回收到free-lists中。当需要的free-lists中没有可用的区块的时候，调用refill()函数为free-lists填充新的空间（取自内存池，用chunk_alloc()函数）。内存池的处理十分复杂，看的一头雾水。

 

SGI配置器使用方法：

 

 

其中第二个template参数接受缺省的alloc，可以是第一级配置器也可以是第二级配置器。SGI STL已经把它设定为第二级配置器。

 

 

3. 内存基本处理工具

在头文件<stl_uninitialized>中，定义了3个全局函数，uninitialized_copy(),uninitialized_fill(),uninitialized_fill_n(). 看到这些名字应该就知道它们是什么作用了，它们负责在已分配好的空间进行构造。这三个函数都具有”commit or rollback”语意。要么构造出所有元素，要么不构造任何东西。

在具体的实现中，这三个函数也用到了traits技法，通过traits萃取出元素的特性，如果是POD（Plain Old Data）型别，说明其拥有trivial ctor/ dtor/ copy/ assignment函数，因此可以使用copy()、fill()、fill_n()等算法，如果不是POD型别就只能够循环调用construct()函数了。这里用到的也是函数重载的方法，和上面destroy用到的方法是一样的。

注意：在unitialized_copy()实现的时候，针对char*和wchar_t*两种型别，可以采用最有效率的memmove()来复制，因此需要两份特化版本。