Chapter 5: Using the Container Classes

OVERVIEW

Practically every programmer has used arrays, and many have used linked lists. These are the two most widely used containers for holding multiple items of data in many programming languages. But both these containers suffer from limitations. While an array has the great advantage of giving us constant-time access to its elements, its principal limitation is that you have to know its size in advance—before you start placing data in it. If you did not know in advance the size needed for an array, you would probably declare an array so large as to suffice for the worst possible case. As a consequence, the array could be too large for most runs of the program—leading to inefficient memory utilization—or not large enough because you underestimated the size needed for the worst case—leading to program crash.^[1] Another serious limitation of an array is that once an array is declared and initialized, it is not possible to insert new elements into the array or delete any existing elements without writing additional code for creating a new array.

On the other hand, linked lists have the advantage of being perfectly flexible with regard to their size. You do not need to know in advance how much data you'd be storing in a linked list. You can make a linked list larger by inserting a new node anywhere—at the beginning, in the middle, or at the end. And you can cause a linked list to shrink by deleting nodes anywhere you do not need them. But this convenience of linked lists come at a price. First, insertion of new elements and removal of existing elements requires that you pay close attention to memory allocation and deallocation. Additionally, you are stuck with inefficient access to the data items stored in the nodes of a linked list. Since a linked list does not allow for random access, locating a data item may require searching sequentially starting from the first node and working your way to the end.

The container classes of the C++ Standard Template Library (STL) and those that come with the Java Collections Framework are designed to redress the various shortcomings mentioned above by providing us with a variety of containers that combine the desirable features of arrays with the desirable features of linked lists without exposing the users to memory management issues. For example, a modern container such as a vector in C++ or an ArrayList in Java can combine the best of a conventional array—constant-time access to the elements—with most of the best of a linked list—insertions and deletions anywhere (although not as efficiently as a pure linked list). So if an application needs a dynamically expandable container for which constant-time access to the elements is of critical importance, but in which you only occasionally need to insert or delete elements, you'd choose a vector in C++ or an ArrayList in Java. On the other hand, if you had an application in which the insertions and deletions anywhere were of critical importance, and you did not need constant-time array-like access and you did not want to bother with memory allocation and deallocation yourself, you'd use the STL container list in C++ and the container LinkedList from the Java Collections Framework. This kind of reasoning can be used to choose for an application the container that best suits the application.

In addition to the container classes, the C++ Standard Template Library and the Java Collections Framework also provide algorithms that can be used with the containers for sorting, searching, inserting, deleting, shuffling, and so on. To give the reader a flavor of these algorithms, we will use some of them when we present example code illustrating the various container classes.

The main aim of this chapter is the same as for the last chapter—to provide the reader with an early familiarity with useful objects that can then be used in later chapters to exemplify the more basic ideas in C++ and Java. So it is possible that some of the programming syntax that you will see in this chapter will seem strange. If that's the case, the author hopes that the strange syntax will not be a source of frustration and that it will only raise questions in the mind of the reader that he/she would want to see resolved in the later chapters of the book.

^[1]What if some application required you to place all the words in a text file in an array of strings. If the size of the file was allowed to be arbitrary, how would you know what sized array to declare? You'd probably try to guess the largest size that your program would have to deal with, and then use that number for the array declaration. But what if that guess proved to be wrong at some future time?