Velocity Reviews > Dynamic Array

Dynamic Array

Ronny Mandal
Guest
Posts: n/a

 04-17-2005
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

Walter Roberson
Guest
Posts: n/a

 04-17-2005
In article <d3u5tq\$pvu\$(E-Mail Removed)>,
Ronny Mandal <(E-Mail Removed)> 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

Daniel Cer
Guest
Posts: n/a

 04-17-2005
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] = 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] = 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?
>
>

Jack Klein
Guest
Posts: n/a

 04-18-2005
On Sun, 17 Apr 2005 19:22:02 +0200, "Ronny Mandal"
<(E-Mail Removed)> 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/~a...FAQ-acllc.html

Ronny Mandal
Guest
Posts: n/a

 04-18-2005
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.

Mark McIntyre
Guest
Posts: n/a

 04-18-2005
On Mon, 18 Apr 2005 23:17:27 +0200, in comp.lang.c , "Ronny Mandal"
<(E-Mail Removed)> 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>

Chris Croughton
Guest
Posts: n/a

 04-19-2005
On Mon, 18 Apr 2005 23:17:27 +0200, Ronny Mandal
<(E-Mail Removed)> 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
Guest
Posts: n/a

 04-20-2005
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
> <(E-Mail Removed)> 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
Guest
Posts: n/a

 04-20-2005
On Wed, 20 Apr 2005 12:56:54 -0600, Daniel Cer
<(E-Mail Removed)> 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

Daniel Cer
Guest
Posts: n/a

 04-21-2005
>>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