cstl -- c语言编写通用数据结构和常用算法库（模仿SGI STL)

vbs100

震撼啊 太强大的

vbs100

我没学过c++ 我理解的泛型就是一种通用的数据结构 我在一本书(Mastering Algorithms with C)上看到一种实现方法
typedef struct ListElmt_ {
    void               *data;
    struct ListElmt_   *next;
} ListElmt;
typedef struct List_ {
    int                size;
    int                (*match)(const void *key1, const void *key2);
    void               (*destroy)(void *data);
    ListElmt           *head;
    ListElmt           *tail;
} List;
这种方法的关键是保存数据的内存是由用户来管理的 而数据结构本身管理的内存是只用要维持这个数据结构 当然这种方法和楼主浩瀚的stl相比不值一提 (lighttpd 的 splay tree 好像就是这样的)

现在有几个很菜的问题想请教下
楼主这种我没具体用过 我不知道应该用这个stl保存值还是保存指针
如果是保存值 那一个大型的结构体传进去就难免有一次内存copy 这个从性能上看有点划不来
如果是保存指针 那删除的时候应该怎么处理 ？  这时好像很容易内存泄漏

还有数据结构里面的元素是怎么比较大小关系的呢？

接下来我会好好研究楼主的stl 免得以后老是离不开造轮子

vbs100

所以要提供一个通用数据释放函数 由用户自己来定义 就像我前面例子里的destroy
全部是本地变量可以直接赋成 free 有指针的就要自己释放了 不然直接扔掉就内存泄漏了

vbs100

想到一种方法解决  比如
list_t t_l = create_list(abc_t *);

直接把指针放到你的 cstl 里 这样不就解决了 ？删除的时候你再返回这个指针
这样用户数据的内存管理由用户负责 数据结构的内存管理由你来负责 不知道这样行不？？

vbs100

原帖由 tm_wb 于 2009-4-11 22:38 发表

现在cstl也可以保存指针，但是需要这样需要用户做很多额外的工作，还有就是复制数据的时候很麻烦。

传(空)指针，可以减少数据复制 用户额外做的事情也不多  我来班门弄斧一下，说说传值和传指针用户使用上的区别
我这里说的数据结构不特指 cstl 中的

首先用户定义了一个结构
typedef sturct {
int a;
void *b;
...
} abc_t;
如果用户自定义结构内有指针变量，那这个指针应该是指向heap上数据的指针，至少也应该是指向全局变量的(不建议用啊)

定义一个类型为 abc_t 的变量
传值：
abc_t abc; // abc是一个stack上的变量
传指针：
abc_t *abc = malloc(*abc); // abc是一个heap上的变量

修改这个 abc
传值：
abc.a = 10;
...
传指针：
abc->a = 10;
...

插入到一个 cstl 的数据结构里面
传值：插入函数会有一个malloc(sizeof(abc_t)在heap上申请内在用于保存用户数据 一个memcpy(,,sizeof(abc_t)  把stack上的数据复制到heap上
传指针：指针赋值

从cstl 的数据结构里面取出一个数据
传值：取出函数会有一个memcpy(,,sizeof(abc_t)  把heap上的数据复制到stack上(也可能传指针，对不起没来得及看代码)
传指针：指针赋值

修改一个 cstl 的数据结构里
传值：修改函数会有一个memcpy(,,sizeof(abc_t)  把stack上的数据复制到heap上(如果取出操作返回的是指针，这步也没有)
传指针：无(因为通过指针修改heap上的数据会立即生效)

从cstl 的数据结构里面删除一个数据
传值：这里有点麻烦，要调用用户的释放函数，不能简单的free，所以不符合内存谁申请释放的原则
传指针：把这个地址返回给用户，让用户自己释放

以上我是所能想到的传值和传指针的区别，其实也是用宏和用空指针来实现通用数据结构的区别。 所以传指针可以减少内存copy，而用户所以 做事情并没有增加，只是用户上的方法不同。

vbs100

我明白你说的传值的好处了。连续插入数据的时候这点对用户来说确实方便，用户只用一个数据拷贝，不用重新申请
但是数据结构底层却隐藏了一个malloc内存，和一个内存copy
传指针的时候正如你所说的那样，连续插入数据的时候是要连续的分配内存 比如
abc_t *a;
a = malloc(sizeof(*a));
a->n_value = 1;
a->d_value = 1.0;
insert (a)

a = malloc(sizeof(*a));
a->n_value = 2;
a->d_value = 2.0;
insert (a)

这样做的好处就是少了一次内存copy,当然这样看起来很奇怪，也很麻烦

此为还有当复制容器时
保存值的容器可以很容易就复制了，
但是保存指针的容器复制后两个容器中的指针都是指向一块内存了，当销毁一个容器后另一个容器就无效了。

这个我还没写过这么复杂的数据结构。我是这样想的，复制就涉及了两个用户数据的关系，就像最重要的比较两个用户数据的前后关系，应当由用户提供函数，复制容器时调用
而且在传值的的情况下，用户定义的结构里有指针，直接复制还是会出现一个容器销毁后另一个容器就无效

[ 本帖最后由 vbs100 于 2009-4-13 14:53 编辑 ]

vbs100

刚才又看细看了前面的贴子，原来和lz一直纠缠的问题前面lz早就说过了  不再水了
这个库很通用，保存数据时传值传指针都可以，只凭用户的爱好
非常敬佩lz的专业精神，文档代码风格，工程组织都是我们学习的典范 期待更完美的cstl