STL是建立在泛化之上的。数组泛化为容器，参数化了所包含的对象的类型。函数泛化为算法，参数化了所用的迭代器的类型。指针泛化为迭代器，参数化了所指向的对象的类型。STL中的六大组件：容器、算法、迭代器、配置器、适配器、仿函数。

这六大组件中在容器中分为序列式容器和关联容器两类，正好作为STL源码剖析这本书的内容。迭代器是容器和算法之间的胶合剂，从实现的角度来看，迭代器是一种将operator*、operator->、operator++、operator—等指针相关操作予以重载的class template.所有STL容器都附带有自己专属的迭代器，因为只有容器设计者才知道如何遍历自己的元素。仿函数是一种重载了operator()的class或class template,一般函数指针可视为狭义的仿函数。配接器是一种用来修饰容器或仿函数或迭代器接口的东西，例如STL提供的queue和stack，虽然看似容器，其实只能算是一种容器配接器，因为他们的底部完全借助deque，所有操作都由底层的deque供应。改变functor接口者，成为funciton adapter；改变container接口者，成为container adapter；改变iterator接口者，成为iterator adapter。

         在STL内部定义了几类迭代器，但是在使用的时候，根据迭代器的使用方法可以将迭代器分为输入、输出迭代器、前向、双向迭代器、随机存取迭代器。

         STL所实现的，是依据泛型思维架设起来的一个概念结构。这个以抽象概念为主体而非以实际类为主体的结构，形成了一个严谨的接口标准。在此接口之下，任何组件都有最大的独立性，并以所谓迭代器胶合起来，或以所谓配接器互相配接，或以所谓仿函数动态选择某种策略。

         对于空间配置器，在std中使用的allocator配置器，但是在STL中不是使用的标准配置器而是使用的SGI自定义的配置器alloc。因为标准中的allocator配置器效率不是很高。因为allocator配置器只是把New和delete做了一层简单的包装。

                   STL中的空间配置，std::alloc

         对于一个平常的操作

         ClassFoo {  };

         Foo*fp = new Foo;

         Deletefp;

         上述过程包括连个阶段，调用new分配内存，调用Foo()构造对象。Delete中也包括两个阶段，调用~Foo()析构对象，调用delete释放内存。为了分工明确，STL 中将这两个阶段分开来操作。内存配置操作由alloc::allocate()负责，内存释放操作由alloc::deallocate()负责；对象构造操作由::construct()负责，对象析构操作由::destroy()负责。配置器定义于<memory>之中，SGI <memory>内含 stl_alloc.h stl_construct.h  前者负责内存空间的配置与释放，后者负责对象的构造与析构。

         考虑到小区块可能造成的内存破碎问题，SGI设计了双层的配置器，第一级直接使用Malloc()和free()，第二级则视情况来判断使用什么策略，当配置区块超过128KB，直接使用第一级配置器；当配置区块下雨128BK，使用辅助的memory pool整理方式，而不再求助于第一级配置器。无论使用第一级还是第二级配置器，都封装成了不接收参数的alloc，然后有简单的封装成simple_alloc类。这个类使得空间配置器对外有了标准接口。这个类中只有四个static的函数，对应着alloc中一对函数

Template<class T,class Alloc>

Class simple_alloc

{

         Public:

         StaticT* allocate(size_t n)

{  return 0 == n? 0:(T*)Alloc::allocate(n*sizeof(T));}

         StaticT* allocate(void)

                   {  return (T*) Alloc::allocate(sizeof (T)); }

         Staticvoid deallocate(T* p,size_t n)

{  if(0 !+ n)Alloc::deallocate(p,n*sizeof(T));}

         Staticvoid deallocate(T* p)

                   {  Alloc::deallocate(p,sizeof(T));}

}；

内部的四个static成员函数对应着空间配置器中的实现的函数，然后有全局的构造和析构哈数，这两者的结合把资源管理集合起来了。

我们只需要知道，在SGI STL中是有专门的空间配置器的，空间配置器管理这内存的分配和释放，也就是说内存配置器中初始化了两个函数分别管理内存的释放和分配，内存的分配时有优化的，首先看申请的内存是否够大，如果很大，那么就直接调用第一级的配置器，也就是使用malloc，如果不超过128KB，那么就使用第二级的配置器，第二级的配置器中保存了一系列的链表，从保存的链表内找一个合适的内存块来满足要求，这个配置器是不接收模板参数的alloc，对外又做了简单的封装—simple_alloc，此类也是封装那一对函数。同时有一对全局的函数，负责对象的构造和析构，也就是destroy()和construct().

         有了空间配置器alloc和上层封装simple_alloc之后，如何使用呢？

Template<class T,calss Alloc= alloc>

Class vector

{

         Public:

                   TypedefT value_type;

         Protected:

                   Typedefsimple_alloc<value_type,Alloc> data_allocator;

};

         到现在为止，我们知道了空间配置器是alloc，在容器作为默认的空间配置器，为了拥有更好的对外接口，封装成了simple_alloc类，里面封装了alloc中的两个重要函数，分别用户与内存的分配和释放，同时拥有了两个全局函数用于对象的构造和析构—construct()  destroy()。

         其实，还有三个全局函数，uninitialized_copy()  uninitialized_fill()  uninitialized_fill_n()，分别对应高层次函数copy()fill() fill_n()---这些都是STL算法。这三个全局函数从名字也可以判断其作用。

         上述的uninit*三个函数都有都了泛化 特化的技术，为了更高效的处理。在泛化的分支中使用到了STL中的那三个函数。

总结：在空间配置中，要明白SLT使用了自己定义的alloc配置器，这个配置器分为两级，提供了内存的释放和分配的工作，然后定义了五个全局函数，两个全局是用来对象的构造和析构，三个全局是更高效的初始化内存存在的。为了更好的使用alloc.对外封装了simple_alloc这个类，在各个容器中都是使用这一个类。

高效STL--非标准散列容器