Хороший C-эквивалент вектора STL? - PullRequest
Новая
       7

Хороший C-эквивалент вектора STL?

17 голосов
/ 11 августа 2010

Я заметил, что в нескольких местах в нашей кодовой базе мы используем динамически расширяемые массивы, то есть базовый массив в сочетании со счетчиком элементов и значением «max elements».

Что я хочу сделать, это заменить их на общую структуру данных и служебные функции по обычным объектно-ориентированным причинам. Элементы массива могут быть как базовыми типами данных, так и структурами, мне нужен быстрый произвольный доступ к элементам и, желательно, безопасная реализация.

Итак, в основном я хотел бы использовать вектор 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 для некоторых разных очередей, но я не могу найти ничего подобного для массивов.

Кто-нибудь здесь мудрее?

Ответы [ 6 ]

9 голосов
/ 11 августа 2010

glib предоставляет тип GArray , который реализует динамически растущий массив. Если вы можете использовать внешние сторонние библиотеки, glib почти всегда является хорошим выбором в качестве «стандартной» библиотеки для C. Он предоставляет типы для всех базовых структур данных, для строк Юникода, для значений даты и времени и т. Д.

3 голосов
/ 11 августа 2010

Существует sglib, который реализует различные списки, hashmaps и rbtrees в общем виде (т.е. специализируется на типе). Существует также функция быстрой сортировки массивов:

2 голосов
/ 29 марта 2014

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

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

Вы можете ознакомиться с полной ссылкой API на http://wolkykim.github.io/qlibc/

1 голос
/ 10 мая 2015

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

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

1 голос
/ 21 апреля 2011

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

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

1 голос
/ 12 августа 2010

здесь простая замена вектора, его ОДНА функция для всех, его строго C89 и threadsafe;мне слишком тяжело, я пользуюсь своим;нет производительности, но прост в использовании 

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