In looking through Listing 13.14, you see that the Stringclass that you’ve built is begin-
ning to become pretty robust. You’ll also realize that it is a longer listing than what
you’ve seen. Fortunately, the Standard C++ Library provides an even more robust String
class that you’ll be able to use by including the <string>library.Linked Lists and Other Structures ......................................................................
Arrays are much like Tupperware. They are great containers, but they are of a fixed size.
If you pick a container that is too large, you waste space in your storage area. If you pick
one that is too small, its contents spill all over and you have a big mess.
One way to solve this problem is shown in Listing 13.9. However, when you start using
large arrays or when you want to move, delete, or insert entries in the array, the number
of allocations and deallocations can be expensive.
One way to solve such a problem is with a linked list. A linked list is a data structure that
consists of small containers that are designed to link together as needed. The idea is to
write a class that holds one object of your data—such as one Cator one Rectangle—and
that can point at the next container. You create one container for each object that you
need to store, and you chain them together as needed.
Linked lists are considered an advanced level topic. More information can be found on
them in Appendix E, “A Look at Linked Lists.”Creating Array Classes ........................................................................................
Writing your own array class has many advantages over using the built-in arrays. For
starters, you can prevent array overruns. You might also consider making your array class
dynamically sized: At creation, it might have only one member, growing as needed dur-
ing the course of the program.
You might also want to sort or otherwise order the members of the array. You might have
a need for one or more of these powerful array variants:- Ordered collection—Each member is in sorted order.
- Set—No member appears more than once.
- Dictionary—This uses matched pairs in which one value acts as a key to retrieve
the other value. - Sparse array—Indices are permitted for a large set, but only those values actually
added to the array consume memory. Thus, you can ask for SparseArray[5]or
SparseArray[200], but it is possible that memory is allocated only for a small
number of entries.
444 Day 13