GO
home account info subscribe login search FAQ/help site map contact us


 
Brief Full
 Advanced
      Search
 Search Tips
[an error occurred while processing this directive]
Previous Table of Contents Next


CHAPTER 7
THE STANDARD TEMPLATE LIBRARY’S CONTAINER CLASSES

How do I...

7.1  Create a container object that automatically grows or shrinks as needed?
7.2  Read a single element of a container?
7.3  Modify a single element of a container?
7.4  Use a generic LIFO data model?
7.5  Prevent automatic reallocation of a container?
7.6  Traverse through a container’s elements?
7.7  Implement a queue data model?

A container is essentially an object that can hold other objects as its elements. Generally, you can add an element to a container and remove an existing element from it. A container is not confined to a specific type—it can store objects of any kind. Such a container is said to be generic. C supports one container type in the form of built-in arrays (more information on arrays can be found in Chapter 1, “A Quick Introduction to the Language”). Other languages support other data models. Pascal, for example, has a set type, and Lisp supports lists (hence its name).

C++ inherited its support for arrays from C. Arrays have several properties that, more or less, correspond to the mathematical notion of a vector:

  Arrays can store any data type.
  Arrays provide random access, meaning the time needed to access any element is identical, regardless of the element’s position (this is not the case in lists, for example).

Still, under some circumstances, arrays are less convenient than other data models—for example, it is impossible to insert a new element in the middle of an array. Furthermore, you cannot append new elements to the end of an array. Other containers enable these operations. Conversely, a list enables you to append new elements at its end. A special type of a list, a heterogenic list, can hold elements of different types at the same time.

For years, programmers were implementing their own lists, queues, sets and other container types to make up for the lack of language support. Yet homemade containers incur significant drawbacks. They are not portable; they are sometimes less than 100 percent bug free; their interfaces vary from one implementer to another; they can be less than optimal in terms of runtime performance and memory usage.

In the latest phase of the standardization of C++, Alex Stepanov, a professor and a mathematician, suggested adding a generic library of containers and algorithms to C++. He based his proposal on a similar generic library that he designed for Ada a decade earlier. At that time (November 1993), the committee was under pressure to complete the ongoing standardization process as quickly as possible. Consequently, suggestions for language extensions were rejected, one after another. Yet Stepanov’s proposal was too good to be forsaken. The committee adopted it unanimously.

In essence, the proposed generic library was a collection of containers based on mathematical data models such as vectors, queues, lists, and stacks. It also contained a set of generic algorithms such as sort, merge, find, replace, and so on. Because both constituents of the library, namely containers and algorithms, were designed to be completely generic, they were implemented with templates. To create a uniform interface, operator overloading was also used extensively.

In this chapter, you will explore the following containers of the Standard Template Library (STL): vectors, strings, stacks, lists, and queues. Iterators and their role in the STL framework will also be discussed. Finally, some other containers, as well as “almost container” classes of the Standard Library, will be discussed.

Please note that several compilers will generate warnings from some of the sample code listings used throughout the chapter. You can be safely ignore warnings regarding mixed unsigned/signed integers in relational expressions, and warnings that method names are too long and have to be truncated by the debugger. These warnings result from the specific implementation of the Standard Template Library your compiler is using. The code will run if the warnings are ignored.

7.1 Create a Container Object That Automatically Grows or Shrinks as Needed

This How-To shows how to create an instance of a container object. The demonstration starts with the most widely used container, the vector.

7.2 Read a Single Element of a Container

Two ways to read a single element are from a vector and a string. The first is by using the overloaded subscript operator. The second is by using the member function at(). The benefits and drawbacks of each access method will be explained, and rules of thumb provided for choosing the appropriate one.

7.3 Modify a Single Element of a Container

The two methods for reading an element of a vector also enable the user to modify the element’s value. This How-To will demonstrate how it is done.

7.4 Use a Generic LIFO Data Model

For some applications, a last-in-first-out (LIFO) data model is very convenient. This How-To demonstrates how to use the stack container to simulate a simplified exception handling mechanism.

7.5 Prevent Automatic Reallocation of a Container

The best thing about STL containers is that they free the programmer from worrying about manual reallocation of memory after a container has consumed its initial storage. When the container has consumed its free storage and additional elements have to be inserted, the container reallocates itself. The reallocation process consists of four steps. First, a new memory buffer is allocated large enough to store the container plus additional headroom. Second, existing elements are copied to the new location. Third, the destructors of the elements in their previous location are invoked. Finally, the previous memory buffer is released. Reallocation is therefore costly in terms of performance. Moreover, it invalidates existing iterators. This How-To will demonstrate how one can avert reallocation.

7.6 Traverse Through a Container’s Elements

This How-To will explore the issue of iterators in STL. This How-To will explain what iterators are, how they differ from built-in pointers, and how they are used. In addition, const iterators are differentiated from plain iterators.

7.7 Implement a Queue Data Model

This How-To will demonstrate how to implement a queue using STL’s generic queue container. The properties of a queue data model and some of its real-world applications are discussed.


Previous Table of Contents Next


Products |  Contact Us |  About Us |  Privacy  |  Ad Info  |  Home

Use of this site is subject to certain Terms & Conditions, Copyright © 1996-1999 EarthWeb Inc.
All rights reserved. Reproduction whole or in part in any form or medium without express written permision of EarthWeb is prohibited.