libcstl簡介
libcstl是一個應用于C語言程式設計的函數庫,它将程式設計過程中經常使用的資料結構如向量、連結清單、集合、樹等封 裝成相應的資料結構并提供一系列的操作函數來操作儲存在這些資料結構中的資料,同時它還将常用的算法如 排序、查找、劃分等封裝成相應的算法函數并提供疊代器來使兩者之間建立聯系友善使用。從libcstl的名字 就可以看出它于STL有一定的關系,是的libcstl的接口和實作都是模仿了STL。
libcstl的産生主要是基于使用C語言程式設計過程中經常要使用向量、連結清單、集合等資料結構和排序、查找、劃分 等算法,但是對于這些資料結構和算法每次都要重複的實作,如果有一個通用的類似于STL的資料結構和算法 的庫就可以節約時間和成本,這樣libcstl就誕生了。
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的底層實作.
配置 queue_t 擴充卡的底層實作(--enable-queue-implementation=ARGUMENT)
這個選項是配置 queue_t 的底層實作,ARGUMENT 作為 queue_t 的底層實作,ARGUMENT 是 list(--enable-queue-implementation=list),預設使用 deque_t 為 queue_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%)。預設使用紅黑樹作為底層實作。
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可以動态增長,并且易于使用,你可很友善的插入删除字元或子串,友善的替換等等.
疊代器
疊代器是對容器的特定範圍的資料進行周遊的類型,這個範圍可能是整個容器或者是容器的一部分.疊代器表示的 是容器中資料的位置的資料結構,它将各個容器的資料位置統一,使用同樣的接口進行操作。各個容器都提供了疊代器結構, 同時各種算法都是通過疊代器來操作的,是以說疊代器是容器和算法之間聯系的橋梁。
算法
libcstl為了處理資料提供了許多算法,例如查找,排序,拷貝,修改還有算術操作.算法不屬于任何一種容器,它能 夠處理任何容器中的資料,算法都是以疊代器作為輸入
容器使用代碼
以vector_t例子介紹容器的使用,容器的使用可以分為四步:
1.建立容器
2.初始化容器
3.對容器操作
4.銷毀容器
以下是使用容器的代碼,其中對容器周遊用了兩種方法, 一種是疊代器,一種是用下标,建議周遊的時候使用疊代器。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <cstl/cvector.h>
/**
*bref 比較容器中兩個節點值的大小
*/
void value_greater(const void *cpv_first, const void *cpv_second, void *pv_output)
{
if (*(int *)cpv_first > *(int *)cpv_second){
*(bool_t *)pv_output = true;
}else{
*(bool_t *)pv_output = false;
}
}
/**
*bref 用疊代器周遊容器
*/
void vector_travel_by_iter(vector_t *pt_vec)
{
iterator_t iter;
if (pt_vec == NULL){
fprintf(stderr, "[travel_inter]:vector is null.\n");
return;
}
printf("------------使用疊代器周遊 ------------\n");
for (iter = vector_begin(pt_vec); !iterator_equal(iter, vector_end(pt_vec)); iter = iterator_next(iter)){
printf("%d ", *(int *)iterator_get_pointer(iter));
}
printf("\n");
}
/**
*bref 用下标周遊容器
*/
void vector_travel_by_index(vector_t *pt_vec)
{
size_t t_index = 0;
if (pt_vec == NULL){
fprintf(stderr, "[travel_index]:vector is null.\n");
return;
}
printf("------------使用下标周遊------------\n");
for (t_index = 0; t_index < 10; t_index++){
printf("%d ", *(int *)vector_at(pt_vec, t_index));
}
printf("\n");
}
int main(int argc, char *argv[])
{
vector_t *pt_vec = create_vector(int);
size_t t_index = 0;
iterator_t iter;
if (pt_vec == NULL){
fprintf(stderr, "create vector is failed.\n");
return -1;
}
vector_init(pt_vec);
srand((unsigned int)time(NULL));
///循環指派
for (t_index = 0; t_index < 10; t_index++){
vector_push_back(pt_vec, rand()%64);
}
printf("begin sorting:\n");
vector_travel_by_iter(pt_vec);
vector_travel_by_index(pt_vec);
printf("\nafter order sorting:\n");
///有條件排序,排序條件以回調函數的形式給出,如果回調函數為空,使用預設條件(遞增)排序
algo_sort_if(vector_begin(pt_vec), vector_end(pt_vec), value_greater);
vector_travel_by_iter(pt_vec);
printf("\nafter reverse sorting:\n");
///預設條件(遞增)排序
algo_sort(vector_begin(pt_vec), vector_end(pt_vec));
vector_travel_by_index(pt_vec);
vector_destroy(pt_vec);
return 0;
}
編譯:
gcc -o test_vector test_vector.c -I/root/libcstl/lib/include/ -L/root/libcstl/lib/lib/ -lcstl
運作結果如下:
begin sorting:
------------使用疊代器周遊 ------------
27 7 16 58 49 24 53 14 34 22
------------使用下标周遊------------
27 7 16 58 49 24 53 14 34 22
after order sorting:
------------使用疊代器周遊 ------------
58 53 49 34 27 24 22 16 14 7
after reverse sorting:
------------使用下标周遊------------
7 14 16 22 24 27 34 49 53 58
libcstl适用的資料類型
上面這些例子使用的都是基本的資料類型,但是在實際的程式設計過程中經常使用的是自定義的資料結構類型,libcstl-1.0不能夠有效的 處理這些資料類型的,但是libcstl-2.0.0相對于1.0.1來說最大的提高就是增強了對各種資料類型的處理能力。libcstl-2.0.0有效的 處理絕大部分的資料類型。它将資料類型分為3類:
1.C語言内建類型:如:int, long, double等。
2.使用者自定義類型:使用者自己定義的資料結構。
3.libcstl内建類型:如vector_t, set_t, hash_multimap_t等。
其中libcstl内建類型是使用者自定義類型的特例,隻是libcstl對于libcstl内建類型進行了預設的處理
自定義資料類型使用例子
使用自定義資料類型步驟如下:
1.定義資料類型
2.定義與該資料類型相對應的初始函數,拷貝,比較函數,銷毀函數
3.使用type_register(user_t, user_init, user_copy, user_less, user_destroy);注冊
4.建立容器
5.初始化容器
6.操作容器
7.銷毀容器
#include <stdlib.h>
#include <stdio.h>
#include <cstl/clist.h>
#define N_MAX 29
typedef unsigned char uint8_t;
typedef unsigned short uint16_t;
typedef unsigned int uint32_t;
typedef struct{
uint8_t id;
uint8_t age;
uint8_t sex;
char name[N_MAX];
}user_t;
static void _user_init(const void *cpv_input, void *pv_output)
{
user_t * user_input = (user_t *)cpv_input;
memset(user_input, 0, sizeof(user_t));
*(bool_t *)pv_output = true;
}
static void _user_destroy(const void *cpv_input, void *pv_output)
{
user_t * user_input = (user_t *)cpv_input;
memset(user_input, 0, sizeof(user_t));
*(bool_t *)pv_output = true;
}
static void _user_copy(const void *cpv_first, const void *cpv_second, void *pv_output)
{
user_t *user_1 = (user_t *)cpv_first;
user_t *user_2 = (user_t *)cpv_second;
user_1->id = user_2->id;
user_1->age = user_2->age;
user_1->sex = user_2->sex;
strncpy(user_1->name, user_2->name, N_MAX);
*(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)->id < ((user_t *)cpv_second)->id){
*(bool_t *)pv_output = true;
}else{
*(bool_t *)pv_output = false;
}
}
void list_travel_by_iter(list_t *pt_list)
{
iterator_t iter;
user_t user;
if (pt_list == NULL){
fprintf(stderr, "[travel_inter]:list is null.\n");
return;
}
printf("------------使用疊代器周遊 ------------\n");
printf("Id\t Name \tAge\tSex\t\n");
for (iter = list_begin(pt_list); !iterator_equal(iter, list_end(pt_list)); iter = iterator_next(iter)){
iterator_get_value(iter, &user);
printf("%u\t %s \t% u\t %c\n", user.id, user.name, user.age, user.sex?'m':'f');
}
printf("\n");
}
int main(int argc, char *argv[])
{
list_t *pt_list = NULL;
size_t index;
user_t user_obj[] = {{134, 57, 1, "steven jobs"},
{110, 50, 1, "bill gates"},
{85, 52, 0, "alex martelli"},
{220, 30, 0, "michel wood"},
{24, 72, 1, "bob green"},
{102, 29, 1, "devil cash"}};
type_register(user_t, _user_init, _user_copy, _user_less, _user_destroy);
pt_list = create_list(user_t);
if (pt_list == NULL){
fprintf(stderr, "create list is failed.\n");
return -1;
}
list_init(pt_list);
for (index = 0; index < 6; index++){
list_push_back(pt_list, &user_obj[index]);
}
printf("before sorting\n");
list_travel_by_iter(pt_list);
list_sort(pt_list);
printf("after sorting\n");
list_travel_by_iter(pt_list);
list_destroy(pt_list);
return 0;
}
編譯
gcc -o test_list test_list.c -I/root/libcstl/lib/include/ -L/root/libcstl/lib/lib/ -lcstl
運作結果如下:
before sorting
------------使用疊代器周遊 ------------
Id Name Age Sex
134 steven jobs 57 m
110 bill gates 50 m
85 alex martelli 52 f
220 michel wood 30 f
24 bob green 72 m
102 devil cash 29 m
after sorting
------------使用疊代器周遊 ------------
Id Name Age Sex
24 bob green 72 m
85 alex martelli 52 f
102 devil cash 29 m
110 bill gates 50 m
134 steven jobs 57 m
220 michel wood 30 f