Dynamic, unpreditable sized array in C

Question

I am going to make an array of structure values. The number of the entries depend on the input so there is no way to estimate the length of the array.

In a FOR loop, parsing the input, I would create an entry for every iteration. That means I need to reallocate array because the size grows and this leads to inefficiency in terms of performance.

If I were allowed to program in C++, I would use vector. Unfortunately I can't, and I can't think of any better idea.

Please help me, any advice would be appreciated.

There's no way to estimate the length of the array, but do you know what the maximum length may be (i.e. is there a hard limit)? — Fiddling Bits, Aug 08 '14 at 13:02

score 5 · Accepted Answer · answered Aug 08 '14 at 13:00

5

If I were allowed to program in C++, I would use vector.

Then you can do what vector would do: when you need to reallocate, double the size of the allocation. That should amortize realloc performance issues.

answered Aug 08 '14 at 13:00

cnicutar

178,505
25
365
392

2

@downvoter: Thanks for the feedback! Would you mind leaving a comment to educate me on what is wrong in what I said ? – cnicutar Aug 08 '14 at 14:10
cnicutar: The question title and tags clearly states "C" not "C++". You are NOT answering "this" question hence the downvote. – Adrian Aug 12 '14 at 15:04
@Adrian I *am* answering the question. I am simply stating a typical way of handling this problem in C that happens to emulate what the user is expecting from C++ . There is nothing C++-specific in my answer. – cnicutar Aug 12 '14 at 15:36

score 1 · Answer 2 · edited May 23 '17 at 12:05

This article contains a complete solution for your problem. Basically it implements a "Vector" type class using C Implementing a dynamically sized array in C

It defines the vectory type like this:

// Define a vector type
typedef struct {
  int size;      // slots used so far
  int capacity;  // total available slots
  int *data;     // array of integers we're storing
} Vector;
void vector_init(Vector *vector);
void vector_append(Vector *vector, int value);
int vector_get(Vector *vector, int index);
void vector_set(Vector *vector, int index, int value);
void vector_double_capacity_if_full(Vector *vector);
void vector_free(Vector *vector);

There are similar questions already answered on Stack Overflow, have a look at them as well:

EDIT: Informative post on Wikipedia: Dynamic array

In computer science, a dynamic array, growable array, resizable array, dynamic table, mutable array, or array list is a random access, variable-size list data structure that allows elements to be added or removed. It is supplied with standard libraries in many modern mainstream programming languages.

A dynamic array is not the same thing as a dynamically allocated array, which is a fixed-size array whose size is fixed when the array is allocated, although a dynamic array may use such a fixed-size array as a back end.

You need to make a compromise between "Dynamic" and "Performance" - there is no such thing as a free lunch — Adrian, Aug 12 '14 at 15:00

score 0 · Answer 3 · answered Aug 08 '14 at 13:17

Actually there is NO better idea that what you suggested, C++ std::vector does exactly this under the hood (maybe with a more advanced estimation algorithm)

You simply need something like

typedef struct mystruct mystruct;
struct mystruct
{
 //Your struct's members
};

struct vector
{
mystruct* array;
unsigned dimension;
unsigned filled;
};

void vector_init(struct vector *v, int initial_size)
{
    v->dimension=initial_size;
    v->filled=0;
    v->array= malloc(sizeof(mystruct)*initial_size);
}

void vector_add(struct vector *v, mystruct obj)
{
   if(v->dim<=v->filled)
   {
       v->dimension*=2;
       realloc(v->array, v->dimension);
   }
   v->array[filled] = obj;
   v->filled++;
}

int main()
{
    struct vector *v;
    vector_init(v);
    mystruct struct_instance;

    int i;
    for(i=0; i<whatever; i++)
    {
        insert_obj(array, struct_instance);
    }
    return 0;
}

Dynamic, unpreditable sized array in C

3 Answers3