« 给 C 实现一个垃圾收集器 | 返回首页 | 引用计数与垃圾收集之比较 »

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

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

云风 提交于 June 10, 2008 09:49 PM |

TrackBack

如果你想引用这篇文章，请复制下面的链接发送引用通告（GBK）
http://blog.codingnow.com/mt/mt-tb.cgi/388

Comments

个人感觉, vector 这样的东西,还是一种抽象数据类型(ADT).

用模板的语法表现起来比较自然.

对vector,能否在C中设计出类似模板的表现方式呢?

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

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

太多的可能性会影响思考。

Posted by: Cloud [TypeKey Profile Page] | (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 [TypeKey Profile Page] | (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

Post a comment

非这个主题相关的留言请到：留言本