C dynamically growing array

Question

I have a program that reads a  raw  list of in-game entities  and I intend to make an array holding an index number  int  of an indeterminate number of entities  for processing various things  I would like to avoid using too much memory or CPU for keeping such indexes     A quick and dirty solution I use so far is to declare  in the main processing function  local focus  the array with a size of the maximum game entities  and another integer to keep track of how many have been added to the list  This isn t satisfactory  as every list holds 3000  arrays  which isn t that much  but feels like a waste  since I ll possible use the solution for 6-7 lists for varying functions   I haven t found any C  not C   or C   specific solutions to achieve this  I can use pointers  but I am a bit afraid of using them  unless it s the only possible way    The arrays do not leave the local function scope  they are to be passed to a function  then discarded   in case that changes things   If pointers are the only solution  how can I keep track of them to avoid leaks

User · Answer

These posts apparently are in the wrong order! This is #1 in a series of 3 posts. Sorry.

In attempting to use Lie Ryan's code, I had problems retrieving stored information. The vector's elements are not stored contiguously,as you can see by "cheating" a bit and storing the pointer to each element's address (which of course defeats the purpose of the dynamic array concept) and examining them.

With a bit of tinkering, via:

ss_vector* vector; // pull this out to be a global vector

// Then add the following to attempt to recover stored values.

int return_id_value(int i,apple* aa) // given ptr to component,return data item
{   printf("showing apple[%i].id = %i and  other_id=%i\n",i,aa->id,aa->other_id);
    return(aa->id);
}

int Test(void)  // Used to be "main" in the example
{   apple* aa[10]; // stored array element addresses
    vector = ss_init_vector(sizeof(apple));
    // inserting some items
    for (int i = 0; i < 10; i++)
    {   aa[i]=init_apple(i);
        printf("apple id=%i and  other_id=%i\n",aa[i]->id,aa[i]->other_id);
        ss_vector_append(vector, aa[i]);
     }   
 // report the number of components
 printf("nmbr of components in vector = %i\n",(int)vector->size);
 printf(".*.*array access.*.component[5] = %i\n",return_id_value(5,aa[5]));
 printf("components of size %i\n",(int)sizeof(apple));
 printf("\n....pointer initial access...component[0] = %i\n",return_id_value(0,(apple *)&vector[0]));
 //.............etc..., followed by
 for (int i = 0; i < 10; i++)
 {   printf("apple[%i].id = %i at address %i, delta=%i\n",i,    return_id_value(i,aa[i]) ,(int)aa[i],(int)(aa[i]-aa[i+1]));
 }   
// don't forget to free it
ss_vector_free(vector);
return 0;
}

It's possible to access each array element without problems, as long as you know its address, so I guess I'll try adding a "next" element and use this as a linked list. Surely there are better options, though. Please advise.

User · Answer

Building on Matteo Furlans design  when he said  most dynamic array implementations work by starting off with an array of some  small  default size  then whenever you run out of space when adding a new element  double the size of the array   The difference in the  work in progress  below is that it doesn t double in size  it aims at using only what is required  I have also omitted safety checks for simplicity   Also building on brimboriums idea  I have tried to add a delete function to the code     The storage h file looks like this      ifndef STORAGE H  define STORAGE H   ifdef   cplusplus extern  C     endif      typedef struct                int  array          size t size        Array       void Array Init Array  array       void Array Add Array  array  int item       void Array Delete Array  array  int index       void Array Free Array  array     ifdef   cplusplus    endif   endif    STORAGE H      The storage c file looks like this      include  lt stdio h gt   include  lt stdlib h gt   include  storage h      Initialise an empty array    void Array Init Array  array         int  int pointer       int pointer    int   malloc sizeof int         if  int pointer    NULL                       printf  Unable to allocate memory  exiting  n            free int pointer           exit 0             else               array- gt array   int pointer           array- gt size   0              Dynamically add to end of an array    void Array Add Array  array  int item         int  int pointer       array- gt size    1       int pointer    int   realloc array- gt array  array- gt size   sizeof int         if  int pointer    NULL                       printf  Unable to reallocate memory  exiting  n            free int pointer           exit 0             else               array- gt array   int pointer          array- gt array array- gt size-1    item              Delete from a dynamic array    void Array Delete Array  array  int index         int i      Array temp      int  int pointer       Array Init  amp temp        for i index  i lt array- gt size  i                  array- gt array i    array- gt array i   1              array- gt size -  1       for  i   0  i  lt  array- gt size  i                  Array Add  amp temp  array- gt array i               int pointer    int   realloc temp array  temp size   sizeof int         if  int pointer    NULL                       printf  Unable to reallocate memory  exiting  n            free int pointer           exit 0             else               array- gt array   int pointer                Free an array    void Array Free Array  array       free array- gt array     array- gt array   NULL    array- gt size   0        The main c looks like this      include  lt stdio h gt   include  lt stdlib h gt   include  storage h   int main int argc  char   argv         Array pointers      int i       Array Init  amp pointers        for  i   0  i  lt  60  i                  Array Add  amp pointers  i                      Array Delete  amp pointers  3        Array Delete  amp pointers  6        Array Delete  amp pointers  30        for  i   0  i  lt  pointers size  i                          printf  Value   d Size  d  n   pointers array i   pointers size              Array Free  amp pointers        return  EXIT SUCCESS       Look forward to the constructive criticism to follow

User · Answer

To create an array of unlimited items of any sort of type   typedef struct STRUCT SS VECTOR       size t size      void   items    ss vector    ss vector  ss init vector size t item size        ss vector  vector      vector   malloc sizeof ss vector        vector- gt size   0      vector- gt items   calloc 0  item size        return vector     void ss vector append ss vector  vec  void  item        vec- gt size        vec- gt items   realloc vec- gt items  vec- gt size   sizeof item        vec- gt items vec- gt size - 1    item      void ss vector free ss vector  vec        for  int i   0  i  lt  vec- gt size  i            free vec- gt items i         free vec- gt items       free vec       and how to use it      defining some sort of struct  can be anything really typedef struct APPLE STRUCT       int id    apple   apple  init apple int id        apple  a      a   malloc sizeof apple        a- gt  id   id      return a       int main int argc  char  argv          ss vector  vector   ss init vector sizeof apple            inserting some items     for  int i   0  i  lt  10  i            ss vector append vector  init apple i             dont forget to free it     ss vector free vector        return 0      This vector array can hold any type of item and it is completely dynamic in size

User · Answer

I can use pointers  but I am a bit afraid of using them   If you need a dynamic array  you can t escape pointers  Why are you afraid though  They won t bite  as long as you re careful  that is   There s no built-in dynamic array in C  you ll just have to write one yourself  In C    you can use the built-in std  vector class  C  and just about every other high-level language also have some similar class that manages dynamic arrays for you  If you do plan to write your own  here s something to get you started  most dynamic array implementations work by starting off with an array of some  small  default size  then whenever you run out of space when adding a new element  double the size of the array  As you can see in the example below  it s not very difficult at all   I ve omitted safety checks for brevity  typedef struct     int  array    size t used    size t size    Array   void initArray Array  a  size t initialSize      a- gt array   malloc initialSize   sizeof int      a- gt used   0    a- gt size   initialSize     void insertArray Array  a  int element         a- gt used is the number of used entries  because a- gt array a- gt used    updates a- gt used only  after  the array has been accessed       Therefore a- gt used can go up to a- gt size    if  a- gt used    a- gt size        a- gt size    2      a- gt array   realloc a- gt array  a- gt size   sizeof int          a- gt array a- gt used      element     void freeArray Array  a      free a- gt array     a- gt array   NULL    a- gt used   a- gt size   0     Using it is just as simple  Array a  int i   initArray  amp a  5       initially 5 elements for  i   0  i  lt  100  i      insertArray  amp a  i       automatically resizes as necessary printf  quot  d n quot   a array 9        print 10th element printf  quot  d n quot   a used       print number of elements freeArray  amp a

User · Answer

There are a couple of options I can think of    Linked List  You can use a linked list to make a dynamically growing array like thing  But you won t be able to do array 100  without having to walk through 1-99 first  And it might not be that handy for you to use either  Large array  Simply create an array with more than enough space for everything Resizing array  Recreate the array once you know the size and or create a new array every time you run out of space with some margin and copy all the data to the new array  Linked List Array combination  Simply use an array with a fixed size and once you run out of space  create a new array and link to that  it would be wise to keep track of the array and the link to the next array in a struct     It is hard to say what option would be best in your situation  Simply creating a large array is ofcourse one of the easiest solutions and shouldn t give you much problems unless it s really large

User · Answer

These posts may be in the wrong order  This is  2 in a series of 3 posts  Sorry  I ve  quot taken a few liberties quot  with Lie Ryan s code  implementing a linked list so individual elements of his vector can be accessed via a linked list  This allows access  but admittedly it is time-consuming to access individual elements due to search overhead  i e  walking down the list until you find the right element  I ll cure this by maintaining an address vector containing subscripts 0 through whatever paired with memory addresses  This is still not as efficient as a plain-and-simple array would be  but at least you don t have to  quot walk the list quot  searching for the proper item         Based on code from https   stackoverflow com questions 3536153 c-dynamically-growing-array typedef struct STRUCT SS VECTOR     size t size       of vector elements     void   items     makes up one vector element s component contents     int subscript     this element s subscript nmbr  0 thru whatever     struct STRUCT SS VECTOR  this element     linked list via this ptr     struct STRUCT SS VECTOR  next element     and next ptr   ss vector   ss vector  vector     ptr to vector of components  ss vector  ss init vector size t item size     item size is size of one array member     vector  malloc sizeof ss vector         vector- gt this element   vector       vector- gt size   0     initialize count of vector component elements     vector- gt items   calloc 1  item size      allocate  amp  zero out memory for one linked list element     vector- gt subscript 0      vector- gt next element NULL              If there s an array of element addresses subscripts  install it now      return vector- gt this element     ss vector  ss vector append ss vector  vec element                  int i                                                                                --ptr to this element   --element nmbr     ss vector  local vec element 0         If there is already a next element  recurse to end-of-linked-list     if vec element- gt next element   size t 0           local vec element  ss vector append vec element- gt next element i      recurse to end of list         return local vec element               vec element is NULL  so make a new element and add at end of list     local vec element  calloc 1 sizeof ss vector       memory for one component     local vec element- gt this element local vec element     save the address     local vec element- gt next element 0      vec element- gt next element local vec element- gt this element      local vec element- gt subscript i    vec element- gt size       local vec element- gt size i     increment   of vector components             If there s an array of element addresses subscripts  update it now      return local vec element     void ss vector free one element int i gboolean Update subscripts          Walk the entire linked list to the specified element  patch up              the element ptrs before next  then free its contents  then free it              Walk the rest of the list  updating subscripts  if requested              If there s an array of element addresses subscripts  shift it along the way      ss vector  vec element      struct STRUCT SS VECTOR  this one      struct STRUCT SS VECTOR  next one      vec element vector      while  vec element- gt this element- gt subscript  i  amp  amp  vec element- gt next element   size t  0      skip         this one vec element- gt this element     trailing ptr         next one vec element- gt next element     will become current ptr         vec element next one                now at either target element or end-of-list     if vec element- gt this element- gt subscript  i          printf  quot vector element not found n quot   return          free this one     this one- gt next element next one- gt next element    previous element points to element after current one     printf  quot freeing element  i  at  lu quot  next one- gt subscript  size t next one       printf  quot  between  lu and  lu n quot   size t this one  size t next one- gt next element       vec element next one- gt next element       free next one      free the current element        renumber if requested     if Update subscripts          i 0          vec element vector          while vec element   size t  0              vec element- gt subscript i              i                vec element vec element- gt next element                               If there s an array of element addresses subscripts  update it now         Check  temporarily show the new list     vec element vector      while vec element   size t  0          printf  quot    remaining element  i  at  lu n quot  vec element- gt subscript  size t vec element- gt this element           vec element vec element- gt next element               return       void ss vector free one element    void ss vector insert one element ss vector  vec element int place          Walk the entire linked list to specified element  quot place quot   patch up              the element ptrs before next  then calloc an element and store its contents at  quot place quot               Increment all the following subscripts              If there s an array of element addresses subscripts  make a bigger one               copy the old one  then shift appropriate members            Not yet implemented         void ss vector insert one element    void ss vector free all elements void          Start at  quot vector quot  Walk the entire linked list  free each element s contents               free that element  then move to the next one              If there s an array of element addresses subscripts  free it      ss vector  vec element      struct STRUCT SS VECTOR  next one      vec element vector      while vec element- gt next element   size t  0          next one vec element- gt next element             free vec element- gt items     don t forget to free these         free vec element- gt this element           vec element next one          next one vec element- gt this element               get rid of the last one         free vec element- gt items      free vec element       vector NULL              If there s an array of element addresses subscripts  free it now  printf  quot  nall vector elements  amp  contents freed n quot         void ss vector free all elements       defining some sort of struct  can be anything really typedef struct APPLE STRUCT     int id     one of the data in the component     int other id     etc     struct APPLE STRUCT  next element    apple     description of component  apple  init apple int id     make a single component     apple  a     ptr to component     a   malloc sizeof apple       memory for one component     a- gt id   id     populate with data     a- gt other id id 10      a- gt next element NULL         don t mess with aa- gt last rec here     return a     return pointer to component     int return id value int i apple  aa     given ptr to component  return single data item     printf  quot was inserted as apple  i  id    i      quot  i aa- gt id       return aa- gt id      ss vector  return address given subscript ss vector  vec element int i      always make the first call to this subroutine with global vbl  quot vector quot      ss vector  local vec element 0         If there is a next element  recurse toward end-of-linked-list     if vec element- gt next element   size t 0          if  vec element- gt this element- gt subscript  i               return vec element- gt this element           local vec element  return address given subscript vec element- gt next element i      recurse to end of list         return local vec element            else         if  vec element- gt this element- gt subscript  i      last element             return vec element- gt this element              otherwise  none match         printf  quot reached end of list without match n quot            return  size t  0             return address given subscript    int Test void      was  quot main quot  in the original example     ss vector  local vector      local vector ss init vector sizeof apple       element  quot 0 quot      for  int i   1  i  lt  10  i       inserting items  quot 1 quot  thru whatever         local vector ss vector append vector i              test search function     printf  quot  n NEXT  test search for address given subscript n quot        local vector return address given subscript vector 5       printf  quot finished return address given subscript 5  with vector at  lu n quot   size t local vector       local vector return address given subscript vector 0       printf  quot finished return address given subscript 0  with vector at  lu n quot   size t local vector       local vector return address given subscript vector 9       printf  quot finished return address given subscript 9  with vector at  lu n quot   size t local vector          test single-element removal     printf  quot  nNEXT  test single element removal n quot        ss vector free one element 5 FALSE      without renumbering subscripts     ss vector free one element 3 TRUE     WITH renumbering subscripts        ---end of program---        don t forget to free everything     ss vector free all elements         return 0

User · Answer

When you re saying     make an array holding an index number  int  of an indeterminate number of entities   you re basically saying you re using  pointers   but one which is a array-wide local pointer instead of memory-wide pointer  Since you re conceptually already using  pointers   i e  id numbers that refers to an element in an array   why don t you just use regular pointers  i e  id numbers that refers to an element in the biggest array  the whole memory    Instead of your objects storing a resource id numbers  you can make them store a pointer instead  Basically the same thing  but much more efficient since we avoid turning  array   index  into a  pointer    Pointers are not scary if you think of them as array index for the whole memory  which is what they actually are

User · Answer

As with everything that seems scarier at first than it was later  the best way to get over the initial fear is to immerse yourself into the discomfort of the unknown  It is at times like that which we learn the most  after all   Unfortunately  there are limitations  While you re still learning to use a function  you shouldn t assume the role of a teacher  for example  I often read answers from those who seemingly don t know how to use realloc  i e  the currently accepted answer   telling others how to use it incorrectly  occasionally under the guise that they ve omitted error handling  even though this is a common pitfall which needs mention  Here s an answer explaining how to use realloc correctly  Take note that the answer is storing the return value into a different variable in order to perform error checking   Every time you call a function  and every time you use an array  you are using a pointer  The conversions are occurring implicitly  which if anything should be even scarier  as it s the things we don t see which often cause the most problems  For example  memory leaks     Array operators are pointer operators  array x  is really a shortcut for   array   x   which can be broken down into    and  array   x   It s most likely that the   is what confuses you  We can further eliminate the addition from the problem by assuming x to be 0  thus  array 0  becomes  array because adding 0 won t change the value         and thus we can see that  array is equivalent to array 0   You can use one where you want to use the other  and vice versa  Array operators are pointer operators   malloc  realloc and friends don t invent the concept of a pointer which you ve been using all along  they merely use this to implement some other feature  which is a different form of storage duration  most suitable when you desire drastic  dynamic changes in size   It is a shame that the currently accepted answer also goes against the grain of some other very well-founded advice on StackOverflow  and at the same time  misses an opportunity to introduce a little-known feature which shines for exactly this usecase  flexible array members  That s actually a pretty broken answer        When you define your struct  declare your array at the end of the structure  without any upper bound  For example   struct int list       size t size      int value         This will allow you to unite your array of int into the same allocation as your count  and having them bound like this can be very handy   sizeof  struct int list  will act as though value has a size of 0  so it ll tell you the size of the structure with an empty list  You still need to add to the size passed to realloc to specify the size of your list   Another handy tip is to remember that realloc NULL  x  is equivalent to malloc x   and we can use this to simplify our code  For example   int push back struct int list   fubar  int value        size t x    fubar   fubar 0 - gt size   0            y   x   1       if   x  amp  y     0            void  temp   realloc  fubar  sizeof   fubar                                       x   y    sizeof fubar 0 - gt value 0            if   temp    return 1             fubar   temp     or  if you like   fubar 0    temp              fubar 0 - gt value x    value      fubar 0 - gt size   y      return 0     struct int list  array   NULL    The reason I chose to use struct int list    as the first argument may not seem immediately obvious  but if you think about the second argument  any changes made to value from within push back would not be visible to the function we re calling from  right  The same goes for the first argument  and we need to be able to modify our array  not just here but possibly also in any other function s we pass it to     array starts off pointing at nothing  it is an empty list  Initialising it is the same as adding to it  For example   struct int list  array   NULL  if   push back  amp array  42            success      P S  Remember to free array   when you re done with it

User · Answer

These posts apparently are in the wrong order  This is  3 in a series of 3 posts  Sorry  I ve  quot taken a few MORE liberties quot  with Lie Ryan s code  The linked list admittedly was time-consuming to access individual elements due to search overhead  i e  walking down the list until you find the right element  I have now cured this by maintaining an address vector containing subscripts 0 through whatever paired with memory addresses  This works because the address vector is allocated all-at-once  thus contiguous in memory  Since the linked-list is no longer required  I ve ripped out its associated code and structure  This approach is not quite as efficient as a plain-and-simple static array would be  but at least you don t have to  quot walk the list quot  searching for the proper item  You can now access the elements by using a subscript  To enable this  I have had to add code to handle cases where elements are removed and the  quot actual quot  subscripts wouldn t be reflected in the pointer vector s subscripts  This may or may not be important to users  For me  it IS important  so I ve made re-numbering of subscripts optional  If renumbering is not used  program flow goes to a dummy  quot missing quot  element which returns an error code  which users can choose to ignore or to act on as required  From here  I d advise users to code the  quot elements quot  portion to fit their needs and make sure that it runs correctly  If your added elements are arrays  carefully code subroutines to access them  seeing as how there s extra array structure that wasn t needed with static arrays  Enjoy   include  lt glib h gt   include  lt stdio h gt   include  lt stdlib h gt   include  lt string h gt   include  lt ctype h gt       Code from https   stackoverflow com questions 3536153 c-dynamically-growing-array    For pointer-to-pointer info see     https   stackoverflow com questions 897366 how-do-pointer-to-pointers-work-in-c-and-when-might-you-use-them typedef struct STRUCT SS VECTOR     size t size       of vector elements     void   items     makes up one vector element s component contents     int subscript     this element s subscript nmbr  0 thru whatever       struct STRUCT SS VECTOR  this element     linked list via this ptr       struct STRUCT SS VECTOR  next element     and next ptr   ss vector   ss vector  vector     ptr to vector of components ss vector  missing element int subscript     intercepts missing elements     printf  quot missing element at subscript  i n quot  subscript       return NULL     typedef struct TRACKER VECTOR     int subscript      ss vector  vector ptr    tracker vector      up to 20 or so  max suggested  tracker vector  tracker  int max tracker 0     max allowable   of elements in  quot tracker vector quot  int tracker count 0     current   of elements in  quot tracker vector quot  int tracker increment 5       of elements to add at each expansion  void bump tracker vector int new tracker count        init or lengthen tracker vector     if max tracker  0     not yet initialized       tracker calloc tracker increment  sizeof tracker vector            max tracker tracker increment  printf  quot initialized  i-element tracker vector of size  lu at  lu n quot  max tracker sizeof tracker vector   size t tracker           tracker count            return            else if  max tracker lt  tracker count     append to existing tracker vector by writing a new one  copying old one         tracker vector  temp tracker calloc max tracker tracker increment sizeof tracker vector              for int i 0  i lt max tracker  i       temp tracker i  tracker i       copy old tracker to new         max tracker max tracker tracker increment          free tracker           tracker temp tracker  printf  quot   re-initialized  i-element tracker vector of size  lu at  lu n quot  max tracker sizeof tracker vector   size t tracker           tracker count            return           else if        fall through for most  quot bumps quot      tracker count        return        bump tracker vector    ss vector  ss init vector size t item size     item size is size of one array member     ss vector  vector  malloc sizeof ss vector         vector- gt size   0     initialize count of vector component elements     vector- gt items   calloc 1  item size      allocate  amp  zero out memory for one linked list element     vector- gt subscript 0      bump tracker vector 0      init store the tracker vector     tracker 0  subscript 0      tracker 0  vector ptr vector       return vector    - gt this element       ss init vector    ss vector  ss vector append  int i     ptr to this element  element nmbr     ss vector  local vec element 0      local vec element  calloc 1 sizeof ss vector       memory for one component     local vec element- gt subscript i    vec element- gt size       local vec element- gt size i     increment   of vector components     bump tracker vector i       increment store tracker vector     tracker i  subscript i      tracker i  vector ptr local vec element    - gt this element      return local vec element        ss vector append    void bubble sort void          bubble sort     struct TRACKER VECTOR local tracker      int i 0      while i lt tracker count-1          if tracker i  subscript gt tracker i 1  subscript              local tracker subscript tracker i  subscript     swap tracker elements             local tracker vector ptr tracker i  vector ptr              tracker i  subscript tracker i 1  subscript              tracker i  vector ptr tracker i 1  vector ptr              tracker i 1  subscript local tracker subscript              tracker i 1  vector ptr local tracker vector ptr              if i gt 0  i--     step back and go again                   else              if i lt tracker count-1  i                       while        void bubble sort    void move toward zero int target subscript     toward zero     struct TRACKER VECTOR local tracker         Target to be moved must range from 1 to max tracker     if  target subscript lt 1    target subscript gt tracker count   return     outside range        swap target subscript ptr and target subscript-1 ptr     local tracker vector ptr tracker target subscript  vector ptr      tracker target subscript  vector ptr tracker target subscript-1  vector ptr      tracker target subscript-1  vector ptr local tracker vector ptr     void renumber all subscripts gboolean arbitrary         assumes tracker count has been fixed and tracker tracker count 1 has been zeroed out     if arbitrary      arbitrary renumber  ignoring  quot true quot  subscripts         for int i 0 i lt tracker count i                 tracker i  subscript i             else    use  quot true quot  subscripts  holes and all         for int i 0 i lt tracker count i                 if   size t tracker i  vector ptr  0     renumbering  quot true quot  subscript tracker  amp  vector element                 tracker i  subscript tracker i  vector ptr- gt subscript               else    renumbering  quot true quot  subscript tracker  amp  NULL vector element                 tracker i  subscript -1                for           bubble sort              if arbitrary  ELSE      renumber all subscripts    void collapse tracker higher elements int target subscript         Fix tracker vector by collapsing higher subscripts toward 0          Assumes last tracker element entry is discarded      int j      for j target subscript  j lt tracker count-1  j            tracker j  subscript tracker j 1  subscript          tracker j  vector ptr tracker j 1  vector ptr               Discard last tracker element and adjust count     tracker count--      tracker tracker count  subscript 0      tracker tracker count  vector ptr  size t 0       void collapse tracker higher elements    void ss vector free one element int target subscript  gboolean Keep subscripts          Free requested element contents              Adjust subscripts if desired  otherwise  mark NULL         ----special case  vector 0      if target subscript  0     knock out zeroth element no matter what         free tracker 0  vector ptr            ----if not zeroth  start looking at other elements     else if tracker count lt target subscript-1          printf  quot vector element not found n quot   return          Requested subscript okay  Freeit       else         free tracker target subscript  vector ptr       free element ptr        done with removal      if Keep subscripts     adjust subscripts if required          tracker target subscript  vector ptr missing element target subscript       point to  quot 0 quot  vector     else    NOT keeping subscripts intact  i e  collapsing renumbering all subscripts toward zero         collapse tracker higher elements target subscript           renumber all subscripts TRUE      gboolean arbitrary means as-is  FALSE means by  quot true quot  subscripts          if  target subscript  0  else    show the new list    for int i 0 i lt tracker count i    printf  quot    remaining element  i  at  lu n quot  tracker i  subscript  size t tracker i  vector ptr         void ss vector free one element    void ss vector free all elements void          Start at  quot tracker 0  quot   Walk the entire list  free each element s contents               then free that element  then move to the next one              Then free the  quot tracker quot  vector      for int i tracker count i gt  0 i--              Modify your code to free vector element  quot items quot  here         if tracker i  subscript gt  0  free tracker i  vector ptr             free tracker       tracker count 0       void ss vector free all elements       defining some sort of struct  can be anything really typedef struct APPLE STRUCT     int id     one of the data in the component     int other id     etc     struct APPLE STRUCT  next element    apple     description of component  apple  init apple int id     make a single component     apple  a     ptr to component     a   malloc sizeof apple       memory for one component     a- gt id   id     populate with data     a- gt other id id 10      a- gt next element NULL         don t mess with aa- gt last rec here     return a     return pointer to component    int return id value int i apple  aa     given ptr to component  return single data item     printf  quot was inserted as apple  i  id    i      quot  i aa- gt id       return aa- gt id      ss vector  return address given subscript int i       return tracker i  vector ptr     int Test void      was  quot main quot  in the example     int i      ss vector  local vector      local vector ss init vector sizeof apple       element  quot 0 quot      for  i   1  i  lt  10  i       inserting items  quot 1 quot  thru whatever      local vector ss vector append i         finished ss vector append          list all tracker vector entries     for i 0  i lt tracker count  i     printf  quot tracker element   i  has address  lu n quot  tracker i  subscript   size t tracker i  vector ptr           ---test search function     printf  quot  n NEXT  test search for address given subscript n quot        local vector return address given subscript 5   printf  quot finished return address given subscript 5  with vector at  lu n quot   size t local vector       local vector return address given subscript 0   printf  quot finished return address given subscript 0  with vector at  lu n quot   size t local vector       local vector return address given subscript 9   printf  quot finished return address given subscript 9  with vector at  lu n quot   size t local vector          ---test single-element removal     printf  quot  nNEXT  test single element removal n quot        ss vector free one element 5 TRUE      keep subscripts  install dummy error element printf  quot finished ss vector free one element 5  n quot        ss vector free one element 3 FALSE   printf  quot finished ss vector free one element 3  n quot        ss vector free one element 0 FALSE          ---test moving elements printf  quot  n Test moving a few elements up n quot        move toward zero 5       move toward zero 4       move toward zero 3          show the new list     printf  quot New list  n quot        for int i 0 i lt tracker count i    printf  quot     i element  i  at  lu n quot  i tracker i  subscript  size t tracker i  vector ptr           ---plant some bogus subscripts for the next subscript test     tracker 3  vector ptr- gt subscript 7      tracker 3  subscript 5      tracker 7  vector ptr- gt subscript 17      tracker 3  subscript 55  printf  quot  n RENUMBER to use   quot actual  quot  subscripts n quot           renumber all subscripts FALSE       printf  quot Sorted list  n quot        for int i 0 i lt tracker count i            if   size t tracker i  vector ptr  0              printf  quot     i element  i  or   i at  lu n quot  i tracker i  subscript tracker i  vector ptr- gt subscript  size t tracker i  vector ptr                     else              printf  quot     i element  i  at 0 n quot  i tracker i  subscript                   printf  quot  nBubble sort to get TRUE order back n quot        bubble sort        printf  quot Sorted list  n quot        for int i 0 i lt tracker count i            if   size t tracker i  vector ptr  0           printf  quot     i element  i  or   i at  lu n quot  i tracker i  subscript tracker i  vector ptr- gt subscript  size t tracker i  vector ptr            else  printf  quot     i element  i  at 0 n quot  i tracker i  subscript                 END TEST SECTION        don t forget to free everything     ss vector free all elements         return 0     int main int argc  char  argv        char cmd 5  main buffer 50      Intentionally big for  quot other quot  I O purposes     cmd 0  32     blank   ASCII 32         while cmd   quot R quot  amp  amp cmd   quot W quot    amp  amp cmd   quot E quot          amp  amp cmd   quot   quot        while cmd 0   82 amp  amp cmd 0   87 amp  amp cmd 0   69    amp  amp cmd 0   32           memset cmd    0   sizeof cmd            memset main buffer    0   sizeof main buffer               default back to the cmd loop         cmd 0  32     blank   ASCII 32         printf  quot REad  TEst  WRITe  EDIt  or EXIt   quot            fscanf stdin   quot  s quot   main buffer           strncpy cmd main buffer 4           for int i 0 i lt 4 i   cmd i  toupper cmd i            cmd 4    0           printf  quot  s received n  quot  cmd              process top level commands         if cmd 0   82   printf  quot READ accepted n quot       Read         else if cmd 0   87   printf  quot WRITe accepted n quot        Write         else if cmd 0   84               printf  quot TESt accepted n quot      TESt             Test                      else if cmd 0   69      quot E quot              if cmd 1   68   printf  quot EDITing n quot        eDit             else if cmd 1   88   printf  quot EXITing n quot   exit 0       eXit             else    printf  quot   unknown E command  c c n quot  cmd 0  cmd 1                      else    printf  quot   unknown command n quot            cmd 0  32     blank   ASCII 32          while          default back to the cmd loop        main

User · Answer

Well  I guess if you need to remove an element you will make a copy of the array despising the element to be excluded      inserting some items void  element 2 remove   getElement2BRemove     for  int i   0  i  lt  vector- gt size  i            if vector i   element 2 remove  copy2TempVector vector i              free vector- gt items   free vector   fillFromTempVector vector        Assume that getElement2BRemove    copy2TempVector  void       and fillFromTempVector      are auxiliary methods to handle the temp vector

[c] C dynamically growing array

Examples related to c

Examples related to dynamic-arrays