3.1 Arrays
The simplest way to implement our collection is to use an array to hold the items. Thus the implementation of the collection object becomes:
/* Array implementation of a collection */
#include <assert.h> /* Needed for assertions */
#include "collection.h" /* import the specification */
struct t_collection {
int item_cnt;
int max_cnt; /* Not strictly necessary */
int item_size; /* Needed by FindInCollection */
void *items[];
}; Points to note:- We have imported the specification of this object into the implementaton - this enables the compiler to verify that the implementation and the specification match. Although it's not necessary to include the specification (cf function prototypes), it is much safer to do so as it enables the compiler to detect some common errors and ensures that the specification and its implementation remain consistent when the object is changed.
- items is typed as an array of void * in the struct. It is an array of item's which happen to be pointers - but remember that we are trying to hide this from users of the class. Many C programmers would write the equivalent void ** here.
- Why is the attribute max_cnt not strictly necessary?
Hint: it's related to the pre- and post-conditions specified for methods on this object.
Select here to load collection.c
Points to note:
- ConsCollection uses the memory allocator calloc to dynamically allocate memory off the program's heap for the collection. Two calls are necessary - one to allocate space for the "header" structure itself and one to allocate space for the array of item pointers.
- assert calls have been added for the pre-conditions (cf full description of assert). Note that the pre-conditions here are expressed as a number of conditions linked by &&. Since assert requires a single boolean expression as its argument, one assert would suffice. However, we have chosen to implement each individual condition as a separate assert. This is done to assist de-bugging: if the pre-conditions are not satisfied, it is more helpful to know which one of multiple conditions has not been satisfied!
- memcmp is a standard function which compares blocks of memory byte by byte [man page for memcmp].
- The use of memcp and ItemKey severely constrain the form of the key - it must be in a contiguous string of characters in the item. There are ways of providing more flexible keys (eg ones having multiple fields within item or ones calculated from item. These rely on C capabilities which will be discussed in a later section.
- There is no treatment of errors, e.g. if no memory is available on the heap for calloc.
This is a serious shortcoming. No software without a consistent strategy for detecting, reporting and recovering from errors can be considered well engineered. It is difficult to debug, prone to crashes from faults which are difficult to correct because there is no indication of the source of the error.
See Basic Arrays in C and C++ below:
A Note
This tutorial assumes you've already gone through the pointers tutorial. If you haven't, please start there. This tutorial draws from insights gained in that tutorial and includes terms and phrases that won't make sense if you haven't already gone through that tutorial.Array basics
Let's start by looking at a single variable used to store a person's age.C Code Listing 1
1: #include <stdio.h>
2:
3: int main()
4: {
5: short age;
6: age=23;
7: printf("%d\n", age);
8: return 0;
9: }C++ Code Listing 1
1: #include <iostream>
2:
3: int main()
4: {
5: short age;
6: age=23;
7: std::cout << age << std::endl;
8: return 0;
9: }Not much to it. The variable age is created at line (5) as a short. A value is assigned to age. Finally, age is printed to the screen.
Here's how to create an array and one way to initialize an array:
C Code Listing 2
1: #include <stdio.h>
2:
3: int main()
4: {
5: short age[4];
6: age[0]=23;
7: age[1]=34;
8: age[2]=65;
9: age[3]=74;
10: return 0;
11: }C++ Code Listing 2
1: #include <iostream>
2:
3: int main()
4: {
5: short age[4];
6: age[0]=23;
7: age[1]=34;
8: age[2]=65;
9: age[3]=74;
10: return 0;
11: }On line (5), an array of 4 short's is created. Values are assigned to each variable in the array on line (6) through line (9).
short variable, or element, in the array is straightforward. Simply provide a number in square braces next to the name of the array. The number identifies which of the 4 elements in the array you want to access. | The program above shows that the first element of an array is accessed with the number 0 rather than 1. Later in the tutorial, We'll discuss why 0 is used to indicate the first element in the array. |
Printing arrays
Our program is a bit unrevealing in that we never print the array to screen. Here is the same program with an attempt to print the array to the screen:C Code Listing 3
1: #include <stdio.h>
2:
3: int main()
4: {
5: short age[4];
6: age[0]=23;
7: age[1]=34;
8: age[2]=65;
9: age[3]=74;
10:
11: printf("%x\n", age);
12: return 0;
13: }C++ Code Listing 3
1: #include <iostream>
2:
3: int main()
4: {
5: short age[4];
6: age[0]=23;
7: age[1]=34;
8: age[2]=65;
9: age[3]=74;
10:
11: std::cout << age << std::endl;
12: return 0;
13: }Line (11) is meant to print the 4 ages to the screen. But instead of printing out the four short variables, what appears to be nonsense prints out instead.| What the "nonsense" output actually is and why the 4 array values were not printed will be addressed later in the tutorial. For now, the important point to come away with is that simply providing the name of the array in an output statement will not print out the elements of the array. |
C Code Listing 4
1: #include <stdio.h>
2:
3: int main()
4: {
5: short age[4];
6: age[0]=23;
7: age[1]=34;
8: age[2]=65;
9: age[3]=74;
10: printf("%d\n", age[0]);
11: printf("%d\n", age[1]);
12: printf("%d\n", age[2]);
13: printf("%d\n", age[3]);
14: return 0;
15: }C++ Code Listing 4
1: #include <iostream>
2:
3: int main()
4: {
5: short age[4];
6: age[0]=23;
7: age[1]=34;
8: age[2]=65;
9: age[3]=74;
10: std::cout << age[0] << std::endl;
11: std::cout << age[1] << std::endl;
12: std::cout << age[2] << std::endl;
13: std::cout << age[3] << std::endl;
14: return 0;
15: }Lines (10) through line (13) produce the output we are expecting.There is no single statement in the language that says "print an entire array to the screen". Each element in the array must be printed to the screen individually.
Copying arrays
Suppose that after filling our 4 element array with values, we need to copy that array to another array of 4short's? Try this:C Code Listing 5
1: #include <stdio.h>
2:
3: int main()
4: {
5: short age[4];
6: short same_age[4];
7: age[0]=23;
8: age[1]=34;
9: age[2]=65;
10: age[3]=74;
11:
12: same_age=age;
13:
14: printf("%d\n", same_age[0]);
15: printf("%d\n", same_age[1]);
16: printf("%d\n", same_age[2]);
17: printf("%d\n", same_age[3]);
18: return 0;
19: }C++ Code Listing 5
1: #include <iostream>
2:
3: int main()
4: {
5: short age[4];
6: short same_age[4];
7: age[0]=23;
8: age[1]=34;
9: age[2]=65;
10: age[3]=74;
11:
12: same_age=age;
13:
14: std::cout << same_age[0] << std::endl;
15: std::cout << same_age[1] << std::endl;
16: std::cout << same_age[2] << std::endl;
17: std::cout << same_age[3] << std::endl;
18: return 0;
19: }Line (12) tries to copy the age array into the same_age array. What happened when you tried to compile the program above? | The point here is that simply assigning one array to another will not copy the elements of the array. The hard question to answer is why the code doesn't compile. Later in the tutorial this example will be re-examined to explain why line (12) doesn't work. This code should not compile on either C or C++ compilers. However, some older C++ compilers may ignore the ISO C++ standard and allow line 12 to compile. If it does compile on your C++ compiler, make a mental note that it is incorrect behavior. |
C Code Listing 6
1: #include <stdio.h>
2:
3: int main()
4: {
5: short age[4];
6: short same_age[4];
7:
8: age[0]=23;
9: age[1]=34;
10: age[2]=65;
11: age[3]=74;
12:
13: same_age[0]=age[0];
14: same_age[1]=age[1];
15: same_age[2]=age[2];
16: same_age[3]=age[3];
17:
18: printf("%d\n", same_age[0]);
19: printf("%d\n", same_age[1]);
20: printf("%d\n", same_age[2]);
21: printf("%d\n", same_age[3]);
22: return 0;
23: }C++ Code Listing 6
1: #include <iostream>
2:
3: int main()
4: {
5: short age[4];
6: short same_age[4];
7:
8: age[0]=23;
9: age[1]=34;
10: age[2]=65;
11: age[3]=74;
12:
13: same_age[0]=age[0];
14: same_age[1]=age[1];
15: same_age[2]=age[2];
16: same_age[3]=age[3];
17:
18: std::cout << same_age[0] << std::endl;
19: std::cout << same_age[1] << std::endl;
20: std::cout << same_age[2] << std::endl;
21: std::cout << same_age[3] << std::endl;
23: return 0;
23: }This technique for copying arrays works fine. Two arrays are created: age and same_age. Each element of the age array is assigned a value. Then, in order to copy of the four elements in age into the same_age array, we must do it element by element. 
The technique used to copy one array into another is exactly the same as the technique used to copy 4 separate variables into 4 other variables. So what is the advantage to using arrays over separate variables?
One significant advantage of an array over separate variables is the name. In our examples, using four separate variables requires 4 unique names. The 4
short variables in our array have the same name, age. The 4 short's in the array are identical except for an index number used to access them. This distinction allows us to shorten our code in a way that would be impossible with 4 variables, each with unique names: C Code Listing 7
1: #include <stdio.h>
2:
3: int main()
4: {
5: short age[4];
6: short same_age[4];
7: int i, j;
8: age[0]=23;
9: age[1]=34;
10: age[2]=65;
11: age[3]=74;
12:
13: for(i=0; i<4; i++)
14: same_age[i]=age[i];
15:
16: for(j=0; j<4; j++)
17: printf("%d\n", same_age[j]);
18: return 0;
19: }C++ Code Listing 7
1: #include <iostream>
2:
3: int main()
4: {
5: short age[4];
6: short same_age[4];
7: int i, j;
8: age[0]=23;
9: age[1]=34;
10: age[2]=65;
11: age[3]=74;
12:
13: for(i=0; i<4; i++)
14: same_age[i]=age[i];
15:
16: for(j=0; j<4; j++)
17: std::cout << same_age[j] << std::endl;
18: return 0;
19: }Since the only difference between each of the short's in the arrays is their index, a loop and a counter can be used to more easily copy all of the elements. The same technique is used to shorten the code that prints the array to the screen. Even though arrays give us some convenience when managing many variables of the same type, there is little difference between an array and variables declared individually. There is no single statement to copy an array, there is no single statement to print an array.
If we want to perform any action on an array, we must repeatedly perform that action on each element in the array.
Array Internals
To understand what exactly is happening inside of arrays, first recall the behavior of variables from the pointer tutorial:Try:
fl. In our examples, we'll assume that a float requires 4 bytes. Depending on the computer's architecture, a float may require 2, 4, 8 or some other number of bytes. fl is used in line (5), two distinct steps occur:
|
age, not age[2])? Here's the program from earlier in the tutorial that was our first crude attempt at printing out the contents of an array:
C Code Listing 8
1: #include <stdio.h>
2:
3: int main()
4: {
5: short age[4];
6: age[0]=23;
7: age[1]=34;
8: age[2]=65;
9: age[3]=74;
10:
11: printf("%x\n", age);
12: return 0;
13: }C++ Code Listing 8
1: #include <iostream>
2:
3: int main()
4: {
5: short age[4];
6: age[0]=23;
7: age[1]=34;
8: age[2]=65;
9: age[3]=74;
10:
11: std::cout << age << std::endl;
12: return 0;
13: }Line (11) prints out nonsense, not the contents of our array.Let's apply the 2 steps from the pointers tutorial to our array on line (11):
- On line (11), The program finds and grabs the address reserved for
age. Simple enough. According to the image,agestarts at address 924 so it is address 924 that is grabbed. - The contents stored at that address are retrieved (Oops!).
As a result, step 2 isn't performed on arrays, just step 1. The output from line (11) is the address of the array: step 2 has not occurred. In order to get a value from an array, the programmer must "manually" do step 2 to retrieve the contents.
Accessing elements in an array
From the pointer tutorial, we know that in order to get the contents at an address we use the* operator. Let's try it on our printing example:C Code Listing 9
1: #include <stdio.h>
2:
3: int main()
4: {
5: short age[4];
6: age[0]=23;
7: age[1]=34;
8: age[2]=65;
9: age[3]=74;
10:
11: printf("%d\n", *age);
12: return 0;
13: }C++ Code Listing 9
1: #include <iostream>
2:
3: int main()
4: {
5: short age[4];
6: age[0]=23;
7: age[1]=34;
8: age[2]=65;
9: age[3]=74;
10:
11: std::cout << *age << std::endl;
12: return 0;
13: }On line (11) the * operator has been added. When this code is compiled and executed, 23 prints to the screen. When just the array's name is provided, only step 1 occurs with an array. We then manually do step 2 to get the contents at that address--namely the value of the first element of our array.That's all fine and good, but what about the rest of the array? What if we want to access the second, third, or fourth element of our array? We know that when we use the name of an array, step 1 occurs and we get the address of the first element of that array. We also know (from the pointers tutorial) that an address is nothing more than an integer. Given that the address is nothing but an integer, we can use addition to access the other array elements!
The big question is: How much do we add to age in line (11) above to get the address of the second element in the age array?
age beginning at 924, the second at 926, the third at 928, and so on. However, in this case C and C++ don't follow the rules of arithmetic. C and C++ follow the rules of pointer arithmetic. I'm sorry. Don't blame me. I'm just the storyteller, I didn't invent the darned language.In C and C++ you add "1" to
age (that is, the address of age) to access the second element, add "2" to age to access the third element, etc. If you hadn't seen the fancy image showing that each element of age (each short variable) had 2 bytes, then you might have said "1" and gotten the correct answer. We'll explain all of this in just a bit. But first let's see what that looks like in code.Here is how we can print the value of the second element in the array:
C Code Listing 10
1: #include <stdio.h>
2:
3: int main()
4: {
5: short age[4];
6: age[0]=23;
7: age[1]=34;
8: age[2]=65;
9: age[3]=74;
10:
11: printf("%d\n", *(age+1));
12: return 0;
13: }C++ Code Listing 10
1: #include <iostream>
2:
3: int main()
4: {
5: short age[4];
6: age[0]=23;
7: age[1]=34;
8: age[2]=65;
9: age[3]=74;
10:
11: std::cout << *(age+1) << std::endl;
12: return 0;
13: }Line (11) now shows pointer arithmetic in action:- Step 1 is done on
age--the address 924 is returned. - Using pointer arithmetic, 1 is added to 924 which produces the address of the next element in the array. Looking at the image of our example, the result is 926.
- Using the
*operator ("do step 2 on a number"), the contents at that address are retrieved. The contents at address 926 is the number 34, which is what prints to the screen.
* operator and the + operator occur in the correct order. This is due to operator precedence rules.Pointer Arithmetic
"This new learning amazes me, Sir Bedevere! Explain again, how sheep's bladders can be employed to prevent earthquakes."Why is pointer arithmetic different from normal arithmetic? If you recall from the pointers tutorial, pointers in C and C++ are typed. That is, in C and C++ you can have
-King Arthur, Monty Python and the Holy Grail
float pointers, int pointers, char pointers, etc. Here's an excerpt from a side note in the pointers tutorial:| ...A primary motivation for having a pointer type for each variable type is to help the compiler. Referring back to an earlier example, when we get the contents at an address ("do step 2 on a number"), the compiler must know how to get the contents at the address. The compiler needs to know two things when getting the contents at an address:
|
short integers. So, the address is a short pointer (that is, it is a: short*).The type of the pointer not only allows the compiler to correctly get the contents at an address, but it also allows the compiler to correctly calculate the number of bytes to add when doing pointer arithmetic:
1: int miles[4]; 2: miles[0]=342; 3: miles[1]=86; 4: miles[2]=911; 5: miles[3]=7; 6: ... *(miles+2) ...
miles is the address of an integer, or an int*. By the rules of pointer arithmetic, line (4) will get the contents at address 928.1: float gpa[4]; 2: gpa[0]=2.3; 3: gpa[1]=4.0; 4: gpa[2]=3.27; 5: gpa[3]=0.0; 6: ... *(gpa+2) ...
gpa is the address of a floating point number, or a float*. By the rules of pointer arithmetic, line (4) will get the contents at address 932.1: char letter[4]; 2: letter[0]='M'; 3: letter[1]='a'; 4: letter[2]='r'; 5: letter[3]='k'; 6: ... *(letter+2) ...
letter is the address of an character, or a char*. By the rules of pointer arithmetic, line (4) will get the contents at address 926.Array Basics Revisited
Now that we have some insight about C and C++ array quirks, let's take another look at how we started accessing array elements. Prior to diving into this whole step 1 step 2 business with arrays we were initializing, printing, copying, and in general accessing array elements using square braces:C Code Listing 11
1: #include <stdio.h>
2:
3: int main()
4: {
5: short age[4];
6: age[0]=23;
7: age[1]=34;
8: age[2]=65;
9: age[3]=74;
10:
11: printf("%d\n", age[2]);
12: return 0;
13: }C++ Code Listing 11
1: #include <iostream>
2:
3: int main()
4: {
5: short age[4];
6: age[0]=23;
7: age[1]=34;
8: age[2]=65;
9: age[3]=74;
10:
11: std::cout << age[2] << std::endl;
12: return 0;
13: }On lines (6-9) we are using square braces to access elements for initialization. On line (11) we are using square braces to print out the third element of the array. From the previous section you might have been led to believe that you would print out the third element by putting something like *(age+2). As it turns out, the *(age+2) syntax is the "correct" syntax, in terms of how the language handles arrays (and pointers). The square braces syntax is nothing more than a shorthand for the pointer syntax. When you type age[2], the compiler internally converts it to: *(age+2). In fact, whenever you use the square braces, the compiler just blindly substitutes the first term into the left-hand side of the addition and the second term into the right-hand side of the addition:
monkey[ crackers ], the compiler tries to compile*(monkey + crackers)I'm not kidding! Let's prove it.
When as a youngster you were asked to add
5+3, no problem. But what about when the numbers were switched and you were asked to add 3+5? Still no problem because of the commutative property of addition. The commutative property of addition holds in C and C++ just like it did when you were a youngster. So, *(age+2) produces exactly the same result as *(2+age). That is, the number of bytes equivalent to two short integers is added to age and then the contents are retrieved at that address. OK, so what? In the previous paragraph I said that when you write something like age[2] the compiler blindly substitutes it into its pointer syntax and compiles *(age+2). So, let's turn it around and prove that all of this array stuff is nothing but simple pointer access with a little addition:C Code Listing 12
1: #include <stdio.h>
2:
3: int main()
4: {
5: short age[4];
6: 0[age]=23;
7: 1[age]=34;
8: 2[age]=65;
9: 3[age]=74;
10:
11: printf("%d\n", 2[age]);
12: return 0;
13: }C++ Code Listing 12
1: #include <iostream>
2:
3: int main()
4: {
5: short age[4];
6: 0[age]=23;
7: 1[age]=34;
8: 2[age]=65;
9: 3[age]=74;
10:
11: std::cout << 2[age] << std::endl;
12: return 0;
13: } | is equivalent to |  |
age array is accessed. Before compiling 2[age], the compiler first blindly converts it into *(2+age). Pretty cool, eh?We now have more than enough information to answer the question: "Why do arrays in C and C++ start at zero instead of one?". We know that the name of the array produces the address of the beginning of the array; and we know that the beginning of the array is also the address of the first element of the array. So, all of these are exactly the same:
*age*(age+0)age[0]
Re-summarizing, to access any element in an array provide:
- The name of the array. This gets the address of the first element of the array.
- A number. Pointer arithmetic is used to add this number to the address resulting in the address of one of the elements in the array. Of course if zero is added the address is unchanged (it remains the address of the first element).
- Use the
*operator to get the contents at that address. Alternately use the square bracket syntax and the compiler will do the addition and content retrieval for you.
