C++: Data Structures: Physical Structures - Arrays
Physical Grouping
- Structs (Records)
- Grouping different types of elements in fields accessed by name is important,
yet there is little algorithmically interesting
in most programming languages about
accessing the fields since they are simply accessed by name.
This type of structure does get more interesting when it's
implemented in a relational database and manipulated
with SQL. The other extension of structs that is
interesting is class, which will be revisited below.
- Arrays
- Arrays of same type elements at are accessed by number
are bound very closely to the hardware in
that elements are stored in consecutive memory locations.
This is a source of both great efficiency and
numerous problems. Arrays are algorithmically interesting and
much attention is devoted to such issues as sorting, searching, insertion,
and deletion.
The problem with physical grouping (arrays)
Using physical grouping such as arrays has a very
high price. The programmer is always faced with the problem of what
to do when the array is full and there is more data. There are
several approaches, each with its own serious problems:
- Ignore the problem - This classic "solution" is one of the leading
sources of bugs and opens the door to hackers.
- Produce an error - It's better for a program to stop with an error
than continue apparently doing something but with a bug in the
computation. But of course, it is then failing to solve some user's
problem.
- Reallocate a larger array - This isn't a bad solution if all uses
of the array are easily controlled so that the address of the expanded
array is easily used by everyone. If the array address has been passed as a
parameter, it is unlikely that everyone will be referring to the new
array, so some other solution has to be used, eg, handles (pointers
to pointers), and similarly for the variable that records the current
maximum allocation. The other complication is that the need to increase the size
may occur many places in the program, necessitating many checks.
Some of this complication can be put into a function, but it only takes one
place where the function isn't called to produce a bug.