云风的 BLOG: 用 C 实现一个变长数组

我想用 C++ 的人都用过 std::vector 。它是一个可变长的数组，在很多时候都比 C 固有的定长数组要灵活。

C 里没有这样的标准化设施，但是写软件的人通常都会实现一个。正所谓，不厌其烦的重造轮子 :D 。这里我们不讨论造轮子的好坏问题，直接讨论下实现这么个东西的一点小技巧吧。总是固执于用谁做的轮子的问题，眼光就太短浅了。

一般的 vector 的实现，需要记录三个数据：数据空间的地址，空间大小，数组里已存在的元素个数。也可能是这三个元素的变体。比如在 msvc 的 stl 实现中，vector 保存的是三个 iterator：数组头指针、最后一个元素的指针、分配出来的全部空间的末尾指针。

msvc 的 vector 的分配策略是这样的。一开始不于分配空间，当第一个元素被 push back 后，空间扩展。通常，扩展的请求至少要满足请求扩展的尺寸，或者是讲已有的空间容量翻倍。比如，当你已经有 16 个单元的数组空间时，如果再申请 3 个，vector 会自己扩展到 32 个单元；若你一次要求从 16 个单元扩展到 40 个单元（超过 16*2），那么就直接扩展到 40 。

记得 stlport 也是类似的策略吧，实现的可能稍有不同。

正是如此，我们在用 vector 的时候要比较小心。如有可能，最好先 reserve 出需要的空间，而不是一个个的 push back 。否则，如果你从 0 个元素，push back 100 次，其空间会重新分配 8 次（1、2、4、8、16、32、64、128）。btw, 如果你经常这样做，最好实现一个优秀的 allocator 。IMHO ，msvc 的 stl 实现并不比 stlport 差，大多数性能差别都是因为 msvc 的 stl 实现未能给出一个通用的，优化过的分配器而已。（实现一个好的内存分配器，对于大的 C++ 软件项目，都值得去做）

今天想说的并不是怎么优化这个策略。是我这几天在写代码时发现，如果你遵照空间加倍这个策略来运作，其实并不需要三个变量来维持 vector 结构，两个就够了。那个表识容量大小的变量是多余的。:D

下面是段示范代码：

struct vector { int *data; int size; }; void vector_expand(struct vector *v, int s) { int new_size=v->size + s; if ((new_size ^ v->size) > v->size) { v->data=(int *)realloc(v->data,sizeof(int)*new_size * 2); } }

利用二进制逻辑运算的性质，我们只需要把新的尺寸和老的尺寸异或，再和老的尺寸比较，就可以知道，新的尺寸的二进制最高是 1 的那一位的位置是否大于老的尺寸。然后分配新尺寸的两倍，空间是绰绰有余的。

当然，如果你希望空间分配的恰到好处（2^n -1 ），可以稍微写的繁琐一点，以下代码在 32bit 机器上，可以把一个数字从它的二进制为 1 的最高位到最低位都填成 1 。

unsigned foo(unsigned a) { a|=a>>1; a|=a>>2; a|=a>>4; a|=a>>8; a|=a>>16; return a; }

今天把前两天写的 gc 模块开源了，本来想放到 sourceforge 上，但是我懒的注册帐号。google code 看起来更方便，选了个 bsd 的许可。然后把代码上传了。

project 在这里 http://code.google.com/p/manualgc/ 暂无下载，请直接用 svn check out 。

开源要有勇气，尤其是这么 dirty 的代码。不过话说回来，程序写了这么多年，写代码早就不拘小节了。我感觉这个东西设计上有点意思，现在也没看到有人做类似的玩意，具体实现则是次要的东西。应该还是会对某些同学有点意义的。

暂时还没完整测试过，姑且用之，不喜欢的人请直接无视。

Comments

那个不要表示容量大小的变量的技巧，不能处理数组长度减小的情况吧，不过也许这种情况会比较少？另，这个 blog 的验证问题永远都是六加一么？

Posted by: GlacJAY | (14) June 29, 2009 02:18 PM

云风的书>打着游戏的幌子却写着写编程的小伎俩,以此来吸引读者,不过没有太过分,因为至少对得起书名,不写编程写啥?对于想进入游戏领域,却有一定编程基础的人,毫不保留的说一点帮助都没有.工作一两年,如果你是一个有心的人，这些小伎俩你是可以很快从实践中习得的. 但是可以看出云风同学是一个很砖研的人,一点点启发是: 注意细节对于一个搞技术的人是很重要,往往一个伟大的设计就是砖研于某个细节的成就,我看了>后很有体会. 另外我要说的是,云风同学不可能写出和游戏相关一些的东西,因为工作不允许,因为存在商业竞争,保密什么的. 从技术角度来讲,游戏编程和其它的软件编程到最终分解为一个个小的问题后并没有本质的区别. 本人虽然踏入游戏编程才半年,在理解游戏框架的情况后开发新的功能,但没有感觉和以前的编程有太大的区别.不过马上要转入做服务器端了,不知道有没有大的感觉?所以,云风同学最后写出来的书让人觉得和游戏一点都不沾边是可以理解的（你要一个写搜索的人避开搜索问题来写编程，估计和云风同学写的一样了）.因为最终就是用计算机来解决问题,只是面对的问题不同而已,游戏面对的就是"游戏这个问题". 很多公司为什么要发重金买国外的游戏代码呢?(从云风的书中可以看出网蚁买过韩国人的代码)因为＂游戏这个问题＂并不是你精通编程就能做出来的，就像很多人做数学卷子很会，但是让它对一个搜索质量问题进行建模他就傻眼了（看了google吴军的数学之美有些启发），必须经过实践和经验的积累．看书的人是想尽快能被游戏公司看中，想获得实践的机会，所以期待和游戏直接相关的东西．所以真要写得和游戏沾边，还不得不直接列出游戏中的"这个问题"来，讲解如何解决和实现．比如人物在场景中如何移动，场景编辑器的实现（N多种，一个公司基本一个），如何保证游戏场景显示不卡（异步机制），游戏界面是如何做的？.....

Posted by: highshow | (13) January 10, 2009 01:50 AM

个人感觉, vector 这样的东西,还是一种抽象数据类型(ADT). 用模板的语法表现起来比较自然. 对vector,能否在C中设计出类似模板的表现方式呢?

Posted by: mike | (12) July 3, 2008 08:29 AM

做底层 C 足够了。C++ 比较多余。用 C++ 编写代码的时间，不如好好的考虑怎样把问题划简，用跟个简洁的方式表达。太多的可能性会影响思考。

Posted by: Cloud | (11) June 12, 2008 10:41 PM

呵呵

Posted by: ajivact | (10) June 12, 2008 04:41 PM

hello 朋友，我读过你的书,现在我也在做游戏这一块了，比你小很多，不过有些回忆还是相似的，嘿嘿

Posted by: ajivact | (9) June 12, 2008 04:39 PM

最近看云风的书，里面写的你比较倾向用C++做游戏项目的，什么时候又转C了呢？什么原因？

Posted by: 天黑请闭眼 | (8) June 12, 2008 02:25 PM

@Zwinger 啥隐患？没啥问题啊？你是说分配失败？分配失败后，系统就该跑不下去了。直接退出好了，不用管内存泄露。 FreeBSD 下有一个 reallocf ，不过我觉得绝大多数情况没什么用。

Posted by: Cloud | (7) June 11, 2008 09:47 PM

vector_expand()里面realloc()的使用有个内存泄露的隐患。

Posted by: Zwinger | (6) June 11, 2008 08:17 PM

云风，怎么才能联系到你，有些问题想请交你

Posted by: 白鸟 | (5) June 11, 2008 01:15 PM

自我感觉google code比sourceforge容易上手。可能我当时比较笨的原因，sourceforge研究了一会，还不知道具体如何弄，而对于google code,当时翻看了许式伟的google code的介绍文章，一会儿就架好了一个项目。开源是好事，自己现在水平还不行，但对gc这个话题也很感兴趣，也想写个虚拟机，慢慢消化云风的code :).

Posted by: dikatour | (4) June 11, 2008 01:07 PM

GLib上有很多类似的库，只是Windows下编译很麻烦

Posted by: Anonymous | (3) June 11, 2008 10:22 AM

我也实现了一个lzw的解/压缩算法，开源在sourceforge上，发布那晚比较兴奋。你呢？呵呵。

Posted by: DD | (2) June 11, 2008 12:00 AM

恩，一起加班中。。。沙发：）

Posted by: 我大心 | (1) June 10, 2008 10:38 PM

云风的 BLOG

思绪来得快去得也快，偶尔会在这里停留

用 C 实现一个变长数组

Comments

Post a comment