使C动态数组通用

我刚刚编写了一个很好的库,可以很好地处理在C中堆上分配的动态数组.它支持许多操作,使用起来相对简单,"感觉"几乎就像一个常规的旧数组.基于它(堆栈,队列,堆等)模拟许多数据结构也很容易.

它可以处理任何类型的数组,但问题是每个编译只有一个类型.C没有模板,因此在同一程序中不可能有例如动态的int数组和动态字符数组,这是一个问题.

我没有找到任何真正的解决方案,我发现的所有内容都涉及void*,而且,不,我不想要一个void指针数组.能够放指针很好,但我也希望能够拥有一个原始数据类型的数组.(这样你可以添加例如3,并访问它:array.data [i]

我是不是该 :

为我想要使用的每种类型复制/粘贴一次库(可怕,但它会工作并且效率很高)

使它成为一个巨大的宏,我可以扩展我想要的类型(因此它将具有与1相同的效果,但有点优雅和可用)

将尖头元素的大小变为动态数组结构的一部分.将主要工作,但函数采取和直接返回动态数组类型将有问题.void*并不总是一个可行的选择

放弃这个想法,并在我需要这些高级功能时使用C++

该库的工作原理如下:用法

/* 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
 */

实施(对不起,这是巨大的,但为了问题的完整性,我必须给它)

#include 
#include 
#include 

// 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)

小智.. 10

我要做的是回到预处理器的hackage.通过在必要时添加类型信息,您绝对可以在C++中实现类似模板的功能.

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.

然后你可以像这样使用它:

DA_TEMPLATE(int) intArray;
da_init(intArray);

da_append(intArray, 42);

int foo = intArray.data[0];

一个缺点是,这会创建一个匿名结构,您无法在其范围之外使用,但也许您可以忍受...