# Dynamic Array

Discussion in 'C Programming' started by Ronny Mandal, Apr 17, 2005.

1. ### Ronny MandalGuest

Assume that you want to store n records in an array, and that the array can
hold all n elements, that is, it is declared int a[n].

And suddenlny in run-time, I need to store n+m items. Why cannot this be
done:

a[0] = e(0)
a[1] = e(1)
...
...
a[n] = e(n)

where e(i) is the i-th element

*(a+ (n+1) ) = e(the 1st element after n)
...
...
*(a+ (n+1) ) = e(the m-th element after n)

On the ocntrary, if I allocate an array with 0 elements a[0], C will let me
fill in approx 5 more values.

Is there a way to make the "index-table" of an array grow?

--

Thanks

Ronny Mandal

This e-mail and any attachment are confidential and may be privileged or
otherwise protected from disclosure. It is solely intended for the person(s)
named above. If you are not the intended recipient, any reading, use,
disclosure, copying or distribution of all or parts of this e-mail or
associated attachments is strictly prohibited. If you are not an intended
or by telephone and delete this e-mail and any attachments permanently from

Ronny Mandal, Apr 17, 2005

2. ### Walter RobersonGuest

In article <d3u5tq\$pvu\$>,
Ronny Mandal <> wrote:
>Assume that you want to store n records in an array, and that the array can
>hold all n elements, that is, it is declared int a[n].

>And suddenlny in run-time, I need to store n+m items. Why cannot this be
>done:

>*(a+ (n+1) ) = e(the 1st element after n)

Because when you declare int a[n] (presuming that n has
been #define'd with a constant value) then you are telling
C to reserve -exactly- n locations to store integers, and
you are telling C that it is fine to store whatever it needs to
in the location after that.

If you want *anything* in C to be dynamically sized, then you
must use malloc() or alloc() or the equivilent. Each malloc()
request will grant the amount of storage that you requested
in the call, and you can't store beyond that without undefined
behaviour. However, malloc() allows you to pass in a size
at run-time rather than the fixed sizes that C requires at -compile-
time for [] arrays.

If you are using dynamic memory as an array, and you find you
need more locations in the array, then you can use realloc()
not necessarily extend the array "in place": instead, if necessary,
it will create a new object with the larger size, copy the
contents of the old object to the new one, and return the address
of the new one. Which is fine unless you happened to have been
taking pointers to the old object before, because those pointers
might not be valid anymore...

If you need the effect of dynamic arrays and you need the location
of any one element not to change after you allocate it and you
need to be able to grow the array, then you need to use a techique
such as linked lists or binary trees, or 2-3 trees, or tries; or
you could find one of the several pre-written "sparse array"
implementations and use them without worrying about what's under
the hood.
--
"No one has the right to destroy another person's belief by
demanding empirical evidence." -- Ann Landers

Walter Roberson, Apr 17, 2005

3. ### Daniel CerGuest

You might want to have a look at realloc().

If you have an array 'a' that was already allocated using malloc,
realloc() allows you to dynamically resize the amount of memory
allocated to 'a' (i.e. in this case, effectively resizing the array).
For example, assume that 'a' was allocated using the following code:

int *a;

if (!(a = malloc(sizeof(int)*N))) {
/* some out of memory error handling code */
}

You could then operate on 'a' in the same manner you would use if 'a'
was allocated on the stack using "int a[N];". e.g.:

/* some random code using the just allocated array */
for (i = 0; i < N; i++) { a = i; }

Then if you later need to resize 'a' so that it has M elements you could
use the following:

if (!(a = realloc(a, sizeof(int)*M))) {
/* some out of memory error handling code */
}

After calling realloc, you would then be free to use indices in the
range of 0..(M-1).

/* some more random code using the just reallocated array*/
for (i = N; i < M; i++) { a = i; }

Hope that helps

-Dan

Ronny Mandal wrote:
> Assume that you want to store n records in an array, and that the array can
> hold all n elements, that is, it is declared int a[n].
>
> And suddenlny in run-time, I need to store n+m items. Why cannot this be
> done:
>
> a[0] = e(0)
> a[1] = e(1)
> ...
> ...
> a[n] = e(n)
>
> where e(i) is the i-th element
>
>
> *(a+ (n+1) ) = e(the 1st element after n)
> ...
> ...
> *(a+ (n+1) ) = e(the m-th element after n)
>
> On the ocntrary, if I allocate an array with 0 elements a[0], C will let me
> fill in approx 5 more values.
>
> Is there a way to make the "index-table" of an array grow?
>
>

Daniel Cer, Apr 17, 2005
4. ### Jack KleinGuest

On Sun, 17 Apr 2005 19:22:02 +0200, "Ronny Mandal"
<> wrote in comp.lang.c:

> Assume that you want to store n records in an array, and that the array can
> hold all n elements, that is, it is declared int a[n].
>
> And suddenlny in run-time, I need to store n+m items. Why cannot this be
> done:
>
> a[0] = e(0)
> a[1] = e(1)
> ..
> ..
> a[n] = e(n)
>
> where e(i) is the i-th element
>
>
> *(a+ (n+1) ) = e(the 1st element after n)
> ..
> ..
> *(a+ (n+1) ) = e(the m-th element after n)
>
> On the ocntrary, if I allocate an array with 0 elements a[0], C will let me

If your compiler compiles a program defining an array of [0] elements,
it is not a C compiler. At least not the way you are invoking it.
You may think it is compiling C, but in fact it is compiling a C-like
language with its own non-standard extensions.

It is a constraint violation for an array to be defined with a size of
less than 1 element, and a real C compiler must issue a diagnostic for
this.

--
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, Apr 18, 2005
5. ### Ronny MandalGuest

Thanks, your solution really worked, except that realloc() is a void*
function, the program crashed when I tried to assign its "output" to a,
which was the original array.

RM.

Ronny Mandal, Apr 18, 2005
6. ### Mark McIntyreGuest

On Mon, 18 Apr 2005 23:17:27 +0200, in comp.lang.c , "Ronny Mandal"
<> wrote:

>Thanks, your solution really worked, except that realloc() is a void*
>function,

This isn't going to cause any problems

>the program crashed when I tried to assign its "output" to a,
>which was the original array.

if a was a real array (as oppose to a pointer to something), you can't
assign to them. You've snipped too much context to be sure tho.

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>

Mark McIntyre, Apr 18, 2005
7. ### Chris CroughtonGuest

On Mon, 18 Apr 2005 23:17:27 +0200, Ronny Mandal
<> wrote:

> Thanks, your solution really worked, except that realloc() is a void*
> function, the program crashed when I tried to assign its "output" to a,
> which was the original array.

The output of realloc should always be assigned to a temporary variable
which can be tested, because if it fails (insufficient memory for
instance) the original memory will still be allocated and need to be
freed. Something like

{
void *anew = realloc(a, size);
if (anew)
{
a = anew;
}
else
{
/* some error handling */
}
}

That way you can also put in traces to see what the values are before
assigning them.

How do you know that your program crashed when you tried to assign,
could it have crashed in realloc? It's best to post your code (as small
as possible which produces the problem) so we can see what you are
doing.

Chris C

Chris Croughton, Apr 19, 2005
8. ### Daniel CerGuest

Good advise. However, I think "always" is a little strong.

For example, in the case of a small command line utility, running out of
memory is pretty much "game over", where by the only thing left to do is
print out an "out of memory" error message and then exit the program.
So, in this case, it's not totally unreasonable to have code like the
following:

if (!(a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(OUT_OF_MEM_ERROR_CODE);
}

However, for more substantial applications, e.g. something that acts as
a server, or most interactive applications, then, yeah, it's a good idea
to check the return value of 'realloc' before overwriting the original
value. That way, it's possible to gracefully recover from an operation
that would have exhausted available memory, rather than just exiting the
program.

-Dan

Chris Croughton wrote:
> On Mon, 18 Apr 2005 23:17:27 +0200, Ronny Mandal
> <> wrote:
>
>
>>Thanks, your solution really worked, except that realloc() is a void*
>>function, the program crashed when I tried to assign its "output" to a,
>>which was the original array.

>
>
> The output of realloc should always be assigned to a temporary variable
> which can be tested, because if it fails (insufficient memory for
> instance) the original memory will still be allocated and need to be
> freed. Something like
>
> {
> void *anew = realloc(a, size);
> if (anew)
> {
> a = anew;
> }
> else
> {
> /* some error handling */
> }
> }
>
> That way you can also put in traces to see what the values are before
> assigning them.
>
> How do you know that your program crashed when you tried to assign,
> could it have crashed in realloc? It's best to post your code (as small
> as possible which produces the problem) so we can see what you are
> doing.
>
> Chris C

Daniel Cer, Apr 20, 2005
9. ### Chris CroughtonGuest

On Wed, 20 Apr 2005 12:56:54 -0600, Daniel Cer
<> wrote:

(Post re-ordered so that it makes sense, please don't top-post!)

> Chris Croughton wrote:
>>
>> The output of realloc should always be assigned to a temporary variable
>> which can be tested, because if it fails (insufficient memory for
>> instance) the original memory will still be allocated and need to be
>> freed. Something like
>>
>> {
>> void *anew = realloc(a, size);
>> if (anew)
>> {
>> a = anew;
>> }
>> else
>> {
>> /* some error handling */
>> }
>> }
>>
>> That way you can also put in traces to see what the values are before
>> assigning them.
>>

> Good advise. However, I think "always" is a little strong.

What have I said before about absolute generalisations? Something like
"they're always wrong"? <g>

> For example, in the case of a small command line utility, running out of
> memory is pretty much "game over", where by the only thing left to do is
> print out an "out of memory" error message and then exit the program.

Yup.

> So, in this case, it's not totally unreasonable to have code like the
> following:
>
> if (!(a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*size))) {
> fprintf(stderr, "Fatal error: Out of memory!\n");
> exit(OUT_OF_MEM_ERROR_CODE);
> }

Although you can't guarantee that the fprintf will even work (it might
need to allocate a buffer). But yes, in many cases with simple
command-line utilities the only thing you can do is to give up, try to
display some message and exit.

Although even there I would want to free the existing memory first, to
give fprintf a better chance of succeeding:

{
void *anew = realloc(a, size);
if (!anew)
{
free(a);
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(OUT_OF_MEM_ERROR_CODE);
}
a = anew;
/* ... */
}

Incidentally, two things:

It is not necessary to cast the result of realloc(). Doing so often

There are only two defined values for the exit() function, anything
else is non-portable.

> However, for more substantial applications, e.g. something that acts as
> a server, or most interactive applications, then, yeah, it's a good idea
> to check the return value of 'realloc' before overwriting the original
> value. That way, it's possible to gracefully recover from an operation
> that would have exhausted available memory, rather than just exiting the
> program.

As I indicate, it is anyway, or at least to make it more likely that the
error message gets out.

Chris C

Chris Croughton, Apr 20, 2005
10. ### Daniel CerGuest

>>So, in this case, it's not totally unreasonable to have code like the
>>following:
>>
>> if (!(a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*size))) {
>> fprintf(stderr, "Fatal error: Out of memory!\n");
>> exit(OUT_OF_MEM_ERROR_CODE);
>> }

>
>
> Although you can't guarantee that the fprintf will even work (it might
> need to allocate a buffer). But yes, in many cases with simple
> command-line utilities the only thing you can do is to give up, try to
> display some message and exit.
>
> Although even there I would want to free the existing memory first, to
> give fprintf a better chance of succeeding:
>
> {
> void *anew = realloc(a, size);
> if (!anew)
> {
> free(a);
> fprintf(stderr, "Fatal error: Out of memory!\n");
> exit(OUT_OF_MEM_ERROR_CODE);
> }
> a = anew;
> /* ... */
> }

Yeah, but I would point out that with code like (1), using realloc,
you're not really any worse off than with code like (2), using the more
standard malloc idiom:

(1)

if (!(a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*new_size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
}

(2)

if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
}

In both cases, if you're afraid of fprintf() not having enough memory to
do it's job, then, of course, the thing to do is to free up some memory
before making the call. But, 'a' might just point to a particularly
miniscule chuck of memory, so freeing it alone might not be too helpful.

With that in mind, technically, shouldn't each of the above be changed
to something more like the following?

(3)

if (!(new_a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*new_size))) {
free(a);
/* some code free()-ing anything else we can get * /
free(some_big_array);
/* and */
fclose(some_file_handle);
fclose(some_other_file_handle);
....

fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
} new_a = a;

(4)

if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
/* some code free()-ing anything else we can get * /
free(some_big_array);
/* and */
fclose(some_file_handle);
fclose(some_other_file_handle);
....

fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_SUCCESS);
}

>
> Incidentally, two things:
>
> It is not necessary to cast the result of realloc(). Doing so often

Unless, you're planning on moving any of the source code to C++ at some
point. In which case, the compiler will generate an error like "cannot
convert `void *' to `int *' in assignment".

>
> There are only two defined values for the exit() function, anything
> else is non-portable.
>

Non-portable to non Unix-like systems.

Also, on many Unix based/like systems, you can make use of the
standardized error codes in sysexits.h. But, since many != all, this is
non-portable even between Unix like systems.

-Dan

Daniel Cer, Apr 21, 2005
11. ### Chris CroughtonGuest

On Wed, 20 Apr 2005 19:20:40 -0600, Daniel Cer
<> wrote:

> Yeah, but I would point out that with code like (1), using realloc,
> you're not really any worse off than with code like (2), using the more
> standard malloc idiom:
>
> (1)
>
> if (!(a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*new_size))) {
> fprintf(stderr, "Fatal error: Out of memory!\n");
> exit(EXIT_SUCCESS);
> }
>
> (2)
>
> if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
> fprintf(stderr, "Fatal error: Out of memory!\n");
> exit(EXIT_SUCCESS);
> }
>
> In both cases, if you're afraid of fprintf() not having enough memory to
> do it's job, then, of course, the thing to do is to free up some memory
> before making the call. But, 'a' might just point to a particularly
> miniscule chuck of memory, so freeing it alone might not be too helpful.

It might or might not (it might not point to anything at all, of course,
passing a null pointer to realloc is valid).

> With that in mind, technically, shouldn't each of the above be changed
> to something more like the following?
>
> (3)
>
> if (!(new_a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*new_size))) {
> free(a);
> /* some code free()-ing anything else we can get * /
> free(some_big_array);
> /* and */
> fclose(some_file_handle);
> fclose(some_other_file_handle);
> ....
>
> fprintf(stderr, "Fatal error: Out of memory!\n");
> exit(EXIT_SUCCESS);
> } new_a = a;

ITYM a = new_a;

Yes, indeed, and I've known some programs which deliberately allocate a
large chunk of memory at the start just so that they can free it if they
do run out of memory later before they try to do tidying up.

> (4)
>
> if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
> /* some code free()-ing anything else we can get * /
> free(some_big_array);

But in that case you won't be freeing a, and that might be the biggest
bit of memory you have.

>> Incidentally, two things:
>>
>> It is not necessary to cast the result of realloc(). Doing so often

>
> Unless, you're planning on moving any of the source code to C++ at some
> point. In which case, the compiler will generate an error like "cannot
> convert `void *' to `int *' in assignment".

If you're using C++ you should be using new and delete instead of malloc
and free <g>.

>> There are only two defined values for the exit() function, anything
>> else is non-portable.

>
> Non-portable to non Unix-like systems.

As I said, non-portable. Non-portable isn't necessarily bad, there are
many cases where it is necessary to use some non-portable features, but
it is best to keep such things in a few system-dependent modules so they
can be seen and changed easily in isolation.

> Also, on many Unix based/like systems, you can make use of the
> standardized error codes in sysexits.h. But, since many != all, this is
> non-portable even between Unix like systems.

(like a shell script) it can't depend on them either. Since they are
constants defined in a system implementation file, the documentation of
the program won't be able to say what they are either, so they are
pretty near useless. For instance, I can document a program as
returning:

0: success
1: user error
2: unable to open input
3: unable to create output

etc., and then use it in a script, but if it's

EX_USAGE user error
EX_NOINPUT unable to open input
EX_CANTCREAT unable to create output

etc. then I'd have to try to find syserror.h in some system include
directory and rewrite the script for each system (or even each compiler
version on the system, potentially). The only system I know where such
things worked was VMS, where return values are registered with the
system and everything uses the same mechanism (they also include
severity and program identification in the result). Unix is far too
anarchic for that sort of thing to work.

EXIT_SUCCESS and EXIT_FAILURE are the only values which are guaranteed
to be returned to the system at all on exit (and there's no guarantee
that the system will make those available to any other program, but if
you can't test for success by exit value in a system then it doesn't
matter what you return).

Chris C

Chris Croughton, Apr 21, 2005
12. ### Keith ThompsonGuest

Chris Croughton <> writes:
> On Wed, 20 Apr 2005 19:20:40 -0600, Daniel Cer
> <> wrote:

[...]
>> Also, on many Unix based/like systems, you can make use of the
>> standardized error codes in sysexits.h. But, since many != all, this is
>> non-portable even between Unix like systems.

>
> And since nothing running the program has access to those constants
> (like a shell script) it can't depend on them either.

[snip]

The thing running the program could well be another C program that has
a "#include <sysexits.h>". Or it could be a script that invokes a
small C program to interpret the exit codes.

--
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, Apr 21, 2005
13. ### Gregory PietschGuest

Ronny Mandal wrote:
> Assume that you want to store n records in an array, and that the

array can
> hold all n elements, that is, it is declared int a[n].
>
> And suddenlny in run-time, I need to store n+m items. Why cannot this

be
> done:
>
> a[0] = e(0)
> a[1] = e(1)
> ..
> ..
> a[n] = e(n)
>
> where e(i) is the i-th element
>
>
> *(a+ (n+1) ) = e(the 1st element after n)
> ..
> ..
> *(a+ (n+1) ) = e(the m-th element after n)
>
> On the ocntrary, if I allocate an array with 0 elements a[0], C will

let me
> fill in approx 5 more values.
>
> Is there a way to make the "index-table" of an array grow?

Seems to me you need dynamic array code. Get FreeDOS edlin and borrow
it.

Gregory Pietsch

>
>
> --
>
> Thanks
>
> Ronny Mandal
>
>
> This e-mail and any attachment are confidential and may be privileged

or
> otherwise protected from disclosure. It is solely intended for the

person(s)
> named above. If you are not the intended recipient, any reading, use,

> disclosure, copying or distribution of all or parts of this e-mail or

> associated attachments is strictly prohibited. If you are not an

intended

message
> or by telephone and delete this e-mail and any attachments

permanently from

Gregory Pietsch, Apr 22, 2005
14. ### Daniel CerGuest

Daniel Cer wrote:
>
>
> Yeah, but I would point out that with code like (1), using realloc,
> you're not really any worse off than with code like (2), using the more
> standard malloc idiom:
>
> (1)
>
> if (!(a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*new_size))) {
> fprintf(stderr, "Fatal error: Out of memory!\n");
> exit(EXIT_SUCCESS);
> }
>
> (2)
>
> if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
> fprintf(stderr, "Fatal error: Out of memory!\n");
> exit(EXIT_SUCCESS);
> }
>

Sorry, to reply to my own post, but I noticed that for some bizarre
reason I used EXIT_SUCCESS instead of EXIT_FAILURE as the argument to
exit() when the system runs out of memory.

I'm actually semi-surprised nobody called me on that

Anyhow, just in case anybody comes across this post later,all of the
"exit(EXIT_SUCCESSS);" statements should be changed to
"exit(EXIT_FAILURE);".

This goes for both for (1) & (2) above and (3) & (4) below.

-Dan

> (3)
>
> if (!(new_a = (TYPE_OF_A*)realloc(a, sizeof(TYPE_OF_A)*new_size))) {
> free(a);
> /* some code free()-ing anything else we can get * /
> free(some_big_array);
> /* and */
> fclose(some_file_handle);
> fclose(some_other_file_handle);
> ....
>
> fprintf(stderr, "Fatal error: Out of memory!\n");
> exit(EXIT_SUCCESS);
> } new_a = a;
>
> (4)
>
> if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
> /* some code free()-ing anything else we can get * /
> free(some_big_array);
> /* and */
> fclose(some_file_handle);
> fclose(some_other_file_handle);
> ....
>
> fprintf(stderr, "Fatal error: Out of memory!\n");
> exit(EXIT_SUCCESS);
> }
>
>>

Daniel Cer, Apr 24, 2005
15. ### Daniel CerGuest

Chris Croughton wrote:
>>(4)
>>
>>if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
>> /* some code free()-ing anything else we can get * /
>> free(some_big_array);

>
>
> But in that case you won't be freeing a, and that might be the biggest
> bit of memory you have.
>
>

The code in (4) was only suppose to contrast with (2), reproduced below.

(2)

if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_FAILURE);
}

That is, assuming no memory has been allocated for 'a' yet, how can
someone write code that will try to allocate some memory, such that if
not enough memory is available, then the program will exit and display
an "Out of memory" error message. Sorry, if my original message somehow
wasn't clear on that point. The code in (1) and (3) where given for the
case where 'a' actually points to something,.

Anyhow, for something like this, I've seen a fair amount code (prehaps
naively written code) that just looks something like (2). However, given
your point that if the program can't allocate any more memory, there
might not be enough memory for fprintf() to execute sucessfully, the
code in (4) was put forth as a more proper solution. That is, if
possible, a program should free other dynamically allocated memory
before making the call to fprintf().

-Dan

Daniel Cer, Apr 24, 2005
16. ### CBFalconerGuest

Daniel Cer wrote:
>

.... snip ...
>
> The code in (4) was only suppose to contrast with (2), reproduced below.
>
> (2)
>
> if (!(a = (TYPE_OF_A*)malloc(sizeof(TYPE_OF_A)*size))) {
> fprintf(stderr, "Fatal error: Out of memory!\n");
> exit(EXIT_FAILURE);
> }

Which should be written (all casts are suspicious):

if (!(a = malloc(size * sizeof(*a)))) {
fprintf(stderr, "Fatal error: Out of memory!\n");
exit(EXIT_FAILURE);
}

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the