• 欢迎光临~

utarray详解

开发技术 开发技术 2022-07-24 次浏览

库函数

//必须要有,程序开头先声明UT_array变量,然后调用utarray_new,程序结束前要记得调用utarray_free,否则堆内存不被释放
utarray_new(UT_array *a, UT_icd *icd)
utarray_free(UT_array *a)
//最常用的函数
utarray_push_back(UT_array *a,void *p)
utarray_pop_back(UT_array *a)
utarray_front(UT_array *a)
utarray_back(UT_array *a)
utarray_len(UT_array *a)
utarray_eltptr(UT_array *a,int j)
utarray_eltidx(UT_array *a,void *e)
//相对不常用的函数
utarray_insert(UT_array *a,void *p, int j)
utarray_resize(UT_array *dst,int num)
utarray_concat(UT_array *dst,UT_array *src)
utarray_clear(UT_array *a)
utarray_sort(UT_array *a, cmpfunc *cmp)
utarray_find(UT_array *a, void *v, cmpfunc *cmp)

utarray_new: 先声明UT_array指针做第一个参数,第二个参数是自定义类型,库给了三种预设类型: ut_str_icd, ut_int_icd, ut_ptr_icd,要传地址进去。
utarray_free: 释放堆内存,最后必须有
utarray_push_back: 末尾添加节点,传入的是指针,所以数字必须取地址,字面量也不行(封装函数转一下就可以了)
utarray_pop_back: 弹出末尾节点。
utarray_front: 返回头节点指针。
utarray_back: 返回尾节点指针。
utarray_len: 返回数组长度。
utarray_eltptr: 根据索引返回节点指针。
utarray_eltidx: 根据节点地址返回索引。
utarray_insert: 在索引为j的位置插入一个元素,复杂度O(N),慎用。
utarray_resize: 把数组的长度改成参数二的值,长了截断断了增补。
utarray_concat: 拼接两个数组
utarray_clear: 数组清空,注意,这里会根据UT_icd注册的函数执行清空,如果注册的是NULL,就只是把长度变为0
utarray_sort: cmp书写规则类似于qsort。
utarray_find: 内部使用二分查找实现,所以必须排过序(升序降序都可以),比较函数必须和utarray_sort的一样。参数二是待搜索值的地址。

正文

int cmp(const void *a, const void *b)
{
	return *(int *)b - *(int *)a;
}

size_t Find(UT_array *arr, const int num)
{
	void *temp = utarray_find(arr, &num, cmp);
	if (temp)
	{
		return (int)utarray_eltidx(arr, temp);
	}
	else
	{
		return -1;
	}
}

int main()
{
	UT_array *arr;
	utarray_new(arr, &ut_int_icd);
	for (int i = 1; i <= 11111111; i = i * 10 + 1)
	{
		utarray_push_back(arr, &i);
	}

	for (int i = 0; i < utarray_len(arr); i++)
	{
		printf("%d: %dn", i, *(int *)utarray_eltptr(arr, i));
	}
	utarray_pop_back(arr);
	utarray_pop_back(arr);
	printf("========pop %d times========n", 2);
	for (int i = 0; i < utarray_len(arr); i++)
	{
		printf("%d: %dn", i, *(int *)utarray_eltptr(arr, i));
	}
	utarray_sort(arr, cmp);
	printf("========sorted========n");
	for (int i = 0; i < utarray_len(arr); i++)
	{
		printf("%d: %dn", i, *(int *)utarray_eltptr(arr, i));
	}
	printf("11 idx: %dn", Find(arr, 11));
	printf("111111 idx: %dn", Find(arr, 111111));
	utarray_free(arr);
	return 0;
}

程序执行了以下操作:

  1. 数组内用棍填充,最大填充到八棍。
  2. 打印。
  3. pop两个元素。
  4. 再次打印。
  5. 降序排序数组。
  6. 再次打印。
  7. 搜索并打印11和111111的位置。

最终结果:

0: 1
1: 11
2: 111
3: 1111
4: 11111
5: 111111
6: 1111111
7: 11111111
========pop 2 times========
0: 1
1: 11
2: 111
3: 1111
4: 11111
5: 111111
========sorted========
0: 111111
1: 11111
2: 1111
3: 111
4: 11
5: 1
11 idx: 4
111111 idx: 0

搜索函数封装了下,写起来更加直观,查不到时总能正确返回-1。

后记

变长数组有什么用?
在某些场合下内存开销会更小,而且同时具有栈和数组的特性,但是时间开销上要比定长数组要大一些。
总的来说,就像C++里面vector一样。你说我只用定长数组行不行?当然可以,甚至大多数情况下时间复杂度更小。那为什么用vector?还不是因为香而且代价也不大?

程序员灯塔
转载请注明原文链接:utarray详解
喜欢 (0)