20

我注意到在我们的代码库中的几个地方，我们使用动态扩展数组，即一个基本数组加上一个元素计数器和一个“最大元素”值。

出于通常的面向对象的原因，我想做的是用通用的数据结构和实用程序函数替换它们。数组元素可以是基本数据类型或结构，我需要快速随机访问元素，最好是类型安全的实现。

所以，基本上，我想使用的是 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 实现了一些不同队列的类似概念，但我找不到类似的数组。

这里有人更聪明吗？

4

7 回答 7

10

glib 提供了一个GArray类型，它实现了一个动态增长的数组。如果您可以使用外部 3rd 方库，glib 作为 C 的“标准”库几乎总是一个不错的选择。它为所有基本数据结构、unicode 字符串、日期和时间值等提供类型。

于 2010-08-11T08:30:31.717 回答
4

这里是一个简单的向量替换，它的 ONE 函数，它严格的 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;
}
于 2010-08-11T22:54:44.783 回答
3

有 sglib，它以一种通用的方式实现了各种列表、hashmap 和 rbtree（即通过专门化一个类型）。数组还有一个快速排序功能：

于 2010-08-11T08:30:45.007 回答
2

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/查看完整的 API 参考

于 2014-03-29T03:34:58.077 回答
2

到目前为止，我正在使用以下宏实现没有问题。它不是一个完整的实现，但会自动增长数组：

#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)（或您用来分配它的任何功能）释放它。

于 2015-05-10T07:51:08.910 回答
1

我通常像你一样为这样的目的滚动我自己的代码。这并不是特别困难，但是如果没有整个 OO 框架，就不容易实现类型安全等。

如前所述，glib 提供了您所需要的——如果 glib2 对您来说太大了，您仍然可以使用 glib1.2。它很旧，但没有外部依赖项（如果您需要线程支持，pthread 除外）。如有必要，代码也可以集成到更大的项目中。它是 LGPL 许可的。

于 2011-04-21T15:20:06.193 回答
0

就个人而言，我更喜欢“ Gena ”库。它与stl::vector纯C89非常相似。

使用起来很舒服，因为您可以：

  • 像普通 C 数组一样访问向量元素vec[k][j]：
  • 拥有多维数组；
  • 复制向量；
  • 在单独的模块中实例化必要的向量类型一次，而不是每次需要向量时都这样做；
  • 您可以选择如何将值传递给向量以及如何从向量中返回它们：按值或按指针。

你可以在这里查看：

https://github.com/cher-nov/Gena

于 2020-11-24T07:47:18.213 回答