一個好的C等效STL向量？

Question

我注意到，在我們的代碼庫的幾個地方，我們使用動態擴展數組，即一個基本數組與一個元素計數器和一個「最大元素」值。

我想要做的就是用通用的數據結構和實用程序函數替換這些通用的面向對象的原因。 數組元素可以是基本數據類型或結構體，我需要對元素進行快速隨機訪問，最好是類型安全的實現。

所以，基本上，我想用是一個STL向量，但代碼庫被限制爲C89，所以我必須想出別的東西:-)

我給它一些思考和鞭打只是爲了展示我的目標：

/* Type-safe dynamic list in C89 */ 

#define list_declare(type) typedef struct _##type##_list_t { type * base_array; size_t elements; size_t max_size; } type##_list_t 
#define list(type) type##_list_t 
#define list_new(type, initial_size) { calloc(initial_size, sizeof(type)), 0, initial_size } 
#define list_free(list) free(list.base_array) 
#define list_set(list, place, element) if (list.elements < list.max_size) { list.base_array[place] = element; } else { /* Array index out of bounds */ } 
#define list_add(list, element) if (list.elements < list.max_size) { list.base_array[list.elements++] = element; } else { /* Expand array then add */ } 
#define list_get(list, n) list.base_array[n] 

/* Sample usage: */ 

list_declare(int); 

int main(void) 
{ 
    list(int) integers = list_new(int, 10); 
    printf("list[0] = %d\n", list_get(integers, 0)); 
    list_add(integers, 4); 
    printf("list[0] = %d\n", list_get(integers, 0)); 
    list_set(integers, 0, 3); 
    printf("list[0] = %d\n", list_get(integers, 0)); 
    list_free(integers); 

    return EXIT_SUCCESS; 
} 

...但是，必須有其他人誰做了這個之前。我知道FreeBSD sys/queue.h對於一些不同隊列的類似概念的實現，但我找不到像這樣的陣列。

有沒有人在這裏任何明智？

Answer 1

glib提供GArray類型，它實現了一個動態增長的數組。如果您可以使用外部第三方庫，那麼glib幾乎總是作爲C的「標準」庫的不錯選擇。它爲所有基本數據結構，unicode字符串，日期和時間值等提供類型。

Answer 2

有sglib，它以通用的方式實現各種列表，hashmaps和rbtrees（即通過專門化一種類型）。還有數組快速排序功能：

• http://sglib.sourceforge.net/

Answer 3

這裏一個簡單的載體替代，其功能之一爲人人，其嚴格C89和線程; 庫存對我來說太難了，我用我自己的; 沒有表現，但易於使用

/* owner-structs too */ 
typedef struct { 
    char name[20],city[20]; 
    int salary; 
} My,*Myp; 

typedef char Str80[80]; 

/* add here your type with its size */ 
typedef enum {SPTR,INT=sizeof(int),DOUBLE=sizeof(double),S80=sizeof(Str80),MY=sizeof(My)} TSizes; 

typedef enum {ADD,LOOP,COUNT,FREE,GETAT,GET,REMOVEAT,REMOVE} Ops; 

void *dynarray(char ***root,TSizes ts,Ops op,void *in,void *out) 
{ 
    size_t d=0,s=in?ts?ts:strlen((char*)in)+1:0; 
    char **r=*root; 
    while(r && *r++) ++d; 
    switch(op) { 
    case ADD: if(!*root) *root=calloc(1,sizeof r); 
       *root=realloc(*root,(d+2)*sizeof r); 
       memmove((*root)+1,*root,(d+1)*sizeof r); 
       memcpy(**root=malloc(s),in,s); 
       break; 
    case LOOP: while(d--) ((void (*)(char*))in)((*root)[d]); break; 
    case COUNT: return *(int*)out=d,out; 
    case FREE: if(r) { 
       ++d; while(d--) realloc((*root)[d],0); 
       free(*root);*root=0; 
       } break; 
    case GETAT: { size_t i=*(size_t*)in; 
       if(r && i<=--d) 
        return (*root)[d-i]; 
       } break; 
    case GET: { int i=-1; 
       while(++i,d--) 
       if(!(ts?memcmp:strncmp)(in,(*root)[d],s)) 
        return *(int*)out=i,out; 
       return *(int*)out=-1,out; 
       } 
    case REMOVEAT: { size_t i=*(size_t*)in; 
        if(r && i<=--d) { 
        free((*root)[d-i]); 
        memmove(&(*root)[d-i],&(*root)[d-i+1],(d-i+1)*sizeof r); 
        return in; 
        } 
       } break; 
    case REMOVE: while(*(int*)dynarray(root,ts,GET,in,&d)>=0) 
       dynarray(root,ts,REMOVEAT,&d,0); 
    } 
    return 0; 
} 

void outmy(Myp s) 
{ 
    printf("\n%s,%s,%d",s->name,s->city,s->salary); 
} 

main() 
{ 
    My z[]={{"Buffet","Omaha",INT_MAX},{"Jobs","Palo Alto",1},{"Madoff","NYC",INT_MIN}}; 
    Str80 y[]={ "123","456","7890" }; 
    char **ptr=0; 
    int x=1; 

    /* precondition for first use: ptr==NULL */ 
    dynarray(&ptr,SPTR,ADD,"test1.txt",0); 
    dynarray(&ptr,SPTR,ADD,"test2.txt",0); 
    dynarray(&ptr,SPTR,ADD,"t3.txt",0); 

    dynarray(&ptr,SPTR,REMOVEAT,&x,0); /* remove at index/key ==1 */ 
    dynarray(&ptr,SPTR,REMOVE,"test1.txt",0); 

    dynarray(&ptr,SPTR,GET,"t3.txt",&x); 
    dynarray(&ptr,SPTR,LOOP,puts,0); 

    /* another option for enumerating */ 
    dynarray(&ptr,SPTR,COUNT,0,&x); 
    while(x--) 
     puts(ptr[x]); 
    dynarray(&ptr,SPTR,FREE,0,0); /* frees all mallocs and set ptr to NULL */ 

    /* start for another (user)type */ 
    dynarray(&ptr,S80,ADD,y[0],0); 
    dynarray(&ptr,S80,ADD,y[1],0); 
    dynarray(&ptr,S80,ADD,y[2],0); 
    dynarray(&ptr,S80,ADD,y[0],0); 
    dynarray(&ptr,S80,LOOP,puts,0); 
    dynarray(&ptr,S80,FREE,0,0); /* frees all mallocs and set ptr to NULL */ 

    /* start for another (user)struct-type */ 
    dynarray(&ptr,MY,ADD,&z[0],0); 
    dynarray(&ptr,MY,ADD,&z[1],0); 
    dynarray(&ptr,MY,ADD,&z[2],0); 
    dynarray(&ptr,MY,ADD,&z[0],0); 
    dynarray(&ptr,MY,LOOP,outmy,0); 
    dynarray(&ptr,MY,FREE,0,0); 

    return 0; 
} 

Answer 4

我通常推出自己的代碼，用於諸如這樣，像你這樣。這並不是特別困難，但是如果沒有整個面向對象的框架，就不能實現類型安全等。如前所述，glib提供了你所需要的 - 如果glib2對你來說太大，你仍然可以使用glib1.2。這是相當古老的，但沒有外部依賴（除了pthread，如果你需要線程支持）。如有必要，代碼也可以集成到更大的項目中。這是LGPL許可。

Answer 5

qLibc在純C中實現了一個向量。數據結構允許它存儲任何類型的對象（void * object），它爲字符串，格式化的字符串和整數類型提供了方便的包裝。

下面是您的想法的示例代碼。

qvector_t *vector = qvector(QVECTOR_OPT_THREADSAFE); 
vector->addstr(vector, "Hello"); 
vector->addstrf(vector, "World %d", 123); 
char *finalstring = vector->tostring(vector); 

printf("%s", finalstring); 
free(finalstring) 
vector->free(vector); 

對象類型：

int a = 1, b = 2; 
qvector_t *vector = qvector(QVECTOR_OPT_THREADSAFE); 
vector->add(vector, (void *)&a, sizeof(int)); 
vector->add(vector, (void *)&b, sizeof(int)); 
int *finalarray = vector->toarray(vector); 

printf("a = %d, b = %d", finalarray[0], finalarray[1]); 
free(finalarray) 
vector->free(vector); 

注）我做了這個示例代碼僅供參考，其示例代碼複製。 它可能有拼寫錯誤。

可以毫無問題檢查出在http://wolkykim.github.io/qlibc/

Answer 6

我使用下面的宏實現完整的API參考爲止。這是不是一個完整的實現，但自動增長的數組：

#define DECLARE_DYN_ARRAY(T) \ 
    typedef struct \ 
    { \ 
     T *buf; \ 
     size_t n; \ 
     size_t reserved; \ 
    } T ## Array; 

#define DYN_ARRAY(T) T ## Array 

#define DYN_ADD(array, value, errorLabel) DYN_ADD_REALLOC(array, value, errorLabel, realloc) 

#define DYN_ADD_REALLOC(array, value, errorLabel, realloc) \ 
    { \ 
     if ((array).n >= (array).reserved) \ 
     { \ 
      if (!(array).reserved) (array).reserved = 10; \ 
      (array).reserved *= 2; \ 
      void *ptr = realloc((array).buf, sizeof(*(array).buf)*(array).reserved); \ 
      if (!ptr) goto errorLabel; \ 
      (array).buf = ptr; \ 
     } \ 
     (array).buf[(array).n++] = value; \ 
    } 

要使用你第一次寫：DECLARE_DYN_ARRAY(YourType)

要聲明你寫DYN_ARRAY(YourType) array = {0}變量。

添加元素DYN_ADD(array, element, errorLabel)。

您使用array.buf[i]訪問元素。

您得到的元素數量爲array.n。

完成後你free(array.buf)釋放它（或任何功能，您用來分配它。）