Download PDF : Arrays

Download PDF : Arrays
Download PDF : Arrays

An array is a collection data that has homogeneous type. It is stored in memory and, in C++, is accessed directly from memory, which is one reason for the efficiency the use of arrays in a program, and is one reason for the attendant dangers. Most machine architectures have facilities to access memory in exactly the way that C++ calculates the addresses of its array members through indexing. The C++ compiler can issue machine language instructions that directly implement C++ array commands without a lot of supporting instructions as is needed in a language where the access is less direct and more strongly protected.
1. Outline of topics in the chapter
5.1 Introduction to Arrays
Declaring and Referencing Arrays
Arrays in Memory
Initializing Arrays

5.2 Arrays in functions
Indexed Variables as Function Arguments
Entire Arrays as Function Arguments
The const Parameter modifier
Functions That Return an Array
Example: Production Graph

5.3 Programming with Arrays
Multidimensional Array Basics
Multidimensional Array Parameters

2. General remarks on the chapter
Students who come to C++ from Java will be concerned to find that the array is not an object, and has none of the member functions nor any protection against misuse that the Java array has. Students that come to C++ from some more protective language such as Pascal will find the low level, non-protective C/C++ array notion to be a concern at the least. I will give some of the concerns, and a bit of the reasoning behind them. I usually discuss these ideas in my presentation of the array concept.
5.1 Introduction to Arrays
C++ has adopted the (low-level) C notion of array without change.  In C++ the notion of array is quite 'low level'. By this I mean that in C++, arrays, along with pointers and the notion of conversion of an array to a pointer, provide a mechanism that closely models memory and address concepts in traditional computer hardware. The concept is both simple and general, and has the potential to be quite efficient -- and, in careless hands, it is quite dangerous.

We have said that the C++ array mechanism provides no protection against abuse and error. Ellis and Stroustrup (ARM page 137) point out the low-level nature of C++ arrays result in the following major limitations:

1) An array is of fixed size, with the size specified at compile time.
2) An array is one-dimensional. Multidimensional arrays in C/C++ are arrays of base type arrays.
3) An array is not self-describing. Given a pointer to an array, there is no information to determine the size of an array.

This last property means that passing an array as a function parameter is inherently dangerous. The array type deteriorates into a pointer when passed as a function parameter. This implies that a separate size parameter must be provided for safety if a function is to have an array argument.

If any of the properties mentioned are a problem in programming, the C++ programmer always has the option to create an ADT by embedding the array in a class. This class could overload the [] operator and provide array bounds checking, variable array size, or otherwise addresses the above properties that are seen as shortcomings in a given setting.
Declaring and Referencing Arrays
Be careful with the terminology. The text points out that there is much terminology, and it varies greatly. The problems will usually be with students who have some programming experience, but not enough to allow them to be comfortable with a change in the words used to describe these ideas.

A particular problem that my Pascal refugees have is that Pascal provides the start and ending array indices, both extremes of which are usable. Unless a programming problem calls for an array to start at some value other than 1, the Pascal arrays traditionally start at 1 and run to the given size.  On the other hand, C/C++ arrays always run from 0 to one less than the array size. The starting index is not mentioned in the declaration, and the number that is mentioned, the size of the array, is not a usable index.

A difficulty Java students have is caused by the fact that Java arrays have member functions. I have seen students who know Java well, when asked to write a low-level stand-alone copy function for arrays use the array as if it were a Java array or a C++ vector.

My students tend to confuse the use of the [] in x[4] in a declaration, as in int x[4]; with the use of the [] in x[3] in an access to the array. I think the problem should be mentioned to your classes. The text discusses this at the top of page 173. In x[4] the [] are technically array declarators. In x[3] the [] are the index operator

Arrays in Memory
As mentioned in the opening paragraph, C/C++ arrays do not provide array bounds checking. If an index outside the array bounds is used, strange results may occur. Unfortunately, out of bounds array index use is not guaranteed to cause a problem. If an MS DOS, Windows 9x (includes Me), or pre-OS-X Mac platform is used, there is significant potential for hanging the machine by overwriting an important address that belongs to the operating system.

Better protection is promised in the latest Macintosh operating system (OS-X) and Windows 2000 and XP. I can’t speak about the Mac as I have never used one. I have done some programming under Windows NT and 2000. These are more stable platforms than Windows 9x. However, Windows 9x is sufficiently unstable that I cannot recommend it for any programming. Windows 9x still tends to behave really strangely when a C++ application uses out of bounds array indices. Be careful. There be dragons. Reboot often.

You will hear students say that "with a bad write to memory, you can cause the hard disk to be reformatted." This isn't going to happen. My students appreciate being told this comforting bit of information. Most PCs today have EIDE controllers. These controllers do not have the capability to low-level format a hard disk without a utility from the manufacturer. The few SCSI controllers that exist in PCs may have disk utilities in ROM that could format a disk. It may be possible for inadvertent write to specific addresses to possibly start this menu on a machine with an operating system that does not protect memory. This is in fact unlikely, and if it did happen, it is unlikely to cause mischief.

Some operating systems run in a mode called protected memory mode. Such machines may be Suns or other Unix machines, machines running Linux, some version of BSD, NT or successor, or one of the (few) other fully protected mode operating systems. In these operating systems a physical address on an interface card cannot be reached. In these operating systems, the worst that can happen when array index is very far out-of-bounds is that a run time error can occur. These are reported on Linux system as a segmentation violation. Note that Microsoft Windows 9x and Me do not protect against much of anything. They crash in ways that are mysterious, some even make rebooting difficult.

Sun, HP, VAX, and other workstations run fully protected mode operating systems, usually a Unix variant or a NT or successor.

Finally, an understanding of what happens when you index into an array based on the memory model presented in the text (Display 5.2, page 178) is of great importance. 

Initializing Arrays
In initializing an array,
  int children[3] = {1, 12, 1};
the number of initializers must be no greater than the declared size of the array. There can be fewer initializer. In such an event the first array entries will be initialized from the list, the C++ Standard says the arrays are to be initialized to a zero appropriate to the type. Note that this is true even for primitive types and for class types, where the default constructor is used for the “zero of appropriate type.”  However, if there are no initializers, and the base type is primitive, the array is not initialized all. If the base array type is a class type, if there are no initializers, the default constructor is called for each array item. At least this is what the C++ Standard says, and all three of my compilers seem to do this. (Specifically, I have tried this on Linux and g++-2.9.5 and g++-3.0, Borland 5.0 IDE, Borland’s command line compiler 5.5, and VC++ 6.0).

5.2 Arrays in functions
Here the student must do the self-test exercises, and make up her own exercises. The code fragments should be tested by embedding them in small programs as suggested in the exercises. This stuff isn't difficult, but it does require substantial exposure over a period of time to internalize the ideas....

Download PDF : Arrays

0 commentaires: