Root: 1 revision(s)

2007-06-08T15:04:44Z

1 revision(s)

← Older revision	Revision as of 15:04, 8 June 2007
(No difference)

Root: /* Vectors running wild! */

2007-04-04T07:32:15Z

Vectors running wild!

New page

=Arrays and Vectors=
{{hbox|When you write new code in C++, use Vectors instead of arrays. Almost always they are easier to work with.}}
In old C the way to store a number of values of same type (say integers) is to use an Array -- which can be thought of as a line of slots that we can fill in with values. ''In general'' arrays should have fixed size that is determined during the compile time (there are ways to avoid this problem!). C++ has Vectors -- array's on steroids -- think of these as expandable bags. You can load them with any number of values as you like! If you write code in C++, you can get away without using Arrays at all. But, in old code written in C, arrays appear quite often. So, we shall cover arrays first.

==Arrays==
An array is a series of elements of the same type placed in contiguous memory locations that can be individually referenced by adding an index to a unique identifier.

That means that, for example, we can store 5 values of type <tt>int</tt> in an array without having to declare 5 different variables, each one with a different identifier. Instead of that, using an array we can store 5 different values of the same type, <tt>int</tt> for example, with a unique identifier.

For example, an array to contain 5 integer values of type <tt>int</tt> called <tt>billy</tt> could be represented like this:

[[Image:9-imgarra1.gif]]

where each blank panel represents an element of the array, that in this case are integer values of type <tt>int</tt>. These elements are numbered from to <tt>4</tt> since in arrays the first index is always , independently of its length.

Like a regular variable, an array must be declared before it is used. A typical declaration for an array in C++ is:

<tt> type name [elements]; </tt>

where <tt>type</tt> is a valid type (like <tt>int</tt>, <tt>float</tt>...), <tt>name</tt> is a valid identifier and the <tt>elements</tt> field (which is always enclosed in square brackets <tt>[]</tt>), specifies how many of these elements the array has to contain.

Therefore, in order to declare an array called <tt>billy</tt> as the one shown in the above diagram it is as simple as:

{| class="snippet"
| class="code" |
int billy [5];

|}

'''NOTE'''<nowiki>: The </nowiki><tt>elements</tt> field within brackets <tt>[]</tt> which represents the number of elements the array is going to hold, must be a constant value, since arrays are blocks of non-dynamic memory whose size must be determined before execution. In order to create arrays with a variable length dynamic memory is needed, which is explained later in these tutorials.

===Initializing arrays.===

When declaring a regular array of local scope (within a function, for example), if we do not specify otherwise, its elements will not be initialized to any value by default, so their content will be undetermined until we store some value in them. The elements of global and static arrays, on the other hand, are automatically initialized with their default values, which for all fundamental types this means they are filled with zeros.

In both cases, local and global, when we declare an array, we have the possibility to assign initial values to each one of its elements by enclosing the values in braces <tt>{ }</tt>. For example:

{| class="snippet"
| class="code" |
int billy [5] = { 16, 2, 77, 40, 12071 };

|}

This declaration would have created an array like this:

[[Image:9-imgarra3.gif]]

The amount of values between braces <tt>{ }</tt> must not be larger than the number of elements that we declare for the array between square brackets <tt>[ ]</tt>. For example, in the example of array <tt>billy</tt> we have declared that it has 5 elements and in the list of initial values within braces <tt>{ }</tt> we have specified 5 values, one for each element.

When an initialization of values is provided for an array, C++ allows the possibility of leaving the square brackets empty <tt>[ ]</tt>. In this case, the compiler will assume a size for the array that matches the number of values included between braces <tt>{ }</tt><nowiki>:</nowiki>

{| class="snippet"
| class="code" |
int billy [] = { 16, 2, 77, 40, 12071 };

|}

After this declaration, array <tt>billy</tt> would be 5 ints long, since we have provided 5 initialization values.

===Accessing the values of an array.===

In any point of a program in which an array is visible, we can access the value of any of its elements individually as if it was a normal variable, thus being able to both read and modify its value. The format is as simple as:

<tt> name[index] </tt>

Following the previous examples in which <tt>billy</tt> had 5 elements and each of those elements was of type <tt>int</tt>, the name which we can use to refer to each element is the following:

[[Image:9-imgarra2.gif]]

For example, to store the value <tt>75</tt> in the third element of <tt>billy</tt>, we could write the following statement:

{| class="snippet"
| class="code" |
billy[2] = 75;

|}

and, for example, to pass the value of the third element of <tt>billy</tt> to a variable called <tt>a</tt>, we could write:

{| class="snippet"
| class="code" |
a = billy[2];
|}

Therefore, the expression <tt>billy[2]</tt> is for all purposes like a variable of type <tt>int</tt>.

Notice that the third element of <tt>billy</tt> is specified <tt>billy[2]</tt>, since the first one is <tt>billy[0]</tt>, the second one is <tt>billy[1]</tt>, and therefore, the third one is <tt>billy[2]</tt>. By this same reason, its last element is <tt>billy[4]</tt>. Therefore, if we write billy[5], we would be accessing the sixth element of <tt>billy</tt> and therefore exceeding the size of the array.

In C++ it is syntactically correct to exceed the valid range of indices for an array. This can create problems, since accessing out-of-range elements do not cause compilation errors but can cause runtime errors. The reason why this is allowed will be seen further ahead when we begin to use pointers.

At this point it is important to be able to clearly distinguish between the two uses that brackets <tt>[ ]</tt> have related to arrays. They perform two different tasks: one is to specify the size of arrays when they are declared; and the second one is to specify indices for concrete array elements. Do not confuse these two possible uses of brackets <tt>[ ]</tt> with arrays.

{| class="snippet"
| class="code" |
int billy[5]; // declaration of a new array

billy[2] = 75; // access to an element of the array.
|}

If you read carefully, you will see that a type specifier always precedes a variable or array declaration, while it never precedes an access.

Some other valid operations with arrays:

{| class="snippet"
| class="code" |
billy[0] = a;
billy[a] = 75;
b = billy [a+2];
billy[billy[a]] = billy[2] + 5;
|}

{| class="codebox"
| class="code" |
// arrays example
<nowiki>#include <iostream></nowiki>
using namespace std;

int billy [] = {16, 2, 77, 40, 12071};

int n, result=0;

int main ()
{
for ( n=0 ; n<5 ; n++ )
{
result += billy[n];
}
cout << result;
return 0;
}
| class="result" |
12206
|}

===Multidimensional arrays===

Multidimensional arrays can be described as "arrays of arrays". For example, a bidimensional array can be imagined as a bidimensional table made of elements, all of them of a same uniform data type.

[[Image:9-imgarra5.gif]]

<tt>jimmy</tt> represents a bidimensional array of 3 per 5 elements of type <tt>int</tt>. The way to declare this array in C++ would be:

{| class="snippet"
| class="code" |
int jimmy [3][5];

|}

and, for example, the way to reference the second element vertically and fourth horizontally in an expression would be:

{| class="snippet"
| class="code" |
jimmy[1][3]
|}

[[Image:9-imgarra6.gif]]

(remember that array indices always begin by zero).

Multidimensional arrays are not limited to two indices (i.e., two dimensions). They can contain as many indices as needed. But be careful! The amount of memory needed for an array rapidly increases with each dimension. For example:

{| class="snippet"
| class="code" |
char century [100][365][24][60][60];
|}

declares an array with a <tt>char</tt> element for each second in a century, that is more than 3 billion chars. So this declaration would consume more than 3 gigabytes of memory!


===Arrays as parameters===

At some moment we may need to pass an array to a function as a parameter. In C++ it is not possible to pass a complete block of memory by value as a parameter to a function, but we are allowed to pass its address. In practice this has almost the same effect and it is a much faster and more efficient operation.

In order to accept arrays as parameters the only thing that we have to do when declaring the function is to specify in its parameters the element type of the array, an identifier and a pair of void brackets <tt>[]</tt>. For example, the following function:

{| class="snippet"
| class="code" |
void procedure (int arg[])

|}

accepts a parameter of type "array of <tt>int</tt>" called <tt>arg</tt>. In order to pass to this function an array declared as:

{| class="snippet"
| class="code" |
int myarray [40];
|}

it would be enough to write a call like this:

{| class="snippet"
| class="code" |
procedure (myarray);
|}

Here you have a complete example:

{| class="codebox"
| class="code" |
// arrays as parameters
<nowiki>#include <iostream></nowiki>
using namespace std;

void printarray (int arg[], int length) {
for (int n=0; n<length; n++)
cout << arg[n] << " "<nowiki>;
cout << </nowiki>"\n"<nowiki>;
}

</nowiki>int main ()
{
int firstarray[] = {5, 10, 15};
int secondarray[] = {2, 4, 6, 8, 10};
printarray (firstarray,3);
printarray (secondarray,5);
return 0;
}
| class="result" |
5 10 15
2 4 6 8 10
|}

As you can see, the first parameter (<tt>int arg[]</tt>) accepts any array whose elements are of type <tt>int</tt>, whatever its length. For that reason we have included a second parameter that tells the function the length of each array that we pass to it as its first parameter. This allows the <tt>for</tt> loop that prints out the array to know the range to iterate in the passed array without going out of range.

In a function declaration it is also possible to include multidimensional arrays. The format for a tridimensional array parameter is:

{| class="snippet"
| class="code" |
base_type[][depth][depth]

|}

for example, a function with a multidimensional array as argument could be:

{| class="snippet"
| class="code" |
void procedure (int myarray[][3][4])
|}

Notice that the first brackets <tt>[]</tt> are left blank while the following ones are not. This is so because the compiler must be able to determine within the function which is the depth of each additional dimension.

Arrays, both simple or multidimensional, passed as function parameters are a quite common source of errors for novice programmers. I recommend the reading of the chapter about Pointers for a better understanding on how arrays operate. 

==Vectors -- Arrays made easy==
Arrays are simple as long as their dimensions are fixed. What if the size of the array is determined by the data? While [[C++ Dynamic Memory -- Advanced|there are ways]] to overcome this issue, they tend to be somewhat complicated. An alternative is to use the vector structure that is available in C++. Vectors are way easier to use than traditional arrays. Let's start with an example.
<source lang=cpp>
/** Vector demonstration I
**/
#include <vector>
#include <iostream>
#include <string>
using namespace std;

int main ()
{
vector<string> animals;
do{
string animal;
cout << "An animal (Just Enter to end):";
getline(cin, animal);
if(animal==""){
break;
}
animals.push_back(animal);
}while(true);
cout << "I got the following:\n";
for(unsigned int i=0;i<animals.size();i++){
cout << animals[i]<<'\n';
}

}
</source>
<pre>
An animal (Just Enter to end):rabbit
An animal (Just Enter to end):fox
An animal (Just Enter to end):chicken
An animal (Just Enter to end):
I got the following:
rabbit
fox
chicken
</pre>
{{hbox|Almost always, vectors are better substitutes for arrays. Learn to use them effectively. However, one situation where you may have to use arrays is when dealing with C language (prior to C++) code libraries.}}
Let's go through this code:
;<tt><nowiki>#include <vector></nowiki></tt>: directive needed (to include vector headers) if you want to use vectors.
;<tt><nowiki>vector<string> animals;</nowiki></tt>: animals is a vector, with string elements. (You can define vectors with any type of elements. e.g. <tt><nowiki>vector<int> age;</nowiki></tt>.
;<tt><nowiki>animals.push_back(animal);</nowiki></tt>: add the string stored in animal variable to animals vector. (Vector will grow by one element.)
;<tt><nowiki>animals.size()</nowiki></tt>: The size of the vector. (i.e. number of elements.)
;<tt><nowiki>animals[i]</nowiki></tt>: Elements of vectors can be accessed using the same notation that we use for arrays. (Alternatively you can use <tt><nowiki>animals.at(i)</nowiki></tt>.)

===Vectors of Vectors===
It is possible to define vectors of vectors (of vectors ...) as follows.
<source lang=cpp>
vector < vector <int> > matrix; //defines a vector of vector of integers.
</source>
Following is an example of vector of vectors in use.
<source lang=cpp>
/* vectors of vectors */
#include <vector>
#include <iostream>
#include <sstream>
using namespace std;

int main ()
{
vector < vector <double> > matrix; //matrix is a vector of, vector of doubles.
vector <double> line; //line is a vector of doubles
matrix.push_back(line); //add a 'line' to the 'matrix'
cout << "Enter your matrix. One number at a time.\n";
cout << "'Enter' to break current line.\n";
cout << "x'Enter' to end entering.\n";

int i=0,j=0;
while(true){
string mystr;
getline (cin,mystr); //read what was entered.
if(mystr==""){ // if it is blank (just Enter)
j++; // increase the row count.
matrix.push_back(line);// add a row to the matrix.
cout << "Enter next row.\n";
continue; // no need to waste time, start next iteration.
}
if(mystr=="x"){ // if it is "x"
break; // we are out!
}
// now we assume its a number.
//In reality we need a bit of error handling.
//But let's keep things simple here.
double tmp;
stringstream(mystr) >> tmp; //convert mystr to a double and store in tmp
matrix[j].push_back(tmp); //add that double (tmp) to row j of matrix.
}
cout << "Done entering!\n You entered the following matrix.\n";
for (unsigned int j=0;j<matrix.size();j++){// for each row in matrix
for(unsigned int i=0;i<matrix[j].size();i++){// for each place in jth row.
cout << matrix[j][i] <<'\t';
}
cout << '\n';
}
}

</source>

A typical run of this program would look like the following:
<pre>
Enter your matrix. One number at a time.
'Enter' to break current line.
x'Enter' to end entering.
2
3

Enter next row.
4
5
6
7
8
9

Enter next row.
1

Enter next row.
25
26
x
Done entering!
You entered the following matrix.
2 3
4 5 6 7 8 9
1
25 26
</pre>

===Vectors running wild!===
{{wbox|If you reuse a vector, first you need to explicitly remove all stuff. Remember to empty your bags before refilling them!}}
Think of vectors as bags of unlimited space. They are very convenient because you don't have to know what is the number of items you are going to fill them with in advance, they just keep on growing!! However, this same property can lead to problems if you don't pay attention. One of the common mistakes made by new programmers is forgetting to empty the vector (bag) before putting new set of items (refilling the bag!).

Lets suppose you write a program where you use an array/a vector to store a number of items. Let's say, within the program you do it several times. In arrays when you do the following:
<source lang=cpp>
int vals[5];
...
vals[i]=5;
</source>
we explicitly say '''''replace the slot number <tt>i</tt> of <tt>vals</tt> with value <tt>5</tt>'''''.
But in vectors
<source lang=cpp>
vector <int> vals;
...
vals.push_back(5);
</source>
what we say is '''''add the value <tt>5</tt> to the bag <tt>vals</tt>'''''. Notice that if we don't need the old values, we have to explicitly erase them!

You can erase a whole vector by
<source lang=cpp>
vals.erase();
</source>

Template:Cpptutorial Arrays - Revision history

Root: 1 revision(s)

Root: /* Vectors running wild! */