Chinaunix

标题: cstl -- c语言编写通用数据结构和常用算法库（模仿SGI STL) [打印本页]
作者: tm_wb    时间: 2009-04-09 21:25
标题: cstl -- c语言编写通用数据结构和常用算法库（模仿SGI STL)
cstl是使用C语言编写的一个通用的数据结构和常用的算法库，它模忙SGI STL的接口和实现，支持vector,list,deque等等常用的数据结构，同时还支持排序，查找，划分等常用的算法，此外cstl也包含迭代器的类型，它作为容器和算法之间的桥梁。cstl为C语言编程中的数据管理提供了便利。

    在使用C语言编程的过程中，很多工作都是在管理数据，很多时候我都是在一遍又一遍的开发通用的数据结构如list，我想C语言中如果有一个像的STL那样的库那就节省了很多的时间和精力，但是在网上没有找到，所以决定自己写一个类似的库。

    库的特点就是要通用，如果一个list只能保存int类型或者是针对每一种类型都要有一个相应的list来保存如保存int类型的list_int保存 double类型的叫list_double,那就很麻烦并且也不够通用，但是cstl做到了数据结构的通用型cstl中的容器可以保存任何类型，不管是 int还是double或者是用户自定义的类型abc_t同一个容器都可以保存，例如cstl中双向链表容器list_t既可以保存int又可以保存 double，连用户自定义的类型abc_t都可以保存，只要通过一步创建就可以：
创建一个保存int类型的list_t：
list_t t_l = create_list(int);
这样这个t_l中保存的数据就是int类型的数据了。
又如：
typedef struct _tagabc
{
...
}abc_t;
list_t t_l2 = create_list(abc_t);
这样t_l2中保存的就是abc_t类型的数据了。

    cstl还提供了很多特性，想了解请参考cstl-1.0.0.tar.gz包中的cstl使用手册(cstl.pdf)和cstl参考手册(cstl_reference.pdf)。我已经贴到我的blog里了:activesys.cublog.cn
请将下载的包重命名为cstl-1.0.0.tar.gz

cstl-1.0.0.tar.gz

1.33 MB, 下载次数: 3262
作者: cugb_cat    时间: 2009-04-09 21:32
大概看了下test目录下的代码，貌似楼主没能实现泛型？针对list和针对vector的sort，是用的不同的宏或函数吧？
作者: gawk    时间: 2009-04-09 22:53
牛，支持原创
作者: vbs100    时间: 2009-04-10 01:14
震撼啊 太强大的
作者: 太平绅士    时间: 2009-04-10 01:43
看了一下，LZ写的太厉害了！赞一个。

另外这里好像有类似的实现
http://bbs.chinaunix.net/viewthread.php?tid=848385
作者: mjus    时间: 2009-04-10 05:20
Quite good ! But not a generic one ! what a pity !!!
作者: converse    时间: 2009-04-10 09:03
问个问题:
代码test_algo.c中

  2. vector_t t_v = create_vector(int);
  3.         iterator_t t_i;

  5.         vector_init(&t_v);
  6.         vector_push_back(&t_v, 2);
  7.         vector_push_back(&t_v, 5);
  8.         vector_push_back(&t_v, 4);
  9.         vector_push_back(&t_v, 1);
  10.         vector_push_back(&t_v, 6);
  11.         vector_push_back(&t_v, 3);
  12. t_i = algo_find(vector_begin(&t_v), vector_end(&t_v), 3);
复制代码


如果这里我的数据类型是自定义的话,我看到algo_find里面最后得到的函数指针是fun_default_binary,这个好像就没有办法对自定义类型进行数据比较了吧?
作者: cugb_cat    时间: 2009-04-10 09:27
原帖由 converse 于 2009-4-10 09:03 发表
问个问题:
代码test_algo.c中

vector_t t_v = create_vector(int);
        iterator_t t_i;

        vector_init(&t_v);
        vector_push_back(&t_v, 2);
        vector_push_back(&t_v, 5);
...

恩，我也觉得他这个对泛型没支持的不是很好

[ 本帖最后由 cugb_cat 于 2009-4-10 13:41 编辑 ]
作者: converse    时间: 2009-04-10 09:29
标题: 回复 #8 cugb_cat 的帖子
不是支持的不好,是C语言本身的特点做不到真正的"范型",所以,任何人想用C去做"范型"几乎都是impossiable mission
作者: 到处流浪的猫    时间: 2009-04-10 09:42
注册：2007-8-7
最后登录： 2009-04-09
帖子：1
精华：1
两年发一帖就精了，强！
作者: vbs100    时间: 2009-04-10 10:43
我没学过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 免得以后老是离不开造轮子
作者: tm_wb    时间: 2009-04-10 12:33
标题: 回复 #2 cugb_cat 的帖子
algo_sort()这样的算法都是通过迭代器iterator_t来实现对具体数据的操作，不是通过不同的宏或函数单独处理各个容器类型，你可以看一看algo_sort()的代码。
作者: tm_wb    时间: 2009-04-10 12:41
标题: 回复 #7 converse 的帖子
谢谢回复，
你自己定义针对自定义类型的比较函数举一个test/test_algo.c中的例子
struct abc_t
{
    int n_value;
    long l_value;
    double d_key;
};

static void _abcgreat(const void* cpv_first, const void* cpv_second, void* pv_output);

/* test function body */
{
        deque_t t_q = create_deque(struct abc_t);
        struct abc_t t_abc;

        deque_init(&t_q);
        t_abc.n_value = 70;
        t_abc.l_value = 934000;
        t_abc.d_key = 0.24;
        deque_push_back(&t_q, t_abc);
        t_abc.n_value = 100;
        t_abc.l_value = 3000;
        t_abc.d_key = 2.09;
        deque_push_back(&t_q, t_abc);
        t_abc.n_value = 2;
        t_abc.l_value = -18;
        t_abc.d_key = 110.00;
        deque_push_back(&t_q, t_abc);
        t_abc.n_value = -902;
        t_abc.l_value = 88000;
        t_abc.d_key = -10.007;
        deque_push_back(&t_q, t_abc);

        algo_for_each(deque_begin(&t_q), deque_end(&t_q), _print_abc);
        algo_sort_if(deque_begin(&t_q), deque_end(&t_q), _abcgreat);
        printf("\n");
        algo_for_each(deque_begin(&t_q), deque_end(&t_q), _print_abc);

        deque_destroy(&t_q);
}

static void _abcgreat(const void* cpv_first, const void* cpv_second, void* pv_output)
{
    if(((struct abc_t*)cpv_first)->d_key > ((struct abc_t*)cpv_second)->d_key)
    {
        *(bool_t*)pv_output = true;
    }
    else
    {
        *(bool_t*)pv_output = false;
    }
}
作者: tm_wb    时间: 2009-04-10 12:42
标题: 回复 #8 cugb_cat 的帖子
我已经做了最大的努力了
学识不够才疏学浅
作者: tm_wb    时间: 2009-04-10 12:44
标题: 回复 #10 到处流浪的猫 的帖子
我以前都在csdn上（虽然也没发过多少帖子和文章），由于csdn的blog不能上传非图片类型的文件
并且csdn的blog服务也不太好。
作者: tm_wb    时间: 2009-04-10 12:48
标题: 回复 #11 vbs100 的帖子
CSTL是保存数据的拷贝，STL也是保存数据的拷贝。

“还有数据结构里面的元素是怎么比较大小关系的呢？”
你可以通过自定义比较函数的方法在使用算法的时候调用自己定义的比较函数，
具体的请参看用户手册cstl.pdf和cstl_reference.pdf
谢谢，我会在cstl-1.1中加入更好的对自定义类型的支持。
作者: tm_wb    时间: 2009-04-10 12:50
标题: 感谢大家回帖
rt
感谢大家回帖，我把这个项目贴到我的blog中了activesys.cublog.cn
作者: 太平绅士    时间: 2009-04-10 13:10
昨天粗粗看了一下，比以前任何一个看到的类似stl的C版本都好，
看得出楼主也花了很多的功夫。
个人非常喜欢！
cstl的lincense怎么定的啊？
作者: windyrobin    时间: 2009-04-10 13:42
简单看料下，功能很强大呵！
弱问一句 ，楼主共花了多长时间搞这么个大东东，
有什么体会和感慨没，
和c++ stl相比 ，它的 “不足” 在哪呢？
作者: cugb_cat    时间: 2009-04-10 13:42
原帖由 tm_wb 于 2009-4-10 12:42 发表
我已经做了最大的努力了
学识不够才疏学浅

已经做的很好了，呵呵。
互相学习吧。
作者: pandaisme    时间: 2009-04-10 17:25
标题: 相当的好, 高度赞扬
cstl实现得相当的好, 支持楼主继续开发, 继续扩展和浓缩, 说不定以后可以做成标准呢
作者: tm_wb    时间: 2009-04-10 18:29
标题: 回复 #19 windyrobin 的帖子
从去年11月开始开发的。
和sgi stl比当然还是有很大的差距的，cstl对于自定义类型支持的还有些欠缺，尤其是自定义类型内部带有指针类型的，
我会在1.1版本中加强的。
作者: vbs100    时间: 2009-04-10 20:22
标题: 回复 #22 tm_wb 的帖子
所以要提供一个通用数据释放函数 由用户自己来定义 就像我前面例子里的destroy
全部是本地变量可以直接赋成 free 有指针的就要自己释放了 不然直接扔掉就内存泄漏了
作者: vbs100    时间: 2009-04-10 20:34
标题: 回复 #22 tm_wb 的帖子
想到一种方法解决  比如
list_t t_l = create_list(abc_t *);

直接把指针放到你的 cstl 里 这样不就解决了 ？删除的时候你再返回这个指针
这样用户数据的内存管理由用户负责 数据结构的内存管理由你来负责 不知道这样行不？？
作者: zhaoxix9527    时间: 2009-04-10 21:33
高手啊。。。。。
作者: Knort    时间: 2009-04-11 22:10
glib不好吗？
作者: tm_wb    时间: 2009-04-11 22:38
原帖由 vbs100 于 2009-4-10 20:34 发表
想到一种方法解决  比如
list_t t_l = create_list(abc_t *);

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

现在cstl也可以保存指针，但是需要这样需要用户做很多额外的工作，还有就是复制数据的时候很麻烦。
作者: tm_wb    时间: 2009-04-11 22:40
原帖由 Knort 于 2009-4-11 22:10 发表
glib不好吗？

最开始开发的时候只是为了学习和巩固数据结构和算法。
慢慢的写的多了就干脆做了一个库。
作者: Knort    时间: 2009-04-12 12:05
原帖由 tm_wb 于 2009-4-11 22:40 发表

最开始开发的时候只是为了学习和巩固数据结构和算法。
慢慢的写的多了就干脆做了一个库。


在glib的基础上做扩展不是更好？不用重复造轮子，而且也更贴近实际。
作者: vbs100    时间: 2009-04-13 00:19
原帖由 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，而用户所以 做事情并没有增加，只是用户上的方法不同。
作者: hantor    时间: 2009-04-13 11:01
学习！！
作者: cookis    时间: 2009-04-13 11:28
牛B， 这么短时间，还能将DOC搞得这么细，支持
作者: cookis    时间: 2009-04-13 11:30
赶紧创建一个project ，招募更多的高手，把它搞得更完善，走出国门，销往印度
作者: sorrento    时间: 2009-04-13 11:45
原帖由 cookis 于 2009-4-13 11:30 发表
赶紧创建一个project ，招募更多的高手，把它搞得更完善，走出国门，销往印度


哥们真幽默
作者: sharpshootor    时间: 2009-04-13 11:54
真是强人
作者: hjk857    时间: 2009-04-13 12:08
年起来不错。。。
作者: tm_wb    时间: 2009-04-13 13:01
标题: 回复 #30 vbs100 的帖子
谢谢你的建议
我说明一下使用传值意图
首先你上面用的例子比较特殊，不便于说明问题，我在举一个例子
typedef struct _tagabc
{
    int n_value;
    double d_value;
}abc_t;
这个结构体中不包含指向堆的指针。
插入数据时：
使用传值：
abc_t t_abc = {10, 10.0};
/* 执行插入操作，将t_abc复制 */
/* 第二次插入是可以使用同样一个值 */
t_abc.n_value = 20;
t_abc.d_value = 20.0;
/* 执行插入操作，将t_abc复制 */
使用传地址：
abc_t* pt_abc = (abc_t*)malloc(sizeof(abc_t));
pt_abc->n_value = 10;
pt_abc->d_value = 10.0;
/* 执行插入操作，将pt_abc复制 */
/* 第二次在插入的时候就必须在为这个指针分配内存，因为容器中只是保存了指向内存的指针，并没有复制内存，如果没有为pt_abc分配新的内存就直接修改其值，这样容器中的值也跟着改变了，这对于set_t类的容器来说是致命的错误 */
pt_abc = (abc_t*)malloc(sizeof(abc_t));
pt_abc->n_value = 20;
pt_abc->d_value = 20.0;
/* 执行插入操作，将pt_abc复制 */
这是使用自定义类型的数据，但是要是使用C内部类型那么传地址就更麻烦了。
例如使用int类型
我可以使用4, 8, 298这样的数字文字量来当作参数，传地址就必须如下操作：
int* pn_value = (int*)malloc(sizeof(int));
*pn_value = 4;
/* 执行插入操作，将pn_value复制 */
pn_value = (int*)malloc(sizeof(int));
*pn_value = 8;
/* 执行插入操作，将pn_value复制 */
-----------------------------------------------------------------------------------
取出数据我现在采用的是直接返回指定数据的指针。
-----------------------------------------------------------------------------------
删除数据正像你上面说的一样。
-----------------------------------------------------------------------------------
此为还有当复制容器时
保存值的容器可以很容易就复制了，
但是保存指针的容器复制后两个容器中的指针都是指向一块内存了，当销毁一个容器后另一个容器就无效了。
-----------------------------------------------------------------------------------
现在有事不能继续回复了
晚上再回复，抱歉。
作者: vbs100    时间: 2009-04-13 14:11
标题: 回复 #37 tm_wb 的帖子
我明白你说的传值的好处了。连续插入数据的时候这点对用户来说确实方便，用户只用一个数据拷贝，不用重新申请
但是数据结构底层却隐藏了一个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 编辑 ]
作者: Sorehead    时间: 2009-04-13 16:01
对楼主的行为，不得不佩服。
下载后粗略看了看，各方面都挺规范的，文档也写得很不错，有时间再好好看看。看得出楼主真是下了一番苦功，是个难得做实事的人。
希望楼主再接再厉，向楼主致敬。
作者: tm_wb    时间: 2009-04-13 18:39
标题: 回复 #38 vbs100 的帖子
继续中午的回复
还有另一种数据类型，
typedef struct _tagabc
{
    int* pn_value;
}abc_t;
这样的结构在cstl中支持不够好，因为pn_value指向的是堆上的内存，容器内部结构并不知道
数据具体的情况所以无法对堆上的数据进行复制，这就造成了当数据容器中的数据拷贝或删除时
内存丢失。
简单的说就是cstl没有类似于c++的深拷贝那样的功能。
这个问题我要在cstl 1.1中解决。
谢谢你的建议，我回考虑以后改版时候使用你的方法。

[ 本帖最后由 tm_wb 于 2009-4-13 18:45 编辑 ]
作者: tm_wb    时间: 2009-04-13 19:22
标题: cstl的不足
谢谢大家关注CSTL 1.0.0
CSTL还有很多不足：
1.不能使用数组初始化容器。
2.不能使用任意数据区间初始化容器。
3.对内部含有指针的类型支持的不好。
4.使用自定义类型时要求用户编写额外的二元函数来支持自定义类型的操作。

我会在1.1版中支持这些特性。

如果有什么建议或者发现bug请给我留言或发邮件。
谢谢大家支持。
作者: vbs100    时间: 2009-04-14 01:50
标题: 回复 #40 tm_wb 的帖子
刚才又看细看了前面的贴子，原来和lz一直纠缠的问题前面lz早就说过了  不再水了
这个库很通用，保存数据时传值传指针都可以，只凭用户的爱好
非常敬佩lz的专业精神，文档代码风格，工程组织都是我们学习的典范 期待更完美的cstl
作者: 太平绅士    时间: 2009-04-14 02:26
原帖由 tm_wb 于 2009-4-13 19:22 发表
谢谢大家关注CSTL 1.0.0
CSTL还有很多不足：
1.不能使用数组初始化容器。
2.不能使用任意数据区间初始化容器。
3.对内部含有指针的类型支持的不好。
4.使用自定义类型时要求用户编写额外的二元函数来支持自 ...


说到深拷贝，1.1千万要控制好接口的规模 ---- 这是光说话不做事的人的一点期望
作者: cnhbdu    时间: 2009-04-14 09:10
标题: 回复 #1 tm_wb 的帖子
强悍！拜！
请问楼主：用什么管理的工程？
作者: daxi1987    时间: 2009-04-15 21:31
标题: 回复 #1 tm_wb 的帖子
呃，这个工程有些大了吧
我还是不推荐花大量的时间写这种库
作者: redor    时间: 2009-04-16 11:29
原帖由 converse 于 2009-4-10 09:29 发表
不是支持的不好,是C语言本身的特点做不到真正的"范型",所以,任何人想用C去做"范型"几乎都是impossiable mission


宏可以做到一定程度的泛型.....
作者: xm1984    时间: 2009-04-16 11:29
只能敬佩了，
我也相当想知道楼主是如何管理工程和文档的。
作者: Strange    时间: 2009-04-16 18:07
写的真不错，特别是文档写的很好看
这个库准备用什么license？不登录sourceforge可惜了
正在学习中
作者: tm_wb    时间: 2009-04-16 19:05
标题: cstl的项目管理
惭愧，由于本人对开源项目管理的流程和细节还不太清除，所以cstl才有的是原始的纯手工管理，
不过我现在正在加紧了解开源项目管理的信息，学习怎样管理开源项目。将来我会建立一个个开源项目的。
作者: hitraistlin    时间: 2009-04-16 22:26
想问楼主一下，pdf你是用什么工具做的啊？挺精致的。

另外建议楼主下一版加上平台相关的封装；
比如：封装一个中小内存池管理，一个线程池管理，一个通用对象内存池管理。最好带debug内存泄漏检测。
还有就是宽字节的str处理函数(wcslen,wcscat...),好多平台都没有针对宽字节的。
1.1千万要控制好接口的规模 ---- 这是光说话不做事的人的一点期望
说到深拷贝，其实深拷贝还是浅拷贝，是由用户说的算的。深拷贝的话，用户就要提供深拷贝函数。
另，用宏实现泛型不建议使用，因为泛型和宏都容易代码膨胀。个人认为，宏只是用作函数内部代码段的复用好一些。
作者: angle4    时间: 2009-04-16 22:39
标题: 回复 #10 到处流浪的猫 的帖子
O(∩_∩)O哈哈~
作者: redor    时间: 2009-04-17 13:27
原帖由 tm_wb 于 2009-4-9 21:25 发表
cstl是使用C语言编写的一个通用的数据结构和常用的算法库，它模忙SGI STL的接口和实现，支持vector,list,deque等等常用的数据结构，同时还支持排序，查找，划分等常用的算法，此外cstl也包含迭代器的类型，它作 ...



跟人觉得你这个就是一个算法集合... 算不上STL, STL要使用类似宏的方式实现.
作者: newfido23    时间: 2009-04-17 13:41
这东西比较好，谢谢！
作者: finalfantasy000    时间: 2009-04-20 09:32
如果我叫楼主不要浪费时间在实现C上面的STL，那么就要有很多人要骂我了，但是我还是不得不说。。。。
不要发明重复的轮子了。。。。。
作者: paceboy    时间: 2009-04-20 16:23
下一个看看
作者: tm_wb    时间: 2009-04-23 20:02
标题: libcstl
我在googlecode上为cstl创建了一个开源项目，并改名为libcstl，地址：libcstl.googlecode.com欢迎大家访问！
作者: songbo_1220    时间: 2009-04-24 14:48
太好了，正想找个c的数据结构库，看看先，多谢！
作者: 群雄逐鹿    时间: 2009-04-24 15:19
原帖由 finalfantasy000 于 2009-4-20 09:32 发表
如果我叫楼主不要浪费时间在实现C上面的STL，那么就要有很多人要骂我了，但是我还是不得不说。。。。
不要发明重复的轮子了。。。。。


当然会骂你。除非你给一个更好的轮子
作者: songbo_1220    时间: 2009-04-24 17:49
原帖由 Knort 于 2009-4-12 12:05 发表


在glib的基础上做扩展不是更好？不用重复造轮子，而且也更贴近实际。


支持！虽然新手，但是感觉仁兄的见解是对的，除非glib有不足，否则没必要自己造轮子，扩展更好。
作者: heiyeluren    时间: 2009-04-26 00:26
楼主的这种精神值得敬佩，不管是否使用这个库，但是楼主的底层钻研精神都是值得学习的。
另外，这个库完全值得作为一个数据结构+算法学习的良好代码。

谢谢楼主，我一直支持你！
作者: songbo_1220    时间: 2009-04-27 14:44
google 上搜索 “C Data Structure Library” 了一下， c 的数据结构库有这么些个

#
GDSL - The Generic Data Structures Library, a free data structures ...
7 Jul 2006 ... A free data structures manipulation library under the GNU General ... for C programmers common data structures with powerful algorithms, ...
home.gna.org/gdsl/ - 7k - Cached - Similar pages
#
c-generic-library - Google Code
A generic data structure library modeled after C++ STL. ... The generic data structure library is a bunch of data structures that are designed and created ...
code.google.com/p/c-generic-library/ - 12k - Cached - Similar pages
#
Mathtools.net : C,C++/Algorithms and Data structures
This Library includes the most extensive data structures on the market, plus three options for fast, automatic persistence. Ideal for large, complex C++ ...
www.mathtools.net/C_C__/Algorithms_and_Data_structures/index.html - 37k - Cached - Similar pages
#
SourceForge.net: Kompimi C Data Structure Library
21 Nov 2008 ... A public domain C data structure library, with an emphasis on collections. Currently includes dynamic arrays and lists. ...
sourceforge.net/projects/kompimi-cdsl/ - Similar pages
#
Wayne's Little Data Structures and Algorithms Library
1 Jan 1997 ... Wayne's Little Data Structures and Algorithms Library ... textbooks on data structures and algorithms, and I simply translated them into C. ...
www.cs.toronto.edu/~wayne/libwayne/ - 13k - Cached - Similar pages
#
Part 1: An Introduction to Data Structures
An Extensive Examination of Data Structures Using C# 2.0 ... NET Framework adds new data structures to the Base Class Library, along with new features, ...
msdn.microsoft.com/en-us/library/ms379570.aspx - 46k - Cached - Similar pages
#
Erwin Data Structure Library v2.0.278
The Erwin library is a very efficient and robust data structure template library for C and C++. No templates are used; a Perl script generates C files.
www.programmersheaven.com/download/41177/download.aspx - 38k - Cached - Similar pages
作者: mhsy2003    时间: 2009-04-28 10:48
程序员都是喜欢重新发明轮子的。只是cstl的licence没说明？
作者: aajuu    时间: 2009-04-30 13:40
很尊敬有奉献精神的人～！
作者: Solidus    时间: 2009-05-01 09:31
支持楼主，我也写过一个期望泛用的C数据结构库，不过远远赶不上楼主这个好( http://code.google.com/p/ravenx/)，我在我的一个regex引擎和我的一个LR-PARSER的早期版本中用过
http://code.google.com/p/tokendie/
http://code.google.com/p/arsenalcomp/
到最后都不用了，因为感觉用C去做泛用的库（尤其是数据结构这类基础库）,如果这个库的接口没弄好的话，导致的问题比C++的模板设计错误还麻烦的多，侵入性太强了。而且很多时候在C这个层面需要面对的问题，是不是需要泛用的数据结构还很难说，对性能真正有要求的地方通常数据结构也同样有具体要求。反过来说，大部分没要求的地方，可能简简单单的一个数组，甚至就定义一个#define MAX_NUM ....  xxx zzz[MAX_NUM]就足够了（这类东西是我所见过的C工程里用的最多的），因为局部的简单问题在需求以及性能上是可以预先知道的，真正要改的话把子模块重写一遍就OK了，泛化反而会引来维护问题。

还有就是看见有人说楼主重复发明轮子什么的，其实以我不算丰富的编程经验来看，重复发明轮子通常有两个好处，最直接的是学习经验，第二个就是针对某个特定的问题，写一个不那么好但是够用的工具通常比直接引入一个优雅，高效但是庞大复杂的库进来在后期维护以及修改上要快的多得多，而且整体开发速度也要快很多。（当然我这里主要指的是核心功能），因为别人实现的工具针对你特定的问题永远有些不那么合适的地方，这时候修正起来要繁琐的多，而且过程通常很痛苦，程序这东西还远远没进化到只关注接口而完全忽略实现那个高度。

PS：这里仅仅是说点体会，俺也是个新手，虽然不喜欢泛化但还是相当支持并期待LZ让它更加泛用的！
作者: osmanthusgfy    时间: 2009-05-06 12:37
very good!

强烈建议楼主发布到souceforge或提交给GNU组织!!!!!!!!!!!!!!!!!!!!!!!
作者: lightgu    时间: 2009-05-11 19:04
标题: 回复 #1 tm_wb 的帖子
不能下了吗
作者: bittertea    时间: 2009-05-12 01:26
可否借鉴下bsd内的 sys/ queue.h,  tree.h ? 可以在很多开源代码里发现他的影子, 里面有多种链表/队列 /splay/rbtree结构及基本操作宏(函数)

[ 本帖最后由 bittertea 于 2009-5-12 01:33 编辑 ]
作者: worldthink    时间: 2009-09-21 11:50
谢谢了？这可是俺第一次回复哦
作者: ecjtubaowp    时间: 2009-11-05 13:27
之前不是有一个tstl2cl库吗？
作者: kingbigeast    时间: 2010-12-03 15:41
直接用C++STL不就行了吗？
“不要重复发明轮子”
作者: xianliang    时间: 2011-01-24 14:13
不造一下轮子，如何知道轮子为什么应该做成圆的，如何做成圆的？
作者: 一个人取暖    时间: 2011-06-23 12:12
支持lz继续开源,继续更新
作者: fallening_cu    时间: 2012-03-23 08:27
error:

  2. In file included from src/cstl_stack.c:22:
  3. include/cstl_stack_private.h:44: error: conflicting types for ‘stack_t’
  4. /usr/include/sys/_structs.h:218: error: previous declaration of ‘stack_t’ was here
复制代码
gcc info:

  2. Using built-in specs.
  3. Target: i686-apple-darwin11
  4. Configured with: /private/var/tmp/llvmgcc42/llvmgcc42-2336.1~22/src/configure --disable-checking --enable-werror --prefix=/Developer/usr/llvm-gcc-4.2 --mandir=/share/man --enable-languages=c,objc,c++,obj-c++ --program-prefix=llvm- --program-transform-name=/^[cg][^.-]*$/s/$/-4.2/ --with-slibdir=/usr/lib --build=i686-apple-darwin11 --enable-llvm=/private/var/tmp/llvmgcc42/llvmgcc42-2336.1~22/dst-llvmCore/Developer/usr/local --program-prefix=i686-apple-darwin11- --host=x86_64-apple-darwin11 --target=i686-apple-darwin11 --with-gxx-include-dir=/usr/include/c++/4.2.1
  5. Thread model: posix
  6. gcc version 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2336.1.00)
复制代码
作者: emwoody    时间: 2012-10-23 15:31
看贴不顶！那是不行的！
作者: ll1204    时间: 2013-12-18 12:45
回复 1# tm_wb


    参考一下，学习学习。
作者: yulihua49    时间: 2013-12-24 15:24
逆天啦，它敢返回局部变量：
  1. /* private vector function */
  2. vector_t _create_vector(size_t t_typesize, const char* s_typename)
  3. {
  4.     vector_t t_newvector;

  6.     assert(t_typesize > 0);
  7.     assert(s_typename != NULL);

  9.     t_newvector._t_typesize = t_typesize;
  10.     memset(t_newvector._sz_typename, '\0', _ELEM_TYPE_NAME_SIZE+1);
  11.     strncpy(t_newvector._sz_typename, s_typename, _ELEM_TYPE_NAME_SIZE);
  12.     _unify_types(t_newvector._t_typesize, t_newvector._sz_typename);
  13.     t_newvector._pc_start = NULL;
  14.     t_newvector._pc_finish = NULL;
  15.     t_newvector._pc_endofstorage = NULL;
  16.     t_newvector._pfun_cmp = NULL;

  18.     return t_newvector;
  19. }
复制代码
作者: yulihua49    时间: 2013-12-24 15:55
本帖最后由 yulihua49 于 2013-12-24 16:57 编辑
xianliang 发表于 2011-01-24 14:13
不造一下轮子，如何知道轮子为什么应该做成圆的，如何做成圆的？

这个轮子不得不造，没有类似的东西。

为了算法和容器独立，搞的好复杂。

为了在map中查找一个值：
t_i = algo_find_if(map_begin(&t_m), map_end(&t_m), _find_value);
有必要把头、尾都搅合进去吗？map是可以直接查找的啊，那么办，不就成了数组的顺序查找了吗？
map的迭代，比数组迭代，效率低得多。
作者: yulihua49    时间: 2013-12-25 10:02
本帖最后由 yulihua49 于 2013-12-25 10:08 编辑
yulihua49 发表于 2013-12-24 15:55
这个轮子不得不造，没有类似的东西。

为了算法和容器独立，搞的好复杂。


stl的map，采用K-V模型。
其功能、性能要比V(k)，V(k(Vx,Vy,...))模型要差好多。
就是V包含K，k又包含V的一个或多个成分。不需要单独的k
直接的树查找，要比通过迭代器查找，快N倍。O()虽然没变，但其前边的系数要差好几倍。
作者: d741963250    时间: 2013-12-25 13:58
回复 76# yulihua49


    我一来看到这也惊了一下，返回局部变量，貌似有点说不过去
作者: yulihua49    时间: 2013-12-25 16:17
本帖最后由 yulihua49 于 2013-12-25 16:18 编辑
d741963250 发表于 2013-12-25 13:58
回复 76# yulihua49

它这是可以的，就是别扭。
局部变量是可以返回的，不能返回的是局部变量的地址，地址里的内容会失效。
作者: d741963250    时间: 2013-12-25 16:19
回复 80# yulihua49


    只能说这种用法不多，在结构体的返回中基本没用到过
作者: yulihua49    时间: 2013-12-26 15:24
本帖最后由 yulihua49 于 2013-12-26 16:37 编辑
d741963250 发表于 2013-12-25 16:19
回复 80# yulihua49

map_iterator_t map_find(
const map_t* cpt_map, key_element);
返回值为key_element的数据的位置。

如果找不到，返回什么？
生产系统，要求查询不到返回NULL，不允许程序退出。

这个东西是不能在生产系统中用的，就是个学院派的产品。
-DNODEBUG 并不能完全消除assert。
任何异常都退出，没有给应用者处理错误的机会。
作者: yulihua49    时间: 2013-12-27 14:32
本帖最后由 yulihua49 于 2013-12-27 14:37 编辑
yulihua49 发表于 2013-12-26 15:24
map_iterator_t map_find(
const map_t* cpt_map, key_element);
返回值为key_element的数据的位置。

执行：
map_iterator_t temp;
temp=map_upper_bound(&sta_tree,key_v);
得到
getTrip:key=0218|1|00000000D312A8F8,pair->first=0103|1|00000000D3122622

应该

temp=map_upper_bound(&sta_tree,key_v);返回>key的啊？怎么是这个结果？我做错了什么吗？
里边是什么比较器？

还有：
iterator_prev(&temp);
                if(iterator_equal(&temp, map_end(&sta_tree))) {
ShowLog(5,"getTrip:key=%s,iterator_prev fault!",key_v);
                        return has_date(sch_date,diag);
                }

怎么总是失败？不支持iterator_prev吗？
作者: lattter    时间: 2014-01-28 22:59
bucuoo不错哦!:wink:



欢迎光临 Chinaunix (http://bbs.chinaunix.net/) Powered by Discuz! X3.2