Ein gutes C-Äquivalent von STL-Vektor?

Question

Ich habe festgestellt, dass wir an mehreren Stellen in unserer Codebasis dynamisch expandierende Arrays verwenden, d. H. Ein Basis-Array gekoppelt mit einem Element-Zähler und einem "Max-Elemente" -Wert.

Was ich tun möchte, ist diese für die üblichen objektorientierten Gründe durch eine gemeinsame Datenstruktur und Dienstprogrammfunktionen zu ersetzen. Die Array-Elemente können entweder grundlegende Datentypen oder Strukturen sein, ich brauche schnellen wahlfreien Zugriff auf die Elemente und vorzugsweise eine typsichere Implementierung.

Also, im Grunde, verwenden, was ich möchte, ist ein STL-Vektor, aber der Code-Basis C89 beschränkt ist, so muss ich etwas anderes :-) kommen

ich es einige Gedanken gab und Schlag nur auf diesen ursprünglichen Entwurf, um zu zeigen, was auf das ich bin mit dem Ziel:

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

... aber es jemand sein muss, sonst, die zuvor getan hat. Ich kenne die FreeBSD sys/queue.h-Implementierung eines ähnlichen Konzepts für einige verschiedene Warteschlangen, aber ich kann nichts Ähnliches für Arrays finden.

Ist hier jemand weiser?

Answer 1

glib stellt einen GArray-Typ bereit, der ein dynamisch wachsendes Array implementiert. Wenn Sie externe Bibliotheken von Drittanbietern verwenden können, ist glib fast immer eine gute Wahl als "Standard" -Bibliothek für C. Sie stellt Typen für alle grundlegenden Datenstrukturen, für Unicode-Zeichenfolgen, für Datums- und Uhrzeitwerte usw. bereit.

Answer 2

Es gibt sglib, das verschiedene Listen, hashmaps und rbtrees in generischer Weise implementiert (d. H. Durch Spezialisierung auf einen Typ). Es gibt auch eine schnelle Sortierfunktion für Arrays:

• http://sglib.sourceforge.net/

Answer 3

hier eine einfache Vektor-Ersatz, dessen eine Funktion für alle, seine streng C89 und THREAD; libs sind zu schwierig für mich, ich benutze mein eigenes; keine Leistung, sondern einfach

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

ich meinen eigenen Code für Zwecke wie dies in der Regel zu verwenden, rollen, wie Sie haben. Es ist nicht besonders schwierig, aber Typsicherheit usw. ist ohne ein vollständiges OO-Framework nicht leicht zu erreichen.

Wie bereits erwähnt, bietet glib, was Sie brauchen - wenn glib2 zu groß für Sie ist, können Sie immer noch mit glib1.2 gehen. Es ist ziemlich alt, hat aber keine externen Abhängigkeiten (außer pthread, wenn Sie Thread-Unterstützung benötigen). Der Code kann bei Bedarf auch in größere Projekte integriert werden. Es ist LGPL lizenziert.

Answer 5

qLibc implementiert einen Vektor in reinem C. Die Datenstruktur ermöglicht es, jede Art von Objekt wie (void * object) zu speichern und es bietet praktische Wrapper für String, formatierten String und Integer-Typen.

Hier ist ein Beispielcode für Ihre Idee.

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

für Objekttyp:

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

Hinweis) Ich habe diesen Beispielcode nur für Ihre Referenz, das Kopieren von seinem Beispielcode. könnte es Tippfehler haben.

Sie können bisher ohne Probleme

Answer 6

Ich verwende den folgenden Makro Implementierung bei http://wolkykim.github.io/qlibc/ die Full-API-Referenz überprüfen. Es ist nicht eine vollständige Implementierung, sondern wächst das Array automatisch:

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

Ihnen ersten Schreib benutzen: DECLARE_DYN_ARRAY(YourType)

Variablen Sie DYN_ARRAY(YourType) array = {0} schreiben zu erklären.

Sie fügen Elemente mit DYN_ADD(array, element, errorLabel) hinzu.

Sie greifen auf Elemente mit array.buf[i] zu.

Sie erhalten die Anzahl der Elemente mit array.n.

Wenn Sie mit free(array.buf) befreien es getan (oder was auch immer Funktion Sie es zuzuordnen.)