没有模板代码膨胀的STL：一、设计目标与实现思路_stl 改造为 c 代码膨胀

总目录
一、设计目标与实现思路
二、使用方法与注意事项
三、开发者指南
四、一些讨论和个人心得

公司里很多项目因为模板代码膨胀的问题而放弃甚至禁止使用STL。但是，STL又确实可以给编码带来诸多便利。
在此背景下，我发起了这个开源项目：POD_STL。当前已经完成了vector、string、list、deque、set、multiset、map、multimap等容器，以及一些基本算法、迭代器、函数对象、类型traits、pair的实现，可以支持大多数项目的使用需求。

设计目标

1、在不过多降低性能的前提下，尽量减小STL容器模板带来的目标代码膨胀。
什么是模板代码膨胀？在C++中，函数模板代表一类函数。使用非内联的函数模板时，对于每一种模板参数类型，编译器都会自动生成一个对应此类型实例化的函数。如果不同的实例化类型太多，就会造成目标文件中生成了大量对不同类型实例化的函数实体。这些函数的逻辑、算法几乎完全一样，只是操作的类型不同。这导致目标二进制文件变得太大。
类模板和函数模板类似，但其代码膨胀问题只出现在成员函数的实例化过程中。因为类定义本身不占用程序二进制空间。

POD_STL对于模板代码膨胀做的优化仅针对STL容器（比如vector、map等），不针对STL算法（如copy、find）。因为当前各个项目遇到的模板代码膨胀问题主要来自于容器。而STL算法大部分都是内联的，没有函数实体膨胀问题。

2、不依赖任何C++运行时库，只需要C语言运行时库就可以工作。
这是因为很多嵌入式项目并不需要使用异常等C++特性，如果链接C++运行时库会增大目标文件体积。POD_STL可以让项目只链接C语言运行时库，但仍然支持用C++语言编码，并且使用STL！

3、内部完全不使用new和delete关键字，只用统一的可定制接口（STL_Malloc，STL_Free）来申请/释放内存。
这是为那些重载了new和delete操作符的项目考虑的。这些项目往往有自己的内存申请释放函数，他们可以通过定制POD_STL中的STL_Malloc/STL_Free函数实现来方便的应用自己的内存操作。这样可以避免new/delete关键字被重载后带来的编译错误。
但是，完全不用new会导致一些STL算法无法实现（比如uninitialized_copy只能用new()实现）。这些算法在POD_STL中被裁减。好在这些算法一般用得很少。

4、所有接口与最新的STL标准保持一致。
当今已经有一些项目组自己实现了一些容器来替代STL。但是，还没有任何一套容器的使用方法与STL标准一致。这些替代容器对使用者提出很多要求，比如只允许存放void*指针，只允许map的索引为long long类型等等。这导致这些替代容器远远没有标准STL容器好用。而且一旦项目要从标准STL切换成自定义容器，就要投入很多人力进行整改。即使整改成功了，也把项目所有代码的可移植性大大降低了——毕竟STL接口是世界统一标准，但替代容器接口却是项目组自己闭门造车搞出来的。

POD_STL的所有对外接口与标准STL完全相同（极少数被裁剪的特性除外）！它仍然有完备的模板参数支持，有各种迭代器、算法、函数对象，仍然支持用自定义类型和自定义比较运算符来定制关系型容器（这意味着你可以用任何类型作为map的key）。对于大多数项目，可以不需要修改任何代码，就直接切换到POD_STL，解决目标文件过大的问题！

当然，为了解决模板代码膨胀问题，POD_STL使用了一些优化技巧，其代价是部分STL的定制功能（比如allocator）被裁减，同时对于容器可以存放的元素类型也有限制。好在这些边缘功能平时用得很少，带来的影响并不大。

实现思路

要解决模板代码膨胀问题，最有效的方法是把内部函数实现去模板化。但是，由于容器外部接口不能改变，因此POD_STL的所有容器仍然是类模板。但类模板的所有成员函数都只是一个内联的“壳”，它仅仅只调用其非模板基类的另一个成员函数，在后者中实现真正的功能。

比如，vector容器的push_back函数是这样实现的：