C/C++ young library

C/C++ young library 设计与实现 — 序篇收藏

    开始有实现自己的STL的想法始于2003年，当时刚开始深入学习STL，对各个编译器STL
还不是很了解，大概在2004年年初的时候，在工作中碰到的一件事情促使我开始了这项工作。
当时，因为工作的需要，我需要Borland C++ Builder下调用Visual C++写的动态链接库，
我在动态链接库的一个接口函数中使用了vector，不用说，大家也可以想到，这个函数无
法在Borland C++ Builder下被调用——两个编译器实现的STL完全不同！当时不知所以，后
来在网上查阅了资料，最主要的是阅读了侯捷先生的《STL源码剖析》之后，才明白了原因。
当时没有做太多的考虑，只是想解决STL的移植问题，心想SGI STL移植太麻烦，不如自己
写一个算了，就算写不出来，也算是锻炼了自己的编程能力，复习了一遍数据结构和算法
好了。于是，工作就这样开始了。
    在2005年年中，我完成了用C++实现的一个包含了STL容器和算法以及部分function
object的模板库，因为只想自己用，所以用自己的性的谐音起了一个namespace——young。
但是，理想是美好的，现实是残酷的，在开发的过程中，我一直使用GCC，实际使用时才
发现大多数编译器无法正确编译！唉！说来也怪自己，在看《STL源码剖析》时，直接把
移植那一部分给跳了过去……自我感觉程序写的还算整齐，之后，我把这个库的源码在网上
共享，供想学习STL实现的朋友参考。而这个事情随着我工作的加重，也就被我慢慢的淡
忘了，直到2005年12月……当时我所在的公司是一家从事电力系统产品开发的公司，弱电部
分主要以嵌入式产品为主，我所在的项目是个例外，是一个以PC为上位机，以单片机为下
位机的产品，我主要负责上位机部分。2005年年末的时候，我所负责的部分已快接近尾声，
有一天，负责下位机的同事和我聊天时表示他准备在新产品中使用DSP，他要我在完成工作
之后帮他实现一个实时操作系统。言者无心，听者有意，我正想从事一些基础软件的开发，
遂开始了学习和预研，在设计的时候，我发现因为自己长期在PC平台下工作，习惯了大量
使用STL来进行开发，但是在嵌入式系统的开发中就没有这种待遇了，这对于习惯了使用
STL的我来说可不是一个好消息，“工欲善其事，必先利其器”，我遂决定先开发一个STL的
C实现，再在此基础上进行开发。在开发新的C库的过程中，我大量借鉴了原先开发的C++模
板库的经验，为了区分，我把原来的模板库重新更名为MiniSTL，新的C库称为youngc。
    早在写MiniSTL的时候，我就感觉到C++ template更像一种构建在C++类型系统上的
shell语言，但是使用模板来进行一些传统的开发未必合适。例如模板带来的代码膨胀问题
就是一个头疼的事情。在写MiniSTL的时候，我发现所有的容器类大部分代码都是相同的，
只是调用的默认构造函数、复制构造函数、赋值操作符、析构函数不同而已；所以在写完
youngc之后，我又尝试性的以youngc为kernel，以C++ template为shell，先写了一个
vector，写完之后一调试，发现完全可行！于是，趁热打铁，不到两个星期就把STL中的容
器以这种方式一一实现了，而且还在参考了C++ TR1后，实现了unordered_set, unordered_map,
unordered_multiset、unordered_multimap四个新增的容器。
    在工作以及完成程序库的过程中我积累了一些经验，看着网上不少刚学编程的朋友欲
入门而不得其法，我觉得我应该写些东西，希望读过这个系列文章的朋友能少走一些弯路。
有鉴于此，我想以我实现的这个程序库为例，向刚入门的朋友讲解我在实现过程中所学习
和使用的技术，C/C++编程，数据结构、算法以及一部分软件工程的知识是讲述的重点。
说到软件工程，没有从事过实际工作的朋友很难理解为什么要学习这门“华而不实”的学科，
其实我也是在完成了一个实际的开发工作后才真正的有一点理解的！尤其是测试的重要性，
我也是在最近才理解！我所在的公司有两位年过50的专家，他们就告诉我，开发中最难的
是设计和测试，实现是最简单的。在库的发布中有我编写的数千行的交互式的测试程序，
有了它们的帮助，我找出了程序中的很多致命的BUG，在后续的文章中我将详细的介绍。


    源码我已在OSDN上发布，下载地址为：
   


附：下面列出的书包含了我在实现young程序库所用到的知识，这些书都是我仔细读过或走
马观花翻阅过的。
    《C程序设计语言（第二版）》
    《C++程序设计语言（特别版）》
    《算法导论（第二版）》
    《数据结构与STL》
    《泛型编程与STL》
    《STL源码剖析》
    《深度探索C++对象模型》
    《C++ template》（中文版）
    《Exceptional C++》（中文版）
    《More Exceptional C++》（中文版）
    《Exceptional C++ Style》（中文版）
    《Effective STL》
    《C++编程规范》
    《设计模式：可复用面向对象软件的基础》
    《代码大全（第二版）》

C/C++ young library 设计与实现 — 移植收藏

    这一篇将介绍如何将程序库移植到不同的平台和编译器上。程序库是用标准C和C++来
编写的，理论上是不应该存在移植的问题的，但是由于各个编译器厂家对标准C和C++（尤
其是C++）支持的程度大不相同，所以了解如何移植是很有必要的。由于程序库仍在改进
中，因此以下内容以0.8.4版为参考。

    **2.1**

    youngc程序库的移植。

    *2.1.1*

    要使youngc程序库能顺利编译，编译器至少要满足：
    1、支持标准的函数指针；
    2、支持除法运算。
    我在使用KEIL C51编译的时候，就是由于编译器无法很好的支持函数指针以及不支持
除法运算，导致编译失败。

    *2.1.2*

    下面列出youngc子库中各个文件的功能及其依赖关系：
-------------------------------------------------------------------------------
      文件名                       功能                      包含文件
-------------------------------------------------------------------------------
    yc_config.h        youngc程序库条件编译宏设置文件           无
    yc_definition.h    youngc程序库常量、宏、类型定义文件    stddef.h
                                                             limits.h
                                                             yc_config.h
    yc_memory.h        存储函数声明                          yc_definition.h
    yc_memory.c        存储函数实现                          stdlib.h
                                                             yc_memory.h
    yc_memalgo.h       memory类型通用算法声明                yc_definition.h
    yc_memalgo.c       memory类型通用算法实现                yc_memalgo.h
    yc_rscalgo.h       resource类型通用算法声明              yc_definition.h
    yc_rscalgo.c       resource类型通用算法实现              yc_memalgo.h
                                                             yc_rscalgo.h
    yc_dymemarr.h      动态存储类型数组的声明                yc_definition.h
    yc_dymemarr.c      动态存储类型数组的实现                yc_memalgo.h
                                                             yc_dymemarr.h
    yc_dyrscarr.h      动态资源类型数组的声明                yc_definition.h
    yc_dyrscarr.c      动态资源类型数组的实现                yc_memalgo.h
                                                             yc_rscalgo.h
                                                             yc_dyrscarr.h
    yc_dblnklst.h      双向循环链表的声明                    yc_definition.h
    yc_dblnklst.c      双向循环链表的实现                    yc_memalgo.h
                                                             yc_dblnklst.h
    yc_sglnklst.h      单向链表的声明                        yc_definition.h
    yc_sglnklst.c      单向链表的实现                        yc_memalgo.h
                                                             yc_sglnklst.h
    yc_chkarray.h      数据块阵列的声明                      yc_definition.h
    yc_chkarray.c      数据块阵列的实现                      yc_memalgo.h
                                                             yc_chkarray.h
    yc_bbstree.h       平衡二叉查找树的声明                  yc_definition.h
    yc_bbstree.c       平衡二叉查找树的实现                  yc_memalgo.h
                                                             yc_bbstree.h
    yc_hashtable.h     散列表的声明                          yc_definition.h
    yc_hashtable.c     散列表的实现                          yc_memalgo.h
                                                             yc_hashtable.h
    yc_string.h        动态字符串的声明                      stdio.h
                                                             yc_definition.h
                                                             yc_dymemarr.h
    yc_string.c        动态字符串的实现                      wchar.h（支持宽字符串时需要）
                                                             wctype.h（支持宽字符串时需要）
                                                             ctype.h
                                                             float.h
                                                             string.h
                                                             stdarg.h
                                                             yc_memory.h
                                                             yc_memalgo.h
                                                             yc_string.h
    yc_function.h      辅助函数的声明                        yc_definition.h
    yc_function.c      辅助函数的实现                        limits.h
                                                             math.h
                                                             float.h
                                                             string.h
                                                             yc_function.h
    yc_algorithm.h     通用算法的声明                        yc_memalgo.h
                                                             yc_rscalgo.h
    yc_algorithm.c     通用算法的实现                        yc_algorithm.h
-------------------------------------------------------------------------------

    *2.1.3*

    youngc子库的移植主要由yc_config.h中定义的条件编译宏来完成控制，定义的宏及其
含义如下：

    1、__MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_STANDARD_MEMORY_FUNCTION__
    若编译器附带的标准库支持memcpy、memmove、memset函数则定义该宏。该宏主要用于
控制yc_memalgo.h中的ylib_memcopy、ylib_memmove、ylib_memset函数，如果该宏定义，
则这三个函数被定义为宏，分别调用memcpy、memmove、memset函数；如果使用者想使用自
己实现的效率更高的相应功能的函数，则可以禁止定义该宏，并在yc_memalgo.c中分别实现
ylib_memcopy、ylib_memmove、ylib_memset函数。

    2、__MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_IO_SYSTEM__
    若编译器支持C语言标准库的IO系统，则定义该宏。该宏主要用于控制yc_string.h、
yc_string.c中的动态字符串与IO的交互。

    3、__MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_FILE_SYSTEM__
    若编译器支持C语言标准库的文件系统，则定义该宏。该宏主要用于控制yc_string.h、
yc_string.c中的动态字符串与文件的交互。

    4、__MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_C95_WIDE_CHARACTER__
    若编译器及附带的标准库支持ISO C95标准定义的宽字符功能，则定义该宏。该宏主要
用于控制yc_string.h、yc_string.c中的动态宽字符串的声明与实现。

    5、__MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_BOOLEAN_TYPE__
    若编译器支持bool类型，则定义该宏。如果编译器支持ISO C99标准，或者使用C++编
译器编译，或者编译器扩展了对该功能的支持，均可以在yc_config.h中定义该宏。

    6、__MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_INLINE_FUNCTION__
    若编译器支持内联函数，则定义该宏。如果编译器支持ISO C99标准，或者使用C++编
译器编译，或者编译器扩展了对该功能的支持，均可以在yc_config.h中定义该宏。

    7、__MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_LONG_LONG_TYPE__
    若编译器支持long long类型，则定义该宏。在ISO C99中，long long被定义为不小于
64位的整数，如果编译器支持ISO C99标准，或者编译器扩展了对该功能的支持，均可以在
yc_config.h中定义该宏。

    8、__MACRO_C_YOUNG_LIBRARY_COMPILER_SUPPORT_VARIABLE_LENGTH_ARRAY__
    若编译器支持变长数组，则定义该宏。如果编译器支持ISO C99标准，或者编译器扩展
了对该功能的支持，均可以在yc_config.h中定义该宏。

    *2.1.4*

    使用建议：
    如果需要在工程中使用youngc程序库，可以将youngc目录下的文件全部加入工程进行
编译，也可以只将需要用到的文件加入工程进行编译，但是需要文件之间的依赖关系，可
以参看2.1.2列出的程序库文件表。
    在Linux、Unix下，可以将程序库编译成静态库或共享库；在Windows下，可以将程序
库编译成动态链接库，只是需要修改头文件中函数的声明和.c文件中相应函数的声明。
    如果在无操作系统支持的嵌入式系统上使用的话，建议yc_memory.*不要使用。如果
硬件平台不支持浮点数的话，则散列表无法使用。如果编译器附带的标准库对float.h不
能完全支持的话，则yc_function.c可能会无法通过编译。
    需要注意的是对动态字符串的使用，从上面的文件依赖关系可以看到yc_string.*对
标准库的依赖很大，如果是在嵌入式系统上使用的话，这些标准库函数并不一定能得到完
全的支持，因此，在嵌入式系统中yc_string.*要慎用。目前的C编译器对宽字符的支持不
甚理想。比较好的是在PC以上的硬件平台上使用的编译器，而像编译DSP、ARM等嵌入式硬
件平台程序的C编译器根本就不支持宽字符。然而即使是在PC平台上，Microsoft Visual C++、
Borland C++ Builder等主流编译器对宽字符也并不是完全支持，而像GCC这种号称可移植
的编译器，相同版本的编译器在不同的硬件平台上会呈现出完全不同的支持，再加上国人
常用的汉字编码似乎以四字节编码居多，而国际上流行的编码方式也多为比宽字符更长的
多字节编码。基于这些考虑，我并不鼓励使用标准库定义的宽字符，感觉用处不大！

    **2.2**

    youngcpp程序库的移植。

    *2.2.1*

    youngcpp程序库是一个C++模板库，实现这个库的目的是想验证能否以youngc为内核，
以C++ template为shell，实现一个接口与STL兼容的模板库，在完成并试验了vector之后，
发现是可行的，于是干脆把STL的容器全部实现了。由于youngcpp的容器类具有move语意，
所以使用youngcpp实现复合容器具有比STL更高的效率。
    youngcpp是以标准C++的模板来实现的，因此大多数嵌入式平台使用的C++编译器都无
法正确编译，事实上，除了GCC目前我所用过的嵌入式平台编译器均无法编译。在PC平台
上，Borland C++ Builder 6(SP4)勉强可以编译，Microsoft Visual C++ 7.1以下的微软
编译器是无法编译的，GCC 3.2以下的版本也无法通过编译，GCC 4.0以上的版本我没有用
过，不知道是否能顺利编译。

    *2.2.2*

    下面列出youngcpp子库中各个文件的功能及其依赖关系：
-------------------------------------------------------------------------------
      文件名                            功能                      包含文件
-------------------------------------------------------------------------------
    ycpp_config.hpp           youngcpp程序库条件编译宏设置文件       无
    ycpp_function.hpp         传递给youngc函数指针的适配函数         无
    ycpp_functional.hpp       扩展的function object               youngc/yc_function.h
                                                                  ycpp_string.hpp
    ycpp_algorithm.hpp        对STL算法的扩展                     cstring
                                                                  iterator
                                                                  algorithm
                                                                  ycpp_traits.hpp
    ycpp_traits.hpp           特性萃取                            ycpp_config.hpp
                                                                  type_traits（TR1增补）
    ycpp_memory.hpp           存储管理                            new
                                                                  cstring
                                                                  ycpp_traits.hpp
    ycpp_vector.hpp           同STL的vector容器                   memory
                                                                  iterator
                                                                  stdexcept
                                                                  algorithm
                                                                  youngc/yc_dymemarr.h
                                                                  youngc/yc_dyrscarr.h
                                                                  ycpp_memory.hpp
    ycpp_deque.hpp            同STL的deque的容器                  memory
                                                                  iterator
                                                                  stdexcept
                                                                  algorithm
                                                                  youngc/yc_chkarray.h
                                                                  ycpp_memory.hpp
    ycpp_list.hpp             同STL的list的容器                   memory
                                                                  iterator
                                                                  stdexcept
                                                                  youngc/yc_dblnklst.h
                                                                  youngc/yc_memory.h
                                                                  ycpp_memory.hpp
                                                                  ycpp_function.hpp
                                                                  ycpp_algorithm.hpp
    ycpp_slist.hpp            单链表模板容器的实现                memory
                                                                  iterator
                                                                  stdexcept
                                                                  youngc/yc_sglnklst.h
                                                                  youngc/yc_memory.h
                                                                  ycpp_memory.hpp
                                                                  ycpp_function.hpp
                                                                  ycpp_algorithm.hpp
    ycpp_map.hpp              同STL的map、multimap的容器          memory
                                                                  utility
                                                                  iterator
                                                                  algorithm
                                                                  functional
                                                                  youngc/yc_bbstree.h
                                                                  youngc/yc_memory.h
                                                                  ycpp_memory.hpp
                                                                  ycpp_function.hpp
    ycpp_set.hpp              同STL的set、multiset的容器          memory
                                                                  utility
                                                                  iterator
                                                                  algorithm
                                                                  functional
                                                                  youngc/yc_bbstree.h
                                                                  youngc/yc_memory.h
                                                                  ycpp_memory.hpp
                                                                  ycpp_function.hpp
    ycpp_unordered_map.hpp    TR1新增的unordered_map、            memory
                              unordered_multimap容器              utility
                                                                  iterator
                                                                  functional
                                                                  youngc/yc_hashtable.h
                                                                  youngc/yc_memory.h
                                                                  ycpp_memory.hpp
                                                                  ycpp_function.hpp
                                                                  ycpp_functional.hpp
    ycpp_unordered_set.hpp    TR1新增的unordered_set、            memory
                              unordered_multiset容器              utility
                                                                  iterator
                                                                  functional
                                                                  youngc/yc_hashtable.h
                                                                  youngc/yc_memory.h
                                                                  ycpp_memory.hpp
                                                                  ycpp_function.hpp
                                                                  ycpp_functional.hpp
-------------------------------------------------------------------------------

    *2.2.3*

    youngcpp子库的移植主要由ycpp_config.hpp中定义的条件编译宏来完成控制，定义的
宏及其含义如下：
    1、__MACRO_CPLUSPLUS_YOUNG_LIBRARY_COMPILER_SUPPORT_LONG_LONG_TYPE__
    若C++编译器支持long long类型，则定义该宏。

    2、__MACRO_CPLUSPLUS_YOUNG_LIBRARY_COMPILER_SUPPORT_C95_WIDE_CHARACTER__
    若C++编译器及附带的标准库支持ISO C95标准定义的宽字符功能，则定义该宏。

    3、__MACRO_CPLUSPLUS_YOUNG_LIBRARY_COMPILER_SUPPORT_STANDARD_TYPE_TRAITS__
    若C++编译器及附带的标准库支持TR1定义的文件，则定义该宏。

    4、__MACRO_CPLUSPLUS_YOUNG_LIBRARY_COMPILER_SUPPORT_STANDARD_HASH_FUNCTION_OBJECT__
    若C++编译器及附带的标准库支持TR1定义的中新增的hash function object，
则定义该宏。


    *2.2.4*
    使用建议：
    由于youngcpp的底层实现是建立在youngc基础上的模板库，因此编译youngcpp的时候，
需要将其所依赖的各个youngc模块加入工程，依赖关系可以参看2.2.2列出的程序库文件表。