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型を提供します。外部のサードパーティ ライブラリを使用できる場合、ほとんどの場合、C の「標準」ライブラリとして glib を選択することをお勧めします。glib は、すべての基本データ構造、Unicode 文字列、日付と時刻の値などの型を提供します。

于 2010-08-11T08:30:31.717 に答える
4

ここでは、単純なベクトル置換、すべてに対して 1 つの関数、厳密に 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

さまざまなリスト、ハッシュマップ、および rbtree を一般的な方法で (つまり、型を特殊化することによって) 実装する sglib があります。配列の高速ソート機能もあります。

于 2010-08-11T08:30:45.007 に答える
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 に答える
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);

注）このサンプルコードは、サンプルコードをコピーして参考用に作成しました。タイプミスがあるかもしれません。

完全な API リファレンスはhttp://wolkykim.github.io/qlibc/で確認できます。

于 2014-03-29T03:34:58.077 に答える
1

あなたがしたように、私は通常、このような目的のために独自のコードをロールバックします。特に難しいことではありませんが、オブジェクト指向フレームワーク全体がなければ、型安全性などを実現することは容易ではありません。

前に述べたように、glib は必要なものを提供します。glib2 が大きすぎる場合でも、glib1.2 を使用できます。これはかなり古いものですが、外部依存関係はありません (スレッドのサポートが必要な場合の pthread を除く)。必要に応じて、コードをより大きなプロジェクトに統合することもできます。LGPLライセンスです。

于 2011-04-21T15:20:06.193 に答える