Download PDF : Arrays
Download PDF : Arrays
Introduction
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....
0 commentaires: