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

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

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

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

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- gt data   malloc init capacity   sizeof int      if   v- gt data  return -1     v- gt size   0    v- gt 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

[c] How to replicate vector in c?

Examples related to c