Discussion on Dynamic Arrays

[MistahMoose]

"A Dynamic Array is an Array whose size is not specified when you write the program, but is determined while the program is running" - Savitch

Short Question: What are various ways where you would use a dynamic array vs an automatic array?
(I know a few, but limited knowledge as of now)

Below is what would be called "Variable-Length Array". They are allocated at Run-Time, or while the program is running, but otherwise works exactly like Automatic Arrays.

#include <iostream>
using namespace std;

int main()
{
    int SIZE;
    cin >> SIZE;//get array size
    int arr[SIZE];
    
    for(int i = 0; i <SIZE; i++)//fill array
    {
        arr[i] = 1;
    }

    
    for(int i = 0; i <SIZE; i++)//print array
    {
        cout << arr[i];
    }
    
    return 0;
}

Now compare that to a dynamically allocated array. Which are created and destroyed while the program is running, rather than at program beginning and end.

#include <iostream>
using namespace std;


int main ()
{
    int *Array;
    int SIZE;
    cin >> SIZE;
    Array = new int[SIZE];
    
    for(int i = 0; i <SIZE; i++)//fill Arrayay
    {
        Array[i] = 1;
    }

    
    for(int i = 0; i <SIZE; i++)//print Array
    {
        cout << Array[i];
    }
    
    delete [] Array;//Good practice, but unneeded since program terminates, 
    return 0;

}

When reading about Dynamic arrays it is often said to use them when "You don't know how large of an array you want" or something along those lines.

However as shown above this is accomplished through a relatively similar way with a variable length array (A dynamically allocated array can also have a set size, which further displaces it from the "You don't know how large an array you want" saying).

The main difference I see between how we utilize these arrays are how we handle memory allocation.

I'm trying to wrap my head around what is the best way to utilize each type of array.

Automatic Array, Used when you know exactly how large of an array you want, and use the array throughout the program.

Variable length Array, Used when you don't know exactly how large an array you want, and use the array throughout the program.

Dynamically Allocated Array, Used when you do not need to use an array throughout the whole program. Or when you need to return an Array from a function

The biggest reason I see myself using a dynamically allocated array is if I needed to pass back the whole array from a function. Other than that, What stops me from using a Variable Length array?

[keskiverto]

The C++ Standard? (No, it doesn't stop anyone. It simply does not support you on that path.)

Lacking compiler support for non-standard feature? (No, you use the compiler with most toys.)

Size of stack memory? (Perhaps, if it is limited, but does the compiler use stack for VLA?)


This, naturally, is not the way to do things:

#include <vector>
#include <iostream>

int main()
{
    int SIZE;
    cin >> SIZE;//get array size
    std::vector<int> arr(SIZE);
    
    for(int i = 0; i <SIZE; i++)//fill array
    {
        arr[i] = 1;
    }

    
    for(int i = 0; i <SIZE; i++)//print array
    {
        std::cout << arr[i];
    }
    
    return 0;
}

Or is it?

[MistahMoose]

So how you utilize different array types only really becomes a factor when you start to adhere to a coding standard?

There isn't a right from wrong so long as it works(Assuming you're not using a coding standard), Just a better or worse way?

So long as I know how to utilize the different types of arrays I guess I'll learn when to do which and how i prefer to handle things.

I just have such a strong desire to know NOW.

Time to hit the books and try to start doing some more advanced stuff... See ya' when I break something :|

[freddie1]

What are various ways where you would use a dynamic array vs an automatic array?

Here would be an example from my line of work, which is forestry. One of my programs produces output such as this, which is referred to as a Stand Table...

                     Block #2 Board Foot Volume Per Acre For All Trees

Dbh       RM        RO        SO        WO        CO        BB        YP       Asp    Totals
============================================================================================
12        58         0        73         0       290       101         0       122       645
13         0        44         0        83       417       242         0        71       857
14        78        54       154        79       242        50         0         0       657
15         0        60        74         0        62        77         0         0       272
16         0        83         0         0       181         0         0         0       264
17         0         0        79         0         0        53         0         0       132
18         0         0         0         0       359         0       199         0       557
19         0         0         0         0        62         0         0         0        62
20         0         0         0         0       210         0         0         0       210
21         0         0         0         0         0         0         0         0         0
22         0        94         0         0         0         0         0         0        94
============================================================================================
         136       335       380       161      1823       524       199       194      3751


                         Block #2 Board Voot Volume For Live Trees

Dbh       RM        RO        SO        WO        CO        BB        YP       Asp    Totals
============================================================================================
12        58         0         0         0       235       101         0       122       517
13         0        44         0        83       417       242         0        71       857
14        78        54        74        79       242        50         0         0       577
15         0        60        74         0        62        77         0         0       272
16         0        83         0         0       181         0         0         0       264
17         0         0         0         0         0        53         0         0        53
18         0         0         0         0       359         0       199         0       557
19         0         0         0         0        62         0         0         0        62
20         0         0         0         0       210         0         0         0       210
21         0         0         0         0         0         0         0         0         0
22         0        94         0         0         0         0         0         0        94
============================================================================================
         136       335       148       161      1768       524       199       194      3463


                         Block #2 Board Voot Volume For Dead Trees

Dbh       RM        RO        SO        WO        CO        BB        YP       Asp    Totals
============================================================================================
12         0         0        73         0        55         0         0         0       128
13         0         0         0         0         0         0         0         0         0
14         0         0        80         0         0         0         0         0        80
15         0         0         0         0         0         0         0         0         0
16         0         0         0         0         0         0         0         0         0
17         0         0        79         0         0         0         0         0        79
18         0         0         0         0         0         0         0         0         0
19         0         0         0         0         0         0         0         0         0
20         0         0         0         0         0         0         0         0         0
21         0         0         0         0         0         0         0         0         0
22         0         0         0         0         0         0         0         0         0
============================================================================================
           0         0       232         0        55         0         0         0       287

The numbers in the first column are tree diameters (Diameter At Breast Height) and the letters across the top are species abbreviations. RM stands for Red maple, RO for Red oak, SO for Scarlet oak, WO for White oak, BB for Black birch, YP for Yellow poplar, and Asp for aspen.

Now, our (where I work) timber sales oftentimes contain thousands of marked trees. They are stored in a database. My programs must read and process that data and generate tables such as above. But the thing is, we have many timber sales, and each sale has different species and tree diameters. There are eight species in the batch of tables seen above, but our sales typically can have anywhere from about five species per timber sale to about 20 species. Also, the range of diameters represented by the above data is 12 tp 22 inches. Sometimes we have ranges of 10 to 50 inches.

You have to realize that the above tables represent data summaries. Each tree has to be read out of the database or file and have its specific board foot volume assigned to one of the cells in the above table. If you look at the top table you'll see a 58 in the cell for 12 inch Red maple. A 12 inch tree has about 50 to 60 board feet, so that number would represent only one tree. But in the middle or CO (Chestnut oak) column for 12 inch trees you see the number 290. That likely represents five or six trees. Where this fits in to your question about dynamic arrays is that to perform processing as such as I've described above to produce tables such as above, memory has to be dynamically allocated in exactly the right amount to contain the processed data. Before processing a timber sale one must run code to determine what the ranges of diameters are, and to determine how many distinct species codes are in a given sale. Once that number is determined, one can allocate the arrays of just the right size.

Note above that a tabular two dimensional table or matrix such as represented by those tables requires two dimensional arrays, which can be represented in C or C++ like so...

int iVolume[12][9];

As an aside, in my actual code which created those tables above its considerably more complicated than that. Note this heading...

Block #2 Board Foot Volume Per Acre For All Trees 

All our timber sales are compartmentalized into Cutting Blocks. A timber sale can have from 1 to maybe 30 blocks. So that introduces a third dimension. So if that sale above had 10 cutting blocks the array might be like so...

int iVolume[12][9][11];

And that isn't the end either. Note above there is mention of 'Live Trees' and 'Dead Trees' (there are actually a couple more possible designations). That introduces a 4th dimension...

int iVolume[12][9][11][3];

As another aside, I can tell from your code you posted you are using GCC or at least a non Microsoft compiler, right? Your code won't compile with any Microsoft compiler I have. For this code...

// cl MistahMoose.cpp /O1 /Os /EHsc
//MistahMoose.cpp

#include <iostream>
using namespace std;

int main()
{
    int SIZE;
    cin >> SIZE;//get array size
    int arr[SIZE];
    
    for(int i = 0; i <SIZE; i++)//fill array
    {
        arr[i] = 1;
    }

    
    for(int i = 0; i <SIZE; i++)//print array
    {
        cout << arr[i];
    }
    
    return 0;
}

...I get these errors...

[freddie1]

...continued...

C:\Code\VStudio\VC++9\Silvah\Sil7>cl MistahMoose.cpp /O1 /Os /EHsc
Microsoft (R) C/C++ Optimizing Compiler Version 15.00.21022.08 for x64
Copyright (C) Microsoft Corporation.  All rights reserved.

MistahMoose.cpp
MistahMoose.cpp(11) : error C2057: expected constant expression
MistahMoose.cpp(11) : error C2466: cannot allocate an array of constant size 0
MistahMoose.cpp(11) : error C2133: 'arr' : unknown size

C:\Code\VStudio\VC++9\Silvah\Sil7>

For Line #11 above its stating this...

MistahMoose.cpp(11) : error C2057: expected constant expression

GCC will compile/link that but not MSVC. In the case of GCC however, array functionality breaks down at the point of function call parameters.

To make a very, very long story short, both C and C++ are among the poorest of languages for dealing with multi-dimensional dynamically allocated arrays - at least natively. You have to write classes to handle these in C++.

But getting back to my story with the stand tables above, there is no way of knowing what the subscripts need to be to process the array for any specific timber sale before the data is examined by the running program. That's why the arrays need to be dynamic, i.e., sized at runtime. Has this helped?

[freddie1]

And of course, the above is a most complicated case. There are many simple cases. If you need an array of null terminated character strings to contain the months of the year, then you know before you write your first line of code how big the array must be. It needs to contain exactly 12 elements. That's an example of a static requirement - not dynamic.

[MistahMoose]

Thank you so much for your reply :)

This is a fantastic example.

I just put the code into VS and got the same errors.

I believe a VLA would be able to work the same way as you describe, but would lack function support (Being able to pass between function and main easily). However I am reading now that VLA is not really supported in standard C++, Hence the errors. I half use a g++ compiler(c9.io/putty) and a C++ compiler (VS), between work, school and home.

Maybe one of the reasons I had issues understanding why my automatic/VLA array felt like it could do what a dynamic array does was because I had been using a g++ compiler between work and school.

I realize now I misunderstood keskiverto when he commented on the c++ standard. oops

Thank you both.

[freddie1]

If you are interested in this topic I can provide code showing how I handle it in C++, i.e., dynamic multi-dimensional arrays. But not right now. I'll be tied up likely 'till Thursday and won't be able to post 'till then.

PS - yes, there are issues with passing mult-dimensional arrays as function parameters. But using array classes solves the problem, as the instantiated objects carry all the necessary information along with themselves.

[MistahMoose]

That would be awesome! Id appreciate it. I'd like to be as knowledgeable as possible about arrays, and how to handle them etc. It would definitely benefit me.
I've encountered those issues I believe, but haven't worked enough with classes that use arrays to realize that solution :)

Take your time and get back to me when you can, Whether on a post on in a PM!

Thanks again :)

[freddie1]

Wrote up a tutorial on C++ Dynamic Arrays here...

http://www.jose.it-berater.org/smfforum/index.php?topic=5170.0

I don't look in the Beginners Forum much (mostly hang out in Windows Forum), but I'm kind of amazed all the grief arrays seem to cause folks. I guess I shouldn't be surprised. I had trouble with them too in C++ until I put all the piecies together. Hope this helps.

fred

[gunnerfunner]

Freddie: this is amazing! Many thanks for a real-world example and the tutorial. I read this thread first and then the tutorial and the segue fitted just right. Given the issues with arrays that you have so eloquently touched upon, I was wondering if at work you're using any of the std library containers instead like vectors that manage memory automatically through their allocators. It seems to me that there is no real reason to use arrays at all anymore given the choice of containers, or is there? Maybe something I don't know about? Also, in the tutorial you mention using classes, are you doing something similar with your data on trees or using the raw data outright?

I don't look in the Beginners Forum much (mostly hang out in Windows Forum)

I hope this changes going forward, we could do with more of your ilk around

here