How to replicate vector in c

Question

In the days before c   and vector lists  how did they expand the size of arrays when they needed to store more data

User · Answer

A lot of C projects end up implementing a vector-like API. Dynamic arrays are such a common need, that it's nice to abstract away the memory management as much as possible. A typical C implementation might look something like:

typedef struct dynamic_array_struct
{
  int* data;
  size_t capacity; /* total capacity */
  size_t size; /* number of elements in vector */
} vector;

Then they would have various API function calls which operate on the vector:

int vector_init(vector* v, size_t init_capacity)
{
  v->data = malloc(init_capacity * sizeof(int));
  if (!v->data) return -1;

  v->size = 0;
  v->capacity = init_capacity;

  return 0; /* success */
}

Then of course, you need functions for push_back, insert, resize, etc, which would call realloc if size exceeds capacity.

vector_resize(vector* v, size_t new_size);

vector_push_back(vector* v, int element);

Usually, when a reallocation is needed, capacity is doubled to avoid reallocating all the time. This is usually the same strategy employed internally by std::vector, except typically std::vector won't call realloc because of C++ object construction/destruction. Rather, std::vector might allocate a new buffer, and then copy construct/move construct the objects (using placement new) into the new buffer.

An actual vector implementation in C might use void* pointers as elements rather than int, so the code is more generic. Anyway, this sort of thing is implemented in a lot of C projects. See http://codingrecipes.com/implementation-of-a-vector-data-structure-in-c for an example vector implementation in C.

User · Answer

You can use  quot Gena quot  library  It closely resembles stl  vector in pure C89  From the README  it features   Access vector elements just like plain C arrays  vec k  j   Have multi-dimentional arrays  Copy vectors  Instantiate necessary vector types once in a separate module  instead of doing this every time you needed a vector  You can choose how to pass values into a vector and how to return them from it  by value or by pointer   You can check it out here  https   github com cher-nov Gena

User · Answer

They would start by hiding the defining a structure that would hold members necessary for the implementation   Then providing a group of functions that would manipulate the contents of the structure   Something like this   typedef struct vec       unsigned char   mem      unsigned long  elems      unsigned long  elemsize      unsigned long  capelems      unsigned long  reserve      vec  vec new unsigned long elemsize        vec  pvec    vec  malloc sizeof vec        pvec- gt  reserve   10      pvec- gt  capelems   pvec- gt  reserve      pvec- gt  elemsize   elemsize      pvec- gt  elems   0      pvec- gt  mem    unsigned char  malloc pvec- gt  capelems   pvec- gt  elemsize       return pvec     void vec delete vec  pvec        free pvec- gt  mem       free pvec      void vec grow vec  pvec        unsigned char  mem    unsigned char  malloc  pvec- gt  capelems   pvec- gt  reserve    pvec- gt  elemsize       memcpy mem  pvec- gt  mem  pvec- gt  elems   pvec- gt  elemsize       free pvec- gt  mem       pvec- gt  mem   mem      pvec- gt  capelems    pvec- gt  reserve     void vec push back vec  pvec  void  data  unsigned long elemsize        assert elemsize    pvec- gt  elemsize       if  pvec- gt  elems    pvec- gt  capelems            vec grow pvec             memcpy pvec- gt  mem    pvec- gt  elems   pvec- gt  elemsize    unsigned char  data  pvec- gt  elemsize       pvec- gt  elems           unsigned long vec length vec  pvec        return pvec- gt  elems     void  vec get vec  pvec  unsigned long index        assert index  lt  pvec- gt  elems       return  void   pvec- gt  mem    index   pvec- gt  elemsize       void vec copy item vec  pvec  void  dest  unsigned long index        memcpy dest  vec get pvec  index   pvec- gt  elemsize      void playwithvec         vec  pvec   vec new sizeof int         for  int val   0  val  lt  1000  val    10            vec push back pvec   amp val  sizeof val               for  unsigned long index    int vec length pvec  - 1   int index  gt   0  index--            int val          vec copy item pvec   amp val  index           printf  vec  d     d n   index  val              vec delete pvec       Further to this they would achieve encapsulation by using void  in the place of vec  for the function group  and actually hide the structure definition from the user by defining it within the C module containing the group of functions rather than the header   Also they would hide the functions that you would consider to be private  by leaving them out from the header and simply prototyping them only in the C module

User · Answer

You can see implementation vc vector   struct vc vector     size t count    size t element size    size t reserved size    char  data    vc vector deleter  deleter           vc vector  vc vector create copy const vc vector  vector      vc vector  new vector   vc vector create vector- gt reserved size   vector- gt count                                             vector- gt element size                                             vector- gt deleter     if  unlikely  new vector         return new vector         if  memcpy vector- gt data               new vector- gt data               new vector- gt element size   vector- gt count     NULL        vc vector release new vector       new vector   NULL      return new vector         new vector- gt count   vector- gt count    return new vector      To use it   vc vector  v1   vc vector create 0  sizeof int   NULL   for  int i   0  i  lt  10    i      vc vector push back v1   amp i         v1   0 1 2 3 4 5 6 7 8 9  vc vector  v2   vc vector create copy v1       v2   0 1 2 3 4 5 6 7 8 9  copy of v1      to get pointer to int   const int  v2 data   vc vector data v1

User · Answer

Vector and list aren t conceptually tied to C    Similar structures can be implemented in C  just the syntax  and error handling  would look different  For example LodePNG implements a dynamic array with functionality very similar to that of std  vector  A sample usage looks like  uivector v       uivector push back  amp v  1   uivector push back  amp v  42   for size t i   0  i  lt  v size    i      printf  quot  d n quot   v data i    uivector cleanup  amp v    As can be seen the usage is somewhat verbose and the code needs to be duplicated to support different types  nothings stb gives a simpler implementation that works with any types  but compiles only in C  double  v   0  sb push v  1 0   sb push v  42 0   for int i   0  i  lt  sb count v     i      printf  quot  g n quot   v i    sb free v     A lot of C code  however  resorts to managing the memory directly with realloc  void  newMem   realloc oldMem  newSize   if  newMem           handle error   oldMem   newMem   Note that realloc returns null in case of failure  yet the old memory is still valid  In such situation this common  and incorrect  usage leaks memory  oldMem   realloc oldMem  newSize   if  oldMem           handle error    Compared to std  vector and the C equivalents from above  the simple realloc method does not provide O 1  amortized guarantee  even though realloc may sometimes be more efficient if it happens to avoid moving the memory around

User · Answer

https   github com jakubgorny47 baku-code tree master c vector  Here s my implementation  It s basicaly a struct containing pointer to the data  size  in elements   overall allocated space and a size of the type that s being stored in vector to allow use of void pointer

[c] How to replicate vector in c?

Examples related to c