GettingStartedGuide - activesys/libcstl GitHub Wiki

libcstl getting started guide.

libcstl是什么，为什么会有libcstl?

libcstl是一个应用于C语言编程的函数库，它将编程过程中经常使用的数据结构如向量、链表、集合、树等封装成相应的数据结构并提供一系列的操作函数来操作保存在这些数据结构中的数据，同时它还将常用的算法如排序、查找、划分等封装成相应的算法函数并提供迭代器来使两者之间建立联系方便使用。从libcstl的名字就可以看出它于STL有一定的关系，是的libcstl的接口和实现都是模仿了STL。 libcstl的产生主要是基于使用C语言编程过程中经常要使用向量、链表、集合等数据结构和排序、查找、划分等算法，但是对于这些数据结构和算法每次都要重复的实现，如果有一个通用的类似于STL的数据结构和算法的库就可以节约时间和成本，这样libcstl就诞生了。

编译和安装

在libcstl-2.0.2中使用configure选项来支持2.0.的编译配置。

关闭控制断言(--disable-assert)

定义这个选项可以去掉库中的断言.当库函数接受到非法参数时,断言就会报错,但是有断言的版本执行效率低 (非断言版本效率大约是有断言版本的 20~40 倍).
开启内存管理(--with-memory-management)

这个选项可以开启内存管理，默认情况下内存管理是关闭的。
配置 stack_t 适配器的底层实现(--enable-stack-implementation=ARGUMENT)

这个选项是配置 stack_t 适配器的底层实现的。ARGUMENT 作为 stack_t 的底层实现,ARGUMENT 可以是 vector(--enable-stack-implementation=vector)和 list(--enable-stack-implementation=list), 默认使用 deque_t 作为 stack_t的底层实现.
配置 set_t 的底层实现(--enable-set-implementation=ARGUMENT)
配置 multiset_t 的底层实现(--enable-multiset-implementation=ARGUMENT)
配置 map_t 的底层实现(--enable-map-implementation=ARGUMENT)
配置 multimap_t 的底层实现(--enable-multimap-implementation=ARGUMENT)

以上四个选项是配置关联容器的底层实现的,ARGUMENT 的可选参数是 avl-tree,关联容器默认使用红黑树作为底层实现(红黑树比 avl 树快 40%)。默认使用红黑树作为底层实现。

Windows上的编译可在解压后目录中的built-win目录下找到vc8和vc9两个目录，分别是VS2005和VS2008的工程文件目录。

libcstl基本概念

libcstl由多个分组成，容器，迭代器，算法和函数容器: 容器以某种结构形式管理数据的集合,每一种容器都有各自的特点. 迭代器: 迭代器与容器相关联,应用与容器或容器的子集,它的主要好处在于为容器提供了一个统一的接口.迭代器是容器和算法之间的桥梁,它使得算法独立于特定的容器. 算法: 算法是对数据集合进行某些操作,它可以排序,查找,修改或其他一些操作.算法使用迭代器作为输入,这样算法可以独立于容器,实现在任意容器上的操作.同时算法还使用特定的函数对容器中的数据进行特定的操作. 函数: 函数只是规定了算法中使用的函数形式,并且定义了一些算法中常用的函数，可以作为算法的自定义规则.

容器

容器可以用来排序数据,管理和存储数据,所以为了不同的目的libcstl提供了不同的容器.容器分为: 序列容器: 序列容器主要用来存储和管理数据,容器中的数据的顺序与数据插入到容器中的次序有关,而与数据本身的值无关. libcstl提供的序列容器有:vector_t, list_t, deque_t, slist_t. 关联容器: 关联容器更关系容器中数据的排列顺序,容器中数据的顺序是排序的与数据本身有关而与数据插入到容器中的次序无关.libcstl 提供的关联容器有:set_t, map_t, multiset_t, multimap_t, hash_set_t, hash_map_t, hash_multiset_t, hash_multimap_t. 容器适配器: 除了以上这些容器之外,libcstl为了特殊的目的还提供了容器适配器,它们都是基本的容器实现的. 容器适配器有:stack_t,queue_t,priority_queue_t. 字符串类型： string_t类型可以像c-str一样拷贝,赋值,比较而不必考虑是否有足够的内存来保存字符串,会不会越界等等. 因为string_t可以动态增长,并且易于使用,你可很方便的插入删除字符或子串,方便的替换等等.

如何使用容器

我们以vector_t为例来展示一下如何使用libcstl的容器类型，下面是一段使用vector_t的代码：

#include <stdio.h>
#include <cstl/cvector.h>

int main(int argc, char* argv[])
{
    vector_t* pt_vec = create_vector(int);
    size_t t_index = 0;
    if(pt_vec == NULL)
    {
        return -1;
    }

    vector_init(pt_vec);

    for(t_index = 0; t_index < 10; ++t_index)
    {
        vector_push_back(pt_vec, t_index * 100);
    }
    for(t_index = 0; t_index < vector_size(pt_vec); ++t_index)
    {
        printf("%d, ", *(int*)vector_at(pt_vec, t_index));
    }
    printf("\n");

    vector_destroy(pt_vec);

    return 0;
}

首先使用一个容器类型必须包含必要的头文件，例如vector_t要求包含头文件<cstl/cvector.h>。然后要创建一个容器，这里要指明容器中包含的数据类型，如例子中创建一个保存的数据类型为int的vector_t容器

vector_t* pt_vec = create_vector(int);
if(pt_vec == NULL)
{
    return -1;
}

创建容器的函数返回的是容器类型的指针，如果容器创建失败返回NULL。在使用容器前一定要对它进行初始化，使用后要销毁

vector_init(pt_vec);
...
vector_destroy(pt_vec);

使用容器的过程就是调用容器相应的处理函数来对容器中的数据进行操作，上边的程序就是在vector_t容器的末尾依次添加整形数据然后打印出来。最后的输出结果是：

0, 100, 200, 300, 400, 500, 600, 700, 800, 900,

器的使用规则都是要求按照“创建”->“初始化”->“使用”->“销毁”这样的流程来使用容器的。

迭代器

迭代器是对容器的特定范围的数据进行遍历的类型,这个范围可能是整个容器或者是容器的一部分.迭代器表示的是容器中数据的位置的数据结构，它将各个容器的数据位置统一，使用同样的接口进行操作。各个容器都提供了迭代器结构，同时各种算法都是通过迭代器来操作的，所以说迭代器是容器和算法之间联系的桥梁。

如何使用迭代器

我们沿用上面的vector_t的例子来展示如何使用迭代器：

#include <stdio.h>
#include <cstl/cvector.h>

int main(int argc, char* argv[])
{
    vector_t* pt_vec = create_vector(int);
    iterator_t t_iter;
    size_t t_index = 0;
    if(pt_vec == NULL)
    {
        return -1;
    }

    vector_init(pt_vec);

    for(t_index = 0; t_index < 10; ++t_index)
    {
        vector_push_back(pt_vec, t_index * 100);
    }
    for(t_iter = vector_begin(pt_vec);
        !iterator_equal(t_iter, vector_end(pt_vec));
        t_iter = iterator_next(t_iter))
    {
        printf("%d, ", *(int*)iterator_get_pointer(t_iter));
    }
    printf("\n");

    vector_destroy(pt_vec);

    return 0;
}

使用迭代器时不需要额外的包含头文件，在使用前也不需要创建和初始化，使用后也不需要销毁。这个例子只是将上面例子中打印数据的部分使用迭代器来代替：

for(t_iter = vector_begin(pt_vec);
    !iterator_equal(t_iter, vector_end(pt_vec));
    t_iter = iterator_next(t_iter))
{
    printf("%d, ", *(int*)iterator_get_pointer(t_iter));
}

这里首先将vector_t的第一个数据的位置赋值给迭代器t_iter然后判断这个位置是不是最有一个数据的下一个位置如果不是就向下一个数据迭代。这样就遍历了vector_t的所有数据。最后的输出结果仍然是：

0, 100, 200, 300, 400, 500, 600, 700, 800, 900,

算法

libcstl为了处理数据提供了许多算法,例如查找,排序,拷贝,修改还有算术操作.算法不属于任何一种容器,它能够处理任何容器中的数据,算法都是以迭代器作为输入.

如何使用算法

我们仍然使用上面的例子，上面的例子输入的数据都是有序的下面我们输入无序的数据然后使用算法排序:

#include <stdio.h>
#include <cstl/cvector.h>
#include <cstl/calgorithm.h>

int main(int argc, char* argv[])
{
    vector_t* pt_vec = create_vector(int);
    iterator_t t_iter;
    if(pt_vec == NULL)
    {
        return -1;
    }

    vector_init(pt_vec);

    vector_push_back(pt_vec, 500);
    vector_push_back(pt_vec, 300);
    vector_push_back(pt_vec, 0);
    vector_push_back(pt_vec, 600);
    vector_push_back(pt_vec, 900);
    vector_push_back(pt_vec, 100);
    vector_push_back(pt_vec, 800);
    vector_push_back(pt_vec, 400);
    vector_push_back(pt_vec, 700);
    vector_push_back(pt_vec, 200);

    printf("before sorting: ");
    for(t_iter = vector_begin(pt_vec);
        !iterator_equal(t_iter, vector_end(pt_vec));
        t_iter = iterator_next(t_iter))
    {
        printf("%d, ", *(int*)iterator_get_pointer(t_iter));
    }
    printf("\n");

    algo_sort(vector_begin(pt_vec), vector_end(pt_vec));

    printf("after sorting: ");
    for(t_iter = vector_begin(pt_vec);
        !iterator_equal(t_iter, vector_end(pt_vec));
        t_iter = iterator_next(t_iter))
    {
        printf("%d, ", *(int*)iterator_get_pointer(t_iter));
    }
    printf("\n");

    vector_destroy(pt_vec);

    return 0;
}

要使用算法必须包含头文件<cstl/algorithm.h>，这个例子中我们保存在vector_t中的数据是无序的，经过algo_sort()算法的排序后得到了有序的数据。algo_sort()算法使用了两个迭代器vector_begin()和vector_end()，它们分别代表vector_t的第一个数据的位置和最后一个数据的下一个位置，这样它们表示的范围就是整个vector_t。所以algo_sort()是对整个vector_t排序，结果：

before sorting: 500, 300, 0, 600, 900, 100, 800, 400, 700, 200,
after sorting: 0, 100, 200, 300, 400, 500, 600, 700, 800, 900,

函数

libcstl提供了大量的函数,这些函数主要用来为算法提供扩展功能.算法中每一个算法都有一个后缀为if的版本,这个版本接受函数作为操作的规则.同时用户可以自定义函数来扩展算法功能。

如何使用函数

我们仍然修改上面的例子，这一次我们要按照从大到小排序vector_t中的数据：

#include <stdio.h>
#include <cstl/cvector.h>
#include <cstl/calgorithm.h>
#include <cstl/cfunctional.h>

int main(int argc, char* argv[])
{
    vector_t* pt_vec = create_vector(int);
    iterator_t t_iter;
    if(pt_vec == NULL)
    {
        return -1;
    }

    vector_init(pt_vec);

    vector_push_back(pt_vec, 500);
    vector_push_back(pt_vec, 300);
    vector_push_back(pt_vec, 0);
    vector_push_back(pt_vec, 600);
    vector_push_back(pt_vec, 900);
    vector_push_back(pt_vec, 100);
    vector_push_back(pt_vec, 800);
    vector_push_back(pt_vec, 400);
    vector_push_back(pt_vec, 700);
    vector_push_back(pt_vec, 200);

    printf("before sorting: ");
    for(t_iter = vector_begin(pt_vec);
        !iterator_equal(t_iter, vector_end(pt_vec));
        t_iter = iterator_next(t_iter))
    {
        printf("%d, ", *(int*)iterator_get_pointer(t_iter));
    }
    printf("\n");

    algo_sort_if(vector_begin(pt_vec), vector_end(pt_vec), fun_greater_int);

    printf("after sorting: ");
    for(t_iter = vector_begin(pt_vec);
        !iterator_equal(t_iter, vector_end(pt_vec));
        t_iter = iterator_next(t_iter))
    {
        printf("%d, ", *(int*)iterator_get_pointer(t_iter));
    }
    printf("\n");

    vector_destroy(pt_vec);

    return 0;
}

使用函数前要包含头文件<cstl/cfunctional.h>，默认的排序都是从小到大排序，我们要使用从大到小排序数据就要使用函数来作为算法的谓词改变算法的排序方法，要使用fun_greater_int函数和algo_sort_if()算法来达到目的。排序的结构如下：

before sorting: 500, 300, 0, 600, 900, 100, 800, 400, 700, 200,
after sorting: 900, 800, 700, 600, 500, 400, 300, 200, 100, 0,

libcstl适用的数据类型

上面这些例子使用的都是基本的数据类型，但是在实际的编程过程中经常使用的是自定义的数据结构类型，libcstl-1.0不能够有效的处理这些数据类型的，但是libcstl-2.0.0相对于1.0.1来说最大的提高就是增强了对各种数据类型的处理能力。libcstl-2.0.0有效的处理绝大部分的数据类型。它将数据类型分为3类：

C语言内建类型：如：int, long, double等。
用户自定义类型：用户自己定义的数据结构。
libcstl内建类型：如vector_t, set_t, hash_multimap_t等。

其中libcstl内建类型是用户自定义类型的特例，只是libcstl对于libcstl内建类型进行了默认的处理。

如何使用用户自定义类型

那么我们又如何使用用户自定义类型呢？下面我们用一个例子来展示一下：

#include <stdio.h>
#include <cstl/clist.h>

typedef struct _taguser
{
    int _n_first;
    int _n_second;
}user_t;

static void _user_init(const void* cpv_input, void* pv_output)
{
    ((user_t*)cpv_input)->_n_first = 0;
    ((user_t*)cpv_input)->_n_second = 0;
    *(bool_t*)pv_output = true;
}

static void _user_destroy(const void* cpv_input, void* pv_output)
{
    ((user_t*)cpv_input)->_n_first = 0;
    ((user_t*)cpv_input)->_n_second = 0;
    *(bool_t*)pv_output = true;
}

static void _user_copy(const void* cpv_first, const void* cpv_second, void* pv_output)
{
    ((user_t*)cpv_first)->_n_first = ((user_t*)cpv_second)->_n_first;
    ((user_t*)cpv_first)->_n_second = ((user_t*)cpv_second)->_n_second;
    *(bool_t*)pv_output = true;
}

static void _user_less(const void* cpv_first, const void* cpv_second, void* pv_output)
{
    if(((user_t*)cpv_first)->_n_first < ((user_t*)cpv_second)->_n_first)
    {
        *(bool_t*)pv_output = true;
    }
    else
    {
        *(bool_t*)pv_output = false;
    }
}

int main(int argc, char* argv[])
{
    list_t* pt_list = NULL;
    iterator_t t_iter;
    user_t t_sample;

    type_register(user_t, _user_init, _user_copy, _user_less, _user_destroy);

    pt_list = create_list(user_t);
    if(pt_list == NULL)
    {
        return -1;
    }

    list_init(pt_list);

    t_sample._n_first = 100;
    t_sample._n_second = 45;
    list_push_back(pt_list, &t_sample);
    t_sample._n_first = 400;
    t_sample._n_second = -234;
    list_push_back(pt_list, &t_sample);
    t_sample._n_first = 0;
    t_sample._n_second = 1024;
    list_push_back(pt_list, &t_sample);
    t_sample._n_first = 300;
    t_sample._n_second = -444;
    list_push_back(pt_list, &t_sample);
    t_sample._n_first = 200;
    t_sample._n_second = 0;
    list_push_back(pt_list, &t_sample);

    printf("before sorting: ");
    for(t_iter = list_begin(pt_list);
        !iterator_equal(t_iter, list_end(pt_list));
        t_iter = iterator_next(t_iter))
    {
        iterator_get_value(t_iter, &t_sample);
        printf("(%d, %d), ", t_sample._n_first, t_sample._n_second);
    }
    printf("\n");

    list_sort(pt_list);

    printf("after sorting: ");
    for(t_iter = list_begin(pt_list);
        !iterator_equal(t_iter, list_end(pt_list));
        t_iter = iterator_next(t_iter))
    {
        iterator_get_value(t_iter, &t_sample);
        printf("(%d, %d), ", t_sample._n_first, t_sample._n_second);
    }
    printf("\n");

    list_destroy(pt_list);

    return 0;
}

首先有一个用户自定义的数据类型user_t，为了能够在libcstl的容器中使用这个类型的数据我们需要将这个类型注册，调用 type_register()函数，注意这个注册的动作必须在第一次使用user_t数据类型之前，也就是在第一次创建能够保存user_t类型的容器之前注册，一旦注册成功后在当前进程的其他任何容器都可以使用这个类型了，不用再次注册。我们来看看注册函数type_register(user_t, user_init, user_copy, user_less, user_destroy); 这个函数不仅需要自定义的数据名字"user_t"而且需要4个函数，这4个函数分别是用户定义的类型初始化函数，拷贝函数，比较函数和销毁函数，这4个函数会在libcstl管理user_t类型的数据时用到。这4个函数分别是libcstl的一元函数和二元函数。注册成功了，接下来就像使用普通类型一样使用这个user_t类型了。想要创建保存user_t类型数据的容器就在创建函数的参数中填写上 user_t的名字就行了如pt_list = create_list(user_t);这样就创建了一个保存user_t类型的list_t容器。然后按照容器的使用方式初始化，操作，销毁。上面的例子的结果：

before sorting: (100, 45), (400, -234), (0, 1024), (300, -444), (200, 0),
after sorting: (0, 1024), (100, 45), (200, 0), (300, -444), (400, -234),

从结果中可以看出在排序链表中的数据的时候libcstl调用了用户定义的user_less()比较规则。

如何使用libcstl内建类型

libcstl内建类型是用户自定义类型的特例，libcstl对自己的内建类型做了默认支持，所以在使用之前不必注册可以直接使用，同时容器的创建方式有些变化，下面的例子展示一下list_t容器中保存vector_t容器的例子：

#include <stdio.h>
#include <stdlib.h>
#include <cstl/clist.h>
#include <cstl/cvector.h>

int main(int argc, char* argv[])
{
    list_t* pt_list = create_list(vector_t<int>);
    vector_t* pt_vec = create_vector(int);
    iterator_t t_it_list;
    iterator_t t_it_vec;
    size_t t_i = 0;
    size_t t_j = 0;
    size_t t_count = 0;
    if(pt_list == NULL || pt_vec == NULL)
    {
        return -1;
    }

    list_init(pt_list);
    vector_init(pt_vec);

    srand((unsigned)time(NULL));
    for(t_i = 0; t_i < 10; ++t_i)
    {
        t_count = rand() % 10;
        vector_clear(pt_vec);
        for(t_j = 0; t_j < t_count; ++t_j)
       {
            vector_push_back(pt_vec, rand() - rand());
        }
        list_push_back(pt_list, pt_vec);
    }

    printf("before sorting:\n");
    for(t_it_list = list_begin(pt_list);
        !iterator_equal(t_it_list, list_end(pt_list));
        t_it_list = iterator_next(t_it_list))
    {
        for(t_it_vec = vector_begin(iterator_get_pointer(t_it_list));
            !iterator_equal(t_it_vec, vector_end(iterator_get_pointer(t_it_list)));
            t_it_vec = iterator_next(t_it_vec))
        {
            printf("%d, ", *(int*)iterator_get_pointer(t_it_vec));
        }
        printf("\n");
    }
    printf("\n");

    list_sort(pt_list);

    printf("before sorting:\n");
    for(t_it_list = list_begin(pt_list);
        !iterator_equal(t_it_list, list_end(pt_list));
        t_it_list = iterator_next(t_it_list))
    {
        for(t_it_vec = vector_begin(iterator_get_pointer(t_it_list));
            !iterator_equal(t_it_vec, vector_end(iterator_get_pointer(t_it_list)));
            t_it_vec = iterator_next(t_it_vec))
        {
            printf("%d, ", *(int*)iterator_get_pointer(t_it_vec));
        }
        printf("\n");
    }
    printf("\n");

    list_destroy(pt_list);
    vector_destroy(pt_vec);

    return 0;
}

在创建链表的时候有些特别之处，

list_t* pt_list = create_list(vector_t<int>);
list_t* pt_listex = create_list(vector_t<double>);

前者表示的是list_t中保存的数据类型是保存int类型的vector_t类型，后者表示的是list_t保存的数据类型是保存double类型的 vector_t，这两个list_t类型不兼容。整个程序是在list_t中保存10个vector_t，每一个vector_t中保存了10个以内的int类型数，然后将list_t排序。结果如下：

before sorting:
[-799971873, 19189529, 36681306, 758247299, -1770250270, -590336744, 1781653983, ]
[60794738, 936499678, -922890990, 370082313, -268213918, ]
[1816370431, -729530518, -1115889533, -546197176, -304810366, 1024703870, ]
[1401937248, -44341518, -364448296, 479375924, 893343708, ]
[-29547282, 119153949, 164371868, 153733420, ]
[]
[-1419322953, ]
[-1965520129, -262626207, -159617549, 218442875, -1955291553, 1556920902, -1110975475, 1671573889, ]
[-726838123, 1737274567, -252771018, -635931681, -412578561, -674834695, 304715023, 497545654, ]
[169993302, -704466018, 203095754, 562537534, -684530124, -498653815, 1381413940, 260205642, 395825884, ]

after sorting:
[]
[-1965520129, -262626207, -159617549, 218442875, -1955291553, 1556920902, -1110975475, 1671573889, ]
[-1419322953, ]
[-799971873, 19189529, 36681306, 758247299, -1770250270, -590336744, 1781653983, ]
[-726838123, 1737274567, -252771018, -635931681, -412578561, -674834695, 304715023, 497545654, ]
[-29547282, 119153949, 164371868, 153733420, ]
[60794738, 936499678, -922890990, 370082313, -268213918, ]
[169993302, -704466018, 203095754, 562537534, -684530124, -498653815, 1381413940, 260205642, 395825884, ]
[1401937248, -44341518, -364448296, 479375924, 893343708, ]
[1816370431, -729530518, -1115889533, -546197176, -304810366, 1024703870, ]

从结果中可以看出list_t在排序的时候调用vector_less()函数，这就是libcstl对自己的内建类型的默认支持。

深入的了解libcstl-2.0

想深入的了解libcstl-2.0请参考源码包中doc/目录下的libcstl_user_guide.pdf和libcstl_reference_manual.pdf。

下载libcstl_user_guide.pdf和libcstl_reference_manual.pdf