Contents
Part two of the book focuses on organization of data within our program and so the first in memory way we can organize our data is an array. An array is a primitive data structure in so far as it allows us a way to structure our data. The structure is very basic, but the concept and use of an array is so useful that you can find arrays in almost all languages. At its essence, an array is nothing more than a block of contiguous or continuous memory.
In C++ when you want to create an array like other variables we must declare them first. To declare an array we need to know the type of the array and how large an array we would like to create. Once we create the array, its size is fixed and cannot be changed. We will learn later how we can overcome this shortcoming of arrays, but for now we will have to live with it.
int myArray[10]; //this will create an array of integers of size 10.
The example above will allow us to create an array of integers with enough storage for 10 integers. They will be stored in memory one after the next in a continuous way so that each int is "next to" the next integer. There shouldn't be any "space" between the integers, unless we skip a spot and leave it blank.
A few things to note when you create an array, the size that is used must also be a constant, i.e. you can't use a variable when you create an array. We will see a fuller example down below. Often times when I create an array, I'll declare the array's size as a global constant, which allows me to use it in any functions. Since it's a constant I don't have to worry about it being modified and so it's safe to declare in the global scope.
An array has two major limitations:
We will learn ways to overcome both of these limitations. The solutions to both of these problems will be the subject of a later chapter.
One last thing to know about how arrays are organized is how C++ counts the data in an array. C++ starts counting the data in the array with the index position 0. So when there are 5 pieces of data in an array, they are stored at location 0, 1, 2, 3, and 4. That means if you create an array with size 10, you have 10 spots and they are numbered, or indexed, 0 - 9.
When I talk about arrays I always stress that there are 4 pieces of information that must be known or "remembered" about each array.
For all arrays we will always need to know these 4 pieces of information. Sometimes knowing how full the array is sufficient, for example, after we've "filled" the array then as long as we didn't overflow our array, the name and count of the data in the array is all we need.
Often we will use an array to store a set of data and then use a loop to somehow process that data. Imagine we have a file that contains 20 doubles. Now imagine that you would like to know the average of those numbers. We can write a simple program that will read that data and compute the average.
#include <iostream>
#include <fstream>
const int SIZE = 20; //this is the maximum number of data we can store.
int main()
{
double data[SIZE]; //this will create the array of doubles.
int count = 0; //this will be used to keep track of how many data items we have in the array
std::ifstream in("datafile.txt");
double dataItem;
in >> dataItem;
while( !in.fail() && count < SIZE )
{
data[count] = dataItem;
count++;
in >> dataItem;
}
double sum = 0;
for ( int i=0; i<count; i++ )
sum = sum + data[i];
std::cout << "Average: " << sum / count << std::endl;
}
Program 7.1
Now if the file "datafile.txt" contained the following set of numbers:
10.0
20.0
23.5
45.6
67.8
89.4
5.0
The program would produce this as a result:
Average: 37.3286
So why would we go to this trouble to compute the average when we could do it more easily in a calculator? What if this were just a single step in what we have to do? What if we are also computing standard deviation? We could compute the standard deviation on a calculator but it might be more difficult. What if the numbers changed often and we needed to do this every time they changed? A program might start making sense. Also this is an illustration of how we can use arrays.
So some things to note about how this program works. We are still using our prime, test, process, and reprime loop. Even though we are storing our data in array, we are still using that same basic loop for reading. We have however added a condition into the loop that makes sure that if the count ever is equal to size, our loop stops. Why? Could we do this in another way? The purpose of that check is that whenever we are about to use a variable inside of the brackets for our array, we should always check to make sure that the value in the variable is less than the maximum. We should also check that the variable is at least equal to 0, but we have assured that with the count variable's initialization.
It should come as no surprise that we can pass an array to a function. When we declare a function that takes an array we need to let the function know to expect an array. We do this by adding the square brackets in the function declaration and definition. When we call the function, we simply use just the name of the array without the brackets. We can rewrite Program 7.1 to show how this is done.
#include <iostream>
#include <fstream>
const int SIZE = 20; //this is the maximum number of data we can store.
double computeAverage( double arrayOfDoubles[], int count );
int main()
{
double data[SIZE]; //this will create the array of doubles.
int count = 0; //this will be used to keep track of how many data items we have in the array
std::ifstream in("datafile.txt");
double dataItem;
in >> dataItem;
while( !in.fail() && count < SIZE )
{
data[count] = dataItem;
count++;
in >> dataItem;
}
std::cout << "Average: " << computeAverage(data, count) << std::endl;
}
double computeAverage( double arrayOfDoubles[], int count )
{
double sum = 0;
if ( count >= 0 && count < SIZE )
{
for ( int i=0; i<count; i++ )
sum = sum + arrayOfDoubles[i];
}
return sum / count;
}
Program listing 7.2
Functionally, this program works exactly like Program 7.1 however the use of the function allows us to use that function to compute the average of any array of doubles. The count parameter is needed so that the loop in the function "knows" how many data items are in the array. The function checks that the count is at least equal to 0 and is less than SIZE. This is an example of defensive programming. It wants to check that the parameter it's given make "sense" it at least as far as the count is concerned. It has to trust that the data in the array is valid.
A note about how the array is passed to the function. We learned in the chapter on functions that the default passing mechanism for parameters is pass-by-value and as far as we can tell this is true for the array as well. The truth is that for the array the default is pass-by-reference. The reason is that the compiler only needs to know where in memory the array is stored and it can determine where all the elements are located. Since the only thing stored about the array is the memory location, we can only pass the address of or the reference to the array. For this reason, we should probably pass this array by const so that the function can't modify it. We do this by adding the keyword const before double in the header and the definition. That would prevent any modification of the array by the function computeAverage.
It's also good to know that not only can you pass an entire array to a function, but you can pass individual array elements to a function. For example, say we wanted to take the absolute value before we computed the average, we could modify Program 7.2 to look like this:
#include <iostream>
#include <fstream>
#include <cmath>
const int SIZE = 20; //this is the maximum number of data we can store.
double computeAverage( const double arrayOfDoubles[], int count );
int main()
{
double data[SIZE]; //this will create the array of doubles.
int count = 0; //this will be used to keep track of how many data items we have in the array
std::ifstream in("datafile.txt");
double dataItem;
in >> dataItem;
while( !in.fail() && count < SIZE )
{
data[count] = dataItem;
count++;
in >> dataItem;
}
for ( int i=0;i<count;i++)
{
data[i] = std::abs(data[i]);
}
std::cout << "Average: " << computeAverage(data, count) << std::endl;
}
double computeAverage( const double arrayOfDoubles[], int count )
{
double sum = 0;
if ( count >= 0 && count < SIZE )
{
for ( int i=0; i<count; i++ )
{
sum = sum + arrayOfDoubles[i];
}
}
return sum / count;
}
Program listing 7.3
Also note that the version contains the const before the double in the header and the definition. We can see passing the individual elements of the array to std::abs after the data reading loop.
Single arrays are useful but imagine we needed to store data about a student; we might need to store names and grades. Now imagine we have 100 students. So we could use an array of strings to store the names and then an array of doubles for each of the grades we need. Then in all the first location of the array might be the data for the first student and so on. This might work, but imagine that we need to sort that data. It can be very complex to do that when the number of arrays gets much beyond 2 or 3. While it is possible to do this, it tends to be overly complex and there are better solutions, as we will see soon.
Arrays are extremely useful for storing lots of data of the same type especially when the amount of data is known ahead of time. Even when we don’t know the maximum amount of data, an array is extremely useful. Arrays allow for the creation of basic structured data despite having a fixed size and only being able to store 1 type of data. We will continue to use arrays for many different applications and they will prove their worth many times over.
Written by: David McPherson © 2019