¿Un buen C equivalente al vector STL?

Question

He notado que en varios lugares de nuestra base de código utilizamos matrices que se expanden dinámicamente, es decir, una matriz base unida a un contador de elementos y un valor de "elementos máximos".

Lo que quiero hacer es reemplazarlos con una estructura de datos común y funciones de utilidad, por los motivos habituales orientados a objetos. Los elementos de la matriz pueden ser tipos de datos básicos o estructuras, necesito un acceso aleatorio rápido a los elementos y, preferiblemente, una implementación segura para tipos.

Así que, básicamente, lo que me gustaría utilizar es un vector de STL, pero el código base está restringido a C89, así que tengo que llegar a algo más :-)

lo di un poco de pensamiento y de batida este proyecto inicial, sólo para mostrar lo que estoy destinado a:

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

... sin embargo, tiene que haber alguien que ha hecho esto antes. Soy consciente de la implementación de FreeBSD sys/queue.h de un concepto similar para algunas colas diferentes, pero no puedo encontrar nada parecido para las matrices.

¿Hay alguien aquí más sabio?

Answer 1

glib proporciona un tipo GArray, que implementa una matriz de crecimiento dinámico. Si puede utilizar bibliotecas externas de terceros, glib es casi siempre una buena opción como biblioteca "estándar" para C. Proporciona tipos para todas las estructuras de datos básicas, para cadenas de Unicode, para valores de fecha y hora, y así sucesivamente.

Answer 2

Hay sglib, que implementa varias listas, hashmaps y rbtrees de forma genérica (es decir, especializándose sobre un tipo). También hay una función de clasificación rápida de las matrices:

• http://sglib.sourceforge.net/

Answer 3

aquí un simple vector de reemplazo, su función de uno para todos, su estricta C89 y multi-hilo; libs son demasiado difíciles para mí, yo uso las mías; ningún rendimiento, pero fácil de usar

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

generalmente ruedo mi propio código para fines tales como este, igual que lo hizo. No es particularmente difícil, pero tener seguridad de tipo, etc. no es fácil de lograr sin un marco completo de OO.

Como se mencionó anteriormente, glib ofrece lo que necesita: si glib2 es demasiado grande para usted, podría seguir con glib1.2. Es bastante antiguo, pero no tiene dependencias externas (a excepción de pthread si necesita soporte de subprocesos). El código también se puede integrar en proyectos más grandes, si es necesario. Está licenciado por LGPL.

Answer 5

qLibc implementa un vector en C. puro La estructura de datos le permite almacenar cualquier tipo de objeto como (objeto void *) y proporciona envoltorios convenientes para cadenas, cadenas formateadas y tipos enteros.

Aquí hay un código de muestra para su idea.

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

para el tipo de objeto:

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

Nota) Hice este código de ejemplo sólo para su referencia, la copia de su código de ejemplo. podría tener errores tipográficos.

Se puede extraer de la referencia de la API completa en http://wolkykim.github.io/qlibc/

Answer 6

estoy usando la siguiente implementación macro sin problemas hasta ahora. No es una aplicación completa, pero crece la matriz de forma automática:

#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; \ 
    } 

usarte primera escritura: DECLARE_DYN_ARRAY(YourType)

para declarar variables que escribe DYN_ARRAY(YourType) array = {0}.

Agregue elementos con DYN_ADD(array, element, errorLabel).

Tiene acceso a elementos con array.buf[i].

Obtiene la cantidad de elementos con array.n.

Cuando se hace que liberarla con free(array.buf) (o lo que sea la función que utilizó para asignarlo.)