最近两个月花时间实现了一个小型的容器库(Github地址，以下简称Minimal Container)，实现了C++中的dynamic array,list,queue,map,hashmap,set,hashset等基本的容器，它是一个非正式的、业余的作品，做这个小项目主要是想积累一下写库的经验。这篇文章记录一下我编程时遇到的问题、及每个容器的实现思路。
思考
设计并实现一个好的库不是一件容易的事，需要熟悉业务、积累经验。我在实现Minimal Container时，考虑以下几点：
- 如何做封装：隐藏内部变量，隔离变化，适应变化。
- 如何做抽象：从各种不同的类型、方法、环境中抽象出一致的方法。
- 如何设计接口：从易用、一致性、灵活性方面考虑。
- 如何实现复杂一些的数据结构(如hashtable,red-black tree)。
其实对标准容器库来说，抽象、设计接口并不是难事，因为它的功能不复杂，业内的开源代码、教科书上都已经有总结了。我觉得难点在于如何抽象出一致性，并设计一个简单易用、一致性的接口。比如STL中每个容器中都有empty(),insert(),erase(),find()，并对每个容器的访问抽象了一层，实现的容器的迭代器，使得算法和容器的实现能够分离，也使得接口易于使用。
实现一个业务库可能更难一些，因为它没有范例参考，只能根据开发者的经验来抽象出接口。今年在维护一个内部的告警主机项目(alarmpu)时，我对抽象、设计有了更直接、深刻的理解。alarmpu中采用了插件式设计，将其中类似的一组功能(如初始化告警源、什么时候初始好、什么时候产生告警信号)抽象成了一组函数(通知采用回调函数)，这些函数组成了一个插件(其实就是一个动态链接库DLL)，项目主体只调用DLL一些来完成一些简单的逻辑处理(如程序启用时调用dll来连接到告警源，收到告警信息时将信号转发给平台)，这使得软件很容易扩展，也会隔离变化。要扩展一个新的告警源实现告警联动时，只需实现DLL的一些接口函数即可。实现这些接口不难，难的是从实践中抽象总结出这些接口，这个需要业务经验的积累。
实现
总体实现的一些特点：
- 每个容器都提供一致的容器迭代器，如List::Position,Set::Position,Map::Position，提供一致的向前访问、向后访问接口。
- 每个容器都提供一个回调函数，用来遍历操作容器内的所有元素。
- 函数名采用一致的命名方法: 谓语+宾语。如MakeEmpty()，而不用Empty()；GetFirstPos()，而不用FirstPos()。
- public函数名均使每个首字母大写来分隔单词（如
InsertHead()），private函数名以__开头，用_来分隔单词（如__sort_list()）。
以下按头文件讲述各个容器的实现思路，及编程时遇到的问题。
list.h
用C++模板实现了双向链表，实现了一些基本的增删改查接口。在实现时遇到了两个问题：
-
是否要将链表结点的定义ListNode放到List中？
一般来说，总是要将内部使用的类定义放到内部，主要是封装、隔离变化，也可以减少命名冲突。我在第一遍写的时候也是这么做的，但是在编译返回ListNode的函数时报错，因为不能返回private类型的变量。如果将ListNode声明成public也能编译通过，但是代码不太好看、比较拖沓。后来我将ListNode放到了List外部来定义，显得干净清爽多了。如果担心命名冲突，可以在container中定义了命名空间。
也许会问为什么要在成员函数中返回ListNode类型的元素？因为要实现迭代器，我在list.h中是重命名了ListNode成Position，而在STL中是将ListNode向上封装了一层iterater，原理是一样的。
-
如何实现链表排序？
在剖析STL源码时发现STL中实现了链表排序，自己也想试一把。折腾两天，才写出来。在链表中实现快速排序，还是挺麻烦的，具体方法可以参看我的一篇文章。
darray.h
用C++模板实现了动态数组，实现了一些基本的增删改查接口。设计时遇到了一个问题：
-
数组刚初始化应分配多大空间？什么时候该增加可分配空闲空间的大小，如何增长？当元素删除了很多，要怎么来减少空闲空间的占用？
参考了STL及一些开源代码，我的方法是：刚初始化时分配的数组空间为15个，当插入数据导致空间不够时，再分配(m_dwCapacity * 2)多一倍的空间。元素删除时，只做前移不释放空间，只有当使用空间的大小比空闲空间的大小小时，才将总空间减少至使用大小的1.5倍。
deque.h,queue.h,stack.h
用C++模板实现了双向队列，链表，和栈，实现了一些基本的增删改查接口。这三个数据结构都是基于list,darray实现的，方法基本都是调的list,darray的接口。
hash_map.h,hash_set.h
基于hashtable实现map和set，底层的难点在于如何实现hashtable。hashtable是采用开链法实现，设计时的考虑如下：
-
hash函数的设计。
hash函数的设计直接关系到map,set性能的好坏及空间的利用率。好的hash函数的特点有两个：1）不要太复杂，计算速度快。2）能够比较均匀得落到分配的各个桶内。参考了一些开源代码，我的hash函数如下：
inline size_t hash_mysql(const char* key, size_t len) { if (key == 0) return 0; size_t nr=1, nr2=4; while (len--) { nr^= (((nr & 63)+nr2)*((size_t) (byte) *key++))+ (nr << 8); nr2+=3; } return((size_t) nr); } inline size_t hash_string(const char* pStr, size_t len) { if (pStr == 0) return 0; size_t nHash = 0; while (*pStr) nHash = (nHash<<5) + nHash + *pStr++; return nHash; }第一个是对除字符串类型以外的类型做hash（会先将结构体强转成const char*型，再计算。），第二个是对字符串做hash运算。
-
要预分配的桶的数量是多少，什么时候该增长，如何增长？
这也是关于hash实现很重要的问题。我采用的是STL中的方法：预先定义28个质数，初始化时桶的数量是第一个质数，当插入数据太多，导致桶的数量 小于存储的对象数量时，重新分配一个更多的hash桶数（即采用更大的一个质数）。这28个质数使用数组存储，并定义一个函数来获取更大的一个质数。// 注意：假设 long 至少有 32 bits static const u32 DEFAULT_PRIME_NUM = 28; static const u32 __primlist[DEFAULT_PRIME_NUM] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473ul, 4294967291ul }; // 以下找出上述28个质数之中，最接近并大于n的那个质数 inline u32 __hash_next_prime(u32 n) { for (u32 dwIndex = 0; dwIndex < DEFAULT_PRIME_NUM; dwIndex++) { if (__primlist[dwIndex] >= n) { return __primlist[dwIndex]; } } return __primlist[DEFAULT_PRIME_NUM-1]; } -
hashtable 中的内存管理如何实现？是实现一个小对象的内存管理器？
这是涉及hashtable中的内存管理。在STL中是使用ListNode的小对象内存分配器（即
node_allocator），我实现得简单些。在hashtable内部维护一个空闲链表，即存储空闲结点。在hashtable初始化时，预先分配100个空闲结点，当元素插入时，从链表中取一个空闲结点。如果空闲结点已分配完，则再预分配100个结点。当元素释放时，不释放空间，而是将结点放回到链表中。
rbtree.h,ordered_map.h,ordered_set.h
STL中的map,set是用红黑树实现。红黑树是一种平衡的二叉搜索树，在删除、插入后要进行调整（rotate树中结点和颜色）来维护树的平衡。因为这个数据结构查询效率高（O(logn)），且每次插入删除所做的再调整（即rebalance树结点）的开销相对较合理，所以很多关联存储结构会采用红黑树来实现（比如Linux内核中的CFS调度器，STL中的map,set）。关于红黑树的实现，难点在于删除、插入后的再调整，调整的过程在一般教科书上都有讲述，网上也有一些开源的实现代码，在此不再赘述。
在实现红黑树的过程中，要注意对结点指针的改变顺序比较小心，如果稍一疏忽，查bug调试过程会比较费力。
在编码的时候遇到一个问题：一般都知道在类的构造函数中初始化所有的成员变量，但是如果构造函数中调用的函数使用了类的成员，必须要先在调用的函数前初始化这个成员变量，再调这个函数。我在编程中遇到了这个问题，debug了很久才找到原因。
关于Map,Set的实现基于都是用rbtree封装了一层，直接调用它提供的接口即可实现。