#
来源：http://www.tbdata.org/archives/1390#more-1390
Nginx的内存池实现得很精巧，代码也很简洁。总的来说，所有的内存池基本都一个宗旨：申请大块内存，避免“细水长流”。
一、创建一个内存池
nginx内存池主要有下面两个结构来维护，他们分别维护了内存池的头部和数据部。此处数据部就是供用户分配小块内存的地方。
//该结构用来维护内存池的数据块，供用户分配之用。
typedef struct {
u_char *last; //当前内存分配结束位置，即下一段可分配内存的起始位置
u_char *end; //内存池结束位置
ngx_pool_t *next; //链接到下一个内存池
ngx_uint_t failed; //统计该内存池不能满足分配请求的次数
} ngx_pool_data_t;
//该结构维护整个内存池的头部信息。
struct ngx_pool_s {
ngx_pool_data_t d; //数据块
size_t max; //数据块的大小，即小块内存的最大值
ngx_pool_t *current; //保存当前内存池
ngx_chain_t *chain; //可以挂一个chain结构
ngx_pool_large_t *large; //分配大块内存用，即超过max的内存请求
ngx_pool_cleanup_t *cleanup; //挂载一些内存池释放的时候，同时释放的资源。
ngx_log_t *log;
};
有了上面的两个结构，就可以创建一个内存池了，nginx用来创建一个内存池的接口是：ngx_pool_t *ngx_create_pool(size_t size, ngx_log_t *log)（位于src/core/ngx_palloc.c中）;调用这个函数就可以创建一个大小为size的内存池了。这里，我用内存池的结构图来展 示，就不做具体的代码分析了。
ngx_create_pool接口函数就是分配上图这样的一大块内存，然后初始化好各个头部字段（上图中的彩色部分）。红色表示的四个字段就是来自于上 述的第一个结构，维护数据部分，由图可知：last是用户从内存池分配新内存的开始位置，end是这块内存池的结束位置，所有分配的内存都不能超过 end。蓝色表示的max字段的值等于整个数据部分的长度，用户请求的内存大于max时，就认为用户请求的是一个大内存，此时需要在紫色表示的large 字段下面单独分配；用户请求的内存不大于max的话，就是小内存申请，直接在数据部分分配，此时将会移动last指针。
二、分配小块内存(size <= max)
上面创建好了一个可用的内存池了，也提到了小块内存的分配问题。nginx提供给用户使用的内存分配接口有：
void *ngx_palloc(ngx_pool_t *pool, size_t size);
void *ngx_pnalloc(ngx_pool_t *pool, size_t size);
void *ngx_pcalloc(ngx_pool_t *pool, size_t size);
void *ngx_pmemalign(ngx_pool_t *pool, size_t size, size_t alignment);
ngx_palloc和ngx_pnalloc都是从内存池里分配size大小内存，至于分得的是小块内存还是大块内存，将取决于size的大小； 他们的不同之处在于，palloc取得的内存是对齐的，pnalloc则否。ngx_pcalloc是直接调用palloc分配好内存，然后进行一次0初 始化操作。ngx_pmemalign将在分配size大小的内存并按alignment对齐，然后挂到large字段下，当做大块内存处理。下面用图形 展示一下分配小块内存的模型：
上图这个内存池模型是由上3个小内存池构成的，由于第一个内存池上剩余的内存不够分配了，于是就创建了第二个新的内存池，第三个内存池是由于前面两个内存 池的剩余部分都不够分配，所以创建了第三个内存池来满足用户的需求。由图可见：所有的小内存池是由一个单向链表维护在一起的。这里还有两个字段需要关 注，failed和current字段。failed表示的是当前这个内存池的剩余可用内存不能满足用户分配请求的次数，即是说：一个分配请求到来后，在 这个内存池上分配不到想要的内存，那么就failed就会增加1；这个分配请求将会递交给下一个内存池去处理，如果下一个内存池也不能满足，那么它的 failed也会加1，然后将请求继续往下传递，直到满足请求为止（如果没有现成的内存池来满足，会再创建一个新的内存池）。current字段会随着 failed的增加而发生改变，如果current指向的内存池的failed达到了4的话，current就指向下一个内存池了。猜测：4这个值应该是 作者的经验值，或者是一个统计值。
三、大块内存的分配(size > max)
大块内存的分配请求不会直接在内存池上分配内存来满足，而是直接向操作系统申请这么一块内存（就像直接使用malloc分配内存一样），然后将这块 内存挂到内存池头部的large字段下。内存池的作用在于解决小块内存池的频繁申请问题，对于这种大块内存，是可以忍受直接申请的。同样，用图形展示大块 内存申请模型：
注意每块大内存都对应有一个头部结构（next&alloc），这个头部结构是用来将所有大内存串成一个链表用的。这个头部结构不是直接向操作系 统申请的，而是当做小块内存（头部结构没几个字节）直接在内存池里申请的。这样的大块内存在使用完后，可能需要第一时间释放，节省内存空间，因此 nginx提供了接口函数：ngx_int_t ngx_pfree(ngx_pool_t *pool, void *p)；此函数专门用来释放某个内存池上的某个大块内存，p就是大内存的地址。ngx_pfree只会释放大内存，不会释放其对应的头部结构，毕竟头部结 构是当做小内存在内存池里申请的；遗留下来的头部结构会作下一次申请大内存之用。
四、cleanup资源
可以看到所有挂载在内存池上的资源将形成一个循环链表，一路走来，发现链表这种看似简单的数据结构却被频繁使用。由图可知，每个需要清理的资源都对应有一 个头部结构，这个结构中有一个关键的字段handler，handler是一个函数指针，在挂载一个资源到内存池上的时候，同时也会注册一个清理资源的函 数到这个handler上。即是说，内存池在清理cleanup的时候，就是调用这个handler来清理对应的资源。比如：我们可以将一个开打的文件描 述符作为资源挂载到内存池上，同时提供一个关闭文件描述的函数注册到handler上，那么内存池在释放的时候，就会调用我们提供的关闭文件函数来处理文 件描述符资源了。
五、内存的释放
nginx只提供给了用户申请内存的接口，却没有释放内存的接口，那么nginx是如何完成内存释放的呢？总不能一直申请，用不释放啊。针对这个问 题，nginx利用了web server应用的特殊场景来完成；一个web server总是不停的接受connection和request，所以nginx就将内存池分了不同的等级，有进程级的内存池、connection级 的内存池、request级的内存池。也就是说，创建好一个worker进程的时候，同时为这个worker进程创建一个内存池，待有新的连接到来后，就 在worker进程的内存池上为该连接创建起一个内存池；连接上到来一个request后，又在连接的内存池上为request创建起一个内存池。这样， 在request被处理完后，就会释放request的整个内存池，连接断开后，就会释放连接的内存池。因而，就保证了内存有分配也有释放。
总结：通过内存的分配和释放可以看出，nginx只是将小块内存的申请聚集到一起申请，然后一起释放。避免了频繁申请小内存，降低内存碎片的产生等问题
参考：STL源码分析
（一）vector容器
vector的数据安排以及操作方式，与array非常相似。两者的唯一区别在于空间的运用的灵活性。array是静态空间，一旦配置了就不能改变。vector是动态空间，随着元素的加入，它的内部机制会自行扩充空间以容纳新元素。因此，vector的运用对于内存的合理利用与运用的灵活性有很大的帮助，我们再也不必因为害怕空间不足而一开始要求一个大块的array。
vector动态增加大小，并不是在原空间之后持续新空间（因为无法保证原空间之后尚有可供配置的空间），而是以原大小的两倍另外配置一块较大的空间，然后将原内容拷贝过来，然后才开始在原内容之后构造新元素，并释放原空间。因此，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了。
（二）list容器
相对于vector的连续空间，list就显得复杂许多，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素移除，list永远是常数时间。STL中的list是一个双向链表，而且是一个环状双向链表。
（三）deque容器
deque 是一种双向开口的连续线性空间。所谓双向开口，意思是可以在队尾两端分别做元素的插入和删除操作。deque和vector的最大差异，一在于deque允许于常数时间内对起头端进行元素的插入或移除操作，二在于deque没有所谓容量观念，因为它是动态地以分段连续空间组合而成，随时可以增加一段新的空间并链接在一起。换句话说，像vector那样"因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间"这样的事情在 deque是不会发生的。
deque是由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象，并提供随机存取的接口。避开了"重新配置，复制，释放"的轮回，代价则是复杂的迭代器架构。因为有分段连续线性空间，就必须有中央控制，而为了维持整体连续的假象，数据结构的设计及迭代器前进后退等操作都颇为繁琐。
deque采用一块所谓的map作为主控。这里的map是一小块连续空间，其中每个元素都是指针，指向另一段连续线性空间，称为缓冲区。缓冲区才是deque的存储空间主体。SGI STL允许我们指定缓冲区大小，默认值0表示将使用512 bytes缓冲区。
（四）stack
stack 是一种先进后出（First In Last Out , FILO）的数据结构。它只有一个出口，stack 允许新增元素，移除元素，取得最顶端元素。但除了最顶端外，没有任何其它方法可以存取stack的其它元素，stack不允许遍历行为。
以某种容器作为底部结构，将其接口改变，使之符合“先进后出”的特性，形成一个stack，是很容易做到的。deque是双向开口的数据结构，若以deque为底部结构并封闭其头端开口，便轻而易举地形成了一个stack.因此，SGI STL 便以deque作为缺省情况下的stack底部结构，由于stack 系以底部容器完成其所有工作，而具有这种"修改某物接口，形成另一种风貌"之性质者，称为adapter（配接器），因此，STL stack 往往不被归类为container(容器)，而被归类为 container adapter.
(五） queue
queue是一种先进先出(First In First Out,FIFO) 的数据结构。它有两个出口，queue允许新增元素，移除元素，从最底端加入元素，取得最顶端元素。但除了最底端可以加入，最顶端可以取出外，没有任何其它方法可以存取queue的其它元素。
以某种容器作为底部结构，将其接口改变，使之符合“先进先出”的特性，形成一个queue，是很容易做到的。deque是双向开口的数据结构，若以 deque为底部结构并封闭其底部的出口和前端的入口，便轻而易举地形成了一个queue.因此，SGI STL 便以deque作为缺省情况下的queue底部结构，由于queue 系以底部容器完成其所有工作，而具有这种"修改某物接口，形成另一种风貌"之性质者，称为adapter（配接器），因此，STL queue往往不被归类为container(容器)，而被归类为 container adapter.
(六)heap
heap并不归属于STL容器组件，它是个幕后英雄，扮演priority queue的助手。priority queue允许用户以任何次序将任何元素推入容器中，但取出时一定按从优先权最高的元素开始取。按照元素的排列方式，heap可分为max-heap和min-heap两种，前者每个节点的键值(key)都大于或等于其子节点键值，后者的每个节点键值(key)都小于或等于其子节点键值。因此， max-heap的最大值在根节点，并总是位于底层array或vector的起头处；min-heap的最小值在根节点，亦总是位于底层array或vector起头处。STL 供应的是max-heap，用c++实现。
堆排序c语言实现
http://www.cppblog.com/tankzhouqiang/archive/2011/03/21/142413.html
（七）priority_queue
priority_queue是一个拥有权值观念的queue,它允许加入新元素，移除旧元素，审视元素值等功能。由于这是一个queue，所以只允许在底端加入元素，并从顶端取出元素，除此之外别无其它存取元素的途径。priority_queue带有权值观念，其内的元素并非依照被推入的次序排列，而是自动依照元素的权值排列（通常权值以实值表示）。权值最高者，排在最前面。缺省情况下priority_queue系利用一个max-heap完成，后者是一个以vector表现的 complete binary tree.max-heap可以满足priority_queue所需要的"依权值高低自动递减排序"的特性。
priority_queue完全以底部容器作为根据，再加上heap处理规则，所以其实现非常简单。缺省情况下是以vector为底部容器。queue以底部容器完成其所有工作。具有这种"修改某物接口，形成另一种风貌"之性质者，称为adapter(配接器)，因此，STL priority_queue往往不被归类为container(容器)，而被归类为container adapter.
(八)set,multiset
set的特性是，所有元素都会根据元素的键值自动被排序。set的元素不像map那样可以同时拥有实值(value)和键值(key), set 元素的键值就是实值，实值就是键值，set不允许两个元素有相同的值。set是通过红黑树来实现的，由于红黑树（RB-tree）是一种平衡二叉搜索树，自动排序的效果很不错，所以标准的STL的set即以RB-Tree为底层机制。又由于set所开放的各种操作接口，RB-tree也都提供了，所以几乎所有的set操作行为，都只有转调用RB-tree的操作行为而已。
multiset的特性以及用法和set完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层机制RB-tree的insert_equal()而非insert_unique().
（九）map,multimap
map的特性是，所有元素都会根据元素的键值自动被排序。map的所有元素都是pair,同时拥有实值（value）和键值（key）. pair的第一元素被视为键值，第二元素被视为实值。map不允许两个元素拥有相同的键值.由于RB-tree是一种平衡二叉搜索树，自动排序的效果很不错，所以标准的STL map即以RB-tree为底层机制。又由于map所开放的各种操作接口，RB-tree也都提供了，所以几乎所有的map操作行为，都只是转调RB-tree的操作行为。
multimap的特性以及用法与map完全相同，唯一的差别在于它允许键值重复，因此它的插入操作采用的是底层机制RB-tree的insert_equal()而非insert_unique。
（一）迪杰斯特拉算法（时间复杂度O(n2)）
迪杰斯特拉（Dijkstra）算法是求某个源点到其余各顶点的最短路径，这是一个按路径长度递增的次序产生最短路径的算法。
首先引进一个辅助向量D,它的每个分量D[i]表示当前所找到的从始点v到每个终点vi的最短路径的长度。它的初态为：若从v到vi有弧，则D[i]为弧上的权值；否则置D[i]为无穷大。显然，长度为D[j]=Min{D[i]|vi属于V}的路径就是从v出发的长度最短的一条最短路径。因此，在一般情况下，下一条长度次短的最短路径的长度必为D[j]=Min{D[i]|vi 属于 V-S} 其中D[i]或者为弧（v,vi)上的权值，或者是D[k](vk属于S)和弧（vk,vi）上的权值之和。算法步骤如下：
(1)假设用带权的邻接矩阵arcs来表示带权有向图，arcs[i][j]表示弧(vi,vj)上的权值。若(vi,vj)不存在，则置arcs[i][j]为无穷大。S为已找到从v出发的最短路径的终点的集合，它的初始状态为空集。那么，从v出发到图上其余各顶点（终点）vi,可能达到的最短路径长度的初值为：
D[i]=G.arcs[v][vi],vi属于V
(2)选择Vj，使得
D[j]=Min{D[i]|vi 属于V-S}
vj 就是当前求得的一条从v出发的最短路径的终点。令
S=SＵ ｛ｊ｝
(3) 修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。如果D[j]+arcs[j][k]<D[k]则修改D[k]为 D[k]=D[j]+arcs[j][k]
(4) 重复操作(2),(3)共 n-1次。由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。
（二）弗洛伊德(Floyd)算法（时间复杂度为O(n3)）
弗洛伊德（Floyd）算法是求图中每一对顶点之间的最短路径，时间复杂度为O(n3).
弗洛伊德算法仍从图的带权邻接矩阵cost出发，其基本思想是 :
假设求从顶点vi到vj的最短路径。如果从vi到vj有弧，则从vi到vj存在一条长度arcs[i][j]的路径，该路径不一定是最短路径，尚需进行n次试探。首先考虑路径(vi,v0,vj)是否存在（即判别弧（vi,v0）和(v0,vj)是否存在)。 如果存在，则比较(vi,vj)和(vi,v0,vj)是否存在(即判别弧(vi,v0)和(v0,vj)是否存在).如果存在，则比较(vi,vj)和(vi,v0,vj)的路径长度取长度较短者为从vi到vj的中间顶点的序号不大于0的最短路径。假如在路径上再增加一个顶点v1,也就是说，如果(vi,...v1)和(v1...vj)分别为当前找到的中间顶点的序号不大于0的最短路径，那么（vi,...,v1,...vj）就有可能是从vi到vj的中间顶点的序号不大于1的最短路径。将它和已经得到的从vi到vj中间的顶点序号不大于0的最短路径相比较，从中选出中间顶点的序号不大于1的最短路径之后，再增加一个顶点v2,继续进行试探。依次类推。在一般情况下，若(vi,...,vk)和(vk,...vj)分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将(vi,...vk,...vj)和已经得到的从vi到vj且中间顶点序号不大于k-1的最短路径相比较，其长度较短者便是从vi到vj的中间顶点的序号不大于k的最短路径。这样，在经过n次比较后，最后求得的必是从vi到vj的最短路径。
现定义一个n阶方阵序列
D(-1),D(0),D(1),...D(k),...D(n-1)
其中
D(-1)[i][j]=G.arcs[i][j].
D(k)[i][j]=Min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]} 0<=k<=n-1
从上述计算公式可见，D(1)[i][j]是从vi到vj的中间顶点的序号不大于1的最短路径的长度。D(k)[i][j]是从vi到vj的中间顶点的序号不大于k的最短路径的长度。D(n-1)[i][j]就是从vi到vj的最短路径的长度。
安全边：在每一次迭代之前， A是某个最小生成树的一个子集。在算法的每一步中，确定一条边（u,v),使得将它加入集合A后，仍然不违反这个循环不等式，A U {(u,v)}仍然是某一个最小生成树的子集。称这样的边为A的安全边。
识别安全边的定理：设图G=(V,E)是一个无向连通图，并且在E上定义了一个具有实数值的加权函数w.设A是E的一个子集，它包含于G的某个最小生成树中。设割(S,V-S)是G的任意一个不妨害A的割，且边(u,v)是通过割(S,V-S)的一条轻边，则边(u,v)对集合A来说是安全的。
推论：设G=(V,E)是一个无向联通图，并且在E上定义了相应的实数值加权函数w.设A是E的子集，并包含于G的某一最小生成树中。设C=(Vc,Ec)为森林GA=(V,A) 的一个连通分支。如果边是连接C和Ga中其他某联通分支的一条轻边，则(u,v)对集合A来说是安全.
在Kruskal(
克鲁斯卡尔)算法和Prim(普里姆)算法
在Kruskal算法中，集合A是一个森林，加入集合A中的安全边总是图中连接两个不同联通分支的最小权边。在Prim算法中，集合A仅形成单棵树，添加入集合A的安全边总是连接树与一个不在树中的顶点的最小权边。
Kruskal(
克鲁斯卡尔)算法(O(ElgE))：
该算法找出森林中连接任意两棵树的所有边中，具有最小权值的边(u,v)作为安全边，并把它添加到正在生长的森林中。设C1和C2表示边(u,v)连接的两棵树，因为(u,v)必是连接C1和其他某棵树的一条轻边，所以由上面推论可知，(u,v)对C1来说是安全边。Kruskal 算法同时也是一种贪心算法， 因为在算法的每一步中，添加到森林中的边的权值都是尽可能小的。
下面是伪代码:
MST-KRUSKAL(G,w)
A<--空集
for each vertex v 属于 V[G]
do MAKE-SET(v)
sort the edges of E into nondecreasing order by weight w
for each edge(u,v)属于E,taken in nondecreasing order by weight
do if FIND-SET(u)!=FIND-SET(v)
then A<--AU{(u,v)}
UNION(u,v)
return A
FIND-SET(u)返回包含u的集合中的一个代表元素。于是通过测试FIND-SET(u)是否等同于FIND-SET(v)，就可以确定顶点u和v是否属于同一棵树。通过过程UNION，可以实现树与树的合并。
Prim算法(O(ElgV))
Prim算法的特点是集合A中的边总是形成单棵树。树从任意根顶点r开始形成，并逐渐生成，直至该树覆盖了V中的所有顶点。在每一步，一条连接了树A与Ga=(V,A)中某孤立顶点的轻边被加入树A中。由推论可知，该规则仅加入对A安全的边，因此当算法终止时，A中的边形成了一棵最小生成树。因此每次添加到树中的边都是使树的权尽可能小的边，因此，上述策略也是“贪心“的。
伪代码如下：
MST-PRIM(G,w,r)
for each u 属于V[G]
do key[u] <--空集
n[u]<--NIL
key[r]<--0
Q<--V[G]
while Q!=空集
do u<---EXTRACT-MIN(Q)
for each v属于Adj[u]
do if v 属于Q and w(u,v)<key[v]
then n[u]<---u
key[v]<--w(u,v)
参考：算法导论
刚又想起了很多事情，想起了二高的美好时光，怀念西大，牛逼的2533，一切仿佛都在眼前，我是个怀旧的人。最近压力好大，等有时间了想回西安看看，见见老大，大头还有魏嵩他们。等回家了也要去二高去看看，高中毕业后还没去过。
看过STL空间配置器的源码，总结一下：
(1)STL空间配置器：主要分三个文件实现，stl_construct.h 这里定义了全局函数construct()和destroy(),负责对象的构造和析构。stl_alloc.h文件中定义了一，二两级配置器，彼此合作，配置器名为alloc. stl_uninitialized.h 这里定义了一些全局函数，用来填充(fill)或复制(copy)大块内存数据，他们也都隶属于STL标准规划。
在stl_alloc.h中定义了两级配置器，主要思想是申请大块内存池，小块内存直接从内存池中申请，当不够用时再申请新的内存池，还有就是大块内存直接申请。当申请空间大于128字节时调用第一级配置器，第一级配置器没有用operator::new和operator::delete来申请空间，而是直接调用malloc/free和realloc，并且实现了类似c++中new-handler的机制。所谓c++ new handler机制是，你可以要求系统在内存配置需求无法被满足时，调用一个指定的函数。换句话说，一旦::operator::new无法完成任务，在丢出std::bad_alloc异常状态之前，会先调用由客端指定的处理例程，该处理例程通常称为new-handler.new-handler解决内存做法有特定的模式。SGI第一级配置器的allocate()和realloc都是在调用malloc和realloc不成功后，改调用oom_malloc()和oom_realloc().后两者都有内循环，不断调用"内存不足处理例程",期望在某次调用之后，获得足够的内存而圆满完成任务。但如果“内存不足处理例程“并未被客端设定，oom_malloc()和oom_realloc便调用_THROW_BAD_ALLOC, 丢出bad_alloc异常信息，或利用exit(1)硬生生中止程序。
在stl_alloc.h中定义的第二级配置器中，如果区块够大，超过128字节时，就移交第一级配置器处理，当区块小于128字节时，则以内存池管理，此法又称为次层配置，每次配置一大块内存，并维护对应的自由链表(free-list).下次若再有相同大小的内存需求，就直接从free-list中拔出。如果客端释还小额区块，就由配置器回收到free-lists中，配置器除了负责配置，也负责回收。为了管理方便，SGI第二级配置器会主动将任何小额区块的内存需求量上调至8的倍数。并维护16个free-lists,各自管理大小分别为8，16，24，32，40，48，56，64，72，80，88，96，104， 112，120，128 字节的小额区块。当申请小于等于128字节时就会检查对应的free list，如果free-list中有可用的区块，就直接拿来，如果没有，就准备为对应的free-list 重新填充空间。新的空间将取自内存池，缺省取得20个新节点，如果内存池不足（还足以一个以上的节点），就返回的相应的节点数.如果当内存池中连一个节点大小都不够时，就申请新的内存池,大小为2*total_bytes+ROUND_UP(heap_size>>4), totoal_bytes 为申请的空间大小，ROUND_UP调整为8的倍数，heap_size为当前总申请内存池的大小。如果申请该内存池成功就把原来内存池中剩下的空间分配给适当的free-list.万一山穷水尽，整个system heap空间都不够了（以至无法为内存池注入源头活水），malloc()行动失败，就会四处寻找有无"尚有未用区块，且区块足够大 "之free lists.找到了就挖一块交出，找不到就调用第一级配置器。第一级配置器其实也是使用malloc来配置内存。但它有out-of-memory处理机制（类似new-handler机制），或许有机会释放其他的内存拿来此处使用。如果可以就成功，否则发出bad_alloc异常。
参考：STL源码分析
虚函数是在类中被声明为virtual的成员函数，当编译器看到通过指针或引用调用此类函数时，对其执行晚绑定，即通过指针（或引用）指向的类的类型信息来决定该函数是哪个类的。通常此类指针或引用都声明为基类的，它可以指向基类或派生类的对象。
多态指同一个方法根据其所属的不同对象可以有不同的行为（根据自己理解，不知这么说是否严谨）。
举个例子说明虚函数、多态、早绑定和晚绑定：
李氏两兄妹（哥哥和妹妹）参加姓氏运动会（不同姓氏组队参加），哥哥男子项目比赛，妹妹参加女子项目比赛，开幕式有一个参赛队伍代表发言仪式，兄妹俩都想
去露露脸，可只能一人去，最终他们决定到时抓阄决定，而组委会也不反对，它才不关心是哥哥还是妹妹来发言，只要派一个姓李的来说两句话就行。运动会如期举
行，妹妹抓阄获得代表李家发言的机会，哥哥参加了男子项目比赛，妹妹参加了女子项目比赛。比赛结果就不是我们关心的了。
现在让我们来做个类比（只讨论与运动会相关的话题）：
（1）类的设计：
李氏兄妹属于李氏家族，李氏是基类（这里还是抽象的纯基类），李氏又派生出两个子类（李氏男和李氏女），李氏男会所有男子项目的比赛（李氏男的成员函
数），李氏女会所有女子项目的比赛（李氏女的成员函数）。姓李的人都会发言（基类虚函数），李氏男和李氏女继承自李氏当然也会发言，只是男女说话声音不一
样，内容也会又差异，给人感觉不同（李氏男和李氏女分别重新定义发言这个虚函数）。李氏两兄妹就是李氏男和李氏女两个类的实体。
（2）程序设计：
李氏兄妹填写参赛报名表。
（3）编译：
李氏兄妹的参赛报名表被上交给组委会（编译器），哥哥和妹妹分别参加男子和女子的比赛，组委会一看就明白了（早绑定），只是发言人选不明确，组委会看到报
名表上写的是“李家代表”（基类指针），组委会不能确定到底是谁，就做了个备注：如果是男的，就是哥哥李某某；如果是女的，就是妹妹李某某（晚绑定）。组
委会做好其它准备工作后，就等运动会开始了（编译完毕）。
（4）程序运行：
运动会开始了（程序开始运行），开幕式上我们听到了李家妹妹的发言，如果是哥哥运气好抓阄胜出，我们将听到哥哥的发言（多态）。然后就是看到兄妹俩参加比赛了。。。
但愿这个比喻说清楚了虚函数、多态、早绑定和晚绑定的概念和它们之间的关系。再说一下，早绑定指编译器在编译期间即知道对象的具体类型并确定此对象调用成员函数的确切地址；而晚绑定是根据指针所指对象的类型信息得到类的虚函数表指针进而确定调用成员函数的确切地址。
2、揭密晚绑定的秘密
编译器到底做了什么实现的虚函数的晚绑定呢？我们来探个究竟。
编译器对每个包含虚函数的类创建一个表（称为V TA B L E）。在V TA B L E中，编译器放置特定类的虚函数地址。在每个带有虚函数的类
中，编译器秘密地置一指针，称为v p o i n t e r（缩写为V P T R），指向这个对象的V TA B L E。通过基类指针做虚函数调 用时（也就是做多态调用时），编译器静态地插入取得这个V P T R，并在V TA B L E表中查找函数地址的代码，这样就能调用正确的函数使晚捆绑发生。为每个类设置V TA B L E、初始化V P T R、为虚函数调用插入代码，所有这些都是自动发生的，所以我们不必担心这些。利用虚函数， 这个对象的合适的函数就能被调用，哪怕在编译器还不知道这个对象的特定类型的情况下。（《C++编程思想》）
————这段话红色加粗部分似乎有点问题，我个人的理解看后面的总结。
在任何类中不存在显示的类型信息，可对象中必须存放类信息，否则类型不可能在运行时建立。那这个类信息是什么呢？我们来看下面几个类：
class no_virtual
{
public:
void fun1() const{}
int fun2() const { return a; }
private:
int a;
}
class one_virtual
{
public:
virtual void fun1() const{}
int fun2() const { return a; }
private:
int a;
}
class two_virtual
{
public:
virtual void fun1() const{}
virtual int fun2() const { return a; }
private:
int a;
}
以上三个类中：
no_virtual没有虚函数，sizeof(no_virtual)=4，类no_virtual的长度就是其成员变量整型a的长度；
one_virtual有一个虚函数，sizeof(one_virtual)=8；
two_virtual
有两个虚函数，sizeof(two_virtual)=8； 有一个虚函数和两个虚函数的类的长度没有区别，其实它们的长度就是no_virtual的
长度加一个void指针的长度，它反映出，如果有一个或多个虚函数，编译器在这个结构中插入一个指针（ V P T R）。在one_virtual 和
two_virtual之间没有区别。这是因为V P T R指向一个存放地址的表，只需要一个指针，因为所有虚函数地址都包含在这个表中。
这个VPTR就可以看作类的类型信息。
那我们来看看编译器是怎么建立VPTR指向的这个虚函数表的。先看下面两个类：
class base
{
public:
void bfun(){}
virtual void vfun1(){}
virtual int vfun2(){}
private:
int a;
}
class derived : public base
{
public:
void dfun(){}
virtual void vfun1(){}
virtual int vfun3(){}
private:
int b;
}
两个类VPTR指向的虚函数表（VTABLE）分别如下：
base类
——————
VPTR——> |&base::vfun1 |
——————
|&base::vfun2 |
——————
derived类
———————
VPTR——> |&derived::vfun1 |
———————
|&base::vfun2 |
———————
|&derived::vfun3 |
———————
每当创建一个包含有虚函数的类或从包含有虚函数的类派生一个类时，编译器就为这个类创建一个VTABLE，如上图所示。在这个表中，编译器放置了在这个类
中或在它的基类中所有已声明为virtual的函数的地址。如果在这个派生类中没有对在基类中声明为virtual的函数进行重新定义，编译器就使用基类
的这个虚函数地址。（在derived的VTABLE中，vfun2的入口就是这种情况。）然后编译器在这个类中放置VPTR。当使用简单继承时，对于每
个对象只有一个VPTR。VPTR必须被初始化为指向相应的VTABLE，这在构造函数中发生。
一旦VPTR被初始化为指向相应的VTABLE，对象就"知道"它自己是什么类型。但只有当虚函数被调用时这种自我认知才有用。
个人总结如下：
1、从包含虚函数的类派生一个类时，编译器就为该类创建一个VTABLE。其每一个表项是该类的虚函数地址。
2、在定义该派生类对象时，先调用其基类的构造函数，然后再初始化VPTR，最后再调用派生类的构造函数（
从二进制的视野来看，所谓基类子类是一个大结构体，其中this指针开头的四个字节存放虚函数表头指针。执行子类的构造函数的时候，首先调用基类构造函
数，this指针作为参数，在基类构造函数中填入基类的vptr，然后回到子类的构造函数，填入子类的vptr，覆盖基类填入的vptr。如此以来完成
vptr的初始化。 ）
3、在实现动态绑定时，不能直接采用类对象，而一定要采用指针或者引用。因为采用类对象传值方式，有临时基类对象的产生，而采用指针，则是通过指针来访问外部的派生类对象的VPTR来达到访问派生类虚函数的结果。
VPTR
常常位于对象的开头，编译器能很容易地取到VPTR的值，从而确定VTABLE的位置。VPTR总指向VTABLE的开始地址，所有基类和它的子类的虚函
数地址（子类自己定义的虚函数除外）在VTABLE中存储的位置总是相同的，如上面base类和derived类的VTABLE中vfun1和vfun2
的地址总是按相同的顺序存储。编译器知道vfun1位于VPTR处，vfun2位于VPTR+1处，因此在用基类指针调用虚函数时，编译器首先获取指针指
向对象的类型信息（VPTR），然后就去调用虚函数。如一个base类指针pBase指向了一个derived对象，那pBase->vfun2
()被编译器翻译为 VPTR+1 的调用，因为虚函数vfun2的地址在VTABLE中位于索引为1的位置上。同理，pBase->vfun3
()被编译器翻译为 VPTR+2的调用。这就是所谓的晚绑定。
我们来看一下虚函数调用的汇编代码，以加深理解。
void test(base* pBase)
{
pBase->vfun2();
}
int main(int argc, char* argv[])
{
derived td;
test(&td);
return 0;
}
derived td;编译生成的汇编代码如下：
mov DWORD PTR _td$[esp+24], OFFSET FLAT:??_7derived@@6B@ ; derived::`vftable'
由编译器的注释可知，此时PTR _td$[esp+24]中存储的就是derived类的VTABLE地址。
test(&td);编译生成的汇编代码如下：
lea eax, DWORD PTR _td$[esp+24]
mov DWORD PTR __$EHRec$[esp+32], 0
push eax
call ?test@@YAXPAVbase@@@Z ; test
调用test函数时完成了如下工作：取对象td的地址，将其压栈，然后调用test。
pBase->vfun2();编译生成的汇编代码如下：
mov ecx, DWORD PTR _pBase$[esp-4]
mov eax, DWORD PTR [ecx]
jmp DWORD PTR [eax+4]
首先从栈中取出pBase指针指向的对象地址赋给ecx，然后取对象开头的指针变量中的地址赋给eax，此时eax的值即为VPTR的值，也就是
VTABLE的地址。最后就是调用虚函数了，由于vfun2位于VTABLE的第二个位置，相当于 VPTR+1，每个函数指针是4个字节长，所以最后的
调用被编译器翻译为 jmp DWORD PTR [eax+4]。如果是调用pBase->vfun1()，这句就该被编译为
jmp DWORD PTR [eax]。
现在应该对多态、虚函数、晚绑定有比较清楚的了解了吧。
转贴：http://blog.csdn.net/shenmea00000/archive/2007/10/31/1859762.aspx
转载：http://www.cppblog.com/converse/archive/2007/08/29/31179.html
/********************************************************************
created: 2007/08/28
filename: avltree.c
author: Lichuang
purpose: AVL树的实现代码,
参考资料<<数据结构与算法分析-C语言描述>>, 作者Allen Weiss
*********************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct AVLTree
{
int nData;
struct AVLTree* pLeft;
struct AVLTree* pRight;
int nHeight;
}AVLTree;
int Max(int a, int b);
int Height(AVLTree* pNode);
AVLTree* Insert(int nData, AVLTree* pNode);
AVLTree* SingleRotateWithLeft(AVLTree* pNode);
AVLTree* SingleRotateWithRight(AVLTree* pNode);
AVLTree* DoubleRotateWithLeft(AVLTree* pNode);
AVLTree* DoubleRotateWithRight(AVLTree* pNode);
void DeleteTree(AVLTree** ppRoot);
void PrintTree(AVLTree* pRoot);
int main()
{
int i;
AVLTree* pRoot = NULL;
srand((unsigned int)::time(NULL));
for (i = 0; i < 100000000; ++i)
{
pRoot = Insert(::rand(), pRoot);
}
//PrintTree(pRoot);
DeleteTree(&pRoot);
return 0;
}
int Max(int a, int b)
{
return (a > b ? a : b);
}
int Height(AVLTree* pNode)
{
if (NULL == pNode)
return -1;
return pNode->nHeight;
}
AVLTree* Insert(int nData, AVLTree* pNode)
{
if (NULL == pNode)
{
pNode = (AVLTree*)malloc(sizeof(AVLTree));
pNode->nData = nData;
pNode->nHeight = 0;
pNode->pLeft = pNode->pRight = NULL;
}
else if (nData < pNode->nData) // 插入到左子树中
{
pNode->pLeft = Insert(nData, pNode->pLeft);
if (Height(pNode->pLeft) - Height(pNode->pRight) == 2) // AVL树不平衡
{
if (nData < pNode->pLeft->nData)
{
// 插入到了左子树左边, 做单旋转
pNode = SingleRotateWithLeft(pNode);
}
else
{
// 插入到了左子树右边, 做双旋转
pNode = DoubleRotateWithLeft(pNode);
}
}
}
else if (nData > pNode->nData) // 插入到右子树中
{
pNode->pRight = Insert(nData, pNode->pRight);
if (Height(pNode->pRight) - Height(pNode->pLeft) == 2) // AVL树不平衡
{
if (nData > pNode->pRight->nData)
{
// 插入到了右子树右边, 做单旋转
pNode = SingleRotateWithRight(pNode);
}
else
{
// 插入到了右子树左边, 做双旋转
pNode = DoubleRotateWithRight(pNode);
}
}
}
pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
return pNode;
}
/********************************************************************
pNode pNode->pLeft
/ \
pNode->pLeft ==> pNode
\ /
pNode->pLeft->pRight pNode->pLeft->pRight
*********************************************************************/
AVLTree* SingleRotateWithLeft(AVLTree* pNode)
{
AVLTree* pNode1;
pNode1 = pNode->pLeft;
pNode->pLeft = pNode1->pRight;
pNode1->pRight = pNode;
// 结点的位置变了, 要更新结点的高度值
pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
pNode1->nHeight = Max(Height(pNode1->pLeft), pNode->nHeight) + 1;
return pNode1;
}
/********************************************************************
pNode pNode->pRight
\ /
pNode->pRight ==> pNode
/ \
pNode->pRight->pLeft pNode->pRight->pLeft
*********************************************************************/
AVLTree* SingleRotateWithRight(AVLTree* pNode)
{
AVLTree* pNode1;
pNode1 = pNode->pRight;
pNode->pRight = pNode1->pLeft;
pNode1->pLeft = pNode;
// 结点的位置变了, 要更新结点的高度值
pNode->nHeight = Max(Height(pNode->pLeft), Height(pNode->pRight)) + 1;
pNode1->nHeight = Max(Height(pNode1->pRight), pNode->nHeight) + 1;
return pNode1;
}
AVLTree* DoubleRotateWithLeft(AVLTree* pNode)
{
pNode->pLeft = SingleRotateWithRight(pNode->pLeft);
return SingleRotateWithLeft(pNode);
}
AVLTree* DoubleRotateWithRight(AVLTree* pNode)
{
pNode->pRight = SingleRotateWithLeft(pNode->pRight);
return SingleRotateWithRight(pNode);
}
// 后序遍历树以删除树
void DeleteTree(AVLTree** ppRoot)
{
if (NULL == ppRoot || NULL == *ppRoot)
return;
DeleteTree(&((*ppRoot)->pLeft));
DeleteTree(&((*ppRoot)->pRight));
free(*ppRoot);
*ppRoot = NULL;
}
// 中序遍历打印树的所有结点, 因为左结点 < 父结点 < 右结点, 因此打印出来数据的大小是递增的
void PrintTree(AVLTree* pRoot)
{
if (NULL == pRoot)
return;
static int n = 0;
PrintTree(pRoot->pLeft);
printf("[%d]nData = %d\n", ++n, pRoot->nData);
PrintTree(pRoot->pRight);
}
听着舒伯特和肖邦的小夜曲，两种不同的风格，听了都特别的舒服，感觉特别地宁静，让我浮躁的心能安静下来，说不上好在哪里，可能比较符合我现在的心境吧，或许我生活中还缺少某种元素。
以STL的运用角度而言，空间配置器时最不需要介绍的东西，它总是隐藏在一切组件的背后，整个STL的操作对象（所有的数值）都存放在容器之内，而容器一定需要配置空间以置放资料。下面是一个简单空间配置器代码（来自 STL源码剖析）：
//jjalloc.h
#ifndef _JJALLOC_
#define _JJALLOC_
#include<new>
#include<cstddef>
#include<cstdlib>
#include<climits>
#include<iostream>
using namespace std;
namespace JJ
{
template<class T>
inline T* _allocate(ptrdiff_t size,T*)
{
set_new_handler(0);
T *tmp=(T*)(::operator new((size_t)(size* sizeof(T))));
if(tmp==0){
cerr<<"out of memory"<<endl;
exit(1);
}
return tmp;
}
template<class T>
inline void _deallocate(T* buffer)
{
::operator delete(buffer);
}
template<class T1,class T2>
inline void _construct(T1 *p,const T2& value)
{
new(p)T1(value);//placement new operator
}
template<class T>
inline void _destroy(T* ptr)
{
ptr->~T();
}
template<class T>class allocator{
public:
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
template<class U>
struct rebind
{
typedef allocator<U>other;
};
pointer allocate(size_type n,const void * hint=0)
{
return _allocate((difference_type)n,(pointer)0);
}
void deallocate(pointer p,size_type n)
{
_deallocate(p);
}
void construct(pointer p,const T& value)
{
_construct(p,value);
}
void destroy(pointer p){_destroy(p);}
pointer address(reference x){return (pointer)&x;}
const_pointer const_address(const_reference x)
{
return (const_pointer)&x;
}
size_type max_size()const{
return size_type(UINT_MAX/sizeof(T));
}
};
}//end of namespace JJ
#endif
//jjalloc.cc,测试上面这个简单的配置器
#include"jjalloc.h"
#include<vector>
#include<iostream>
using namespace std;
int main()
{
int ia[5]={0,1,2,3,4};
unsigned int i;
vector<int,JJ::allocator<int> >iv(ia,ia+5);
for(i=0;i<iv.size();i++)
cout<<iv[i]<<' ';
cout<<endl;
}