Chapter 4Using Abstract Data TypesNothing remained in whose reality she could believe, savethose abstract ideas.— Virginia Woolf, Night and Day, 1919Objectives•To appreciate the advantages of abstract data types as a software development strategy.• To develop significant facility with the Vector, Grid, Stack, Queue, Map, Lexicon,and Scanner classes from the client perspective.• To understand the angle-bracket syntax required to use parameterized types in C++.• To be able to explain the explain the advantages of the Vector and Grid classes overone- and two-dimensional arrays with regard to flexibility and safety.• To understand the difference between the Stack and Queue classes in terms of theordering of their elements.• To gain some experience with the strategy of discrete-time simulation.• To understand the Map class as a mapping from keys to values and to develop someintuition about when to use it.• To know how to use the Lexicon class as an easily searchable list of words.• To understand how to use the Scanner class to extract tokens from a string or an inputfile.• To appreciate the role of iterators in working with abstract classes.Using Abstract Data Types – 124 –As you know from your programming experience, data structures can be assembled toform hierarchies. The atomic data types—such as int, char, double, and enumeratedtypes—occupy the lowest level in the hierarchy. To represent more complexinformation, you combine the atomic types to form larger structures. These largerstructures can then be assembled into even larger ones in an open-ended process.Collectively, these assemblages of information into more complex types are called datastructures.As you learn more about programming, however, you will discover that particular datastructures are so useful that they are worth studying in their own right. Moreover, it isusually far more important to know how those structures behave than it is to understandtheir underlying representation. For example, even though a string might be representedinside the machine as an array of characters, it also has an abstract behavior thattranscends its representation. A type defined in terms of its behavior rather than itsrepresentation is called an abstract data type, which is often abbreviated to ADT.Abstract data types are central to the object-oriented style of programming, whichencourages thinking about data structures in a holistic way.In this chapter, you will have a chance to learn about seven classes—Vector, Grid,Stack, Queue, Map, Lexicon, and Scanner—each of which represents an importantabstract data type. For the moment, you will not need to understand how to implementthose classes. In subsequent chapters, you’ll have a chance to explore how each of theseclasses can be implementated and to learn about the algorithms and data structuresnecessary to make those implementations efficient.Being able to separate the behavior of a class from its underlying implementation is afundamental precept of object-oriented programming. As a design strategy, it offers thefollowing advantages:• Simplicity. Hiding the internal representation from the client means that there arefewer details for the client to understand.• Flexibility. Because a class is defined in terms of its public behavior, the programmerwho implements one is free to change its underlying private representation. As withany abstraction, it is appropriate to change the implementation as long as the interfaceremains the same.• Security. The interface boundary acts as a wall that protects the implementation andthe client from each other. If a client program has access to the representation, it canchange the values in the underlying data structure in unexpected ways. Making thedata private in a class prevents the client from making such changes.The ADT classes used in this book are inspired by and draw much of their structurefrom a more advanced set of classes available for C++ called the Standard TemplateLibrary, or STL for short. Although the STL is extremely powerful and provides somecapabilities beyond the somewhat simplified class library covered in this book, it is alsomore difficult to understand from both the client and implementation perspectives. Oneof the primary advantages of using the simplified class library is that you can easilyunderstand the entire implementation by the time you finish this book. Understanding theimplementation gives you greater insight into how classes work in general and whatlibraries like the Standard Template Library are doing for you behind the scenes.Experience has shown, however, that you will be able to understand the implementationof a class more easily if you have first had a chance to use with that class as a client.Using Abstract Data Types – 125 –4.1 The Vector classOne of the most valuable classes in the Standard Template Library and the simplifiedversion of it used in this book is the Vector class, which represents a generalization ofthe array concept presented in section 2.4. To use the Vector class, you must include itsinterface, just as you would for any of the libraries in Chapter 3. The interfaces for eachof the ADT classes introduced in this chapter is simply the name of the class spelled witha lowercase initial letter and followed with the extension .h at the end. Every programthat wants to use the Vector class must therefore include the line#include "vector.h"Arrays are a fundamental type in almost all programming languages and have beenpart of programming language designs since the beginnings of the field. Arrays,however, have a number of weaknesses that can make using them difficult, such as thefollowing:• Arrays are allocated with a particular size that doesn’t change after the array isallocated.• Even though arrays have a fixed size, C++ does not in fact make that size available tothe programmer. In most applications, you need to keep track of the effective size ofthe array, as discussed in Chapter 2.• It is impossible to insert new elements into an array or to delete elements withoutwriting a fair amount of code to shift the existing elements to new index positions.• Many languages, including both C and C++, make no effort to ensure that the elementsyou select are actually present in the array. For example, if you create an array with 25elements and then try to select the value at index position 50, C++ will not ordinarilydetect this as an error.