C++ Notes: Arrays - Problems and Solutions
Inherent Problems
Arrays can be difficult to use reliably for several reasons.
Unknown maximum size of an array
Because arrays are implemented as a pointer to the first element of the
allocated storage, the length, or maximum allocated size, is not generally
available. It's necessary to pass this maximum size to functions which
need to add elements to an array. [Note: Vectors solve this problem.]
Lack of current number of elements
The number of elements currently in an array is another quantity
that the programmer must keep track of. [Note: Vectors solve this problem.]
Fixed size
The programmer has to decide how much memory to allocate for an
array, but sometimes there may be large variations in the requirements.
For example, I was just writing a program to process daily mutual
fund values. The data is downloaded from a service that provides
this data, but I don't know how much data there will be for any fund. It can
vary from a few entries for new funds to many years of data. How big
should I declare the arrays? If I make all arrays large enuf for
the largest possible number of data points (50 years?), then memory
usage will be very wasteful and the program might not even fit into memory on some
machines. If I make the arrays smaller, there might not be suffcient
space for all data. [Note: Vectors solve this problem.]
Lack of subscript checking
C++ doesn't check subscription to see that the subscript is in a
legal range. This lack of checking means that errors are often
undetected for a long time. This is also the source of the most
common hacker exploitation of programs, known as the
buffer overflow exploit. [Note: Vectors can solve this problem. Also, Java and C# provide bounds checking.]
Buffer Overflow
Imagine that in the previous
example, which involved reading numbers into an array,
the input consisted of more than 1000 (the size of the array)
numbers. What happens? The numbers are read into memory
locations after the end of the array. What is the consequence
of this? Hmmmm, that's what hacker knowledge is all about.
[Note: Vectors solve this problem.]
Solutions
Dynamic allocation - Solution to fixed size restriction
Arrays can be dynamically allocated, which is a nice solution
for some problems. But you have to be comfortable with
pointers before using dynamic allocation
(Dynamic Allocation of Arrays).
[Note: This is how vectors are implemented.]
Vectors - Solution to buffer overflow, fixed size, unknown maximum and current size, ...
Object-oriented programming libraries, such as the STL (Standard Template Library)
which comes with modern versions of C++, provide data structures
which are nice replacements for arrays. The simplest alternative
is vector
, which is
essentially a kind of expandable array.