Хороший 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 и поточно; libs слишком сложны для меня, я использую свои собственные; не производительность, но простой в использовании

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

Я обычно ролл мой собственный код для таких целей, как это, как вы это сделали. Это не особенно сложно, но безопасность типа и т. Д. Нелегко достижимо без целого каркаса OO.

Как уже упоминалось ранее, glib предлагает то, что вам нужно - если glib2 слишком большой для вас, вы все равно можете пойти с glib1.2. Он довольно старый, но не имеет внешних зависимостей (кроме pthread, если вам нужна поддержка потоков). При необходимости код может быть интегрирован в более крупные проекты. Это лицензия LGPL.

Answer 5

qLibc реализует вектор в чистом C. Структура данных позволяет хранить любой тип объекта, например (объект void *), и предоставляет удобные оболочки для строковых, форматированных строк и целых типов.

Вот пример кода для вашей идеи.

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

Примечание) Я сделал этот образец кода только для справки, копируя из своего примера кода. у него могут быть ошибки опечатки.

Вы можете проверить полную ссылку API на http://wolkykim.github.io/qlibc/

Answer 6

Я использую следующий макрос реализации без проблем до сих пор. Это не полная реализация, но автоматически растет массив:

#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) (или любой другой функции вы использовали, чтобы выделить его.)