一个与STL vector等效的好的C语言版本？

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实现了一些不同队列的类似概念，但是我找不到类似数组的东西。

这里有更明白的人吗？

- Christoffer

---

至少要么摆脱宏并用函数替换它们，要么修复它们以使其像函数一样工作。后者涉及使用 do { ... } while (0) 包装任何超过一个表达式/语句的宏。 - R.. GitHub STOP HELPING ICE

为什么我要摆脱宏？用函数替换它们会破坏类型独立性，这将不再是通用解决方案。另外，为什么我要用 do ... while 包装？这将使从类似函数的宏中返回值变得不可能。 - Christoffer

@christoffer：重新阅读R的评论。注意使用了“或” - 这些函数宏很糟糕，你应该像R所说的那样通过“修复”它们来改进它们。这使得使用函数宏不那么令人惊讶。我个人更喜欢函数宏大写，以确保质量。 - Arafangion

Answer 1

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

- user355252

---

好的建议，但我们不能使用任何第三方库（至少不是像glib这样的库那么大）。此外，GArray似乎不依赖于类型，它看起来可以将不同类型的对象存储在一个数组中，只要它们具有相同的大小 :-) （例如'int'和'float'）。 - Christoffer

通用的、但又类型安全的容器无法在C语言中实现。因为C的类型系统过于原始，不支持任何通用类型或模板。唯一通用的东西是空指针，但这并不是类型安全的。你必须要习惯于C语言只是一种弱类型语言的事实。 - user355252

通过一些技巧（例如类型转换和 typeof），可以实现相当可靠的类型安全性。然而，我同意在 C 中实现类型安全数据类型几乎是不可能的。 - yyny

Answer 2

这是一个简单的矢量替换函数，适用于所有情况，严格符合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;
}

- user411313

---

这是否考虑了打包和对齐问题？ - Arafangion

使用sizeof，忽略所有pack/align的最佳方法。 - user411313

主啊！在一次面试中，我被给予了这段代码，并被问到“这段代码是做什么用的？”请您帮忙翻译。 - Sam

Answer 3

有一个库叫做sglib，它以通用方式实现了各种列表、哈希映射和红黑树（即通过对类型进行特化来实现）。此外，还有一个用于数组的快速排序函数：

• http://sglib.sourceforge.net/

- Nordic Mainframe

---

好的建议，虽然它缺少我需要的特定数据类型 :-) - Christoffer

Answer 4

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参考文档。

- user3474832

Answer 5

我通常会自己编写代码来实现这样的目的，就像你所做的那样。这并不是特别困难，但是如果没有整个面向对象框架，很难实现类型安全等功能。

如前所述，glib提供了您需要的内容 - 如果glib2对您来说太大了，您仍然可以选择glib1.2。它相当古老，但没有外部依赖项（除非您需要线程支持的pthread）。如果必要，该代码也可以集成到更大的项目中。它是LGPL许可的。

- onitake

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)(或者你用于分配的任何其他函数)来释放它。

- Calmarius

---

很遗憾，这个实现不支持指针类型。 - yyny

Answer 7

个人而言，我更喜欢 "Gena" 库。它与纯 C89 中的 stl::vector 非常相似。

使用它非常方便，因为你可以：

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

你可以在这里查看：

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

- user7369463