resizing an array, is there a better way?

Discussion in 'C Programming' started by someone else, Aug 1, 2004.

  1. someone else

    someone else Guest

    hello

    i'm looking for good ways to resize a structure. for example:


    typedef struct mystruct {
    ....
    }

    mystruct small[1024];
    ....

    /*need to resize */

    mystruct big[2048];
    for(int i=0;i<1024;i++)
    big = small;
    ....


    is there a more efficiant way? this could be very ineficiant, since it
    creates a new array, and then copies all the values from the old array, is
    there a way to keep the old array, with its variables, and just add new
    elements to it?

    any suggestions would be appreciated
    someone else, Aug 1, 2004
    #1
    1. Advertising

  2. someone else

    -berlin.de Guest

    someone else <zooloo@****.the.spammers.net> wrote:
    > i'm looking for good ways to resize a structure. for example:


    You seem to mean "resize an array of structures".

    > typedef struct mystruct {
    > ...
    > }


    > mystruct small[1024];
    > ...


    > /*need to resize */


    > mystruct big[2048];
    > for(int i=0;i<1024;i++)
    > big = small;
    > ...


    > is there a more efficiant way? this could be very ineficiant, since it
    > creates a new array, and then copies all the values from the old array, is
    > there a way to keep the old array, with its variables, and just add new
    > elements to it?


    Yes. Instead of static arrays use a dynamically allocated one. Read in
    your favorite book about C about the functions malloc(), realloc() and
    free(). Basically you would do something like this:

    mystruct *sp, *new_sp;

    if ( ( sp = malloc( 1024 * sizeof *sp ) ) == NULL ) {
    fprintf( stderr, "Failed to allocate 1024 structures\n" );
    exit( EXIT_FAILURE );
    }

    ....

    if ( ( new_sp = realloc( sp, 2048 * sizeof *sp ) ) == NULL ) {
    fprintf( stderr, "Failed to reallocate 2048 structures\n" );
    free( sp );
    exit( EXIT_FAILURE );
    }
    sp = new_sp;

    ....

    free( sp );
    Regards, Jens
    --
    \ Jens Thoms Toerring ___ -berlin.de
    \__________________________ http://www.toerring.de
    -berlin.de, Aug 1, 2004
    #2
    1. Advertising

  3. someone else

    someone else Guest

    thanks jens

    i wasn't sure if realloc preserves the data...
    <-berlin.de> wrote in message
    news:...
    > someone else <zooloo@****.the.spammers.net> wrote:
    > > i'm looking for good ways to resize a structure. for example:

    >
    > You seem to mean "resize an array of structures".

    your right, my mistake :)
    >
    > > typedef struct mystruct {
    > > ...
    > > }

    >
    > > mystruct small[1024];
    > > ...

    >
    > > /*need to resize */

    >
    > > mystruct big[2048];
    > > for(int i=0;i<1024;i++)
    > > big = small;
    > > ...

    >
    > > is there a more efficiant way? this could be very ineficiant, since it
    > > creates a new array, and then copies all the values from the old array,

    is
    > > there a way to keep the old array, with its variables, and just add new
    > > elements to it?

    >
    > Yes. Instead of static arrays use a dynamically allocated one. Read in
    > your favorite book about C about the functions malloc(), realloc() and
    > free(). Basically you would do something like this:
    >
    > mystruct *sp, *new_sp;
    >
    > if ( ( sp = malloc( 1024 * sizeof *sp ) ) == NULL ) {
    > fprintf( stderr, "Failed to allocate 1024 structures\n" );
    > exit( EXIT_FAILURE );
    > }
    >
    > ...
    >
    > if ( ( new_sp = realloc( sp, 2048 * sizeof *sp ) ) == NULL ) {
    > fprintf( stderr, "Failed to reallocate 2048 structures\n" );
    > free( sp );
    > exit( EXIT_FAILURE );
    > }
    > sp = new_sp;
    >
    > ...
    >
    > free( sp );
    > Regards, Jens
    > --
    > \ Jens Thoms Toerring ___ -berlin.de
    > \__________________________ http://www.toerring.de
    someone else, Aug 1, 2004
    #3
  4. someone else

    Malcolm Guest

    "someone else" <zooloo@****.the.spammers.net> wrote
    >
    > i'm looking for good ways to resize a structure. for example:
    >
    >
    > typedef struct mystruct {
    > ...
    > }
    >
    > mystruct small[1024];
    > ...
    >
    > /*need to resize */
    >
    > mystruct big[2048];
    > for(int i=0;i<1024;i++)
    > big = small;
    > ...
    >
    > is there a more efficiant way? this could be very ineficiant, since it
    > creates a new array, and then copies all the values from the old array, is
    > there a way to keep the old array, with its variables, and just add new
    > elements to it?
    >

    The only thing you can do is

    mystruct big[2048];
    int current_size;

    Set current_size to the number of elements that are actual entries.

    You might also want to look at the functions malloc() and realloc(). Most C
    programmers would achieve the above by.

    mystruct *small = malloc( sizeof(mystruct) * 1024);

    to resize

    mystruct *big = realloc( small, sizeof(mystruct) * 2048);

    However this is not really much improvement, because internally realloc()
    usually allocates a new area of memory and then copies.

    If you absolutely need an array which can be extended quickly, your only
    option is to use a more complicated structure. Something like

    struct extensiblearray
    {
    int N chunks;
    int chunksize;
    mystruct **chunklist;
    }:

    The you have functions readextensible(), writeextensible() and
    resizeextensible() which manipulate it transparently. This is a lot of fuss,
    and time you save on extension will to some extent be paid for by the acces
    overhead, but it will mean that you can change the size of the array without
    moving all the elements in memory.
    Malcolm, Aug 1, 2004
    #4
  5. someone else

    Jack Klein Guest

    On Mon, 2 Aug 2004 00:54:29 +0800, "someone else"
    <zooloo@****.the.spammers.net> wrote in comp.lang.c:

    > thanks jens
    >
    > i wasn't sure if realloc preserves the data...


    Please don't top post. Material you add belongs after material you
    are quoting from the post you are replying to, not at the top.

    As for realloc(), if it succeeds it is guaranteed to preserve the
    minimum of the old array size and the new array size, whichever is
    less.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
    Jack Klein, Aug 2, 2004
    #5
  6. someone else

    Jack Klein Guest

    On Sun, 1 Aug 2004 18:02:14 +0100, "Malcolm"
    <> wrote in comp.lang.c:

    >
    > "someone else" <zooloo@****.the.spammers.net> wrote
    > >
    > > i'm looking for good ways to resize a structure. for example:
    > >
    > >
    > > typedef struct mystruct {
    > > ...
    > > }
    > >
    > > mystruct small[1024];
    > > ...
    > >
    > > /*need to resize */
    > >
    > > mystruct big[2048];
    > > for(int i=0;i<1024;i++)
    > > big = small;
    > > ...
    > >
    > > is there a more efficiant way? this could be very ineficiant, since it
    > > creates a new array, and then copies all the values from the old array, is
    > > there a way to keep the old array, with its variables, and just add new
    > > elements to it?
    > >

    > The only thing you can do is
    >
    > mystruct big[2048];
    > int current_size;
    >
    > Set current_size to the number of elements that are actual entries.
    >
    > You might also want to look at the functions malloc() and realloc(). Most C
    > programmers would achieve the above by.
    >
    > mystruct *small = malloc( sizeof(mystruct) * 1024);


    No, most experienced C programmers would use the superior code:

    mystruct *small = malloc(1024 * sizeof *mystruct);

    [snip]

    > However this is not really much improvement, because internally realloc()
    > usually allocates a new area of memory and then copies.


    Maybe it does, maybe it does not. In any case, even if it does
    require copying it is quite possible that it will use a mechanism more
    efficient than the OP's for loop.

    > If you absolutely need an array which can be extended quickly, your only
    > option is to use a more complicated structure. Something like
    >
    > struct extensiblearray
    > {
    > int N chunks;
    > int chunksize;
    > mystruct **chunklist;
    > }:
    >
    > The you have functions readextensible(), writeextensible() and
    > resizeextensible() which manipulate it transparently. This is a lot of fuss,
    > and time you save on extension will to some extent be paid for by the acces
    > overhead, but it will mean that you can change the size of the array without
    > moving all the elements in memory.


    That's very nice, but it has nothing at all to do with arrays.

    --
    Jack Klein
    Home: http://JK-Technology.Com
    FAQs for
    comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
    comp.lang.c++ http://www.parashift.com/c -faq-lite/
    alt.comp.lang.learn.c-c++
    http://www.contrib.andrew.cmu.edu/~ajo/docs/FAQ-acllc.html
    Jack Klein, Aug 2, 2004
    #6
  7. Jack Klein <> writes:
    [...]
    > > You might also want to look at the functions malloc() and
    > > realloc(). Most C programmers would achieve the above by.
    > >
    > > mystruct *small = malloc( sizeof(mystruct) * 1024);

    >
    > No, most experienced C programmers would use the superior code:
    >
    > mystruct *small = malloc(1024 * sizeof *mystruct);


    I think you mean:

    mystruct *small = malloc(1024 * sizeof *small);

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
    Keith Thompson, Aug 2, 2004
    #7
  8. someone else

    Default User Guest

    Jack Klein wrote:

    > No, most experienced C programmers would use the superior code:
    >
    > mystruct *small = malloc(1024 * sizeof *mystruct);



    Well, let's say experienced programmers that read comp.lang.c anyway. I
    hadn't and probably wouldn't ever have come up with that style on my
    own, although I recognized its utility as soon as it was presented here.




    Brian Rodenborn
    Default User, Aug 2, 2004
    #8
  9. someone else

    Malcolm Guest

    "Jack Klein" <> wrote in message
    >
    > > However this is not really much improvement, because internally

    realloc()
    > > usually allocates a new area of memory and then copies.

    >
    > Maybe it does, maybe it does not. In any case, even if it does
    > require copying it is quite possible that it will use a mechanism more
    > efficient than the OP's for loop.
    >

    In practise realloc() will usually be obliged to perform a copy.
    The OP's for loop is a very basic operation. Whilst there are no guarantees,
    this virtually always compiles to a tight processor loop. The important
    thing is that the malloc() / realloc() looks superfically as if it might be
    more efficient than the for loop, but in fact this is an illusion. Big O
    analysis and underlying efficiency won't change much, at most you might get
    a few percentage points improvement because realloc() doesn't always call
    memcpy(), and if memcpy() is slightly faster than native C.

    > > If you absolutely need an array which can be extended quickly, your only
    > > option is to use a more complicated structure.

    >
    > That's very nice, but it has nothing at all to do with arrays.
    >

    It does tell the OP how to achieve his goal using an algorithm that does not
    require a copy operation for every item in the container object (whatever
    you wnat to call it, most people would say "smart array").
    Malcolm, Aug 2, 2004
    #9
  10. someone else

    Malcolm Guest

    "Jack Klein" <> wrote in message
    >
    > No, most experienced C programmers would use the superior code:
    >
    > mystruct *small = malloc(1024 * sizeof *mystruct);
    >

    The problem is that, unless you are a C programmer, "sizeof *small" is
    gibberish, whilst sizeof( mystruct ) has a clear meaning.
    And when you write gibberish, even experienced C programmers sometimes slip
    up.
    Malcolm, Aug 2, 2004
    #10
  11. someone else

    -berlin.de Guest

    Malcolm <> wrote:

    > "Jack Klein" <> wrote in message
    >>
    >> No, most experienced C programmers would use the superior code:
    >>
    >> mystruct *small = malloc(1024 * sizeof *mystruct);
    >>

    > The problem is that, unless you are a C programmer, "sizeof *small" is
    > gibberish, whilst sizeof( mystruct ) has a clear meaning.


    BS. Why should you read C programs when you're not a C programmer?
    With that argument you wouldn't be allowed to use any constructs
    at all that aren't used in exactly the same way in all other
    programming languages. And then one could further argue that all
    programming languages are "gibberish" to most non-programmers...

    Regards, Jens
    --
    \ Jens Thoms Toerring ___ -berlin.de
    \__________________________ http://www.toerring.de
    -berlin.de, Aug 2, 2004
    #11
  12. someone else

    Default User Guest

    Malcolm wrote:

    > The problem is that, unless you are a C programmer, "sizeof *small" is
    > gibberish, whilst sizeof( mystruct ) has a clear meaning.


    If you aren't a C programmer, then a lot of it will be gibberish. Why,
    in that event, would you care?




    Brian Rodenborn
    Default User, Aug 2, 2004
    #12
  13. someone else

    Malcolm Guest

    <-berlin.de> wrote
    >
    > BS. Why should you read C programs when you're not a C programmer?
    >

    Because you program in another language, but you did C as a undergraduate
    course years ago, and now there a program you want to read for some reason.
    >
    > With that argument you wouldn't be allowed to use any constructs
    > at all that aren't used in exactly the same way in all other
    > programming languages. And then one could further argue that all
    > programming languages are "gibberish" to most non-programmers...
    >

    The point is that a construct which is meaningful in English is to be
    preferred to one that is meaningful only in C, other things being equal,
    because even C programmers think in English most of the time.
    Malcolm, Aug 2, 2004
    #13
  14. someone else

    -berlin.de Guest

    Malcolm <> wrote:

    > <-berlin.de> wrote
    >>
    >> BS. Why should you read C programs when you're not a C programmer?
    >>

    > Because you program in another language, but you did C as a undergraduate
    > course years ago, and now there a program you want to read for some reason.
    >>
    >> With that argument you wouldn't be allowed to use any constructs
    >> at all that aren't used in exactly the same way in all other
    >> programming languages. And then one could further argue that all
    >> programming languages are "gibberish" to most non-programmers...
    >>

    > The point is that a construct which is meaningful in English is to be
    > preferred to one that is meaningful only in C, other things being equal,


    No, you should use the construct that's best suited to the job
    at hand. And all things taken into account (i.e. also maintaina-
    bility) the "non-English" construct tends to be better because
    it can help you avoiding certain mistakes when the program gets
    changed. That's IMHO more important than using a worse construct
    just for the benefit of a hypothetical non-C-programmer trying
    to read the program.

    > because even C programmers think in English most of the time.


    Well, I usually don't think in English, having had a hard enough
    time to learn it as the mistakes I still make constantly probably
    show...
    Regards, Jens
    --
    \ Jens Thoms Toerring ___ -berlin.de
    \__________________________ http://www.toerring.de
    -berlin.de, Aug 2, 2004
    #14
  15. someone else

    Malcolm Guest

    <-berlin.de> wrote in message
    >
    > > The point is that a construct which is meaningful in English is to be
    > > preferred to one that is meaningful only in C, other things being equal,

    >
    > No, you should use the construct that's best suited to the job
    > at hand. And all things taken into account (i.e. also maintaina-
    > bility) the "non-English" construct tends to be better because
    > it can help you avoiding certain mistakes when the program gets
    > changed. That's IMHO more important than using a worse construct
    > just for the benefit of a hypothetical non-C-programmer trying
    > to read the program.
    >

    I'm not hung up on this. For instance the y = x ? 1 : 0 is a C contruct
    ("gibberish") whilst

    if(x == 0)
    y = 0;
    else
    x = 1;

    is meaningful to most programmers, though even here the double equals sign
    cannot be avoided.
    However if we have a huge long list of conditional assignments, and using
    the ternary operator makes the pattern clear whilst the if ... else
    construct is long-winded, because it is four lines, I will happily go for
    the former.

    However the fact that if ... else has an obvious English language meaning is
    a point in its favour, its not an advantage you should ignore.

    I'd also say it is a significant point in its favour. There is an argument
    for the size *ptr form being more maintainable, if the type of the pointer
    changes. However in my opinion this benefit is not enough to outweigh the
    disadvantage of the code being less readable.
    >
    > > because even C programmers think in English most of the time.

    >
    > Well, I usually don't think in English, having had a hard enough
    > time to learn it as the mistakes I still make constantly probably
    > show...
    >

    That's another issue. C is an English programming language, and if your
    first language isn't English then of course a word like "break" might not be
    very meaningful to you.
    Malcolm, Aug 2, 2004
    #15
  16. On Mon, 2 Aug 2004, Malcolm wrote:
    >
    > <-berlin.de> wrote
    >> With that argument you wouldn't be allowed to use any constructs
    >> at all that aren't used in exactly the same way in all other
    >> programming languages. And then one could further argue that all
    >> programming languages are "gibberish" to most non-programmers...

    >
    > The point is that a construct which is meaningful in English is to be
    > preferred to one that is meaningful only in C, other things being equal,
    > because even C programmers think in English most of the time.


    But your original complaint was about 'sizeof *small' versus
    'sizeof(int)'; you preferred the latter, whereas it's the former
    that is actually composed of English words. (It is also more
    useful, since it describes the algorithm on a higher level --- the
    code is allocating space for some number of 'small' elements.
    'int' has nothing to do with it, except for the coincidence that
    'small' happens to be a pointer to 'int'.)

    In short: Your position is completely bogus. C is not English;
    yet even if we pretend that it /is/, 'sizeof *small' is /still/
    more descriptive!

    -Arthur
    Arthur J. O'Dwyer, Aug 3, 2004
    #16
  17. someone else

    CBFalconer Guest

    Default User wrote:
    > Malcolm wrote:
    >
    >> The problem is that, unless you are a C programmer, "sizeof *small"
    >> is gibberish, whilst sizeof( mystruct ) has a clear meaning.

    >
    > If you aren't a C programmer, then a lot of it will be gibberish.
    > Why, in that event, would you care?


    If the source is C the odds are high (as compared to other
    languages other than C++) that it will be gibberish to even a C
    programmer without study and thought. Depending on your
    viewpoint, this is either a feature or a failing of the language.
    :)

    --
    "I'm a war president. I make decisions here in the Oval Office
    in foreign policy matters with war on my mind." - Bush.
    "Churchill and Bush can both be considered wartime leaders, just
    as Secretariat and Mr Ed were both horses." - James Rhodes.
    CBFalconer, Aug 3, 2004
    #17
  18. Malcolm wrote:

    > For instance the y = x ? 1 : 0 is a C contruct
    > ("gibberish") whilst
    >
    > if(x == 0)
    > y = 0;
    > else
    > x = 1;


    itym y = 1

    >
    > is meaningful to most programmers,



    Christian
    Christian Kandeler, Aug 3, 2004
    #18
  19. someone else

    Richard Bos Guest

    "Malcolm" <> wrote:

    > "Jack Klein" <> wrote in message
    >
    > > No, most experienced C programmers would use the superior code:
    > >
    > > mystruct *small = malloc(1024 * sizeof *mystruct);

    >
    > The problem is that, unless you are a C programmer, "sizeof *small" is
    > gibberish,


    Unless you are a C programmer, _malloc_ is gibberish.

    Richard
    Richard Bos, Aug 3, 2004
    #19
  20. someone else

    Default User Guest

    CBFalconer wrote:
    >
    > Default User wrote:
    > > Malcolm wrote:
    > >
    > >> The problem is that, unless you are a C programmer, "sizeof *small"
    > >> is gibberish, whilst sizeof( mystruct ) has a clear meaning.

    > >
    > > If you aren't a C programmer, then a lot of it will be gibberish.
    > > Why, in that event, would you care?

    >
    > If the source is C the odds are high (as compared to other
    > languages other than C++) that it will be gibberish to even a C
    > programmer without study and thought. Depending on your
    > viewpoint, this is either a feature or a failing of the language.
    > :)



    Exactly. I can certainly support avoiding obfuscated programming
    constructs, but there's nothing that should cause anyone qualified to
    read the program much of a halt. It might be a new idiom to some people,
    but that shouldn't cause them much distress. Perhaps a quick read of the
    properties of the sizeof operator, but that's not a bad thing.



    Brian Rodenborn
    Default User, Aug 3, 2004
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. jdonnell
    Replies:
    9
    Views:
    297
    Peter Hansen
    Sep 2, 2005
  2. Paul Rubin
    Replies:
    5
    Views:
    416
    Hendrik van Rooyen
    Aug 6, 2009
  3. jerry
    Replies:
    13
    Views:
    847
    Malcolm McLean
    Oct 1, 2011
  4. Pil (Trustworthy from Experience)

    Resizing a div by resizing its borders

    Pil (Trustworthy from Experience), Apr 18, 2009, in forum: Javascript
    Replies:
    9
    Views:
    348
    Proper
    Apr 21, 2009
  5. Proper
    Replies:
    0
    Views:
    197
    Proper
    Apr 18, 2009
Loading...

Share This Page