resizing an array, is there a better way?

[someone else]

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

 

[Jens.Toerring]

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

 

[someone else]

thanks jens

i wasn't sure if realloc preserves the data...

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

 

[Malcolm]

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.

 

[Jack Klein]

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]

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.

 

[Keith Thompson]

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

 

[Default User]

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

 

[Malcolm]

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.

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]

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.

 

[Jens.Toerring]

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

 

[Default User]

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

 

[Malcolm]

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.

 

[Jens.Toerring]

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.
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

 

[Malcolm]

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.

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.

 

[Arthur J. O'Dwyer]

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

 

[CBFalconer]

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.

 

[Christian Kandeler]

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

 

[Richard Bos]

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

Unless you are a C programmer, _malloc_ is gibberish.

Richard

 

[Default User]

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