Daly的游戏人生

闲话STL与数据结构实现

        几乎每一个软件项目都要用到诸如链表,搜索树,堆,哈希表等一系列常用数据结构以及排序,搜索等算法。究竟是用现有的标准库(STL,boost),还是根据项目需要自己实现呢?之所以提出这个问题,是因为笔者发现很多有名的开源项目都没有用一行的STL(更不用说boost,loki之类的,笔者见识有限,至今还没见过有影响力的软件用了boost,尽管他很优秀),于是搜集了一些关于STL的讨论,便成此文。

自己做轮子,还是搭便车?

    在一些性能要求较高的场合,是否用STL在国外论坛似乎一直有争论。(参见 STL for game engine) . 反对STL的一方认为,STL由于其通用性的考虑,效率始终不太高。支持方认为STL都是高手写成且充分受业界评价,已经足够优化,自己实现的数据结构不 见得比他好,只需要在少部分性能关键的代码段做优化即可。
    很多开发团队认为,借助外部库需要非常谨慎,因为代码不掌握在自己手中,对调试和排错有时候会惹麻烦。基于这个理由,很多有实力的公司会开发自己的库。比如百度,EA有自己的STL实现,QQ客户端则用自己写的一套框架。
    还有不少中小型开源项目,干脆用到什么就写什么样的数据结构和算法。一个团队做的东西一般都有个大体方向,形成自己风格的算法库不是难事。个人觉得,每种数据结构都有各自适合的算法,泛型虽然从概念上是个优雅的好主意,但是为了实现泛型,一堆iterator转来转去,未必就够针对性的实现来得直观(毕竟一种软件所用的算法是有限的,而且有时需要特定的优化)。
    anyway, 掌握数据结构的实现方法和STL的使用都应该是一个程序员的基本功。下面分别讨论。

使用并扩展STL

    选择实现版本。STL只是一个规范,他的实现版本对性能也有很大影响。一般用SGI的STL实现,比起VC下的PJ版实现要高效,在VC++下编程,可以用STLPort替换掉VC下的版本。
    明白原理。抱怨STL慢在很多情况下是因为使用不当,用一个库之前最好能明白他的实现原理。侯捷翻译的<STL源码剖析>以SGI版本深入浅出讲述了container, iterator, algorithm的原理。比如,如果知道vector的自动增长原理,使用的时候就会用reserve先分配好预计的内存,减少重新分配,拷贝数据的开销, 这样就已经很接近原生数组了。
    扩展STL。如果对STL实现很了解,还可以自己扩展他,比如写自己的allocator, 或者在他之上添加新的container,并适应泛型算法的调用要求。有本数<designing components with the C++ STL>有相关的例子。

自己做轮子

    如果项目中大量类型使用相同的数据结构,在C++中用模板来实现就最自然不过,在此就不讨论了。
    在C下写的数据结构怎么适应不同类型呢?支撑整个互联网的关键软件都是用纯C来写(linux/unix, mysql, 各种web server, memcached),他们有些规模也不小,如何做到一份算法代码给不同类型使用呢?这就需要一些很tricky的宏技巧。
    方法一:算法函数的参数的值是void指针,指定结构体长度。比如C标准库中的qsort. 在livemedia开源项目中,hashtable通过类型信息来把void指针转换成相应类型。
    方法二:利用偏移量取回结构体数据。
        最经典的是linux内核的链表实现(参见深入分析linux内核链表) . list_entry宏从链表结点中还原出结构体类型。
#define list_entry(ptr, type, member) container_of(ptr, type, member)

#define container_of(ptr, type, member) ({ \
        
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
        (type 
*)( (char *)__mptr - offsetof(type,member) );})

//offsetof宏定义在[include/linux/stddef.h]中:
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

       这可以说是类型无关的链表实现范例。这个container_of宏技巧还用于linux内核中red black tree的实现。

     方法三:用宏代替模板。有些很雷人的实现,比如freeBSD有个左倾红黑树的实现,全是宏替换.(LLRBT宏实现)

posted on 2009-11-15 13:40 Daly 阅读(1706) 评论(0)  编辑 收藏 引用 所属分类: C/C++数据结构与算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理