views:

20951

answers:

8

I know how to create an array of structs but with a predefined size. However is there a way to create a dynamic array of structs such that the array could get bigger?

For example:

    typedef struct
    {
        char *str;
    } words;

    main()
    {
        words x[100]; // I do not want to use this, I want to dynamic increase the size of the array as data comes in.
    }

Is this possible?


I've researched this: words* array = (words*)malloc(sizeof(words) * 100);

I don't think I explained myself clearly, my apologies.

I want to get rid of the 100 and store the data as it comes in. Thus if 76 fields of data comes in, I want to store 76 and not 100. I'm assuming that I don't know how much data is coming into my program. In the struct I defined above I could create the first "index" as:

    words* array = (words*)malloc(sizeof(words));

However I want to dynamically add elements to the array after. I hope I described the problem area clearly enough. The major challenge is to dynamically add a second field, at least that is the challenge for the moment.


I've made a little progress however:

    typedef struct {
        char *str;
    } words;

    // Allocate first string.
    words x = (words) malloc(sizeof(words));
    x[0].str = "john";

    // Allocate second string.
    x=(words*) realloc(x, sizeof(words));
    x[1].FirstName = "bob";

    // printf second string.
    printf("%s", x[1].str); --> This is working, it's printing out bob.

    free(x); // Free up memory.

    printf("%s", x[1].str); --> Not working since its still printing out BOB even though I freed up memory. What is wrong?

I did some error checking and this is what I found. If after I free up memory for x I add the following:

    x=NULL;

then if I try to print x I get an error which is what I want. So is it that the free function is not working, at least on my compiler? I'm using DevC??


Thanks, I understand now due to:

FirstName is a pointer to an array of char which is not being allocated by the malloc, only the pointer is being allocated and after you call free, it doesn't erase the memory, it just marks it as available on the heap to be over written later. – MattSmith

P.S. Sorry for the long page, I guess I'm now getting used to this forum.

I'm in a problem. I have no idea what to do next. Please help someone. I'm trying to modularize and put the creation of my array of structs in a function but it is not working and I've tried everything, just nothing seems to work. I'm trying something very simple and I don't know what else to do. It's along the same lines as before, just another function, loaddata that is loading the data and outside the method I need to do some printing. How can I make it work?. My code is as follows:

    # include <stdio.h>
    # include <stdlib.h>
    # include <string.h>
    # include <ctype.h>

    typedef struct
    {
        char *str1;
        char *str2;
    } words;

    void LoadData(words *, int *);

    main()
    {
        words *x;
        int num;

        LoadData(&x, &num);

        printf("%s %s", x[0].str1, x[0].str2);
        printf("%s %s", x[1].str1, x[1].str2);

        getch();
    }//

    void LoadData(words *x, int * num)
    {
        x = (words*) malloc(sizeof(words));

        x[0].str1 = "johnnie\0";
        x[0].str2 = "krapson\0";

        x = (words*) realloc(x, sizeof(words)*2);
        x[1].str1 = "bob\0";
        x[1].str2 = "marley\0";

        *num=*num+1;
    }//

This simple test code is crashing and I have no idea why. Where is the bug?

A: 

Check out malloc and realloc.

Andrew
+4  A: 

If you want to dynamically allocate arrays, you can use malloc from stdlib.h.

If you want to allocate an array of 100 elements using your words struct, try the following:

words* array = (words*)malloc(sizeof(words) * 100);

The size of the memory that you want to allocate is passed into malloc and then it will return a pointer of type void (void*). In most cases you'll probably want to cast it to the pointer type you desire, which in this case is words*.

The sizeof keyword is used here to find out the size of the words struct, then that size is multiplied by the number of elements you want to allocate.

Once you are done, be sure to use free() to free up the heap memory you used in order to prevent memory leaks:

free(array);

If you want to change the size of the allocated array, you can try to use realloc as others have mentioned, but keep in mind that if you do many reallocs you may end up fragmenting the memory. If you want to dynamically resize the array in order to keep a low memory footprint for your program, it may be better to not do too many reallocs.

coobird
malloc is from stdlib.h.
Thank you for pointing that out, The Night Rider! I've fixed the error.
coobird
In C, it is not mandatory that 'void *' (as returned by malloc()) is cast to another pointer type - you could omit the cast. However, C++ does require a cast.
Jonathan Leffler
A: 

If you want to grow the array dynamically, you should use malloc() to dynamically allocate some fixed amount of memory, and then use realloc() whenever you run out. A common technique is to use an exponential growth function such that you allocate some small fixed amount and then make the array grow by duplicating the allocated amount.

Some example code would be:

size = 64; i = 0;
x = malloc(sizeof(words)*size); /* enough space for 64 words */
while (read_words()) {
 if (++i > size) {
  size *= 2;
  x = realloc(sizeof(words) * size);
 }
}
/* done with x */
free(x);
ob
This is not the correct usage of realloc. Please research and edit appropriately.
Chris Young
I had to code as:x = realloc(x, sizeof(words) * size);
+2  A: 

In C++, use a vector. It's like an array but you can easily add and remove elements and it will take care of allocating and deallocating memory for you.

I know the title of the question says C, but you tagged your question with C and C++...

yjerem
I vote down, because it was the top answer, but now the tag is only c. sorry ;)
elmarco
+1  A: 

Another option for you is a linked list. You'll need to analyze how your program will use the data structure, if you don't need random access it could be faster than reallocating.

Neil Williams
+6  A: 

You've tagged this as C++ as well as C.

If you're using C++ things are a lot easier. The standard template library has a template called vector which allows you to dynamically build up a list of objects.

#include <stdio.h>
#include <vector>

typedef std::vector<char*> words;

int main(int argc, char** argv) {

        words myWords;

        myWords.push_back("Hello");
        myWords.push_back("World");

        words::iterator iter;
        for (iter = myWords.begin(); iter != myWords.end(); ++iter) {
                printf("%s ", *iter);
        }

        return 0;
}

If you're using C things are a lot harder, yes malloc, realloc and free are the tools to help you. You might want to consider using a linked list data structure instead. These are generally easier to grow but don't facilitate random access as easily.

#include <stdio.h>
#include <stdlib.h>

typedef struct s_words {
        char* str;
        struct s_words* next;
} words;

words* create_words(char* word) {
        words* newWords = malloc(sizeof(words));
        if (NULL != newWords){
                newWords->str = word;
                newWords->next = NULL;
        }
        return newWords;
}

void delete_words(words* oldWords) {
        if (NULL != oldWords->next) {
                delete_words(oldWords->next);
        }
        free(oldWords);
}

words* add_word(words* wordList, char* word) {
        words* newWords = create_words(word);
        if (NULL != newWords) {
                newWords->next = wordList;
        }
        return newWords;
}

int main(int argc, char** argv) {

        words* myWords = create_words("Hello");
        myWords = add_word(myWords, "World");

        words* iter;
        for (iter = myWords; NULL != iter; iter = iter->next) {
                printf("%s ", iter->str);
        }
        delete_words(myWords);
        return 0;
}

Yikes, sorry for the worlds longest answer. So WRT to the "don't want to use a linked list comment":

#include <stdio.h>  
#include <stdlib.h>

typedef struct {
    char** words;
    size_t nWords;
    size_t size;
    size_t block_size;
} word_list;

word_list* create_word_list(size_t block_size) {
    word_list* pWordList = malloc(sizeof(word_list));
    if (NULL != pWordList) {
        pWordList->nWords = 0;
        pWordList->size = block_size;
        pWordList->block_size = block_size;
        pWordList->words = malloc(sizeof(char*)*block_size);
        if (NULL == pWordList->words) {
            free(pWordList);
            return NULL;    
        }
    }
    return pWordList;
}

void delete_word_list(word_list* pWordList) {
    free(pWordList->words);
    free(pWordList);
}

int add_word_to_word_list(word_list* pWordList, char* word) {
    size_t nWords = pWordList->nWords;
    if (nWords >= pWordList->size) {
        size_t newSize = pWordList->size + pWordList->block_size;
        void* newWords = realloc(pWordList->words, sizeof(char*)*newSize); 
        if (NULL == newWords) {
            return 0;
        } else {    
            pWordList->size = newSize;
            pWordList->words = (char**)newWords;
        }

    }

    pWordList->words[nWords] = word;
    ++pWordList->nWords;


    return 1;
}

char** word_list_start(word_list* pWordList) {
        return pWordList->words;
}

char** word_list_end(word_list* pWordList) {
        return &pWordList->words[pWordList->nWords];
}

int main(int argc, char** argv) {

        word_list* myWords = create_word_list(2);
        add_word_to_word_list(myWords, "Hello");
        add_word_to_word_list(myWords, "World");
        add_word_to_word_list(myWords, "Goodbye");

        char** iter;
        for (iter = word_list_start(myWords); iter != word_list_end(myWords); ++iter) {
                printf("%s ", *iter);
        }

        delete_word_list(myWords);

        return 0;
}
Tom
I have no choice but to use a dynamic array. If it was a linked-list i wont have a problem. I have written tons of programs with linked lists which is why this program is appearing so complex to me.
Don't cast the return values of functions that return void * in C. It adds nothing, and can potentially hide a missing prototype error.
Chris Young
Chris you always need to cast the return from void* to what you've allocated - this is c not c++.
Tom
@thaggie: you've got that backwards; C does not require the cast, but C++ does.
Jonathan Leffler
@thaggie (again): interesting port of STL iterators into C - good idea. You don't check the return value from add_word_to_list(), which is a pity.
Jonathan Leffler
@Chris/Jonathan - I stand corrected - been too long since I've actually used a c compiler.
Tom
@thaggie: Very nice, I like it. One potential problem is the static strings and add_word_to_word_list. Your example works great for static strings, but for allocated strings it will cause memory leaks. It might be better to allocate the memory and copy the string and then free it in delete_word_list
Ryan
@ryan - Naturally - got to leave something as an exercise for the reader though surely?
Tom
+2  A: 

This looks like an academic exercise which unfortunately makes it harder since you can't use C++. Basically you have to manage some of the overhead for the allocation and keep track how much memory has been allocated if you need to resize it later. This is where the C++ standard library shines.

For your example, the following code allocates the memory and later resizes it:

// initial size
int count = 100;
words *testWords = (words*) malloc(count * sizeof(words));
// resize the array
count = 76;
testWords = (words*) realloc(testWords, count* sizeof(words));

Keep in mind, in your example you are just allocating a pointer to a char and you still need to allocate the string itself and more importantly to free it at the end. So this code allocates 100 pointers to char and then resizes it to 76, but does not allocate the strings themselves.

I have a suspicion that you actually want to allocate the number of characters in a string which is very similar to the above, but change word to char.

EDIT: Also keep in mind it makes a lot of sense to create functions to perform common tasks and enforce consistency so you don't copy code everywhere. For example, you might have a) allocate the struct, b) assign values to the struct, and c) free the struct. So you might have:

// Allocate a words struct
words* CreateWords(int size);
// Assign a value
void AssignWord(word* dest, char* str);
// Clear a words structs (and possibly internal storage)
void FreeWords(words* w);

EDIT: As far as resizing the structs, it is identical to resizing the char array. However the difference is if you make the struct array bigger, you should probably initialize the new array items to NULL. Likewise, if you make the struct array smaller, you need to cleanup before removing the items -- that is free items that have been allocated (and only the allocated items) before you resize the struct array. This is the primary reason I suggested creating helper functions to help manage this.

// Resize words (must know original and new size if shrinking
// if you need to free internal storage first)
void ResizeWords(words* w, size_t oldsize, size_t newsize);
Ryan
Yes its unfortunate when you're familiar with the nice programs like java etc and you its back to the old days with c. Yes i want to allocate the string which is in my reply below.Actually i know how to dynamically allocate the chars in a string. The problem is working with an array of structs.
You discard the return value of realloc. This is wrong: (a) realloc might fail (returning NULL), (b) realolc might return a new pointer because it had to move the data.
Chris Young
Given that the resize is a shrinking operation, it is very unlikely that realloc() would shift the data. Nevertheless, as you suggest, it is a bad idea to think that realloc() won't move data, especially if you ever grow the array.
Jonathan Leffler
@Chris Young - Agreed, I looked too fast at the prototype for realloc and thought it returned void instead of void*. Use the returned value for the memory.
Ryan
A: 

Your code in the last update should not compile, much less run. You're passing &x to LoadData. &x has the type of *words, but LoadData expects words . Of course it crashes when you call realloc on a pointer that's pointing into stack.

The way to fix it is to change LoadData to accept words** . Thi sway, you can actually modify the pointer in main(). For example, realloc call would look like

*x = (words*) realloc(*x, sizeof(words)*2);

It's the same principlae as in "num" being int* rather than int.

Besides this, you need to really figure out how the strings in words ere stored. Assigning a const string to char * (as in str2 = "marley\0") is permitted, but it's rarely the right solution, even in C.

Another point: non need to have "marley\0" unless you really need two 0s at the end of string. Compiler adds 0 tho the end of every string literal.

Arkadiy
"Assigning a const string to char * (as in str2 = "marley\0") is permitted, but it's rarely the right solution, even in C."This is the only solution i know, is there a better solution rather than assigning a string value?
You're assigning a string constant. A string value can be assigned, for example, by using strdup: str2 = strdup("marley"). This way the owner of words structure is responsible for memory deallocation.I really think you would be better off with a more forgiving language,such as Python or even Java
Arkadiy