这使得C动态数组通用 [英] Making C dynamic array generic
本文介绍了这使得C动态数组通用的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我刚写了很好的处理上堆上分配一个动态数组在C.它支持多种业务，是比较简单的用情几乎像一个普通的好老数组一个很好的图书馆。它也很容易模仿基于它的许多数据结构（栈，队列，堆，等...）
它可以处理任何类型的阵列，但问题是，有仅每汇编一个单一的类型。 C没有模板，所以它不可能有例如整数和字符的动态数组动态数组在同一个程序，这是一个问题。
我还没有发现任何真正的解决方案，我发现涉及无效*，和NO，我不希望空指针数组的一切。很高兴能够把三分球，但我也希望能够有一个原始数据类型的数组。 （例如，您可以添加例如，3，和访问它想：array.data [I]
我应该：
-
复制/粘贴库一次，对每种类型我想用（可怕的，但它会工作，是有效的）
-
请它一个巨大的宏，我可以用我想要的类型扩展（所以它会具有相同的效果1，但有些优雅和使用）
-
有无尖元件的尺寸是一个变量，它是动态阵列结构的一部分。将工作大多但会有与功能服用并返回动态数组直接输入一个问题。无效*不会永远是一个可行的选择
-
放弃的想法，并使用C ++而不是每当我需要这样的先进功能
该库是这样的：使用
/ *可变长度阵列库，用于C语言
*使用方法：
*声明一个变量长度数组是这样的：
*
* DA my_array;
*
*总是初始化是这样的：
*
* da_init（安培; DA）; //创建一个干净的空数组
*
*设置长度为数组：
*
* da_setlength（安培;达，N）; //注：如果添加的元素，他们会初始化
* //如果元素被删除，他们永久消失
*
*始终可用内存它超出范围之前（避免纪念品泄漏！）
*
* da_destroy（安培; DA）;
*
*访问元素很像一个普通数组：
* - 无边界检查：da.data [I]
* - 边界检查（调试）：da_get（数据，I）
*
* da.length; //返回可变长度数组的当前长度（不要影响本集的长度！使用da_setlength代替。）
*
*您可以在末尾添加单元素和数组的开始
*
* da_add（安培; DA，价值）; //结尾处
* da_push（安培; DA，价值）; //添加在前面
*
*检索末和阵列的前面（同时去除它们）值与
*
* da_remove（安培; DA）; //从最终
* da_pop（安培; DA）; //从前面
*
*与标准数组或另一个同类型的变长数组并置它
*
* da_append（安培; DA，阵列，array_length）; //标准阵列
* da_append（安培; DA，＆安培; DB）; //另一个可变长度数组
* /
实施（对不起，这是巨大的，但我必须给它一个问题的完整性）
的#include＆LT;＆stdlib.h中GT;
＃包括LT＆;＆stdio.h中GT;
＃包括LT＆;＆string.h中GT;//增加由块堆保留
＃定义ALLOC_BLOCK_SIZE 16//该变长数组将包含的类型。在这种情况下，它的诠释，但它可以是任何东西真的（包括指针，数组，结构，等...）
的typedef INT da_type;//推荐这项禁止各种边界和安全检查（一旦你确定你的程序经过全面测试，获得效率）
＃定义DEBUG_RUNTIME_CHECK_BOUNDS//为可变长度数组变量的数据结构
typedef结构
{
da_type *启动; //点开始的内存分配区域的
da_type *数据; //指向数组的逻辑起点
da_type *结束; //点结束内存中分配的区域
为size_t长度; //数组的长度
}
DA;//初始化变量长度数组，配备2个街区，并把从头开始指针
无效da_init（DA * DA）
{
da_type * PTR =的malloc（ALLOC_BLOCK_SIZE *的sizeof（da_type））;
如果（PTR == 0）出口（1）;
DA-＆GT;开始= PTR;
DA-＆GT;数据= PTR;
DA-＆GT;结束= DA-＆GT;启动+ ALLOC_BLOCK_SIZE;
DA-＆GT;长度= 0;
}//直接设置大小大
无效da_setlength（DA *哒，为size_t newsize）
{
如果（newsize％ALLOC_BLOCK_SIZE！= 0）
newsize + = ALLOC_BLOCK_SIZE - newsize％ALLOC_BLOCK_SIZE; ptrdiff_t的取舍= DA-＆GT;数据 - DA-＆GT;启动;
da_type * PTR =的realloc（DA＆GT;开始，newsize *的sizeof（da_type））;
（！PTR）如果出口（1）; DA-＆GT;开始= PTR;
DA-＆GT;数据= PTR +取舍;
DA-＆GT;结束= PTR + newsize;
DA-＆GT;长度= newsize;
}//销毁可变长度阵列（基本上只是释放内存）
无效da_destroy（DA * DA）
{
免费（DA＆GT;启动）;
#IFDEF DEBUG_RUNTIME_CHECK_BOUNDS
DA-＆GT;启动= NULL;
DA-＆GT;数据= NULL;
DA-＆GT;结束= NULL;
DA-＆GT;长度= 0;
＃万一
}//获取数组的元素与它的指数
#IFDEF DEBUG_RUNTIME_CHECK_BOUNDS
//获取数组的元素与边界检查
da_type da_get（DA *大，无符号整型指数）
{
如果（索引＆gt; =＆DA-GT;长度）
{
的printf（大错误：索引％u是出界的\\ n，指数）;
出口（1）;
}
返回DA-＆GT;数据[指数]
} //设置数组的元素与边界检查
无效da_set（DA *大，无符号整型指数，da_type数据）
{
如果（索引＆gt; =＆DA-GT;长度）
{
的printf（大错误：索引％u是出界的\\ n，指数）;
出口（1）;
}
DA-＆GT;数据[索引] =数据;
}
＃其他
//获取数组的元素没有边界检查
＃定义da_get（DA，指数）（（DA） - GT;数据[（指数）]） //设置数组的元素没有边界检查
＃定义da_set（DA，指数，V）（da_get（DA，指数）= V）
＃万一
//在数组的末尾添加元素
无效da_add（DA *哒，da_type I）
{//如果没有更多的内存
如果（DA＆GT;数据+ DA-＆GT;长度GT; =＆DA-GT端）
{//分配的内存块的大小增加
ptrdiff_t的偏移量= DA-＆GT;数据 - DA-＆GT;启动;
ptrdiff_t的newsize = DA-＆GT;结束 - DA-＆GT;启动+ ALLOC_BLOCK_SIZE;
da_type * PTR =的realloc（DA＆GT;开始，newsize *的sizeof（da_type））;
（！PTR）如果出口（1）; DA-＆GT;数据= PTR +偏移;
DA-＆GT;结束= PTR + newsize;
DA-＆GT;开始= PTR;
}
DA-＆GT;数据[DA-＆GT;长度] =我;
DA-＆GT;长+ = 1;
}//在数组的末尾删除元素（并返回）
da_type da_remove（DA * DA）
{
#IFDEF DEBUG_RUNTIME_CHECK_BOUNDS
如果（DA＆GT;长度== 0）
{
的printf（错误 - 试图从空数组删除项目）;
出口（1）;
}
＃万一
//读取数组的最后一个元素
DA-＆GT;长度 - = 1;
da_type ret_value = DA-＆GT;数据[DA-＆GT;长度]。
//删除多余的内存，如果有太多了
如果（DA＆GT;结束 - （DA＆GT;数据+ DA-＆GT;的长度）GT; ALLOC_BLOCK_SIZE）
{
ptrdiff_t的偏移量= DA-＆GT;数据 - DA-＆GT;启动;
ptrdiff_t的newsize = DA-＆GT;结束 - DA-＆GT;启动 - ALLOC_BLOCK_SIZE;
da_type * PTR =的realloc（DA＆GT;开始，newsize *的sizeof（da_type））;
（！PTR）如果出口（1）; DA-＆GT;数据= PTR +偏移;
DA-＆GT;结束= PTR + newsize;
DA-＆GT;开始= PTR;
}
返回ret_value;
}//在数组的开始添加元素
无效da_push（DA *哒，da_type I）
{//如果阵列达到分配空间的底部，我们需要分配更多的
如果（DA＆GT;数据== DA-＆GT;启动）
{
ptrdiff_t的newsize = DA-＆GT;结束 - DA-＆GT;启动+ ALLOC_BLOCK_SIZE;
da_type * PTR =的realloc（DA＆GT;开始，newsize *的sizeof（da_type））;
（！PTR）如果出口（1）;
memmove与（PTR + ALLOC_BLOCK_SIZE，PTR，DA-＆GT;长*的sizeof（da_type））; DA-＆GT;数据= PTR + ALLOC_BLOCK_SIZE;
DA-＆GT;开始= PTR;
DA-＆GT;结束= PTR + newsize;
}
//在数组中开始存储元素
DA-＆GT;长+ = 1;
DA-＆GT;数据 - = 1;
DA-＆GT;数据[0] = I;
}//删除数组的第一个元素（并返回）
da_type da_pop（DA * DA）
{
#IFDEF DEBUG_RUNTIME_CHECK_BOUNDS
如果（DA＆GT;长度== 0）
{
的printf（错误 - 试图从空数组删除项目）;
出口（1）;
}
＃万一
da_type ret_value = DA-＆GT;数据[0];
DA-＆GT;长度 - = 1;
DA-＆GT;数据+ = 1;
ptrdiff_t的偏移量= DA-＆GT;数据 - DA-＆GT;启动;
如果（偏移＆GT; ALLOC_BLOCK_SIZE）
{
ptrdiff_t的newsize = DA-＆GT;结束 - DA-＆GT;启动 - ALLOC_BLOCK_SIZE;
da_type * PTR =的realloc（DA＆GT;开始，newsize *的sizeof（da_type））;
（！PTR）如果出口（1）;
memmove与（PTR +偏移 - ALLOC_BLOCK_SIZE，PTR +偏移，DA-＆GT;长*的sizeof（da_type））; DA-＆GT;数据= PTR +偏移 - ALLOC_BLOCK_SIZE;
DA-＆GT;开始= PTR;
DA-＆GT;结束= PTR + newsize;
}
返回ret_value;
}//追加t数组送
无效da_array_append（DA * S，常量da_type * T，为size_t t_len）
{
如果（（S-GT＆;长+ t_len）GT;（S-GT和末端 - S-＆GT;启动））
{//如果堆中预留更多空间
ptrdiff_t的偏移量= S-＆GT;数据 - S-＆GT;启动;
ptrdiff_t的newsize = S-＆GT;长+ t_len;
//保证新大小ALLOC块大小的倍数
如果（t_len％ALLOC_BLOCK_SIZE！= 0）
newsize + = ALLOC_BLOCK_SIZE - （t_len％ALLOC_BLOCK_SIZE）; da_type * PTR =的malloc（newsize *的sizeof（da_type））;
（！PTR）如果出口（1）; 的memcpy（PTR，S-GT＆;数据，S-＆GT;长*的sizeof（da_type））;
的memcpy（PTR + S-GT＆;长度，T，t_len *的sizeof（da_type））;
免费（S-GT＆;启动）;
S-GT＆;数据= PTR;
S-GT＆;开始= PTR;
S-GT＆;结束= PTR + newsize;
}
其他
在堆缓冲区//足够的空间 - ＆GT;做到这一点的简单方法
memmove与（S-GT＆;数据+ S-＆GT;长度，T，t_len *的sizeof（da_type））; S-GT＆;长+ = t_len;
}//附加一个DA是追加数组的特例
的#define da_append（S，T）da_array_append（S，（叔） - ＆GT;数据，（叔） - ＆GT;长度）
解决方案
我会做的就是回落到preprocessor hackage。您可以通过添加类型信息肯定实现的东西像C ++模板时，必要的。
结构da_impl {
为size_t LEN;
为size_t elem_size;
为size_t allocsize; // 管他呢
};无效da_init_impl（结构da_impl * IMPL，为size_t elem_size）
{
impl-＆GT; LEN = 0;
impl-＆GT; elem_size = elem_size;
impl-＆GT; allocsize = 0;
}＃定义DA_TEMPLATE（T）结构{da_impl implement执行; T *的数据; }
＃定义da_init（一）da_init_impl（安培; a.impl，sizeof的（* A.数据））//等等。
然后你可以使用这样的：
DA_TEMPLATE（INT）intArray;
da_init（intArray）;da_append（intArray，42）;INT富= intArray.data [0];
一个缺点是，这将创建一个匿名结构，你不能真正使用它的范围之外，但也许你可以忍受...
I just wrote a nice library that handles nicely a dynamic array allocated on heap in C. It supports many operations, is relatively simple to use "feeling" almost like a regular good old array. It is also easy to simulate many data structures based on it (stacks, queues, heaps, etc...)
It can handle arrays of any type, but the problem is that there's only a single type per compilation. C doesn't have templates, so it's impossible to have for example dynamic arrays of ints and dynamic arrays of chars in the same program, which is a problem.
I haven't found any real solution, everything that I found involved void*, and NO, I do NOT want an array of void pointers. It's nice to be able to put pointers, but I also want to be able to have an array of a raw data type. (such that you can add for example, 3, and access it like : array.data[i]
Should I :
Copy/paste the library once for every type I want to use (horrible, but it'll work and be efficient)
Make it a giant macro, that I can expand with the type I want (so it'll have the same effect as 1, but be somewhat elegant and usable)
Have the size of pointed elements be a variable that is part of the dynamic array structure. Will work mostly but there will be a problem with functions taking and returning the dynamic array type directly. void* will not always be a viable option
Abandon the idea and use C++ instead whenever I need such advanced features
The library works like this : Usage
/* Variable length array library for C language
* Usage :
* Declare a variable length array like this :
*
* da my_array;
*
* Always initialize like this :
*
* da_init(&da); // Creates a clean empty array
*
* Set a length to an array :
*
* da_setlength(&da, n); // Note : if elements are added they'll be uninitialized
* // If elements are removed, they're permanently lost
*
* Always free memory before it goes out of scope (avoid mem leaks !)
*
* da_destroy(&da);
*
* Access elements much like a normal array :
* - No boundary checks : da.data[i]
* - With boundary checks (debug) : da_get(data, i)
*
* da.length; // Return the current length of the variable length array (do NOT set the length by affecting this !! Use da_setlength instead.)
*
* You can add single elements at the end and beginning of array with
*
* da_add(&da, value); // Add at the end
* da_push(&da, value); // Add at the front
*
* Retrieve values at the end and front of array (while removing them) with
*
* da_remove(&da); // From the end
* da_pop(&da); // From the front
*
* Concatenate it with a standard array or another variable length array of same type with
*
* da_append(&da, array, array_length); // Standard array
* da_append(&da, &db); // Another variable length array
*/
Implementation (I'm sorry it's huge, but I have to give it for completeness of the question)
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
// Increment by which blocks are reserved on the heap
#define ALLOC_BLOCK_SIZE 16
// The type that the variable length array will contain. In this case it's "int", but it can be anything really (including pointers, arrays, structs, etc...)
typedef int da_type;
// Commend this to disable all kinds of bounds and security checks (once you're sure your program is fully tested, gains efficiency)
#define DEBUG_RUNTIME_CHECK_BOUNDS
// Data structure for variable length array variables
typedef struct
{
da_type *start; // Points to start of memory allocated region
da_type *data; // Points to logical start of array
da_type *end; // Points to end of memory allocated region
size_t length; // Length of the array
}
da;
// Initialize variable length array, allocate 2 blocks and put start pointer at the beginning
void da_init(da *da)
{
da_type *ptr = malloc(ALLOC_BLOCK_SIZE * sizeof(da_type));
if(ptr == 0) exit(1);
da->start = ptr;
da->data = ptr;
da->end = da->start + ALLOC_BLOCK_SIZE;
da->length = 0;
}
// Set the da size directly
void da_setlength(da *da, size_t newsize)
{
if(newsize % ALLOC_BLOCK_SIZE != 0)
newsize += ALLOC_BLOCK_SIZE - newsize % ALLOC_BLOCK_SIZE;
ptrdiff_t offs = da->data - da->start;
da_type *ptr = realloc(da->start, newsize * sizeof(da_type));
if(!ptr) exit(1);
da->start = ptr;
da->data = ptr + offs;
da->end = ptr + newsize;
da->length = newsize;
}
// Destroy the variable length array (basically just frees memory)
void da_destroy(da* da)
{
free(da->start);
#ifdef DEBUG_RUNTIME_CHECK_BOUNDS
da->start = NULL;
da->data = NULL;
da->end = NULL;
da->length = 0;
#endif
}
// Get an element of the array with it's index
#ifdef DEBUG_RUNTIME_CHECK_BOUNDS
//Get an element of the array with bounds checking
da_type da_get(da *da, unsigned int index)
{
if(index >= da->length)
{
printf("da error : index %u is out of bounds\n", index);
exit(1);
}
return da->data[index];
}
//Set an element of the array with bounds checking
void da_set(da *da, unsigned int index, da_type data)
{
if(index >= da->length)
{
printf("da error : index %u is out of bounds\n", index);
exit(1);
}
da->data[index] = data;
}
#else
//Get an element of the array without bounds checking
#define da_get(da, index) ((da)->data[(index)])
//Set an element of the array without bounds checking
#define da_set(da, index, v) (da_get(da, index) = v)
#endif
// Add an element at the end of the array
void da_add(da *da, da_type i)
{ // If no more memory
if(da->data + da->length >= da->end)
{ // Increase size of allocated memory block
ptrdiff_t offset = da->data - da->start;
ptrdiff_t newsize = da->end - da->start + ALLOC_BLOCK_SIZE;
da_type *ptr = realloc(da->start, newsize * sizeof(da_type));
if(!ptr) exit(1);
da->data = ptr + offset;
da->end = ptr + newsize;
da->start = ptr;
}
da->data[da->length] = i;
da->length += 1;
}
// Remove element at the end of the array (and returns it)
da_type da_remove(da *da)
{
#ifdef DEBUG_RUNTIME_CHECK_BOUNDS
if(da->length == 0)
{
printf("Error - try to remove item from empty array");
exit(1);
}
#endif
//Read last element of the array
da->length -= 1;
da_type ret_value = da->data[da->length];
//Remove redundant memory if there is too much of it
if(da->end - (da->data + da->length) > ALLOC_BLOCK_SIZE)
{
ptrdiff_t offset = da->data - da->start;
ptrdiff_t newsize = da->end - da->start - ALLOC_BLOCK_SIZE;
da_type *ptr = realloc(da->start, newsize * sizeof(da_type));
if(!ptr) exit(1);
da->data = ptr + offset;
da->end = ptr + newsize;
da->start = ptr;
}
return ret_value;
}
// Add element at the start of array
void da_push(da *da, da_type i)
{ //If array reaches bottom of the allocated space, we need to allocate more
if(da->data == da->start)
{
ptrdiff_t newsize = da->end - da->start + ALLOC_BLOCK_SIZE;
da_type *ptr = realloc(da->start, newsize * sizeof(da_type));
if(!ptr) exit(1);
memmove(ptr + ALLOC_BLOCK_SIZE, ptr, da->length * sizeof(da_type));
da->data = ptr + ALLOC_BLOCK_SIZE;
da->start = ptr;
da->end = ptr + newsize;
}
// Store element at start of array
da->length += 1;
da->data -= 1;
da->data[0] = i;
}
//Remove 1st element of array (and return it)
da_type da_pop(da *da)
{
#ifdef DEBUG_RUNTIME_CHECK_BOUNDS
if(da->length == 0)
{
printf("Error - try to remove item from empty array");
exit(1);
}
#endif
da_type ret_value = da->data[0];
da->length -= 1;
da->data += 1;
ptrdiff_t offset = da->data - da->start;
if(offset > ALLOC_BLOCK_SIZE)
{
ptrdiff_t newsize = da->end - da->start - ALLOC_BLOCK_SIZE;
da_type *ptr = realloc(da->start, newsize * sizeof(da_type));
if(!ptr) exit(1);
memmove(ptr + offset - ALLOC_BLOCK_SIZE, ptr + offset, da->length * sizeof(da_type));
da->data = ptr + offset - ALLOC_BLOCK_SIZE;
da->start = ptr;
da->end = ptr + newsize;
}
return ret_value;
}
// Append array t to s
void da_array_append(da *s, const da_type *t, size_t t_len)
{
if((s->length + t_len) > (s->end - s->start))
{ // Should reserve more space in the heap
ptrdiff_t offset = s->data - s->start;
ptrdiff_t newsize = s->length + t_len;
// Guarantees that new size is multiple of alloc block size
if(t_len % ALLOC_BLOCK_SIZE != 0)
newsize += ALLOC_BLOCK_SIZE - (t_len % ALLOC_BLOCK_SIZE);
da_type *ptr = malloc(newsize * sizeof(da_type));
if(!ptr) exit(1);
memcpy(ptr, s->data, s->length * sizeof(da_type));
memcpy(ptr + s->length, t, t_len * sizeof(da_type));
free(s->start);
s->data = ptr;
s->start = ptr;
s->end = ptr + newsize;
}
else
// Enough space in heap buffer -> do it the simple way
memmove(s->data + s->length, t, t_len * sizeof(da_type));
s->length += t_len;
}
// Append a da is a particular case of appending an array
#define da_append(s, t) da_array_append(s, (t)->data, (t)->length)
解决方案
What I would do is fall back to preprocessor hackage. You can definitely achieve something like templates in C++ by adding type information when necessary.
struct da_impl {
size_t len;
size_t elem_size;
size_t allocsize; // or whatever
};
void da_init_impl(struct da_impl *impl, size_t elem_size)
{
impl->len = 0;
impl->elem_size = elem_size;
impl->allocsize = 0;
}
#define DA_TEMPLATE(t) struct { da_impl impl; t *data; }
#define da_init(a) da_init_impl(&a.impl, sizeof(*a.data))
// etc.
Then you can use it like this:
DA_TEMPLATE(int) intArray;
da_init(intArray);
da_append(intArray, 42);
int foo = intArray.data[0];
One drawback is that this creates an anonymous structure which you can't really use outside of its scope, but maybe you can live with that...
这篇关于这使得C动态数组通用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
