CODEWITHSUNDEEP
carraysdynamicstructuredynamic-arrays
user3364050
user3364050

Reputation: 5

Dynamic, unpreditable sized array in C

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.

Upvotes: 0

Views: 125

Answers (3)

Adrian
Adrian

Reputation: 6101

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.

Upvotes: 1

woggioni
woggioni

Reputation: 1432

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;
}

Upvotes: 0

cnicutar
cnicutar

Reputation: 182664

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.

Upvotes: 5

Related Questions