製作C動態數組通用指南

Question

我剛剛寫了一個很好的庫，可以很好地處理在C堆中分配的動態數組。它支持很多操作，使用「感覺」相對比較簡單，幾乎就像一個普通的舊數組。它也很容易模擬許多基於它的數據結構（堆棧，隊列，堆等...）

它可以處理任何類型的數組，但問題是每個編譯只有一個類型。 C沒有模板，因此在同一個程序中不可能有例如動態數組的字符串和動態字符數組，這是一個問題。

我還沒有找到任何真正的解決方案，我發現一切都涉及void *和NO，我不想要一個void指針數組。能夠放置指針非常好，但我也希望能夠擁有一個原始數據類型的數組。 （例如，您可以添加例如，3，和訪問它想：array.data [I]

我應該：

1. 複製/粘貼庫一次，每一種類型的我想用（可怕的，但它會工作，並有效）

2. 使它成爲一個巨大的宏，我可以擴大我想要的類型（所以它會有1效果，但有點優雅和可用）

3. 具有指向元素的大小是一個變量是部分o f動態數組結構。將主要工作，但將直接返回動態數組類型的函數會有問題。無效*不會永遠是一個可行的選擇

4. 放棄的想法，並使用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 <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) 

Answer 1

我會做的是回退到預處理器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]; 

一個缺點是，這將創建一個匿名結構，你不能真正使用它的範圍之外，但也許你可以忍受...

Answer 2

使用工會爲您通用數據...

typedef union 
{ 
    int *pIntArr; 
    double *pDblArr; 
    struct *pStructArr; 
    ... // Etc. 
} genericData; 

...和使用結構來保存這個，所以你也可以包括哪些數據的通用數據工會控股，而其長度。

typedef struct 
{ 
    genericData data; 
    int dataType; // 0 == int, 1 == double, 2 == etc. 
    int dataLength; // Number of elements in array 
} genericDataType;