Visual C++ 4.2 Standard Template Library Tutorial

Kalindi Sanghrajka, Rick Troemel, Nevenka Subotic-Burina, and Linda Koontz

October 1996

CONTENTS

1. About This Tutorial

2. Introduction to the Standard C++ Library

3. C++ Template Overview

4. The Standard Template Library

5. Sequence Containers

6. Associative Containers

7. Iterators

8. Container Adapters

9. The C++ String Class

10. Function Objects

11. Standard Template Library Algorithms

12. Standard C++ Library Language Support

13. Exception Handling

14. Standard C++ Library Diagnostics

15. Appendix A: STL References and Further Reading

16. Appendix B: STL Container Class Definitions

17. Appendix C: STL Container Class Methods

18. Appendix D: Allocator Class

1. About This Tutorial

1.1 Objectives

This tutorial will provide an overview of the Standard C++ Libraries as implemented in Microsoft® Visual C++® version 4.2, with an emphasis on the Standard Template Library. Upon completion of this tutorial, you will be able to:

• Identify the different components of the Standard C++ Library.
  
  
• Write simple programs using Visual C++ version 4.2. that use the Standard Template Library components.
  
  
• Understand the Standard C++ Library implementation of exception handling and language support in Visual C++ version 4.2.

1.2 Prerequisites

This tutorial assumes that you understand basic C++ programming. It is also necessary to have a good understanding of C++ templates.

2. Introduction to the Standard C++ Library

2.1 Introduction

Every C++ programmer has probably, at one time or another, written a linked list or set, searching and sorting routines. Most likely, the programmer has re-invented the wheel for every new user-defined data type. Design changes are not easy to implement in such cases. Maintaining such code is not very easy, either.

If the common programming components were part of the C++ language, programmers would not need to "re-invent the wheel."

Finally, the C++ language provides you with general purpose components for common programming tasks through the Standard C++ Library. The Standard C++ Library provides powerful and flexible containers, programmable algorithms, and other components that are efficient and extensible.

The facilities provided by the Standard C++ Library are as follows:

• Language support: Provides common type definitions used throughout the library such as characteristics of predefined types, functions supporting start and termination of C++ programs, support for dynamic memory allocation, support for dynamic type identification, support for exception processing, and other run-time support.
  
  
• Diagnostics: Includes components for reporting several kinds of exceptional conditions, components for documenting program assertions, and a global variable for error number codes.
  
  
• General utilities: Includes components used in other elements of the Standard C++ Library. These components may also be used by any C++ programs. This category also includes components used by the Standard Template Library (STL) and function objects, dynamic memory management utilities, and date/time utilities. This category also includes memory management components from the C library.
  
  
• Strings: Includes components for manipulating sequences of characters, where characters may be of type char, w_char, or of a type defined in a C++ program. The library provides a class template, basic_string, that defines the basic properties of strings. The string and wstring types are predefined template instantiations provided by the library.
  
  
• Localization: Includes internationalization support for character classification and string collation; numeric, monetary, and date/time formatting and parsing; and message retrieval.
  
  
• The Standard Template Library (STL): Provides a C++ program access to the most widely used algorithms and data structures. STL headers can be grouped into three major organizing concepts: containers, iterators, and algorithms. Containers are template classes that provide powerful and flexible ways to organize data: for example, vectors, lists, sets and maps. Iterators are the glue that pastes together algorithms and containers. STL provides a large set of programmable algorithms to handle sorting, searching, and other common tasks.
  
  
• Numerics: Includes components to perform seminumerical operations and components for complex number types, numeric arrays, generalized numeric algorithms, and facilities included from the ISO C library.
  
  
• Input/output: Includes components for forward declarations of iostreams, predefined iostream objects, base iostream classes, stream buffering, stream formatting and manipulators, string streams, and file streams.

The Standard C++ Library also incorporates the Standard C Library.

2.2 Using the Standard C++ Libraries in Visual C++ 4.2

Microsoft® Visual C++® version 4.2 provides the Standard C++ Library facilities through included files and associated static and dynamic libraries.

A C++ program can use the different components of the Standard C++ Library by including the required header and linking with the appropriate static or dynamic library.

Tables 1 and 2 list all the Standard C++ Library headers and the associated static and dynamic libraries provided by Visual C++ 4.2.

Table 1. The Standard C++ Library Headers

Note   The Standard C++ Library headers do not have an “.h” extension. This is in accordance with the latest C++ working papers.

Visual C++ 4.2 includes the following static and dynamic libraries (in addition to the Microsoft Class Library [MFC]):

• Basic C run-time library
  
  
• Standard C++ Library from Plum Hall
  
  
• Old iostream library

Note   With Visual C++ 4.2, the iostream support has been pulled out of the C run-time library and exists as an independent entity. Now Visual C++ has the following libraries:

Table 2. Static and Dynamic Libraries Included with Microsoft Visual C++ 4.2

Case 1. Consider the following sample C++ program where test.cpp uses the Standard C++ Library iostream to print "Hello World".

// test.cpp
#include <iostream>
void main()
{
    cout << "Hello World" << endl ;
}

In Case 1, test.cpp used the Standard C++ Library input/output component to print "Hello World." The program just includes the Standard C++ Library header <iostream>. When compiling the program, specify a run-time library option: /ML[d],/MT[d], or /MD[d]. The program will then link with a basic run-time library (for example, LIBC.LIB with the /ML option) and a Standard C++ Library (for example, LIBCP.LIB with the /ML option). The /GX option enables exception handling. Exception handling must be enabled for any programs that use the Standard C++ Library.

It is important to remember that starting with Visual C++ 4.2, a C++ program, depending on the run-time library compiler option specified (/ML[d],/MT[d], or /MD[d]), will always link with one Basic C run-time library and, depending on headers included, will link with either a Standard C++ Library (as in the case 1), an old iostream library (as in Case 3), or neither (as in Case 2).

Case 2. Consider the following sample program:

// test.cpp
void main()
{
}

Case 3. Consider the following sample program:

// test.cpp
#include <iostream.h>
void main()
{
}

3. C++ Template Overview

3.1 Introduction

Many C++ programs use common data structures such as stacks, queues, and lists. Imagine a program that requires a queue of customers and a queue of messages. You could easily implement a queue of customers, and then take the existing code and implement a queue of messages. If the program grows and there is a need for a queue of orders you could take the queue of messages and convert it to a queue of orders. But what if you need to make some changes to the queue implementation? This would not be a very easy task because the code has been duplicated in many places. Re-inventing source code is not an intelligent approach in an object-oriented environment that encourages re-usability. It seems to make more sense to implement a queue that can contain any arbitrary type rather than duplicating code. How does one do that? The answer is to use Type Parameterization, more commonly referred to as Templates.

C++ templates allow one to implement a generic Queue<T> template that has a T type parameter. T can be replaced with actual types. For example, if the type parameter is <Customers>, C++ will generate the class Queue<Customers>. Therefore, changing the implementation of the Queue becomes relatively simple. In our example, once the changes are implemented in the template Queue<T>, they are immediately reflected in the classes Queue<Customers>, Queue<Messages>, and Queue<Orders>.

Templates are very useful when implementing generic constructs such as vectors, stacks, lists, and queues that can be used with any arbitrary type. C++ templates provide a way to reuse source code, as opposed to inheritance and composition, which provide a way to reuse object code.

C++ provides two types of templates: class templates and function templates. Use function templates to write generic functions: for example, searching and sorting routines that can be used with arbitrary types. The Standard Template Library generic algorithms have been implemented as function templates and the containers have been implemented as class templates.

3.2 Class Templates

3.2.1 Implementing a class template

A class template definition looks like a regular class definition, except it is prefixed by the keyword template. For example, here is the definition of a class template for a stack:

template <class T>

class Stack

{
public:
        Stack(int = 10) ; 
        ~Stack() { delete [] stackPtr ; }
        int push(const T&); 
        int pop(T&) ;  
        int isEmpty()const { return top == -1 ; } 
        int isFull() const { return top == size - 1 ; } 
private:
        int size ;  // number of elements on Stack.
        int top ;  
        T* stackPtr ;  
} ;

T is any type parameter, for example, Stack<Tokens>, where Token is a user defined class. T does not have to be a class type as implied by the keyword class. For example, Stack<int> and Stack<Message*> are valid instantiations, even though int and Message* are not classes.

3.2.2 Implementing class template member functions

Implementing template member functions is somewhat different than implementing the regular class member functions. The declarations and definitions of the class-template member functions should all be in the same header file. Why do the declarations and definitions need to be in the same header file? Consider the following:

//B.h
template <class t>
class b
{
public:
    b() ;
    ~b() ;
} ;

// B.cpp
#include “B.h”
template <class t>
b<t>::b()
{
}
template <class t>
b<t>::~b()
{
}

//main.cpp
#include “B.h”
void main()
{
     b<int> bi ;
     b <float> bf ;
}

When compiling B.cpp, the compiler has both the declarations and the definitions available. At this point, the compiler does not need to generate any definitions for template classes, since there are no instantiations. When the compiler compiles main.cpp, there are two instantiations: template classes B<int> and B<float>. At this point, the compiler has the declarations but no definitions!

While implementing class-template member functions, the definitions are prefixed by the keyword template. Here is the complete implementation of the Stack class template:

//stack.h
#pragma once

template <class T>

class Stack

{
public:
        Stack(int = 10) ; 
        ~Stack() { delete [] stackPtr ; }
        int push(const T&); 
        int pop(T&) ;  // pop an element off the stack
        int isEmpty()const { return top == -1 ; } 
        int isFull() const { return top == size - 1 ; } 
private:
        int size ;  // Number of elements on Stack
        int top ;  
        T* stackPtr ;  
} ;

//Constructor with the default size 10

template <class T>

Stack<T>::Stack(int s)

{
        size = s > 0 && s < 1000 ? s : 10 ;  
        top = -1 ;  // initialize stack
        stackPtr = new T[size] ; 
}

//Push an element onto the Stack. 

template <class T>

int Stack<T>::push(const T& item)

{
        if (!isFull())
        {
                stackPtr[++top] = item ;
                return 1 ;  // push successful
        }
        return 0 ;  // push unsuccessful
}

//Pop an element off the Stack.

template <class T> 

int Stack<T>::pop(T& popValue) 

{
        if (!isEmpty())
        {
                popValue = stackPtr[top--] ;
                return 1 ;  // pop successful
        }
        return 0 ;  // pop unsuccessful
}

3.2.3 Using a class template

Using a class template is very easy. Create the required classes by plugging in the actual type for the type parameters. This process is commonly known as instantiating a class. Here is a sample driver class that uses the Stack class template:

#include <iostream>
#include “stack.h”
void main()
{
        typedef Stack<float> FloatStack ;

        typedef Stack<int> IntStack ;

        FloatStack fs(5) ;
        float f = 1.1 ;
        cout << "Pushing elements onto fs" << endl ;
        while (fs.push(f))
        {
                cout << f << ' ' ;
                f += 1.1 ;
        }
        cout << endl << "Stack Full." << endl
                << endl << "Popping elements from fs" << endl ;
        while (fs.pop(f))
                cout << f << ' ' ;
        cout << endl << "Stack Empty" << endl ;
        cout << endl ;
        IntStack is ;
        int i = 1.1 ;
        cout << "Pushing elements onto is" << endl ;
        while (is.push(i))
        {
                cout << i << ' ' ;
                i += 1 ;
        }
        cout << endl << "Stack Full" << endl
                << endl << "Popping elements from is" << endl ;
        while (is.pop(i))
                cout << i << ' ' ;
        cout << endl << "Stack Empty" << endl ;
}

Here is the output:

Pushing elements onto fs
1.1 2.2 3.3 4.4 5.5 
Stack Full.
Popping elements from fs
5.5 4.4 3.3 2.2 1.1 
Stack Empty
Pushing elements onto is
1 2 3 4 5 6 7 8 9 10 
Stack Full
Popping elements from is
10 9 8 7 6 5 4 3 2 1 
Stack Empty

In the above example we defined a class template Stack. In the driver program we instantiated a Stack of float (FloatStack) and a Stack of int(IntStack). Once the template classes are instantiated, you can instantiate objects of that type (for example, fs and is.)

A very good programming practice is to use typedef while instantiating template classes. Then throughout the program, one can use the typedef name. There are two advantages:

• typedefs are very useful when “templates of templates” are used. For example, when instantiating an int STL vector, you could use:

  typedef vector<int, allocator<int> > INTVECTOR ; 
  

• If the template definition changes, simply change the typedef definition.

This practice is especially helpful when using STL components. There are many implementations of STL available, some of which are incompatible. The implementation in Visual C++ 4.2 may change in future versions. For example, currently the definition of the vector required you to specify an allocator parameter:

typedef vector<int, allocator<int> > INTVECTOR ;
INTVECTOR vi1 ;

In a future version, the second parameter may not be required, for example,

typedef vector<int> INTVECTOR ;
INTVECTOR vi1 ;

Imagine how many changes would be required if there was no typedef!

3.3 Sharing Data Using Static Members

Each instantiation of a class template has it’s own static members that are shared with other objects of that instantiation. This is true of static data members and static member functions.

3.4 Function Templates

To perform identical operation for each type of data compactly and conveniently, use function templates. You can write a single function template definition. Based on the argument types provided in calls to the function, the compiler automatically instantiates separate object code functions to handle each type of call appropriately. The STL algorithms are implemented as function templates.

Function templates are implemented like regular functions, except they are prefixed with the keyword template. Using function templates is very easy; just use them like regular functions. Here is a sample with a function template:

#include <iostream>
//max returns the maximum of the two elements
template <class T>
T max(T a, T b)
{
    return a > b ? a : b ;
}
void main()
{
    
    cout << "max(10, 15) = " << max(10, 15) << endl ;
    cout << "max('k', 's') = " << max('k', 's') << endl ;
    cout << "max(10.1, 15.2) = " << max(10.1, 15.2) << endl ;
}

Here is the output:

max(10, 15) = 15
max('k', 's') = s
max(10.1, 15.2) = 15.2

3.5 Template Specialization

In some cases it is possible to override the template-generated code by providing special definitions for specific types. This is called template specialization. For example:

#include <iostream.h>
//max returns the maximum of the two elements of type T, where T is a
//class or data type for which operator> is defined.
template <class T>
T max(T a, T b)
{
    return a > b ? a : b ;
}
void main()
{    
    cout << "max(10, 15) = " << max(10, 15) << endl ;
    cout << "max('k', 's') = " << max('k', 's') << endl ;
    cout << "max(10.1, 15.2) = " << max(10.1, 15.2) << endl ;
    cout << "max(\"Aladdin\", \"Jasmine\") = " << max("Aladdin", "Jasmine") << endl ;
}

Here is the output:

max(10, 15) = 15
max('k', 's') = s
max(10.1, 15.2) = 15.2
max("Aladdin", "Jasmine") = Aladdin

Not quite the expected results! Why did that happen? The function call max(“Aladdin”, “Jasmine”) causes the compiler to generate code for max(char*, char*), which compares the addresses of the strings! To correct special cases like these or to provide more efficient implementations for certain types, one can use template specializations. The above example can be rewritten with specialization as follows:

#include <iostream.h>
#include <string.h>
//max returns the maximum of the two elements
template <class T>
T max(T a, T b)
{
    return a > b ? a : b ;
}
// Specialization of max for char*
char* max(char* a, char* b)
{
    return strcmp(a, b) > 0 ? a : b ;
}
void main()
{
    
    cout << "max(10, 15) = " << max(10, 15) << endl ;
    cout << "max('k', 's') = " << max('k', 's') << endl ;
    cout << "max(10.1, 15.2) = " << max(10.1, 15.2) << endl ;
    cout << "max(\"Aladdin\", \"Jasmine\") = " << max("Aladdin", "Jasmine") << endl ;
}

Here is the output:

max(10, 15) = 15
max('k', 's') = s
max(10.1, 15.2) = 15.2
max("Aladdin", "Jasmine") = Jasmine

3.6 Templates and Friends

Friendship can be established between a class template and a global function, a member function of another class (possibly a template class), or even an entire class (possibly a template class). Table 3 lists the results of declaring different kinds of friends of a class:

Table 3. Friend Declarations

3.7 Class Templates and Nontype Parameters

The Stack class template, described in the previous section, used only type parameters in the template header. It is also possible to use nontype parameters. For example, the template header could be modified to take an int elements parameter as follows:

template <class T, int elements>
class Stack ;

Then, a declaration such as:

Stack<float, 100> mostRecentSalesFigures ;

could instantiate (at compile time) a 100 element Stack template class named mostRecentSalesFigures (of float values); this template class would be of type Stack<float, 100>.

3.8 Default Template Parameters

Let us look at the Stack class template again:

template <class T, int elements> Stack { ....} ; 

C++ allows you to specify a default template parameter, so the definition could now look like:

template <class T = float, int elements = 100> Stack { ....} ;

Then a declaration such as:

Stack<> mostRecentSalesFigures ;

would instantiate (at compile time) a 100 element Stack template class named mostRecentSalesFigures (of float values); this template class would be of type Stack<float, 100>.

If you specify a default template parameter for any formal parameter, the rules are the same as for functions and default parameters. Once a default parameter is declared, all subsequent parameters must have defaults.

3.9 Member Templates

The following example demonstrates member templates. When you define a class template or a function template as a member of a class, it is called a member template. Visual C++ 4.2 does not support member templates.

class MyAllocator 
{
        int size ;
        template class<T> class types; // member class template
        template class<T> print(T type) ;  // member function template
} ;

4. The Standard Template Library

4.1 Introduction

The Standard Template Library is a part of the Standard C++ Library. Every C++ programmer at one time or another has implemented common data structures such as a list or queue, and common algorithms such as binary search, sort, and so on. Through STL, C++ gives programmers a set of carefully designed generic data structures and algorithms. The generic data structures and algorithms are parameterized types (templates) that require only plugging in of actual types to be ready for use. Finally, STL brings to C++ the long promised dream of re-usable software components.

The STL components are well crafted solutions, which are efficient in code space and execution time.

4.2 STL Components

• Containers are objects that hold other objects.

  The sequential containers include vector, list, and deque.

  The associative containers include map, multimap, set, and multiset.

• Algorithms are generic functions that handle common tasks such as searching, sorting, comparing, and editing.

  Find, search, merge, count, reverse, and sort, are some of the algorithms provided by STL. For a complete list of algorithms refer to the documentation.

• Iterators are generalized pointers and act as the glue between containers and algorithms. STL algorithms are written in terms of iterator parameters, and STL containers provide iterators that can be plugged into the algorithms.

  STL provides the following iterators: input, output, forward, bidirectional and random access, ostream_iterator, and istream_iterator.

• Function objects are objects of any class or struct that overload the function call operator(). Most STL algorithms accept a function object as a parameter that can change the default behavior of the algorithm.

  STL defines function objects for basic arithmetic operations such as addition, subtraction, multiplication, and division. The associated function object types are plus, minus, times, and divides.

  STL also provides function objects for built-in operations such as unary, logical, bitwise, and comparison operators. The associated function object types are modulus, negate, equal_to, not_equal_to, greater, less, greater_equal, less_equal, logical_and, logical_or, and logical_not.

• Adapter is a component that modifies the interface of another component. For example, reverse_iterator is a component that adapts an iterator type into a new type of iterator with all the capabilities of the original, but with the same direction of traversal reversed. STL provides three kind of adapters: Container Adapter, Iterator Adapter, and Function Adapters.
  
  
• Container adapters provided by STL include stack, queue, and priority_queue.
  
  
• Iterator adapters provided by STL include reverse iterators, reverse_bidirectional_iterator, back_insert_iterator, front_insert_iterator, and insert_iterator.
  
  
• Function adapters provided by STL include not1, not2, bind1st, and bind2nd.

These very general components are designed to "plug together" in myriad different useful ways to produce the kind of larger and more specialized components required by programs.

4.3 General Rules About STL and User-Defined Data Types

• When an object is used with an STL container, it is copied (the copy constructor is called) first and the copy is what is actually inserted into the container.

  This means an object held by an STL container must have a copy constructor.

• When an object is removed from an STL container, the object is destroyed (the destructor is called).
  
  
• When an STL container is destroyed, it destroys all objects it currently holds.
  
  
• Many STL components rely on making comparisons of the objects they hold (<, <=, >, >=, ==, !=).

  This means the comparison operators must be defined for objects used with an STL component.

• Some STL components modify the value of an object. This is accomplished using the assignment operator.

  This means the assignment operator ( = ) must be defined for objects used with an STL component.

The header file <utility> defines global versions of the <=, >, >=, and != operators, which are all defined in terms of the < and ==. Therefore, if only the < and == operators are defined, the rest are defined "for free" (if any of the rest are explicitly defined for an object, the explicit definition will override the global definition).

In general, it is assumed that objects to be used with STL containers have at least the following:

• A copy constructor.
  
  
• An assignment operator ( = ).
  
  
• An equality comparison operator ( == ).
  
  
• A less than comparison operator ( < ).

5. Sequence Containers

Sequence containers store and retrieve their data in a sequential fashion. There are three different sequence containers defined in STL: vector, deque and list.

5.1 Vector

#include <vector>
vector<class TYPE, allocator<class TYPE> >

A vector is similar to a normal C array, except that it can change size automatically as needed. Data access or modification is random and can be accomplished via operator[]. Insertion or erasure is efficient at the end only. Insertion or erasure of data at the beginning or in the middle requires shifting the entire array. Therefore, insertion or erasure anywhere but at the end is a linear operation, meaning that the time to execute the operation is a function of the number of elements that must be shifted right or left. Insertion or erasure at the end is a constant operation, meaning that the time to execute the operation will remain unchanged regardless of how many (or how few) elements are in the array.

The following function declares a vector of 10 ints, fills the vector with the values 0 - 9, and then prints the values.

     typedef vector<int, allocator<int> > INTVECT;
     void somefunct()
     {
     // declare an INTVECT with slots for 10 ints
          INTVECT myVector(10);
          int i;

          for(i = 0; i < 10; i++) // fill myVector with the values 0 - 9
               myVector[i] = i;

          for(i = 0; i < 10; i++)  // print the values in myVector
               cout << myVector[i] << ", ";
          cout << endl;
     }

Output of somefunct:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

See APPENDIX B for the vector class definition.

See APPENDIX C for a table of vector methods.

See APPENDIX D for an explanation of the allocator class (second template parameter above).

5.2 Deque

#include <deque>
deque<class TYPE, allocator<class TYPE> >

A deque is similar to a vector, except that insertion or erasure is efficient at either the beginning or the end. Like a vector, data access or modification is random and can be accomplished via operator[]. Insertion or erasure at either the beginning or the end is a constant operation, meaning that the time to execute the operation will remain the same, regardless of how many elements are in the array. Insertion or erasure anywhere in the middle is a linear operation, meaning that the time to execute the operation is a function of the number of items that must be shifted right or left. A deque will generate larger, slower code than a vector. In general, a vector should be used if efficient insertion/erasure at the beginning of the array is not required and a deque should be used if it is.

The following function declares a deque of ints, fills the deque with the values 0-9, inserting each new value at the beginning, then prints the values.

 typedef deque<int, allocator<int> > INTDQ;
     void somefunct()
     {
          INTDQ myDeque;     // declare a deque of ints
          int i;
          for(i = 9; i >= 0; i--)
               myDeque.push_front(i);
          
          for(i = 0; i < 10; i++)
               cout << myDeque[i] << ", ";
          cout << endl;
     }

Output of somefunct:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

• See APPENDIX B for the deque class definition.
  
  
• See APPENDIX C for a table of deque methods.
  
  
• See APPENDIX D for an explanation of the allocator class (second template parameter above).

5.3 List

#include <list>
list<class TYPE, allocator<class TYPE> >

A list, like a vector or a deque, is an extensible array. Lists are implemented as doubly linked lists. Therefore, insertion or erasure at any point in the array is a constant operation, meaning that the time to execute the operation will remain the same, regardless of how many elements are in the list. The penalty for using a list instead of a vector or a deque is paid in data access. There is no random access (no operator[]) for a list, meaning that accessing the nth object in a list requires "surfing" from the beginning of the list through N-1 objects. The following function declares a list of ints, fills the list with the values 0-9, inserting each new value at the beginning, and then prints the values.

 typedef list<int, allocator<int> > INTLIST;
     void somefunct()
     {
          INTLIST myList;     // declare a list of ints
          INTLIST::iterator myListPtr;   // and an iterator
          int i;
          for(i = 9; i >= 0; i--)
               myList.push_front(i);
          
          for(myListPtr = myList.begin(); myListPtr != myList.end();
                      myListPtr++)
               cout << *myListPtr << ", ";
          cout << endl;
     }

Output of somefunct:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

• See APPENDIX B for the list class definition.
  
  
• See APPENDIX C for a table of list methods.
  
  
• See APPENDIX D for an explanation of the allocator class (second template parameter above).

6. Associative Containers

Associative containers store and retrieve their objects according to an association with each other. In other words, the data is stored and retrieved in a sorted order. Therefore, associative containers rely heavily upon comparison operators. There are four different associative containers defined in the STL. They are: set, multiset, map and multimap.

6.1 Set and Multiset

#include <set>
set<TYPE, PREDICATE, ALLOCATOR>

A set is optimized for fast associative lookup. For lookup purposes, objects are matched using operator==. Objects are ordered within the set according to the user-defined comparator object (the second template argument). The comparator object is typically "less<TYPE>", which causes the data to be sorted in ascending order. Each object in a set has a unique value, as duplicate objects are not allowed. A multiset is similar to a set, except that a multiset can contain objects with duplicate values.

The following function declares a set of ints, fills it with 10 random values, then prints them:

     typedef set<int, less<int>, allocator<int> > INTSET;

     void somefunct()
     {
                INTSET mySet;   // declare a set of ints
                INTSET::iterator mySetPtr;      // and an iterator for the set
                int tmpVal;

                srand(13);      // seed the rand function
          // fill the set with 10 random ints - print them as they are added.
                for(int i = 0; i < 9; i++){
                        tmpVal = rand();
                        cout << tmpVal << ", ";
                        mySet.insert(tmpVal);
                }
                cout << endl;

                // print the contents of the set (note the values are sorted)
                for(mySetPtr = mySet.begin(); mySetPtr != mySet.end();
                    mySetPtr++)
                        cout << *mySetPtr << ", ";

                cout << endl;
     }

Output of somefunct:

81, 16376, 24096, 20348, 11872, 30076, 16059, 26999, 28493,
81, 11872, 16059, 16376, 20348, 24096, 26999, 28493, 30076,

• See APPENDIX B for the set and multiset class definitions.
  
  
• See APPENDIX C for a table of set and multiset methods.
  
  
• See APPENDIX D for an explanation of the allocator class (third template parameter above).

6.2 Map and Multimap

#include <map>
map<KEY, TYPE, PREDICATE, ALLOCATOR>

A map holds a set of ordered key/value pairs. The pairs are ordered by key, based upon the user-defined comparator object (3rd template parameter). A map defines a one-to-one relationship, allowing only one value to be associated with a particular key; a multimap defines a one-to-many relationship, allowing many values to be associated with a particular key.

The following declares a map of ints to strings, fills it with 10 key/value pairs and prints them:

     typedef map<int, string, less<int>, allocator<string> > INT2STRING;
     void somefunct()
     {
                 INT2STRING myMap;
                 INT2STRING::iterator i2sPtr;

      // Fill myMap with the digits 9 - 0 in reverse order, 
          // each mapped to its character string counterpart
             myMap.insert(INT2STRING::value_type(9,"Nine"));
             myMap.insert(INT2STRING::value_type(8,"Eight"));
             myMap.insert(INT2STRING::value_type(7,"Seven"));
             myMap.insert(INT2STRING::value_type(6,"Six"));
             myMap.insert(INT2STRING::value_type(5,"Five"));
             myMap.insert(INT2STRING::value_type(4,"Four"));
             myMap.insert(INT2STRING::value_type(3,"Three"));
             myMap.insert(INT2STRING::value_type(2,"Two"));
             myMap.insert(INT2STRING::value_type(1,"One"));
             myMap.insert(INT2STRING::value_type(0,"Zero"));

          // Now print the pairs - note they are now sorted
          // into ascending order...
                 for(i2sPtr = myMap.begin(); i2sPtr != myMap.end(); i2sPtr++)
                         cout << "(" << (*i2sPtr).first << ", "
                              << (*i2sPtr).second << “)” << endl;
  }

Output of somefunct:

(0, Zero)
(1, One)
(2, Two)
(3, Three)
(4, Four)
(5, Five)
(6, Six)
(7, Seven)
(8, Eight)
(9, Nine)

• See APPENDIX B for the map and multimap class definitions
  
  
• See APPENDIX C for a table of map and multimap methods
  
  
• See APPENDIX D for an explanation of the allocator class (fourth template parameter above)

7. Iterators

Iterators are generalized pointers that may be used to traverse the contents of a sequence (for example, an STL container or a C++ array).

• Iterators provide data access for both reading and writing data in a sequence.
  
  
• A C++ pointer is an iterator, but an iterator is not necessarily a C++ pointer.
  
  
• Iterators, like pointers can be dereferenced, incremented and decremented.
  
  
• At any point in time, an iterator is positioned at exactly one place in one collection, and remains positioned there until explicitly moved.

7.1 Types of Iterators

7.1.1 Table of iterator categories

There are five categories of iterators. With the exception of input and output iterators, the relationship between each category of iterator is hierarchical: each iterator inherits the characteristics and behavior of the previous type, as Table 4 illustrates:

Table 4. Iterator Categories and Characteristics

In classical C++ terms, input and output iterator classes are base classes, the forward iterator class is doubly derived from both the input and output iterator classes, the bidirectional iterator class is derived from the forward iterator class, and the random access iterator class is derived from the bidirectional iterator class. This hierarchy implies the following:

• An algorithm that requires only input or output iterators can also be used with forward, bidirectional, or random access iterators.
  
  
• An algorithm that can be used with forward iterators can also be used with bidirectional or random access iterators.
  
  
• An algorithm that can be used with bidirectional iterators can also be used with random access iterators.

It should also be noted that regular C++ pointers fit the characteristics of a random access iterator (and in fact can be used as a random access iterator for STL operations that support random access iterators).

7.2 Iterator Interface Requirements

Different iterator types are required to have a minimum set of interface functions defined, which conform to the behaviors described below. For the following, the value type T is understood to be the data type of the underlying container that the iterator is interfacing with (for example, for a vector<int, allocator<int> >, T = int).

7.2.1 Input iterator interface requirements

A class or built-in data type X can be used as an input iterator for the value type T if and only if the following expressions are defined for X and meet the behavioral requirements stated below. For Table 5, assume a and b are values of type X, r is a reference of type X, and t is a value of type T.

Table 5. Input Iterator Required Behaviors

7.2.2 Output iterator interface requirements

A class or built-in data type X can be used as an output iterator for the value type T if and only if the following expressions are defined for X and meet the behavioral requirements stated below. For Table 6, assume a and b are values of type X, r is a reference of type X, and t is a value of type T.

Table 6. Output Iterator Required Behavior

7.2.3 Forward iterator interface requirements

A class or built-in data type X can be used as a forward iterator for the value type T if and only if the following expressions are defined for X, and meet the behavioral requirements stated below. For Table 7, assume a and b are values of type X, t is a value of type T, and r and s are references of type X.

Table 7. Forward Iterator Required Behavior

7.2.4 Bidirectional iterator interface requirements

A class or built-in data type X can be used as a bidirectional iterator for the value type T if and only if X conforms to the requirements of a forward iterator and defines the following expressions, which meet the behavioral requirements stated below. For Table 8, assume r and s are references of type X.

Table 8. Bidirectional Iterator Required Behavior

7.2.5 Random Access Iterator Interface Requirements

A class or built-in data type X can be used as a random access iterator for the value type T if and only if X conforms to the requirements of a bidirectional iterator and defines the following expressions, which meet the behavioral requirements stated below. For Table 9, assume a and b are values of type X, r is a reference of type X, and n is an int.

Table 9. Random Access Iterator Required Behavior

Note   STL provides global definitions of ">," ">=," "<=," and "!=" defined in terms of "==" or "<". This means that any object which defines "==" and "<" gets the rest “for free.”

7.3 Categories of Iterators Associated With STL Containers

The description of each STL container class includes the category of iterator types they provide. Table 10 lists the various STL containers and the iterators associated with each:

Table 10. STL Containers and Iterators

It is not necessary to remember which type of iterator works with which container. Each container, C<T>, supplies typedefs for iterators:

• iterator (mutable)
  
  
• const_iterator (nonmutable)

To declare an iterator, simply use the syntax C<T>::iterator or C<T>::const_iterator (see example below).

The following example illustrates how to declare an iterator for a vector of ints and use that iterator to display the values:

#include <vector>
#include <iostream>
typedef vector<int, allocator<int> > INTVECT;
void main()
{
     INTVECT myVector(5);     // declare a vector of 5 ints
     INTVECT::iterator myIter;     // declare an iterator for the vector
     for(int iv = 0; iv < 5; iv++)
          myVector[iv] = iv;      // fill the vector with values
     for(myIter = myVector.begin(); myIter != myVector.end(); myIter++)
          cout << *myIter << “, “;
     cout << endl;
}

Output:

0, 1, 2, 3, 4,

Note that the termination condition for the "for loop" was “myIter != myVector.end()” instead of “myIter < myVector.end()”. In the above example, the < operator would have worked because the iterator supplied by a vector is a random access iterator. If our container had been a list, the < operator would not have worked, as the < operator is not defined for the bidirectional iterator that list supplies. The moral of the story is that in such a situation, using != will give the same result and you don’t have to remember which kind of iterator a particular container is supplying.

7.4 Stream Iterators

One of the reasons input and output iterators are defined separately is so that they can be associated with I/O streams.

7.4.1 Istream iterators

STL provides a predefined iterator class called istream_iterator. The istream_iterator class is an input iterator. In Visual C++ version 4.2, istream_iterator<Value_Type, Char_Type, Traits_Type> is derived from the base class iterator<Value_Type, Char_Type, Traits_Type> and conforms to the requirements of an input iterator as described above. istream_iterator provides two constructors, one that takes an input stream as an argument (and ties the iterator to that stream). The other takes no arguments, and is used to provide an end-of-stream marker for several algorithms.

Note   Books Online says that istream_iterator takes two template parameters, Value_Type and Distance_Type, and is derived from input_iterator<Value_Type, Distance_Type>. The classes were modified to the structure stated above for Visual C++  4.2 to overcome some compiler limitations. A future version of Visual C++ will return to the structure and hierarchy reflected in the Books Online. The STL is an emerging standard and will undoubtedly be changed again in the future. In order to minimize the impact these types of changes will have on existing code, the use of typedefs is highly recommended when declaring a particular instantiation of any STL component.

The following fills a vector of strings from an input stream using the copy algorithm in conjunction with an istream_iterator:

// STRING_INPUT is an istream iterator for objects of type string
typedef istream_iterator<string, char, char_traits<char> > STRING_INPUT;
// STRVECTOR is a vector which holds objects of type string
typedef vector<string, allocator<string> > STRVECTOR;
void main()
{
     string FileName;
     STRVECTOR theStrings;
     cout << "Enter Input File Name: ";
     cin >> FileName;
     ifstream ifs(FileName.c_str());   // Open the file read only
     // read to eof, storing each string in theStrings.
     copy(STRING_INPUT(ifs),STRING_INPUT(),back_inserter(theStrings));
}

See section 7.6.1 for more information on the back inserter class.

7.4.2 Ostream iterators

STL provides a predefined iterator class called ostream_iterator. The ostream_iterator class is an output iterator. In Visual C++ version 4.2, ostream_iterator<Value_Type, Char_Type, Traits_Type> is derived from the base class iterator<Value_Type, Char_Type, Traits_Type> and conforms to the requirements of an output iterator as described above. ostream_iterator provides two constructors, one which takes an output stream as an argument (and ties the iterator to that stream). The other takes two arguments, an output stream (with the same effect as the one argument ctor) and a delimiting character, which will be inserted into the stream after each object.

The following is the sample from the istream_iterator section with a new addition. Now, the program prints the strings it has read to stdout, each on a new line. It accomplishes this by again calling the copy algorithm, this time in conjunction with the string container, and sends its output to an ostream_iterator object associated with cout:

// STRING_INPUT is an istream_iterator for objects of type string
typedef istream_iterator<string, char, char_traits<char> > STRING_INPUT;
// STRING_OUTPUT is an ostream_iterator for objects of type string
typedef ostream_iterator<string, char, char_traits<char> > STRING_OUTPUT;
// STRVECTOR is a vector which holds objects of type string
typedef vector<string, allocator<string> > STRVECTOR;
void main()
{
     string FileName;
     STRVECTOR theStrings;
     cout << "Enter Input File Name: ";
     cin >> FileName;
     ifstream ifs(FileName.c_str());   // Open the file read only
     // read to eof, storing each string in theStrings.
     copy(STRING_INPUT(ifs),STRING_INPUT(),back_inserter(theStrings));
// print the contents of theStrings to cout, 
// using copy and STRING_OUTPUT
     copy(theStrings.begin(), theStrings.end(),  
          STRING_OUTPUT(cout,"\n"));
}

7.5 Iterator Adapters

An adapter in STL is a wrapper class that takes an existing class and provides it with a new interface. There are two adapters provided by the STL for iterators: reverse iterators and insert iterators.

7.5.1 Reverse iterators

Reverse iterator adapters transform their iterators to traverse a collection from back to front. There are two adapters supplied by the STL: reverse_bidirectional_iterator, which transforms bidirectional iterators, and reverse_iterator, which transforms random access iterators. Each container, C<T>, supplies typedefs for reverse iterators:

• reverse_iterator (mutable)
  
  
• const_reverse_iterator (nonmutable)

to declare an iterator, simply use the syntax C<T>::reverse_iterator or C<T>::const_reverse_iterator (see example below).

The following example illustrates how to declare a reverse iterator for a vector of ints and use that iterator to display the values in reverse order:

#include <vector>
#include <iostream>
typedef vector<int, allocator<int> > INTVECT;
void main()
{
     INTVECT myVector(5);     // declare a vector of 5 ints
     // declare a reverse iterator for the vector
     INTVECT::reverse_iterator myIter; 
     for(int iv = 0; iv < 5; iv++)
          myVector[iv] = iv;      // fill the vector with values
     for(myIter = myVector.rbegin(); myIter != myVector.rend(); 
         myIter++)
          cout << *myIter << “, “;
     cout << endl;
}

Output:

4, 3, 2, 1, 0,

Note the use of rbegin and rend in the above example. Just as each type of STL container supplies begin and end member functions (which return regular iterators), each also supplies rbegin and rend member functions (which return reverse iterators).

When reverse iterators are passed to a generic algorithm, they make the algorithm work in reverse. Consider the sort algorithm:

sort(myVector.begin(), myVector.end());

Sorts the contents of myVector into ascending order, and:

sort(myVector.rbegin(), myVector.rend());

Sorts the contents into ascending order as seen from back to front, which results in the contents being sorted into descending order.

7.6 Insert Iterators

Insert iterators put an algorithm into insert mode. The most useful effect of this is that insert iterators use insert operations (which expand allocated memory as needed) instead of assignment operations (which assume the space is available) to add objects to a target container. This is done via a redefinition of operator*, so that *i = … calls one of the container’s insert functions instead of operator=. Consider the following use of the copy algorithm to copy the objects from a deque to a vector:

// v1 is and empty vector
vector<int, allocator<int> > v1;   
// d1 holds 100 1’s
deque<int, allocator<int> > d1(100, 1);
// causes an error
copy(d1.begin(), d1.end(), v1.begin());   

The call to copy above will cause a run-time error (probably a GPF) when *(v1.begin()) = *(d1.begin()) is called, because v1 does not have any memory allocated for itself. Replacing v1.begin() with an insert iterator, such as back_inserter will solve the problem as follows:

copy(d1.begin(), d1.end(), back_inserter(v1));  // executes correctly

Now, *(v1.begin()) = *(d1.begin()) (and all subsequent assignments) map to vector::push_back instead of vector::operator=. STL provides three insert adapters: back_inserter, front_inserter, and inserter.

7.6.1 back_inserter iterators

As noted above, back_inserter iterators call the push_back method of the container instead of operator= when the iterator’s operator* method is invoked as an l-value. This means that back_inserter iterators can only be used with containers that support the push_back method (vector, deque, list). The following illustrates a declaration of a back_inserter iterator to be associated with a vector:

// declare a vector of ints
vector<int, allocator<int> > iV;   
// declare a back_inserter iterator associated with iV
back_inserter iVPtr(iV);      

7.6.2 front_inserter iterators

Because front_inserter iterators call the push_front method of the container instead of operator= when the iterator’s operator* method is invoked as an l-value, front_inserter iterators can only be used with containers that support the push_front method (deque, list). The following illustrates a declaration of a front_inserter iterator to be associated with a list:

// declare a list of ints
list<int, allocator<int> > iL;
// declare a front_inserter iterator associated with iL
front_inserter iLPtr(iL);      

7.6.3 Inserter iterators

Inserter iterators call the insert method of the container instead of operator= when the iterator’s operator* method is invoked as an l-value. This means that inserter iterators can be used with all the STL containers, even the sorted associative containers, as they all support an insert method. The following illustrates a declaration of an inserter iterator to be associated with a set that inserts its objects beginning at the second item in the set.

// declare a set of ints
set<int, less<int>, allocator<int> > iS;   
// declare an inserter iterator associated with iS
inserter(iS, iS.begin() + 1); 

8. Container Adapters

An adapter in STL is a wrapper class that takes an existing class and provides it with a new interface. There are three adapters provided by the STL for containers: stack, queue, and priority_queue.

8.1 Stack

A stack adapts any STL container that supports the push_back and pop_back member functions. It implements a container that performs as stack (Last In, First Out). A stack may be used to adapt the behavior of a vector, deque or list (as all three support push_back and pop_back). The deque is the most commonly used container with a stack.

Note   In most implementations of the STL, deque is the default value for the second template parameter of a stack (the second template parameter specifies the stored container type). In Visual C++ 4.2, the default argument is not defined due to compiler limitations.

The following declares a stack of ints, pushes nine values onto the stack, and then pops each one after printing it:

typedef allocator<int> IALLOC;
typedef deque<int, IALLOC> IDQ;
typedef stack<int, IDQ, IALLOC> ISTACK;
void somefunct(void)
{
   ISTACK MyStack;
   for(int i = 1; i < 10; i++)
      MyStack.push(i);
   while(MyStack.size()){
      cout << MyStack.top() << ", ";
      MyStack.pop();
   }
   cout << endl;
}

Output:

9, 8, 7, 6, 5, 4, 3, 2, 1,

• See APPENDIX B for the stack class definition
  
  
• See APPENDIX C for a table of stack methods
  
  
• See APPENDIX D for an explanation of the allocator class (typedef’d as IALLOC above)

8.2 Queue

A queue adapts any STL container that supports the push_back and pop_front member functions. It implements a container that performs as a queue (First In First Out). A queue may be used to adapt the behavior of a deque or list (as both support push_back and pop_front). The deque is the most commonly used container with a queue.

Note   In most implementations of the STL, deque is the default value for the second template parameter of a queue (the second template parameter specifies the stored container type). In Visual C++ version 4.2, the default argument is not defined due to compiler limitations.

The following declares a queue of ints, pushes nine values onto the queue, and then pops each one after printing it:

typedef allocator<int> IALLOC;
typedef deque<int, IALLOC> IDQ;
typedef queue<int, IDQ, IALLOC> IQUEUE;
void somefunct(void)
{
   IQUEUE MyQueue;
   for(int i = 1; i < 10; i++)
      MyQueue.push(i);
   while(MyQueue.size()){
      cout << MyQueue.front() << ", ";
      MyQueue.pop();
   }
   cout << endl;
}

Output:

1, 2, 3, 4, 5, 6, 7, 8, 9,

• See APPENDIX B for the queue class definition
  
  
• See APPENDIX C for a table of queue methods
  
  
• See APPENDIX D for an explanation of the allocator class (typedef as IALLOC above)

8.3 Priority_Queue

A priority_queue adapts any STL container that has a random access iterator to maintain a sorted collections of items. A priority_queue may be used to adapt the behavior of a vector or a deque (as both are associated with a random access iterator and support operator[]). The vector is the most commonly used container with a priority_queue.

Note   In most implementations of the STL, vector is the default value for the second template parameter of a priority_queue (the second template parameter specifies the stored container type). In Visual C++ 4.2, the default argument is not defined due to compiler limitations.

The third template parameter allows you to specify the comparator used to sort the items. The following declares a priority_queue of ints, fills it with 10 random values and prints them in sorted order:

typedef allocator<int> IALLOC;
typedef vector<int, IALLOC> IV;
typedef priority_queue<int, IV, less<int>, IALLOC> PQUEUE;
void somefunct(void)
{
   PQUEUE MyQueue;
   for(int i = 1; i < 10; i++)
      MyQueue.push(rand() % 10);
   while(MyQueue.size()){
      cout << MyQueue.top() << ", ";
      MyQueue.pop();
   }
   cout << endl;
}

Output:

9, 8, 8, 7, 4, 4, 2, 1, 0,

• See APPENDIX B for the priority_queue class definition
  
  
• See APPENDIX C for a table of priority_queue methods
  
  
• See APPENDIX D for an explanation of the allocator class (typedef to IALLOC above)

9. The C++ String Class

9.1 Introduction

How often have C++ programmers wished they could add two strings using an obvious syntax like s1 + s2? Or add characters to a string using a syntax like s1 + “Hi”? Even Microsoft Basic allows that syntax.

The Standard C++ Library provides C++ programmers with a powerful string class. The string class is based on the basic_string class template.

Standard C++ declares two type definitions, string and wstring, based on basic_string:

typedef basic_string<char, char_traits<char>, allocator<char> > string;
typedef basic_string<wchar_t, char_traits<wchar_t>, allocator<wchar_t> > wstring;

The basic_string has been defined in the header <xstring>.

The C++ string class is very easy to use. Table 11 describes all the member functions in brief and the sample in the following section demonstrates the C++ string class.

Table 11. String Class Member Functions

9.2 Example

The following sample converts a word to Pig Latin. To convert a word to Pig Latin, take the first character of a word, stick it at the end of the word and add the characters "ay" to the end of the word. For example, Pig Latin(“hello”) = ellohay.

//piglatin.cpp
#include <string>
#include <iostream>
//convert a string to piglatin
string piglatin(const string& s)
{
    string s1 ;
    string s2(" .,;:?") ;  //word separators
    //word boundary markers
    size_t start, end, next, p0 ;
    int done = 0 ;
    start = end = next = 0 ;
    while (!done)
    {
        // Find start of word.
        start = s.find_first_not_of(s2, next) ;
        // Find end of word.
        // Check for end of string.
        p0 = s.find_first_of(s2, start) ;
        end = (p0 >= s.length()) ? s.length() : p0 - 1 ;
        // Copy all the word separators.
        s1 = s1 + s.substr(next, start - next) ;
        // Convert word to piglatin.
        s1 = s1 + s.substr(start + 1, end - start) + s[start] + "ay" ;
        
        next = end + 1;
        // Check for end of string.
        if( next >= s.length())
            done = 1 ;
            
    }
    return s1 ;
}
void main()
{
    string s("she sells sea shells by the sea shore") ;
    cout << "s = " << s << endl ;
    cout << "\npiglatin(s) = " << piglatin(s) << "\n"<< endl;   
}

Output:

s = she sells sea shells by the sea shore
piglatin(s) = hesay ellssay easay hellssay ybay hetay easay horesay

10. Function Objects

10.1 Function Objects and the Strange Syntax...

Function objects are a fairly new concept of the C++ programming language. Their usage may seem odd at first glance, and the syntax may appear to be confusing. It may be a good idea to read this chapter slowly and deliberately, several times. Readers are encouraged to pull out the code snippets, build them, and try stepping through the debugger.

10.2 Introduction

A function object is an object of a class/struct type that includes an operator() member function. An operator() member function allows us to create an object that behaves like a function. For example, a Matrix class could overload operator() to access an element whose row and column index are specified as arguments to operator().

class Matrix
{
       public:
               Matrix(int, int) ;
               //…
               int operator(int, int) const ;
      private:
              Array<int> m_matrix ;
              int m_row ;
              int m_col ;
} ;
int Matrix::operator(int r, int c) const
{
       if ( r > 0 && r <= m_row && c > 0 && c <= m_col)
           return m_matrix[r, c] ;
       else
           return 0 ;
}
Matrix m(10, 10) ;
//….
int  element = m(5, 5) ;

Function objects also have the advantage of the fact that () is the only operator that can take an arbitrary number of arguments. Ever felt the need to create a new function from existing function(s)? C++ does not allow that. How about using function objects? It is important to note:

• Function objects are objects that behave like functions.
  
  
• Since they are objects they can be created.
  
  
• Function objects always return a value.

10.3 STL Function Objects

The Standard Template Library provides function objects for standard math operations such as addition, subtraction, multiplication, and division. STL also provides function objects for unary operations, logical operations, bitwise operations, and comparison operations. Table 12 lists all the function objects provided by STL. The function objects have been defined in the header file <functional>.

Table 12. STL Function Objects

These function objects can be used with STL algorithms to change the default behavior of the STL algorithms. Consider the STL algorithm sort. By default, sort sorts the elements of a sequence in ascending order. To sort the elements in a descending order use the STL function object greater<T> as demonstrated in the following example:

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
void main()
{
        typedef vector<int, allocator<int> > VECTOR_INT ;
        typedef ostream_iterator<int, char, char_traits<char> > OUTIT ;
        int a[10] = {30, 56, 79, 80, 45, 10, 4, 125, 67, 80} ;
        VECTOR_INT v1(a, a + 10) ;
        OUTIT out(cout, ", ") ;
        cout << "v1 before sort(first, last)" << endl ;
        copy(v1.begin(), v1.end(), out) ;
        cout << endl ;
        // using default sort algorithm, sorts elements in ascending order
        sort(v1.begin(), v1.end()) ;
        cout << "v1 after sort(first, last)" << endl ;
        copy(v1.begin(), v1.end(), out) ;
        cout << endl ;
        random_shuffle(v1.begin(), v1.end()) ;
        cout << "v1 before sort(first, last, using STL function object)"
             << endl ;
        copy(v1.begin(), v1.end(), out) ;
        cout << endl ;
        //customizing sort algorithm, to sort elements in descending order
        //using a function object.
        sort(v1.begin(), v1.end(), greater<int>()) ;
        cout << "v1 after sort(first, last, using STL function-object)" 
             << endl ;
        copy(v1.begin(), v1.end(), out) ;
        cout << endl ;
}

Build the above sample and see the output. We recommend stepping through the code in the debugger to see what is happening under the covers.

STL function objects can also be used in  C++ programs directly. For example:

int n1 = (times<int>())(10, 20) ;   // sets n1 to value 200
int n2 = (minus<int>())(300, 100) ; // sets n2 to value 200

10.4 STL Function Adapters

Function adapters help us construct a wider variety of function objects using existing function objects. Using function adapters is often easier than directly constructing a new function object type with a struct or class definition.

STL provides three categories of function adapters: negators, binders, and adapters for pointer to functions.

10.4.1 Binders

Binders are function adapters that convert binary function objects into unary function objects by binding an argument to some particular value.

STL provides two types of binder function objects: binder1st<Operation> and binder2nd<Operation>. A binder function object takes only a single argument.

STL provides two template functions, bind1st and bind2nd, to create binder function objects. The functions bind1st and bind2nd each take as arguments a binary function object f and a value x. As might be surmised, bind1st returns a function object of type binder1st<Operation>, and bind2nd returns a function object of type binder2nd<Operation>. Here are the function prototypes for the bind1st and bind2nd functions:

template <class Operation, class T>
binder1st<Operation> bind1st(const Operation& f, const T& x) ;
template <class Operation, class T>
binder2nd<Operation> bind2nd(const Operation& f, const T& x) ;

Let us try to understand what binders do by looking at the following:

int result = (bind2nd(greater<int>(), 200))(i)

Assume i is an integer. You can rewrite the above expression as follows:

int result = (greater<int>())(i, 200)

The expression "bind2nd(greater<int>(), 200)" really is a more convenient way to implement the following:

// f is a binary function object that takes two integers, x and y.
// returns true if x > y
greater<int> f ;
// b is a unary function object; it returns true if its argument is > 200.
binder2nd< greater<int> > b = bind2nd(f, 200) ;
// Store the results of the comparison i > 200.
int result = b(i) ; // equivalent to the expression f(i, 200) ;

So now it is easier to understand: f is a binary function object that compares two integers, x and y; b is a unary function object that sets the second argument of f to the value 200; and result is therefore (i > 200).

Then why use an expression as complex as "bind2nd(greater<int>(), 200)"? Consider the following example:

int a1[1000] ;
//code to initialize a1 …
int* where = find_if(a1, a1+1000, bind2nd(greater<int>(), 200));

The find_if function finds the first element in array a1, which is > 200. In this case it is not possible to use the expression "(greater<int>())(i, 200)" as the third argument to find_if. How does one determine the value of i? The find_if function will supply the value i to the function object greater and the unary function object created by bind2nd. Also, bind2nd binds the value 200 to the second argument of function object greater.

This notation makes it possible to work with the entire container at once, instead of writing loops to deal with individual elements. It makes the source code smaller, more reliable, and easier to read.

bind1st converts the binary function object f into a unary function object by binding the argument x to the first argument of function object f.

bind2nd converts the binary function object f into a unary function object by binding the argument x to the second argument of function object f.

10.4.2 Negators

A negator returns the complement of a result obtained by applying a provided unary or binary operation.

STL provides two types of negator function objects: unary_negate<Operation> and binary_negate<Operation>. A negator function object takes only a single argument.

The two template functions, not1 and not2, create negator function objects. The function not1 takes a unary function object f as its argument and returns a function object of type unary_negate<Operation>. The function not2 takes a binary function object f as its argument and returns a function object of type binary_negate<Operation>. Here are the function prototypes for the not1 and not2 functions:

template <class Operation>
unary_negate<Operation> not1(const Operation& f) ;
template <class Operation>
binary_negate<Operation> not2(const Operation& f) ;

Let us try to understand what negators do by looking at the following example:

int a1[1000] ;
//code to initialize a1 …
int* where = find_if(a1, a1+1000, not1(bind2nd(greater<int>(), 200)));

In this case, find_if finds the first element in array a1 that is not > 200 (that is, <= 200). The function bind2nd creates a unary function object which returns the result of the comparison i > 200. The function not1 takes the unary function object as an argument and creates another function object. This function object merely negates the results of the comparison i > 200. Here is an example of using the not2 function:

sort(v1.begin(), v1.end(), not2(greater<int>())) ;

In this case, sort will sort elements in ascending order. The not2 function negates the results of the function object greater.

10.4.3 Pointer-to-function adapters

Adapters for pointers to functions convert existing binary or unary functions to function objects. Adapters for pointers to functions allow the programmer to utilize the existing code to extend the library, apply idioms unique to your application, and so forth.

STL provides two types of pointer-to-function objects: pointer_to_unary_function<Arg, Result> and pointer_to_binary_function<Arg1, Arg2, Result>. The pointer_to_unary_function function object takes one argument of type Arg, and pointer_to_binary_function takes two arguments of type Arg1 and Arg2.

STL provides two versions of the template function ptr_fun to create pointer-to-function function objects. The first version of ptr_fun takes a unary function f as its argument and returns a function object of type pointer_to_unary_function<Arg, Result>. The second version of ptr_fun takes a binary function f as its argument and returns a function object of type pointer_to_binary_function<Arg1, Arg2, Result>. Here are the function prototypes for the ptr_fun functions:

template<class Arg, class Result> inline
pointer_to_unary_function<Arg, Result> ptr_fun(Result (*F)(Arg))
      
template<class Arg1, class Arg2, class Result> inline
pointer_to_binary_function<Arg1, Arg2, Result> 
ptr_fun(Result(*F)(Arg1, Arg2)) ;

Let us look at an example and try to understand what pointers to functions do:

#pragma warning(disable: 4786)
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
// Return an integral random number in the range [0, n).
int Rand(int n)
{
    return rand() % n ;
}
void main()
{
   const int VECTOR_SIZE = 8 ;
   // A template class vector of int
   typedef vector<int, allocator<int> > IntVector ;
   //Define an iterator for template class vector of strings
   typedef IntVector::iterator IntVectorIt ;
   IntVector Numbers(VECTOR_SIZE) ;
   IntVectorIt start, end, it ;
   // Initialize vector Numbers
   Numbers[0] = 4 ;
   Numbers[1] = 10;
   Numbers[2] = 70 ;
   Numbers[3] = 30 ;
   Numbers[4] = 10;
   Numbers[5] = 69 ;
   Numbers[6] = 96 ;
   Numbers[7] = 100;
   start = Numbers.begin() ;   // location of first
                               // element of Numbers
   end = Numbers.end() ;       // one past the location
                               // last element of Numbers
    cout << "Before calling random_shuffle\n" << endl ;
   // Print content of Numbers.
   cout << "Numbers { " ;
   for(it = start; it != end; it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;
   
   // Shuffle the elements in a random order
    // the ptr_fun adaptor converts
    // a function to a function object.
    random_shuffle(start, end, ptr_fun<int, int>(Rand)) ;
    cout << "After calling random_shuffle\n" << endl ;
    cout << "Numbers { " ;
   for(it = start; it != end; it++)
      cout << *it << " " ;
   cout << " }\n" << endl ;   
}

In this example, function ptr_fun converts the C++ unary function Rand into a pointer_to_binary_function function object. Build the above sample and examine the output. We recommend stepping through the code in the debugger to see what is happening under the covers!!

11. Standard Template Library Algorithms

11.1 Introduction

This chapter will introduce the STL algorithm fundamentals and present some examples. Remembering some basic rules will help you to understand the algorithms and how to use them.

• STL provides generic parameterized, iterator-based functions (a fancy description for template functions). These functions implement some common array-based utilities, including searching, sorting, comparing, and editing.
  
  
• The STL algorithms are user programmable. What this means is that you can modify the default behavior of an algorithm to suit your needs. For example, the sort algorithm:

  sort(first, last) ; //sorts elements of a sequence 
                      //in ascending order by default. 
  

  In this case the STL algorithm assumes an operator == or operator < exists, and uses it to compare elements.

  The default behavior of the STL algorithms can be changed by specifying a predicate. The predicate function could be:

  • A C++ function. For example, sort_descending is a C++ function that compares two elements. In this case the sort algorithm takes a function pointer, as follows:

    // User programmable version of sort       
    sort(first, last, sort_descending); 
    

  • Or, the predicate function could be a function object. Either define a function object, or use the function objects provided by STL. For example:

    //using function object greater<int>()
    //provided by STL
    sort(first, last, greater<int>()) ; 
    

• Every algorithm operates on a range of sequence. A sequence is a range of elements in an array or container, or user-defined data structures delimited by a pair of iterators.
  • The identifier first points to the first element in the sequence.
    
    
  • The identifier last points one element beyond the end of the region you want the algorithm to process.
    
    
  • A common notation used to represent the sequence is [first, last). This is a notation for an open interval. The notation [first, last) implies that the sequence ranges from first to last, including first but not including last.
    
    
  • The algorithm will increment an internal iterator with the ++ operator until it equals last. The element pointed to by last will not be processed by the algorithm.
• STL Algorithms do not perform range or validity checking on the iterator or pointer values. Many algorithms work with two sequences. For example, the copy algorithm takes three parameters, as follows:

  //Copy contents of sequence1 to sequence2.
  // First1 and last1 mark start and end of
  // Sequence1, respectively. First2 marks the start
  // of sequence2.
  copy(first1, last1, first2) ; 
  

  • ·If sequence2 is shorter than sequence1, copy will merrily continue writing into unconnected areas of memory.
• Some STL algorithms also creates an in-place version and a copying version. For example:

  // In-place version places the results back in
  //the same container.
  reverse(first, last) ;
  // Copying version places the results in
  //in another sequence and does not modify the 
  //original sequence.
  reverse_copy(first1, last1, first1) ; 
  

• The STL generic algorithms can be divided into the following four main categories:
  1. Nonmutating-Sequence Algorithms operate on containers without, in general, modifying the contents of the container.
     
     
  2. Mutating-Sequence Algorithms typically modify the containers on which they operate.
     
     
  3. The Sorting-Related Algorithms include sorting and merging algorithms, binary searching algorithms, and set operations on sorted sequences.
     
     
  4. Finally there is a small collection of Generalized Numeric Algorithms.
• The STL algorithms are defined in the three header files: <algorithm>, <functional>, <numeric>.

Let us look at some examples now. These examples demonstrate how to use the algorithms and explain different concepts.

11.2 reverse and reverse_copy

Description: Reverse the order of items in a sequence specified by the range [first, last).

Signature:

template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last) ;

Description: Create a reversed copy of a sequence. Copy a sequence specified by [first, last) into a sequence of the same size, starting at result. Return an iterator positioned immediately after the last new element.

Signature:

template <class BidirectionalIterator, class OutputIterator>
OutputIterator reverse_copy(BidirectionalIterator first, 
                            BidirectionalIterator last, 
                            OutputIterator result) ;

11.2.1 Using reverse and reverse_copy

The following example demonstrates how to use the reverse and reverse_copy functions.

//reverse.cpp

#pragma warning(disable:4786)

#include <iostream>
#include <algorithm>
#include <list>
#include <string>

void main()
{
        typedef list<string, allocator<string> > STRINGLIST ;
        typedef STRINGLIST::iterator STRINGLIST_ITERATOR ;
        typedef ostream_iterator<string, char, 
                                 char_traits<char> > OS_ITERATOR ;

        string Names1[6] = {"Bob", "Tim", "David", "Lisa", "Donna",        
                            "Cathy" } ;
        string Names2[6] ;
        OS_ITERATOR out(cout, ", ") ;

        STRINGLIST namesList1, namesList2(6) ;

        int i ;
        STRINGLIST_ITERATOR iT, iT2 ;

        // print contents of Names1
        cout << "Names1 array: " << endl ;
        for(i = 0; i < 6; i++)
                cout << Names1[i] << ", " ;
        cout << "\n" << endl ;

        // Reverse contents of Names1
        //using in-place version of reverse.
        reverse(&Names1[0], &Names1[6]) ;

        // Print contents of Names1.
        cout << "Names1 array after reverse: " << endl ;
        for(i = 0; i < 6; i++)
                cout << Names1[i] << ", " ;
        cout << "\n" << endl ;

        //Reverse contents of Names1 and place results in Names2
        //using copying version of reverse.
        reverse_copy(&Names1[0], &Names1[6], &Names2[0]) ;

        //Print contents of Names2.
        cout << "Names2 array after reverse_copy: " << endl ;
        for(i = 0; i < 6; i++)
                cout << Names1[i] << ", " ;
        cout << "\n" << endl ;

        //Initialize nameList1 with contents of array Names.
        for (i = 0; i < 6; i++)
                namesList1.push_back(Names1[i]) ;

        // Print contents of nameList1.
        cout << "namesList1 list: " << endl ;
        for(iT = namesList1.begin(); iT != namesList1.end(); iT++)
                cout << *iT << ", " ;
        cout << "\n" << endl ;

        //Reverse contents of namesList1
        // using in-place version of reverse.
        reverse(namesList1.begin(), namesList1.end()) ;

        // Print contents of nameList1.
        cout << "namesList1 list after reverse: " << endl ;
        for(iT = namesList1.begin(); iT != namesList1.end(); iT++)
                cout << *iT << ", " ;
        cout << "\n" << endl ;

        //Reverse contents of namesList1 and place results in
        //namesList2 using copying version of reverse.
        reverse_copy(namesList1.begin(), 
                     namesList1.end(), 
                     namesList2.begin()) ;

        // Print contents of nameList1
        cout << "namesList2 list after reverse_copy: " << endl ;
        for(iT2 = namesList2.begin(); iT2 != namesList2.end(); iT2++)
        {
                cout << *iT2 << ", " ;
        }
        cout << "\n" << endl  << flush;
   }

11.3 sort

Description: Sort a sequence. Sort all elements in the range [first, last) into ascending order. The first version uses operator< to compare elements while the second version uses a function/function object.

Signature:

template <class RandomAccessIterator>
void sort(RandomAccessIterator first_, RandomAccessIterator last_) ;

template <class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first_, 
          RandomAccessIterator last_,
          Compare compare_) ;

11.3.1 Using sort

The following example demonstrates how to use the nonpredicate and predicate version of the sort function.

//sort.cpp
//Using the generic sort algorithm

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

bool comp(int x, int y)
{
        return x > y ;
}

class compObj
{
public:
        bool operator()(int x, int y)
        {
                return x > y ;
        }
} ;
void main()
{
        typedef vector<int, allocator<int> > VECTOR_INT ;
        typedef ostream_iterator<int, char, char_traits<char> > OUTIT ;

        int a[10] = {30, 56, 79, 80, 45, 10, 4, 125, 67, 80} ;
        VECTOR_INT v1(a, a + 10) ;
        OUTIT out(cout, ". ") ;

        cout << "v1 before sort(first, last)" << endl ;
        copy(v1.begin(), v1.end(), out) ;
        cout << endl ;

        // Default sort algorithm: sorts elements in ascending order.
        sort(v1.begin(), v1.end()) ;

        cout << "v1 after sort(first, last)" << endl ;
        copy(v1.begin(), v1.end(), out) ;
        cout << endl ;

        random_shuffle(v1.begin(), v1.end()) ;

        cout << "v1 before sort(first, last, comp_function)" << endl ;
        copy(v1.begin(), v1.end(), out) ;
        cout << endl ;

        //Customizing sort algorithm: to sort elements
        //in descending order using a compare function.
        sort(v1.begin(), v1.end(), comp) ;

        cout << "v1 after sort(first, last, comp_function)" << endl ;
        copy(v1.begin(), v1.end(), out) ;
        cout << endl ;

        random_shuffle(v1.begin(), v1.end()) ;

        cout << "v1 before sort(first, last, your function-object)"
             << endl ;
        copy(v1.begin(), v1.end(), out) ;
        cout << endl ;

        //Customizing sort algorithm: to sort elements 
        //in descending order using a function.
        sort(v1.begin(), v1.end(), compObj()) ;

        cout << "v1 after sort(first, last, your function-object)"
             << endl ;
        copy(v1.begin(), v1.end(), out) ;
        cout << endl ;

        random_shuffle(v1.begin(), v1.end()) ;

        cout << "v1 before sort(first,last,using STL function-object)" 
<< endl ;
 copy(v1.begin(), v1.end(), out) ;
 cout << endl ;

 //Customizing sort algorithm: to sort elements
 //in descending order using a function object.
 sort(v1.begin(), v1.end(), greater<int>()) ;

 cout << "v1 after sort(first, last, using STL function-object)"
      << endl ;
 copy(v1.begin(), v1.end(), out) ;
 cout << endl ;
}

12. Standard C++ Library Language Support

12.1 Introduction

The language support section of the Standard C++ Library provides common type definitions used throughout the library, characteristics of pre-defined types, functions supporting start and termination of C++ programs, support for dynamic memory allocation, support for dynamic type identification, support for exception processing, and other run-time support.

12.2 Types: cstddef

This header file basically includes stddef.h. There are two macros, NULL and offsetof, and two types, ptrdiff_t and size_t, specifically listed in this section of the standard.

To determine the distance (or the number of elements) between two elements you can use the distance() function. If you pass it an iterator pointing to the first element and one pointing to the third element, it will return a 2.

The distance function is in the utility header file and it takes two iterators as parameters and returns a number of type difference_type. Difference_type maps is an int. The sequence is:

typedef _PDFT difference_type 
#define _PDFT ptrdiff_t 
typedef int ptrdiff_t 

Note   With Visual C++ 4.2 the online help states the difference function takes 3 parameters and returns void. For example:

template <class Init, class Dist> 
void distance(InIt first, InIt last, Dist&n); 

However, it actually takes two parameters and returns a value, as follows:

   template <class Init, class Dist>
Dist distance(InIt first, InIt last) 

12.3 Using the distance() Function

The following example demonstrates the distance() function:

#include <iostream>
#include <vector>
#include <iterator>
#include <string>
#pragma warning (disable:4786)
typedef vector<string, allocator<string> > VTRLIST;
void main() {
    VTRLIST Vector;
    VTRLIST::iterator iVector;
    VTRLIST::difference_type dTheDiff;
    Vector.push_back("A1");
    Vector.push_back("B2");
    Vector.push_back("C3");
    Vector.push_back("D4");
    Vector.push_back("E5");
    Vector.push_back("F6");
    Vector.push_back("G7");
    // Print out the list.
    iVector=Vector.begin();
    cout << "The list is: ";
    for (int i = 0; i < 7 ; i++, iVector++)
        cout << *iVector  << "  ";
   
    // Initialize the iterator the first element".
    iVector=Vector.begin();
    cout << "\n\nAdvance to the 3rd element." << endl;
    advance( iVector, 2);
    cout << "The element is " << *iVector << endl;
    dTheDiff = distance( Vector.begin(), iVector);
           cout << "The distance from the beginning is " << dTheDiff << endl;
    cout << "Calculate it in reverse order " << endl;
    dTheDiff = distance( iVector, Vector.begin());
    cout << "The distance is " << dTheDiff << endl;
    cout << "\nUse distance() to count from the 3rd element to the 
             end."  << endl;
    dTheDiff = distance( iVector, Vector.end());
    // Note that end() returns one past the end of the sequence.
    cout << "The distance is " << dTheDiff << endl;
    cout <<"\nUse distance() to count the total length." << endl;
    dTheDiff = distance( Vector.begin(), Vector.end() );
    cout << "The total distance is " << dTheDiff << endl;
}

The program output is:

The list is: A1  B2  C3  D4  E5  F6  G7
Advance to the 3rd element.
The element is C3
The distance from the beginning is 2
Calculate it in reverse order
The distance is -2
Use distance() to count from the 3rd element to the end.
The distance is 5
Use distance() to count the total length.
The total distance is 7

12.4 Implementation Properties: limits, climits, cfloat

The numeric_limits component provides information about properties of fundamental types. Specializations are provided for each fundamental type such as int, floating point, and bool. The member is_specialized returns true for the specializations of numeric_limits for the fundamental types

The numeric_limits class is defined in the limits header file.

template<class T>  class numeric_limits {
public:
static const bool has_denorm;
static const bool has_denorm_loss;
static const bool has_infinity;
static const bool has_quiet_NaN;
static const bool has_signaling_NaN;
static const bool is_bounded;
static const bool is_exact;
static const bool is_iec559;
static const bool is_integer;
static const bool is_modulo;
static const bool is_signed;
static const bool is_specialized;
static const bool tinyness_before;
static const bool traps;
static const float_round_style round_style;
static const int digits;
static const int digits10;
static const int max_exponent;
static const int max_exponent10;
static const int min_exponent;
static const int min_exponent10;
static const int radix;
static T denorm_min() throw();
static T epsilon() throw();
static T infinity() throw();
static T max() throw();
static T min() throw();
static T quiet_NaN() throw();
static T round_error() throw();
static T signaling_NaN() throw();
};

12.5 numeric_limits Class Member Functions

Table 13 describes the member functions of the numeric_limit class.

Table 13. Member Functions of the numeric_limit Class

12.6 Using the numeric_limits Class Member Functions

The following example demonstrates the numeric_limits class member functions:

#include <iostream>
#include <limits>
void main() {
   cout << " 1 The minimum value for char is " << 
      (int)numeric_limits<char>::min() << endl;
   cout << " 2 The minimum value for int  is " << 
      numeric_limits<int>::min() << endl;
   cout << " 3 The maximum value for char is " << 
      (int)numeric_limits<char>::max() << endl;
   cout << " 4 The maximum value for int  is " << 
      numeric_limits<int>::max() << endl;
   cout << " 5 The number of bits to represent a char is " << 
      numeric_limits<char>::digits << endl;
   cout << " 6 The number of bits to represent an int is " << 
      numeric_limits<int>::digits << endl;
   cout <<" 7 The number of digits representble in base 10 for float is" 
       << numeric_limits<float>::digits10 << endl;
   cout << " 8 Is a char signed?              " <<
      numeric_limits<char>::is_signed << endl;
   cout << " 9 Is an unsigned integer signed? " <<
      numeric_limits<unsigned int>::is_signed << endl;
   cout << "10 Is a integer an integer? " <<
      numeric_limits<int>::is_integer << endl;
   cout << "11 Is a float an integer?   " <<
      numeric_limits<float>::is_integer << endl;
   cout << "12 Is a integer exact? " <<
      numeric_limits<int>::is_exact << endl;
   cout << "13 Is a float  exact?  " <<
      numeric_limits<float>::is_exact << endl;
   cout << "14 The radix for float is            "  << 
      numeric_limits<float>::radix << endl;
   cout << "15 The epsilon for float is          " <<
      numeric_limits<float>::epsilon() << endl;
   cout << "16 The round error for float is      " <<
      numeric_limits<float>::round_error() << endl;
   cout << "17 The minimum exponent for float is " <<
      numeric_limits<float>::min_exponent << endl;
   cout << "18 The minimum exponent in base 10   " <<
      numeric_limits<float>::min_exponent10 << endl;
   cout << "19 The maximum exponent is           " <<
      numeric_limits<float>::max_exponent << endl;
   cout << "20 The maximum exponent in base 10   " <<
      numeric_limits<float>::max_exponent10 << endl;
   cout << "21 Can float represent positive infinity?  " <<
      numeric_limits<float>::has_infinity << endl;
   cout << "22 Can double represent positive infinity? " <<
      numeric_limits<double>::has_infinity << endl;
   cout << "23 Can int represent positive infinity? " <<
      numeric_limits<int>::has_infinity << endl;
   cout << "24 Can float represent a NaN?           " <<
      numeric_limits<float>::has_quiet_NaN << endl;
   cout << "25 Can float represent a signaling NaN? " <<
      numeric_limits<float>::has_signaling_NaN << endl;
   cout << "26 Does float allow denormalized values?   " <<
      numeric_limits<float>::has_denorm << endl;
   cout << "27 Does float detect denormalization loss? " <<
      numeric_limits<float>::has_denorm_loss << endl;
   cout << "28 Representation of positive infinity for float " <<
      numeric_limits<float>::infinity() << endl;
   cout << "29 Representation of quiet NaN for float         " <<
      numeric_limits<float>::quiet_NaN() << endl;
   cout << "30 Minimum denormalized number for float         " <<
      numeric_limits<float>::denorm_min() << endl;
   cout << "31 Minimum positive denormalized value for float " <<
      numeric_limits<float>::denorm_min() << endl;
   cout << "32 Does float adhere to IEC 559 standard?  " <<
      numeric_limits<float>::is_iec559 << endl;
   cout << "33 Is float bounded? " <<
      numeric_limits<float>::is_bounded << endl;
   cout << "34 Is float modulo?  " <<
      numeric_limits<float>::is_modulo << endl;
   cout << "35 Is int modulo?    " <<
      numeric_limits<float>::is_modulo << endl;
   cout << "36 Is trapping implemented for float?    " <<
      numeric_limits<float>::traps << endl;
   cout << "37 Is tinyness detected before rounding? " <<
      numeric_limits<float>::tinyness_before << endl;
   cout << "38 What is the rounding style for float? " <<
      (int)numeric_limits<float>::round_style << endl;
   cout << "39 What is the rounding style for int? " <<
      (int)numeric_limits<int>::round_style << endl;
}

Output:

 1 The minimum value for char is -128
 2 The minimum value for int  is -2147483648
 3 The maximum value for char is 127
 4 The maximum value for int  is 2147483647
 5 The number of bits to represent a char is 7
 6 The number of bits to represent an int is 31
 7 The number of digits representable in base 10 for float is 6
 8 Is a char signed?              1
 9 Is an unsigned integer signed? 0
10 Is a integer an integer? 1
11 Is a float an integer?   0
12 Is a integer exact? 1
13 Is a float  exact?  0
14 The radix for float is            2
15 The epsilon for float is          1.19209e-007
16 The round error for float is      0.5
17 The minimum exponent for float is -125
18 The minimum exponent in base 10   -37
19 The maximum exponent is           128
20 The maximum exponent in base 10   38
21 Can float represent positive infinity?  1
22 Can double represent positive infinity? 1
23 Can int represent positive infinity? 0
24 Can float represent a NaN?           1
25 Can float represent a signaling NaN? 1
26 Does float allow denormalized values?   1
27 Does float detect denormalization loss? 1
28 Representation of positive infinity for float 1.#INF
29 Representation of quiet NaN for float         -1.#IND
30 Minimum denormalized number for float         1.4013e-045
31 Minimum positive denormalized value for float 1.4013e-045
32 Does float adhere to IEC 559 standard?  1
33 Is float bounded? 1
34 Is float modulo?  0
35 Is int modulo?    0
36 Is trapping implemented for float?    1
37 Is tinyness detected before rounding? 1
38 What is the rounding style for float? 1
39 What is the rounding style for int? 0

Additional values defined from the <climits> and <cfloat> header files which include <limits.h> and float.h, respectively, are:

CHAR_BIT         INT_MAX       LONG_MIN        SCHAR_MIN      UCHAR_MAX      
  CHAR_MAX      INT_MIN       MB_LEN_MAX      SHRT_MAX       UINT_MAX              
  CHAR_MIN      LONG_MAX      SCHAR_MAX       SHRT_MIN      ULONG_MAX     
    USHRT_MAX 
  DBL_DIG             DBL_MIN_EXP        FLT_MIN_10_EXP     LDBL_MAX_10_EXP 
  DBL_EPSILON      FLT_DIG             FLT_MIN_EXP         LDBL_MAX_EXP    
  DBL_MANT_DIG    FLT_EPSILON         FLT_RADIX           LDBL_MIN        
  DBL_MAX             FLT_MANT_DIG        FLT_ROUNDS          LDBL_MIN_10_EXP  
  DBL_MAX_10_EXP      FLT_MAX             LDBL_DIG            LDBL_MIN_EXP    
  DBL_MAX_EXP    FLT_MAX_10_EXP    LDBL_EPSILON                     
  DBL_MIN             FLT_MAX_EXP         LDBL_MANT_DIG                    
  DBL_MIN_10_EXP       FLT_MIN             LDBL_MAX                         

Note   The LDBLxxx constants are not listed in the online help for Visual C++ 4.2 but they are defined in <float.h>

There are two additional constants defined in the Visual C++ 4.2 implementation that are not a part of the Standard C++ Library, they are:

_DBL_RADIX       
_DBL_ROUNDS       

See the online help with Visual C++ 4.2 for descriptions of these constants.

12.7 Start and Termination: cstdlib

The cstdlib header file includes the C header file <cstdlib.h>. Table 14 lists the functions specified.

Table 14. Functions Specified in cstdlib

12.8 Dynamic Memory Management: new

The online help for the new header file lists the following.

    typedef void (*new_handler)();
    class bad_alloc;
    class nothrow;
    new_handler set_new_handler(new_handler ph) throw();
    void operator delete(void *p) throw();
    void operator delete(void *, void *) throw();
    void operator delete(void *p, const nothrow&) throw();
    void operator delete[](void *p) throw();
    void operator delete[](void *, void *) throw();
    void operator delete[](void *p, const nothrow&) throw();
    void *operator new(size_t n) throw(bad_alloc);
    void *operator new(size_t n, const nothrow&) throw();
    void *operator new(size_t n, void *p) throw();
    void *operator new[](size_t n) throw(bad_alloc);
    void *operator new[](size_t n, const nothrow&) throw();
    void *operator new[](size_t n, void *p) throw();
    };

The main thing to note is that there is support for the operator new either returning NULL or throwing an exception on failure.

The class nothrow{} is used as a function parameter to indicate that the function should never throw an exception.

The online help for the operator new in the Visual C++ 4.2 Standard C++ Library Reference is pretty good. Either query on 'operator new' or look in the help for the <new> header file.

In the above prototypes, don't let the throw(), throw you. Visual C++ 4.2 does not implement these exception specifications. This is noted in the online help.

Microsoft C++ does not support the function throw signature mechanism, as described in section 15.5 of the ANSI C++ draft.

Microsoft C++ does not support the function exception specification mechanism, as described in section 15.4 of the ANSI C++ draft.

An exception specification specifies the type of exceptions a function can throw, for example:

void Func() throw (ProblemOne, ProblemTwo) {}
is equivalent to:
void Func() {
{
   try {}
   catch (ProblemOne) {}
   catch (ProblemTwo) {}
   catch (…) { unexpected(); }
}

These operators:

   void *operator new(size_t n) throw(bad_alloc);
   void *operator new[](size_t n) throw(bad_alloc);

will throw a bad_alloc exception if the memory allocation fails. Or if you define a new_handler function via set_new_handler, the new handler function will be called instead.

These operators:

    void *operator new(size_t n, const nothrow&) throw();
    void *operator new(size_t n, void *p) throw();
    void *operator new[](size_t n, const nothrow&) throw();
    void *operator new[](size_t n, void *p) throw();

will simply return NULL if the memory allocation fails.

In the following sample, the first operator new will attempt to allocate memory and, if it fails, will throw an exception. The second operator new accepts a second parameter of type nothrow. This parameter indicates that if the allocation fails, it should return NULL and not throw an exception. The third operator, new, will allocate memory for an array of that type and, if it fails, throw an exception.

#include <new>
#include <iostream>
class BigClass {
public:
    BigClass() {};
    ~BigClass(){}
        double BigArray[99999999];
};
void main() {
    try {
    BigClass * p = new BigClass;
    }
    catch( bad_alloc a) {
        const char * temp = a.what();
        cout << temp << endl;
        cout << "Threw a bad_alloc exception" << endl;
    }
    BigClass * q = new(nothrow) BigClass;
    if ( q == NULL )
        cout << "Returned a NULL pointer" << endl;
    try {
    BigClass * r = new BigClass[3];
    }
    catch( bad_alloc a) {
        const char * temp = a.what();
        cout << temp << endl;
        cout << "Threw a bad_alloc exception" << endl;
    }
}
Program Output is:
bad allocation
Threw a bad_alloc exception
Returned a NULL pointer
bad allocation
Threw a bad_alloc exception
    

Note that the above example uses the what() function to print out the type of exception. This function is a part of the exception class. The value returned by what() is implementation defined.

An important thing to note is that code which previously returned a NULL when a call to new failed will instead throw an exception if you use the standard C++ header files. This means that if you modify your code to include <new> then you also need to modify your code to check for an exception rather than checking to see if new returned NULL.

12.8.1 Mixing old iostream and Standard C++ Libraries

Intermixing old header files with the new standard C++ header files can cause multiple problems with the new operator. For example, if the following code:

class BigClass {
public:
   BigClass() {};
   ~BigClass(){}
      double BigArray[99999999];
};
void main() {
   BigClass * q = new BigClass;
   if ( q == NULL )
      cout << "Returned a NULL pointer" << endl;
}

includes these header files, you get the noted results.

#include <iostream.h>
// No Errors.
#include <iostream.h>
#include <new>
// No errors - returns a NULL.
#include <new>
#include <iostream.h>
// No errors - returns a NULL.
#include <new>
#include <iostream>
// Throws an exception instead of returning NULL.
#include <iostream>
// Throws an exception instead of returning NULL.

If you are using the newer forms of the operator new such as:

class BigClass {
public:
   BigClass() {};
   ~BigClass(){}
      double BigArray[99999999];
};
void main() {
   try {
   BigClass * p = new BigClass;
   }
   catch( bad_alloc a) {
      const char * temp = a.what();
      cout << temp << endl;
      cout << "Threw a bad_alloc exception" << endl;
   }
   BigClass * q = new(nothrow) BigClass;
   if ( q == NULL )
      cout << "Returned a NULL pointer" << endl;
}

and include the following header files, you will get the noted results.

#include <new>
#include <iostream>
// No Errors.
#include <iostream>
#include <new>
// No Errors.
 #include <iostream>
// No Errors.
#include <new>
//C:\MSDEV\Projects\defcon\Text5.cpp(40) : error C2065: 'cout' : undeclared identifier
//C:\MSDEV\Projects\defcon\Text5.cpp(40) : error C2297: '<<' : bad right operand
//C:\MSDEV\Projects\defcon\Text5.cpp(40) : error C2065: 'endl' : undeclared identifier
//C:\MSDEV\Projects\defcon\Text5.cpp(41) : error C2297: '<<' : bad right operand
//C:\MSDEV\Projects\defcon\Text5.cpp(45) : error C2297: '<<' : bad right operand
#include <new>
#include <iostream.h>
// ext5.obj : error LNK2001: unresolved external symbol "void * __cdecl operator new(unsigned int,struct nothrow_t const &)"(??2@YAPAXIABUnothrow_t@@@Z)
// Debug/defcon.exe : fatal error LNK1120: 1 unresolved externals
#include <iostream.h>
#include <new>
// Text5.obj : error LNK2001: unresolved external symbol "void * __cdecl operator new(unsigned int,struct nothrow_t const &)"(??2@YAPAXIABUnothrow_t@@@Z)
// Debug/defcon.exe : fatal error LNK1120: 1 unresolved external
#include <iostream.h>
//C:\MSDEV\Projects\defcon\Text5.cpp(47) : error C2061: syntax error : identifier 'bad_alloc'
//C:\MSDEV\Projects\defcon\Text5.cpp(47) : error C2310: catch handlers must specify one type
//C:\MSDEV\Projects\defcon\Text5.cpp(48) : error C2065: 'a' : undeclared identifier
//C:\MSDEV\Projects\defcon\Text5.cpp(48) : error C2228: left of '.what' must hav class/struct/union type
//C:\MSDEV\Projects\defcon\Text5.cpp(52) : error C2317: 'try' block starting on line '44' has no catch handlers
//C:\MSDEV\Projects\defcon\Text5.cpp(52) : error C2065: 'nothrow' : undeclared identifier
//C:\MSDEV\Projects\defcon\Text5.cpp(52) : error C2660: 'new' : function does not take 2 parameters

12.9 Type Identification: typeinfo

The <typeinfo> header defines a type associated with the type information generated by the implementation (type_info). It also defines two types for reporting dynamic type identification errors (bad_cast and bad_typeid).

The type_info class is defined with a raw_name member in the help and header files (in both Visual C++ and the library). However, in the current version of the C++ Library Standard, there is no raw_name member. The raw_name member function returns a const char* to a null-terminated string representing the decorated name of the object type.

class type_info {
public:
   virtual ~type_info();
   int operator==(const type_info& rhs) const;
   int operator!=(const type_info& rhs) const;
   int before(const type_info& rhs) const;
   const char* name() const;
   const char* raw_name() const;
private:
   ...
};

12.10 Exception Handling: exception

The exception class defines the base class for the types of objects thrown as exceptions by the C++ Standard Library components. The exception header file defines the exception class that is the base class for all exceptions thrown by the C++ Standard Library. The following code would catch any exception thrown by classes and functions in the Standard C++ Library:

try {
   // code
}
catch ( const exception &ex)
{
   cout << "exception: " << ex.what();
}

The exception class is defined in the header file exception, as follows:

class exception {
public:
    exception() throw();
    exception(const exception& rhs) throw();
    exception& operator=(const exception& rhs) throw();
    virtual ~exception() throw();
    virtual const char *what() const throw();
private:
…
};

See Exception Handling and Standard C++ Library Diagnostics for further details.

12.11 Other Run-Time Support: cstdarg, csetjmp, ctime, csignal, cstdlib

With Visual C++ 4.2, each of these headers files includes the corresponding C header file, stdarg.h, setjmp.h, time.h, signal.h, and stdlib.h. Macros, types, and functions listed for each of these in the Standard C++ Library are as follows:

cstdarg  
Macros:    va_arg    va_end   va_start  
         Types:        va_list   
                  
 csetjmp  
Macro:         setjmp  
         Types:          jmp_buf                           
         Function:      longjmp 
 ctime   
Macros:         CLOCKS_PER_SEC 
       Types:          clock_t       
Functions:      clock  
        
 csignal   
       Macros:         SIGABRT        SIGILL   SIGSEGV   SIG_DFL 
        SIG_IGN         SIGFPE         SIGINT   SIGTERM   SIG_ERR
        Types:           sig_atomic_t                              
        Functions:      raise          signal     
                
cstdlib
        Functions:      getenv   system 

13. Exception Handling

13.1 Introduction

There was always a need to write robust and powerful programs that are resistant to run time errors, logic errors, and all other unexpected events. Exception handling is a relatively new and powerful tool that can be used for better and safer programming. As in many other areas, a good intention can lead to disastrous results. So, if you are not sure why and how to use exception handling, you are better off not using it at all.

13.2 C++ Exception Handling

C++ exception handling uses three statements (try, catch, and throw) added to the C++ language. With C++ exception handling, your program can propagate unexpected events to a higher execution context that is better able to recover from such abnormal events. These exceptions are handled by code outside the normal flow of control. The Microsoft C++ compiler implements the C++ exception-handling model based on the ISO WG21/ANSI X3J16 working papers toward the evolving standard for C++.

13.3 Structured Exception Handling

Structured exception handling is an extension to Microsoft C/C++ that can be used in either C or C++. Structured exception handling uses two constructs: try-except, known as exception handling, and try-finally, known as termination handling. The try-except statement enables applications to gain control of a program when events that normally terminate execution occur. The try-finally statement enables applications to guarantee execution of cleanup code when execution of a block of code is interrupted.

Note   Structured exception handling works with Microsoft Win32® for both C and C++ source files. However, it is not specifically designed for C++. Your code is more portable when using C++ exception handling and is also more flexible because it can handle exceptions of any type. For C++ programs, it is recommended that you use the new C++ exception-handling mechanism (try, catch, and throw statements).

13.4 Exception Handling Differences

The major difference between structured exception handling and C++ exception handling is that the C++ exception-handling model uses any data type, while the C structured exception-handling model uses type; unsigned int. That is, C exceptions are identified by an unsigned integer value, whereas C++ exceptions are identified by data type. When an exception is raised in C, each possible handler executes a filter, which examines the C exception context and determines whether to accept the exception, pass it to some other handler, or ignore it. When an exception is thrown in C++, it may be of any type.

A second difference is that the C structured exception handling model is referred to as asynchronous because exceptions occur secondary to the normal flow of control. The C++ exception handling mechanism is fully synchronous, which means that exceptions occur only when they are thrown.

If a C exception is raised in a C++ program, it can be handled by a structured exception handler with its associated filter or by a C++ catch handler, whichever is dynamically nearest to the exception context.

13.4.1 Using different exception handling mechanisms

The following example demonstrates how to use different exception handling mechanisms:

// Compile Options /GX
      /**************************************************************
      This simple program demonstrates how the asynchronous exceptions
      could be caught by C++ exceptions handling mechanism 
      
      ************************************************************/
            #include <stdio.h>
      int *p = NULL;      // pointer used to generate an AV
      class CMyObject {
      public:
      ~CMyObject () {
         printf ("Here is the destructor for CMyObject\n");
      }
      };
      void function1()
      {
         CMyObject ob;
         
         *p=3;   // causes an Access Violation exception
         }
      void function2()
      {
         try {
         function1();
         } catch (...) {
         printf("Caught an exception in function2()\n");
         }
      }
       int main (void) {
         function2 ();
         return 0;
      }
   Program Output:
   Here is the destructor for CMyObject
   Caught an exception in function1()
   Caught an exception in function2()

13.4.2 The synchronous-exception handling model

Synchronous exceptions are objects thrown in C++ with a throw() statement. The synchronous exception-handling model is designed for catching synchronous exceptions only. The asynchronous exception-handling model is designed to catch synchronous exceptions and structured exception-handling type exceptions such as access violation and divides by zero.

The compiler can assume exception can only happen at function calls. This makes it a lot easier to optimize the code and allows the removal of exception handling tracking code for local unwindable objects whose scope doesn't span across a function call (or where all calls are inlined).

13.4.3 The asynchronous exception handling model

The synchronous exception-handling model is just an optimized version of the asynchronous exception-handling model. So the two models can be intermixed. The asynchronous exceptions can still be caught by the synchronous model with minor gotchas. The state tracking may not be quite up-to-date in the function where the exception occurs. This means that some of the local unwindable objects in the function that cause access violation may not get destructed, or an access violation in a function that has a try/catch may not get caught by this function.

13.4.4 _declspec(nothrow)

You can also tune your code by telling the compiler that a particular function never throws an exception by using _declspec(nothrow) on the function declaration, or by using the new C++ nothrow specification.

13.5 Major Points from the C++ Working Paper

• Exception handling provides a way of transferring control and information from a point in the execution of a program to an exception handler associated with a point previously passed by the execution.
  
  
• A goto, break, return, or continue statement can be used to transfer control out of a try block or handler, but not into one. When this happens, each variable declared in the try block will be destroyed in the context that directly contains its declaration.
  
  
• A function try block associates a handler seq with the ctor initializer, if present, and the function body. An exception thrown during the execution of the initializer expressions in the ctor initializer or during the execution of the function body transfers control to a handler in a function try block in the same way as an exception thrown during the execution of a try block transfers control to other handlers.

            //Example:
            int f(int);
            class C {
                    int i;
                    double d;
            public:
                    C(int, double);
            };
            C::C(int ii, double id)
            try
                    i(f(ii)), d(id)
            {
                    // Constructor function body
            }
            catch (...)
            {
                // Handles exceptions thrown from the ctor-initializer
                // and from the constructor function body.
            }
  

13.6 Throwing an Exception

Throwing an exception transfers control to a handler. An object is passed and the type of that object determines which handlers can catch it.

      //Example:
          throw "Help!";
          can be caught by a handler of some char* type:
          try {
              // ...
          }
          catch(const char* p) {
              // Handle character string exceptions here.
          }
       and
          class Overflow {
              // ...
          public:
              Overflow(char,double,double);
          };
          void f(double x)
          {
              // ...
              throw Overflow('+',x,3.45e107);
          }

This can be caught by a handler for exceptions of type Overflow, as follows:

          try {
              // ...
              f(1.2);
              // ...
          }
          catch(Overflow& oo) {
              // handle exceptions of type Overflow here
          }

When an exception is thrown, control is transferred to the nearest handler with an appropriate type. The nearest handler is the handler whose try block the thread of control most recently entered but has not yet exited.

A throw expression initializes a temporary object of the static type of the operand of throw and uses that temporary object to initialize the appropriately typed variable named in the handler.

The memory for the temporary copy of the exception being thrown is allocated in an implementation-defined way. The temporary persists as long as there is a handler being executed for that exception.

A throw expression with no operand rethrows the exception being handled without copying it. For example, code that must be executed because of an exception, yet cannot completely handle the exception, can be written as follows:

      //Example:
          try {
              // ...
          }
          catch (...) {  // catch all exceptions
              // respond (partially) to exception
              throw;     // pass the exception to some
                         // other handler
          }

If no exception is presently being handled, executing a throw expression with no operand calls terminate().

13.7 Constructors and Destructors

As control passes from a throw point to a handler, destructors are invoked for all automatic objects constructed since the try block was entered. The automatic objects are destroyed in the reverse order of the completion of their construction.

An object that is partially constructed will have destructors executed only for its fully constructed subobjects. If a constructor for an element of an automatic array throw an exception, only the constructed elements of that array will be destroyed.

The process of calling destructors for automatic objects constructed on the path from a try block to a throw expression is called stack unwinding.

13.8 Handling an Exception

The exception declaration in a handler describes the type(s) of exceptions that can cause that handler to be entered. The exception declaration shall not denote an incomplete type. Types shall not be defined in an exception declaration.

The handlers for a try block are tried in order of appearance. That makes it possible to write handlers that can never be executed—for example, by placing a handler for a derived class after a handler for a corresponding base class.

A ... in a handler exception declaration functions similarly to ... in a function parameter declaration; it specifies a match for any exception. If present, a ... handler shall be the last handler for its try block.

If no match is found among the handlers for a try block, the search for a matching handler continues in a dynamically surrounding try block.

An exception is considered handled upon entry to a handler. (Note: the stack will have been unwound at that point.)

If no matching handler is found in a program, the function terminate() is called. Whether or not the stack is unwound before calling, terminate() is implementation defined.

Referring to any nonstatic member or base class of an object in the function try block handler of a constructor or destructor for that object results in undefined behavior.

The fully constructed base classes and members of an object shall be destroyed before entering the function try block handler of a constructor or destructor for that object.

The scope and lifetime of the parameters of a function or constructor extend into the handlers of a function try block.

If the handlers of a function try block contain a jump into the body of a constructor or destructor, the program is ill-formed.

If a return statement appears in a handler of function try block of a constructor, the program is ill-formed.

The exception being handled is rethrown if control reaches the end of a handler of the function try block of a constructor or destructor. Otherwise, a function returns when control reaches the end of a handler for the function try block.

When the catch handler specifies a class object, a copy constructor is used to initialize a temporary object that is bound to the optionally specified name in the exception declaration for the catch handler. The object shall not have an abstract class type, because objects of those types shall not be created. That object is destroyed when the handler is exited, after the destruction of any automatic objects initialized within the handler. The copy constructor and destructor shall be accessible in the context of the catch handler. If the copy constructor and destructor are implicitly declared, such a use in the catch handler causes these functions to be implicitly defined; otherwise, the program shall provide a definition for these functions. If the use of a temporary object can be eliminated without changing the meaning of the program (except for execution of constructors and destructors associated with the use of the temporary object), the optional name can be bound directly to the temporary (or original) object specified in a throw expression that causes the catch handler to be executed. The copy constructor and destructor associated with the object shall be accessible even when the temporary object is eliminated.

When the catch handler specifies a nonconstant object, any changes to the object that are effected before the handler has exited are changes to the temporary copy for the handler. These changes will not affect the temporary (or original) object that was initialized by execution of the throw expression. When the catch handler specifies a reference to a nonconstant object, any changes to the referenced object are changes to the temporary (or original) object initialized when the throw expression was executed. These changes will have effect if that object is rethrown.

13.9 Exception Specifications

By using an exception specification as a suffix of its declarator, a function declaration lists exceptions that its function may directly or indirectly throw.

          
exception-specification:
                  throw ( type-id-listopt )
          type-id-list:
                  type-id
                  type-id-list ,  type-id

An exception specification shall appear only on a function declarator in a function, pointer declaration, or pointer definition. An exception specification shall not appear in a typedef declaration.

         //Example:
          void f() throw(int);             // OK
          void (*fp)() throw (int);        // OK
          void g(void pfa() throw(int));   // OK
          typedef int (*pf)() throw(int);  // Ill-formed

Note   Exception specification is optional and the absence of one does not impose restrictions on the possible function exceptions.

If any declaration of a function has an exception specification, all declarations, including the definition, of that function shall have an exception specification with the same set of type IDs. If a virtual function has an exception specification, all declarations, including the definition, of any function that override that virtual function in any derived class shall only allow exceptions that are allowed by the exception specification of the base-class virtual function.

         //Example:
          struct B {
              virtual void f() throw (int, double);
              virtual void g();
          };
          struct D: B {
              void f();                    // ill-formed
              void g() throw (int);        // OK
          };

The declaration of D::f is ill-formed because it allows all exceptions, whereas B::f allows only int and double. Similarly, any function or pointer-to-function assigned to, or initializing, a pointer-to-function shall only allow exceptions that are allowed by the pointer or function being assigned or initialized.

//Example:
          void (*pf1)();    // no exception specification
          void (*pf2)() throw(A);
          void f()
          {
                  pf1 = pf2;  // ok: pf1 is less restrictive
                  pf2 = pf1;  // error: pf2 is more restrictive
          }

In such an assignment or initialization, exception specifications on return types and parameter types shall match exactly.

Calling a function through a declaration whose exception specification allows exceptions other than those allowed by the exception specification of the function definition is ill-formed. No diagnostic is required.

Types shall not be defined in exception specifications.

An exception specification can include the same class more than once and can include classes related by inheritance even though doing so is redundant. An exception specification can include identifiers that represent incomplete types. An exception specification can also include the name of the predefined class bad_exception.

If a class X is in the type-id-list of the exception specification of a function, that function is said to allow exception objects of class X or any class publicly and unambiguously derived from X. Similarly, if a pointer type Y* is in the type-id-list of the exception specification of a function, the function allows exceptions of type Y* or exceptions that are pointers to any type publicly and unambiguously derived from Y. Otherwise, a function only allows exceptions that have the same type as the types specified in the type-id-list of its exception specification.

Whenever an exception is thrown and the search for a handler encounters the outermost block of a function with an exception specification, the unexpected() function is called if the exception specification does not allow the exception.

         class X { };
          class Y { };
          class Z: public X { };
          class W { };
          void f() throw (X, Y)
          {
              int n = 0;
              if (n) throw X();        // OK
              if (n) throw Z();        // also OK
              throw W();               // will call unexpected()
          }

The unexpected() function may throw an exception that will satisfy the exception specification for which it was invoked (in this case, the search for another handler will continue at the call of the function with this exception specification) or it may call terminate.

An implementation shall not reject an expression simply because when it is executed it throws or might throw an exception that the containing function does not allow.

      extern void f() throw(X, Y);
          void g() throw(X)
          {
                  f();   // OK
          }

The call to f is well formed even though when called, f may throw exception Y that g does not allow.

A function with no exception specification allows all exceptions. A function with an empty exception specification, throw(), does not allow any exceptions.

An exception specification is not considered part of a function type.

Note   There is no compile-time checking of function exception specification. It would be too complicated and too costly. For example, in order to check the exception propagation, the compiler would need to check the code of the called function, any function it calls, and so on.

13.10 Special Functions

The exception handling mechanism relies on two functions, terminate() and unexpected(), for coping with errors related to the exception handling mechanism itself.

13.10.1 The terminate() function

Exception handling must be abandoned for less subtle error handling techniques:

• When a exception handling mechanism, after completing evaluation of the object to be thrown but before completing the initialization of the exception declaration in the matching handler; (1) calls an existing user function via an uncaught exception or (2) cannot find a handler for a thrown exception.
  
  
• When the destruction of an object during stack unwinding exits using an exception.
  
  
• When construction or destruction of a nonlocal object with static storage duration exits using an exception.
  
  
• When execution of a function registered with atexit exits using an exception.
  
  
• When a throw expression with no operand attempts to rethrow an exception and no exception is being handled.
  
  
• When unexpected throws an exception that is not allowed by the previously violated exception specification and bad_exception is not included in that exception specification.
  
  
• When the implementation's default unexpected_handler is called
  
  
• When the implementation's exception handling mechanism encounters some internal error.

In such cases, void terminate(); is called.

13.10.2 The unexpected() function

If a function with an exception specification throws an exception that is not listed in the exception specification, the unexpected() function is called.

The unexpected() function shall not return, but it can throw (or rethrow) an exception. If it throws a new exception that is allowed by the previously violated exception specification, the search for another handler will continue at the call of the function whose exception specification was violated. If it throws or rethrows an exception that the exception specification does not allow, one of two things can happen. If the exception specification does not include the name of the predefined exception bad_exception, the terminate() function is called; otherwise, the thrown exception is replaced by an implementation-defined object of the type bad_exception and the search for another handler will continue at the call of the function whose exception specification was violated.

An exception specification guarantees that only the listed exceptions will be thrown. If the exception specification includes the name bad_exception, any exception not on the list may be replaced by bad_exception within the function unexpected().

13.10.3 The uncaught_exception() function

The following predicate returns true after completing evaluation of the object to be thrown until the exception declaration in the matching handle completes initialization. (This includes stack unwinding.)

          bool uncaught_exception();

13.11 Exceptions and Access

If the exception declaration in a catch clause has class type and the function in which the catch clause occurs does not have access to the destructor of that class, the program is ill-formed.

An object can be thrown if it can be copied and destroyed in the context of the function in which the throw expression occurs.

14. Standard C++ Library Diagnostics

14.1 Introduction

The Diagnostics Library contains new components that C++ programs may use to detect and report error conditions.

The following header files contain components for reporting several kinds of exceptional conditions, documenting program assertions, and a global variable for error number codes:

14.2 Exception Class Hierarchies

Using a common base class allows the use of one handler for many related exceptions. For example, a set of exception objects for memory allocation problems could be derived from the MemoryException base class such as out memory or ZeroAlloc. A single catch (MemoryException) handler would catch all memory exceptions including new ones. Virtual functions allow derived exception classes to use internal information that doesn’t exist in the base class.

14.2.1 Using class hierarchy to define your own exception classes

The following example demonstrates how to use class hierarchies to define your own exception classes.

    // Compile Options. /GX
      /**************************************************************
      This program demonstrates how to use Class Hierarchies to define 
      your own exception classes. 
      It does not use a new new operator function from the Standard 
      Template Library. The intention is to demonstrate how to use
      class hierarchies to define your own exception classes.
      **************************************************************/
      #include <iostream>
      class MemoryException 
      {
         public:
            virtual void DisplayMessage() = 0;
      };
      class OutOfMemory : public MemoryException 
         {
         public:
            void DisplayMessage();
         };
      void OutOfMemory::DisplayMessage()
         {
         cout <<  " Out of Memory!" << endl;
         }

      class BadPointer : public MemoryException
      {
         private:
         void * p;
            virtual void DisplayMessage();
      };
      void BadPointer :: DisplayMessage ()
         {
         cout << "Invalid pointer: " << endl;
         }
      const size_t szBuf = 99999999;
      int* iBuf;
      char* cBuf;
      void InitApp();
      void main ()
      {
         try   {
            InitApp();
            }
         catch (MemoryException & ex)
         
            {
            ex.DisplayMessage();
            }
      }   
      void InitApp()
         {
            try {
            iBuf = new int [szBuf];
            cBuf = new char [szBuf];
            }
            catch (...) {
               throw OutOfMemory();
            }
         }

The program output is:

Out of Memory!

14.3 Templates and Exceptions

Exceptions defined within a template class can be specific to each generated class. Given the following:

template <class T> class Vector
{
   public:
   class ExceptionRange { }; //exception class 
};

A catch block would need to specify the type of vector that it is handling, as follows:

catch (Vector<int>:: ExceptionRange )
{
   //
}

14.3.1 Using exception classes with templates

The following example demonstrates how to use exception classes with templates.

       // Compile Options /GX
      /**************************************************************
      This program demonstrates how to use Exception classes with 
      templates. The template class vector is user defined. 
      Each vector type needs to have a handler defined or the exception
      will be handled by function terminate ().
      **************************************************************/
      #include <iostream>
      template <class T>
      class Vector {
         T* pT;
         int sz;
      public:
         
         Vector (int s=1);
         ~Vector();
         class ExceptionRange {};  //Exception class
         T& operator [] (int i);
         
         int size () const { return sz;}
      };
      template<class T>
      inline Vector<T>::Vector(int s)  { pT = new T[sz=s];}
      template<class T>
      inline Vector<T>::~Vector() { delete [] pT;}
      void range_error (Vector<int> & v)
      {
         v[v.size()+10]; // trigger range error
      }
       template<class T>
          T& Vector<T>::operator [] (int i)
         {
         if (0<=i && i <sz) return pT[i];
         throw ExceptionRange ();
         return pT[0];
         }
      void Do_Vector (Vector<int>& v)
      {
         range_error(v);
      }

      void main (void) 
      {
        Vector <int> v(10);
      try
         {
      Do_Vector (v);
         }
      // Catch (Vector<class int>::ExceptionRange)
      catch (Vector <int>::ExceptionRange)
      {
         // Handler for vector range exception
         cout << "Exception: Vector out of range" << endl;
      }
      }   
      Program Output:
      Exception: Vector out of range

You would need to define handlers for each excepted type of vector; otherwise, the types not listed will be handled by terminate () function. The exception could be defined outside of the Vector class as a global to all vector types.

Exceptions defined within a class follow the standard access rules. If a class only handles an exception internally, the exception class should be private or protected. If you want the exception to be handled externally, make it public or define it outside of the error-producing class.

14.3.2 Using exception classes with STL containers

The following is an example of how to use exception classes with STL containers.

      // Compile Options /GX
      /**************************************************************
      This is a header file for the derived template class MyVector. 
      MyVector is a derived from Vector template class. It contains 
      the exception class ExceptionRange. The operator [] is overloaded
      and throws the ExceptionRange when there is an attempt to
      access an out of range vector object. 
      **************************************************************/
// MyVector.h
      #ifndef MY_VECTOR_DEFINED
      #define MY_VECTOR_DEFINED
      #include <vector>
      #include <iostream>
      template<class T> class MyVector : public vector<T,allocator<T> >
      {
      public:
      typedef allocator<T> A;
         explicit MyVector(const A& al = A()) : vector<T,A>(al) {};
         explicit MyVector(size_type n, const T& v = T(), 
         const A& al = A()) : vector<T,A>(n, v, al) {}
         MyVector(const MyVector& x) : vector<T,A>(x) {}
         MyVector(const_iterator first, const_iterator last, 
         const A& al = A()) : vector<T,A>(first, last, al) {} 

      class ExceptionRange 
      {
      public:
      ExceptionRange (size_type _P) {
         cout << endl;
         cout <<"An attempt was made to access an element out of 
                            range"<<endl;
         cout << "Element for index: " << _P << " doesn't exist." 
                             << endl; 
         }
      };
      const_reference operator[](size_type _P) const throw 
                                                  (ExceptionRange)
         {
         if ( _P > ((end()-1) - begin()))
            {
            throw ExceptionRange(_P);
            return(*(end()));
            }
         return (*(begin() + _P));
         }
         reference operator[](size_type _P) throw (ExceptionRange)
         {
         if ( _P > ((end()-1) - begin()))
            {
            throw ExceptionRange(_P);
            return(*(end()));
            }
         return (*(begin() + _P));
         }
      };
      #endif
// VectorMain.cpp 
/**************************************************************
       // Compile Options /GX
      /**************************************************************
      This program demonstrates how to use Exception classes with 
      STL. 
      MyVector is a derived from Vector template class.
      This is just one method to make the use of STL library more safe.
      **************************************************************/
      #include <iostream>
      #include "MyVector.h"
      void main()
      {
      MyVector<int> intVect;
      MyVector<int>::iterator intVectPtr;
      for(int i = 0; i < 20; i++)
         intVect.push_back(i*2);
      for(intVectPtr = intVect.begin(); intVectPtr != intVect.end();
       intVectPtr++)
         cout << *intVectPtr << ", ";
         cout <<endl<<endl;

      try 
      {
      for (int k = 0; k < 30 ;k++ )
         cout << intVect[k] <<", ";
      }
      catch (MyVector <int>::ExceptionRange)
      {
         cout <<endl;
         cout << "Exception: Vector out of range" << endl;
      }     
      }   

Program Output:

0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38,
0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38,
An attempt was made to access an element out of range.
Element for index: 20 doesn't exist.
Exception: Vector out of range.

14.4 Exception Classes

The Standard C++ Library defines a base class exception as follows:

class exception {
public:
    exception() throw();
    exception(const exception& rhs) throw();
    exception& operator=(const exception& rhs) throw();
    virtual ~exception() throw();
    virtual const char *what() const throw();
    };

The class serves as the base class for all exceptions thrown by certain expressions and by the Standard C++ Library. The C-string value returned by what() is left unspecified by the default constructor, but may be defined by the constructors for certain derived classes. None of the member functions throws any exceptions.

• The Standard C++ Library provides classes to be used to report certain errors in C++ programs. In the error model reflected in these classes, errors are divided into two broad categories: logic errors and run-time errors.
  
  
• The distinguishing characteristic of logic errors is that they are due to errors in the internal logic of the program. In theory, they are preventable.
  
  
• By contrast, run-time errors are due to events beyond the scope of the program. They cannot be easily predicted in advance. The header <stdexcept> defines several types of predefined exceptions for reporting errors in a C++ program. These exceptions are related via inheritance.

14.4.1 Header <stdexcept> synopsis

  #include <exception>
  #include <string>
  namespace std {
    class logic_error;
      class domain_error;
      class invalid_argument;
      class length_error;
      class out_of_range;
    class runtime_error;
      class range_error;
      class overflow_error;
      class underflow_error;
  }

class logic_error 

  namespace std {
    class logic_error : public exception {
    public:
      logic_error(const string& what_arg);
    };
  }

The class LOGIC_ERROR defines the type of objects thrown as exceptions to report errors that are, presumably, detectable before the program executes, such as violations of logical preconditions or class invariants.

  logic_error(const string& what_arg);
  Effects:
    Constructs an object of class logic_error.
  Postcondition:
    what() == what_arg.data().

class domain_error

  namespace std {
    class domain_error : public logic_error {
    public:
      domain_error(const string& what_arg);
    };
  }

The class DOMAIN_ERROR defines the type of objects thrown as exceptions, by the implementation, to report domain errors.

  domain_error(const string& what_arg);
  Effects:
    Constructs an object of class domain_error.
  Postcondition:
    what() == what_arg.data().
Class invalid_argument 
  namespace std {
    class invalid_argument : public logic_error {
    public:
      invalid_argument(const string& what_arg);
    };
  }

The class INVALID_ARGUMENT defines the type of objects thrown as exceptions to report an invalid argument.

 invalid_argument(const string& what_arg);
 Effects:
    Constructs an object of class invalid_argument.
  Postcondition:
    what() == what_arg.data().

class length_error 

  namespace std {
    class length_error : public logic_error {
    public:
      length_error(const string& what_arg);
    };
  }

The class LENGTH_ERROR defines the type of objects thrown as exceptions to report an attempt to produce an object whose length exceeds its maximum allowable size.

  length_error(const string& what_arg);
  Effects:
    Constructs an object of class length_error.
  Postcondition:
    what() == what_arg.data().
Class out_of_range
  namespace std {
    class out_of_range : public logic_error {
    public:
      out_of_range(const string& what_arg);
    };
  }

The class OUT_OF_RANGE defines the type of objects thrown as exceptions to report an argument value not in its expected range.

  out_of_range(const string& what_arg);
  Effects:
    Constructs an object of class out_of_range.
  Postcondition:
    what() == what_arg.data().

class runtime_error                        

  namespace std {
    class runtime_error : public exception {
    public:
      runtime_error(const string& what_arg);
    };
  }

The class RUNTIME_ERROR defines the type of objects thrown as exceptions to report errors presumably detectable only when the program executes.

  runtime_error(const string& what_arg);
  Effects:
    Constructs an object of class runtime_error.
  Postcondition:
    what() == what_arg.data().

class range_error 

  namespae std {
    class range_error : public runtime_error {
    public:
      range_error(const string& what_arg);
    };
  }

The class RANGE_ERROR defines the type of objects thrown as exceptions to report range errors in internal computations.

  range_error(const string& what_arg);
  Effects:
    Constructs an object of class range_error.
  Postcondition:
    what() == what_arg.data().

class overflow_error

  namespace std {
    class overflow_error : public runtime_error {
    public:
      overflow_error(const string& what_arg);
    };
  }

The class OVERFLOW_ERROR defines the type of objects thrown as exceptions to report an arithmetic overflow error.

  overflow_error(const string& what_arg);
  Effects:
    Constructs an object of class overflow_error.
  Postcondition:
    what() == what_arg.data().

class underflow_error 

  namespace std {
    class underflow_error : public runtime_error {
    public:
      underflow_error(const string& what_arg);
    };
  }

The class UNDERFLOW_ERROR defines the type of objects thrown as exceptions to report an arithmetic underflow error.

  underflow_error(const string& what_arg);
  Effects:
    Constructs an object of class underflow_error.
  Postcondition:
    what() == what_arg.data().

14.4.2 Assertions

This provides macros for documenting C++ program assertions, and for disabling the assertion checks.

The contents are the same as the Standard C library.

14.4.3 Error numbers

The contents are the same as the Standard C library.

14.4.4 Floating-point exception class sample

The following example demonstrates how to implement a floating-point exception class.

// Floating-point exception class sample
// Compile Options /GX
/*******************************************************************
    This program demonstrates how to use the exception classes 
    from the diagnostics library to handle floating point exceptions;
    float_error class is derived from logic_error base class.
********************************************************************/
   #include <exception>
   #include <iostream>
   #include <complex>
   //floating-point exception class
   class float_error : public logic_error    
   {
      public:
         float_error (char buffer[]) : logic_error (buffer)
         {
         cout <<"Floating point math error occurred in 
                            your program ";
         cout <<"More details below:"<<endl;
         }
   };
   //Math error handler
   int _matherr (struct _exception * ex)
   {
      char buffer [128];
      const char * ErrorType;

   //Determine type of error.
      switch (ex->type)
         {
         case _DOMAIN:
             ErrorType = "Domain Error: ";
               break;
         case _SING:
            ErrorType = "Singularity Error:";
            break;
         case _OVERFLOW:
            ErrorType = "Overflow Error:";
            break;
         case _UNDERFLOW:
            ErrorType = "Underflow Error:";
            break;
         case _PLOSS:
            ErrorType = "Partial Loss of significance:";
            break;
         case _TLOSS:
            ErrorType = "Total loss of significance:";
            break;
         default:
            ErrorType = "Some other math error:";
      }
   //Construct error string.
      sprintf (buffer, "%s: %s(%g,%g) returns %g",ErrorType,
             ex->name,ex->arg1,ex->arg2,ex->retval);
   //Throw an exception.
      
      throw float_error(buffer);
      return 0;
   }    
   void  TestMathErrors(double (*fp) (double), double arg)
   {
      //Next text
      bool caught = false;
      //Generate a floating-point error.
      try {
         double x = fp (arg);
         }
      catch (exception & ex)
      {
         cout << ex.what() << endl<<endl;
         caught = true;
      }
      if (!caught) 
         cout << "didn't catch exception through materr\r\n";
   }
   int main (void) 
   {
      typedef double (*fp) (double);
      //Array to the several functions
      fp math_function [] = { &sqrt, &log, &sin, &tan, &acos };  
      double arg []= { -1.0, 0.0, 1.5e25, 1.5e25, 2  };

      for (int n=0;  n < 5;n++)
         
         TestMathErrors(math_function[n],arg[n]);
      
      return 0;
   }

Program output is:

Floating point math error occurred in your program. More details below:
Domain Error: : sqrt(-1,-3.10504e+231) returns -1.#IND
Floating point math error occurred in your program. More details below:
Singularity Error:: log(0,-3.10504e+231) returns -1.#INF
Floating point math error occurred in your program. More details below:
Total loss of significance:: sin(1.5e+025,-3.10504e+231) returns -1.#IND
Floating point math error occurred in your program. More details below:
Total loss of significance:: tan(1.5e+025,-3.10504e+231) returns -1.#IND
Floating point math error occurred in your program. More details below:
Domain Error: : acos(2,-3.10504e+231) returns -1.#IND

15. Appendix A: STL References and Further Reading

ANSII C++ Working Paper. May 1996.

Glass, Graham and Brett Schuchert. The STL Primer. Prentice Hall. 1996

Ladd, Scott Robert. C++ I/O Streams, Containers, and Standard Classes. M&T Books. 1996

Musser, David R. and Atul Saini. STL Tutorial and Reference Guide. Addison-Wesley

Plauger, P.J. The Draft Standard C++ Library. Prentice Hall.

Plauger, P.J. C++ User’s Journal. Series of articles beginning June, 1996.

Stroustrup, Bjarne. The C++ Programming Language, Second Edition. AT&T. 1993

16. Appendix B: STL Container Class Definitions

All the definitions provided below are for STL Container classes provided in Microsoft Visual C++ 4.2.

16.1 deque

Note   In the definition below, the template parameter Type represents the type of data the deque will store (for example, int). The template parameter A represents the allocator object the deque will use for memory allocation.

      
   // TEMPLATE CLASS deque
template<class TYPE, class A>
   class deque {
public:
   typedef deque<TYPE, A> Myt;
   typedef A allocatorTYPE;
   typedef A::sizeTYPE sizeTYPE;
   typedef A::differenceTYPE differenceTYPE;
   typedef A::pointer Tptr;
   typedef A::const_pointer Ctptr;
   typedef POINTER_X(Tptr, A) Mapptr;
   typedef A::reference reference;
   typedef A::const_reference const_reference;
   typedef A::valueTYPE valueTYPE;
      // CLASS iterator
   class iterator : public Ranit<TYPE, differenceTYPE> {
   public:
      friend class deque<TYPE, A>;
      iterator();
      iterator(Tptr P, Mapptr M);
      reference operator*() const;
      iterator& operator++();
      iterator operator++(int);
      iterator& operator--();
      iterator operator--(int);
      iterator& operator+=(differenceTYPE N);
      iterator& operator-=(differenceTYPE N);
      iterator operator+(differenceTYPE N) const;
      iterator operator-(differenceTYPE N) const;
      differenceTYPE operator-(const iterator& X) const;
      reference operator[](differenceTYPE N) const;
      bool operator==(const iterator& X) const;
      bool operator<(const iterator& X) const;
   protected:
      void Add(differenceTYPE N);
   protected:
      Tptr First, Last, Next;
      _Mapptr Map;
      };
      // CLASS const_iterator
   class const_iterator : public iterator {
   public:
      const_iterator();
      const_iterator(Tptr P, Mapptr M);
      const_iterator(const iterator& X);
      const_reference operator*() const;
      const_iterator& operator++();
      const_iterator operator++(int);
      const_iterator& operator--();
      const_iterator operator--(int);
      const_iterator& operator+=(differenceTYPE N);
      const_iterator& operator-=(differenceTYPE N);
      const_iterator operator+(differenceTYPE N) const;
      const_iterator operator-(differenceTYPE N) const;
      differenceTYPE operator-(const const_iterator& X) const;
      const_reference operator[](differenceTYPE N) const;
      bool operator==(const const_iterator& X) const;
      bool operator<(const const_iterator& X) const;
      };
   typedef reverse_bidirectional_iterator<iterator, valueTYPE, reference,
            Tptr, differenceTYPE> reverse_iterator;
   typedef reverse_bidirectional_iterator<const_iterator, valueTYPE,
            const_reference, Ctptr, differenceTYPE> const_reverse_iterator;
   explicit deque(const A& Al = A());
   explicit deque(sizeTYPE N, const TYPE& V = TYPE(),const A& Al = A());
   deque(const Myt& X);
   typedef const_iterator It;
   deque(It F, It L, const A& Al = A());
   ~deque();
   Myt& operator=(const Myt& X);
   iterator begin();
   const_iterator begin() const;
   iterator end();
   const_iterator end() const;
   reverse_iterator rbegin();
   const_reverse_iterator rbegin() const;
   reverse_iterator rend();
   const_reverse_iterator rend() const;
   void resize(sizeTYPE N, TYPE X = TYPE());
   sizeTYPE size() const;
   sizeTYPE max_size() const;
   bool empty() const;
   A getAllocator() const;
   const_reference at(sizeTYPE P) const;
   reference at(sizeTYPE P);
   const_reference operator[](sizeTYPE P) const;
   reference operator[](sizeTYPE P);
   reference front();
   const_reference front() const;
   reference back();
   const_reference back() const;
   void push_front(const TYPE& X);
   void pop_front();
   void push_back(const TYPE& X);
   void pop_back();
   void assign(It F, It L);
   void assign(sizeTYPE N, const TYPE& X = TYPE());
   iterator insert(iterator P, const TYPE& X = TYPE());
   void insert(iterator P, sizeTYPE M, const TYPE& X);
   void insert(iterator P, It F, It L);
   iterator erase(iterator P);
   iterator erase(iterator F, iterator L);
   void clear();
   void swap(Myt& X);
   friend void swap(Myt& X, Myt& Y);
protected:
   void Buyback();
   void Buyfront();
   void Freeback();
   void Freefront();
   void Xran() const;
   A allocator;
   iterator First, Last;
   Mapptr Map;
   sizeTYPE Mapsize, Size;
   };
      // deque TEMPLATE OPERATORS
template<class TYPE, class A> inline bool operator==(const deque<TYPE, A>& X, 
      const deque<TYPE, A>& Y);
template<class TYPE, class A> inline bool operator<(const deque<TYPE, A>& X,
      const deque<TYPE, A>& Y);

16.2 list

Note   In the definition below, the template parameter Type represents the type of data the list will store (for example, int). The template parameter A represents the allocator object the list will use for memory allocation.

// TEMPLATE CLASS list
template<class TYPE, class A>
   class list {
protected:
   typedef POINTER_X(void, A) Genptr;
   struct Node;
   friend struct Node;
   struct Node {
      Genptr Next, Prev;
      TYPE Value;
      };
   typedef POINTER_X(Node, A) Nodeptr;
   struct Acc;
   friend struct Acc;
   struct Acc {
      typedef REFERENCE_X(Nodeptr, A) Nodepref;
      typedef A::reference Vref;
      static Nodepref Next(Nodeptr P)
      static Nodepref Prev(Nodeptr P)
      static Vref Value(Nodeptr P)
      };
public:
   typedef list<TYPE, A> Myt;
   typedef A allocator_type;
   typedef A::size_type size_type;
   typedef A::difference_type difference_type;
   typedef A::pointer Tptr;
   typedef A::const_pointer Ctptr;
   typedef A::reference reference;
   typedef A::const_reference const_reference;
   typedef A::value_type value_type;
      // CLASS iterator
   class iterator;
   friend class iterator;
   class iterator : public Bidit<TYPE, difference_type> {
   public:
      iterator()
      iterator(Nodeptr P)
      reference operator*() const
      iterator& operator++()
      iterator operator++(int)
      iterator& operator--()
      iterator operator--(int)
      bool operator==(const iterator& X) const
      Nodeptr Mynode() const
   protected:
      Nodeptr Ptr;
      };
      // CLASS const_iterator
   class const_iterator;
   friend class const_iterator;
   class const_iterator : public iterator {
   public:
      const_iterator()
      const_iterator(Nodeptr P)
      const_iterator(const iterator& X)
      const_reference operator*() const
      const_iterator& operator++()
      const_iterator operator++(int)
      const_iterator& operator--()
      const_iterator operator--(int)
      bool operator==(const const_iterator& X) const
      };
   typedef reverse_bidirectional_iterator<iterator,
      value_type, reference, Tptr, difference_type>
         reverse_iterator;
   typedef reverse_bidirectional_iterator<const_iterator,
      value_type, const_reference, Ctptr, difference_type>
         const_reverse_iterator;
   explicit list(const A& Al = A())
   explicit list(size_type N, const TYPE& V = TYPE(),
      const A& Al = A())
   list(const Myt& X)
   typedef const_iterator It;
   list(It F, It L, const A& Al = A())
   ~list()
   Myt& operator=(const Myt& X)
   iterator begin()
   const_iterator begin() const
   iterator end()
   const_iterator end() const
   reverse_iterator rbegin()
   const_reverse_iterator rbegin() const
   reverse_iterator rend()
   const_reverse_iterator rend() const
   void resize(size_type N, TYPE X = TYPE())
   size_type size() const
   size_type max_size() const
   bool empty() const
   A get_allocator() const
   reference front()
   const_reference front() const
   reference back()
   const_reference back() const
   void push_front(const TYPE& X)
   void pop_front()
   void push_back(const TYPE& X)
   void pop_back()
   void assign(It F, It L)
   void assign(size_type N, const TYPE& X = TYPE())
   iterator insert(iterator P, const TYPE& X = TYPE())
   void insert(iterator P, size_type M, const TYPE& X)
   void insert(iterator P, const TYPE *F, const TYPE *L)
   void insert(iterator P, It F, It L)
   iterator erase(iterator P)
   iterator erase(iterator F, iterator L)
   void clear()
   void swap(Myt& X)
   friend void swap(Myt& X, Myt& Y)
   void splice(iterator P, Myt& X)
   void splice(iterator P, Myt& X, iterator F)
   void splice(iterator P, Myt& X, iterator F, iterator L)
   void remove(const TYPE& V)
   typedef binder2nd<not_equal_to<TYPE> > Pr1;
   void remove_if(Pr1 Pr)
   void unique()
   typedef not_equal_to<TYPE> Pr2;
   void unique(Pr2 Pr)
   void merge(Myt& X)
   typedef greater<TYPE> Pr3;
   void merge(Myt& X, Pr3 Pr)
   void sort()
   void sort(Pr3 Pr)
   void reverse()
protected:
   Nodeptr Buynode(Nodeptr Narg = 0, Nodeptr Parg = 0)
   void Freenode(Nodeptr S)
   void Splice(iterator P, Myt& X, iterator F, iterator L)
   void Xran() const
   A allocator;
   Nodeptr Head;
   size_type Size;
   };
      // list TEMPLATE OPERATORS
template<class TYPE, class A> inline
   bool operator==(const list<TYPE, A>& X,
      const list<TYPE, A>& Y)
template<class TYPE, class A> inline
   bool operator<(const list<TYPE, A>& X,
      const list<TYPE, A>& Y)

16.3 map and multimap

Note   In the definitions below, the template parameter K represents the type of data the map will store (for example, int). The template parameter Pr represents the user-defined comparator object (for example, less<K>). The template parameter A represents the allocator object the map will use for memory allocation.

// TEMPLATE CLASS map
template<class K, class TYPE, class Pr, class A>
   class map {
public:
   typedef map<K, TYPE, Pr, A> Myt;
   typedef pair<const K, TYPE> value_type;
   struct Kfn : public unary_function<value_type, K> {
      const K& operator()(const value_type& X) const
      };
   class value_compare
      : public binary_function<value_type, value_type, bool> {
      friend class map<K, TYPE, Pr, A>;
   public:
      bool operator()(const value_type& X,
         const value_type& Y) const
   protected:
      value_compare(Pr Pred)
      Pr comp;
      };
   typedef K key_type;
   typedef TYPE referent_type;
   typedef Pr key_compare;
   typedef A allocator_type;
   typedef A::reference Tref;
   typedef Tree<K, value_type, Kfn, Pr, A> Imp;
   typedef Imp::size_type size_type;
   typedef Imp::difference_type difference_type;
   typedef Imp::reference reference;
   typedef Imp::const_reference const_reference;
   typedef Imp::iterator iterator;
   typedef Imp::const_iterator const_iterator;
   typedef Imp::reverse_iterator reverse_iterator;
   typedef Imp::const_reverse_iterator const_reverse_iterator;
   typedef pair<iterator, bool> Pairib;
   typedef pair<iterator, iterator> Pairii;
   typedef pair<const_iterator, const_iterator> Paircc;
   explicit map(const Pr& Pred = Pr(), const A& Al = A())
   typedef const value_type *It;
   map(It F, It L, const Pr& Pred = Pr(),
   iterator begin()
   const_iterator begin() const
   iterator end()
   const_iterator end() const
   reverse_iterator rbegin()
   const_reverse_iterator rbegin() const
   reverse_iterator rend()
   const_reverse_iterator rend() const
   size_type size() const
   size_type max_size() const
   bool empty() const
   A get_allocator() const
   Tref operator[](const key_type& Kv)
   Pairib insert(const value_type& X)
   iterator insert(iterator P, const value_type& X)
   void insert(It F, It L)
   iterator erase(iterator P)
   iterator erase(iterator F, iterator L)
   size_type erase(const K& Kv)
   void clear()
   void swap(Myt& X)
   friend void swap(Myt& X, Myt& Y)
   key_compare key_comp() const
   value_compare value_comp() const
   iterator find(const K& Kv)
   const_iterator find(const K& Kv) const
   size_type count(const K& Kv) const
   iterator lower_bound(const K& Kv)
   const_iterator lower_bound(const K& Kv) const
   iterator upper_bound(const K& Kv)
   const_iterator upper_bound(const K& Kv) const
   Pairii equal_range(const K& Kv)
   Paircc equal_range(const K& Kv) const
protected:
   Imp Tr;
   };
      // map TEMPLATE OPERATORS
template<class K, class TYPE, class Pr, class A> inline
   bool operator==(const map<K, TYPE, Pr, A>& X,
      const map<K, TYPE, Pr, A>& Y)
template<class K, class TYPE, class Pr, class A> inline
   bool operator<(const map<K, TYPE, Pr, A>& X,
      const map<K, TYPE, Pr, A>& Y)
      // TEMPLATE CLASS multimap
template<class K, class TYPE, class Pr, class A>
   class multimap {
public:
   typedef multimap<K, TYPE, Pr, A> Myt;
   typedef pair<const K, TYPE> value_type;
   struct Kfn : public unary_function<value_type, K> {
      const K& operator()(const value_type& X) const
      };
   class value_compare
      : public binary_function<value_type, value_type, bool> {
      friend class Myt;
   public:
      bool operator()(const value_type& X,
         const value_type& Y) const
   protected:
      value_compare(Pr Pred)
      Pr comp;
      };
   typedef K key_type;
   typedef TYPE referent_type;
   typedef Pr key_compare;
   typedef A allocator_type;
   typedef Tree<K, value_type, Kfn, Pr, A> Imp;
   typedef Imp::size_type size_type;
   typedef Imp::difference_type difference_type;
   typedef Imp::reference reference;
   typedef Imp::const_reference const_reference;
   typedef Imp::iterator iterator;
   typedef Imp::const_iterator const_iterator;
   typedef Imp::reverse_iterator reverse_iterator;
   typedef Imp::const_reverse_iterator const_reverse_iterator;
   typedef pair<iterator, iterator> Pairii;
   typedef pair<const_iterator, const_iterator> Paircc;
   explicit multimap(const Pr& Pred = Pr(),
   typedef const value_type *It;
   multimap(It F, It L, const Pr& Pred = Pr(), const A& Al = A())
   iterator begin()
   const_iterator begin() const
   iterator end()
   const_iterator end() const
   reverse_iterator rbegin()
   const_reverse_iterator rbegin() const
   reverse_iterator rend()
   const_reverse_iterator rend() const
   size_type size() const
   size_type max_size() const
   bool empty() const
   A get_allocator() const
   iterator insert(const value_type& X)
   iterator insert(iterator P, const value_type& X)
   void insert(It F, It L)
   iterator erase(iterator P)
   iterator erase(iterator F, iterator L)
   size_type erase(const K& Kv = K())
   void clear()
   void swap(Myt& X)
   friend void swap(Myt& X, Myt& Y)
   key_compare key_comp() const
   value_compare value_comp() const
   iterator find(const K& Kv)
   const_iterator find(const K& Kv) const
   size_type count(const K& Kv) const
   iterator lower_bound(const K& Kv)
   const_iterator lower_bound(const K& Kv) const
   iterator upper_bound(const K& Kv)
   const_iterator upper_bound(const K& Kv) const
   Pairii equal_range(const K& Kv)
   Paircc equal_range(const K& Kv) const
protected:
   Imp Tr;
   };
      // multimap TEMPLATE OPERATORS
template<class K, class TYPE, class Pr, class A> inline bool operator==(const multimap<K, TYPE, Pr, A>& X,
      const multimap<K, TYPE, Pr, A>& Y)
template<class K, class TYPE, class Pr, class A> inline
   bool operator<(const multimap<K, TYPE, Pr, A>& X,
      const multimap<K, TYPE, Pr, A>& Y)

16.4 set and multiset

Note   In the definitions below, the template parameter K represents the type of data the set will store (for example, int). The template parameter Pr represents the user-defined comparator object (for example, less<K>). The template parameter A represents the allocator object the set will use for memory allocation.

// TEMPLATE CLASS set
template<class K, class Pr,
   class A>
   class set {
public:
   typedef set<K, Pr, A> Myt;
   typedef K TYPE;
   typedef TYPE value_type;
   struct Kfn : public unary_function<value_type, K> {
      const K& operator()(const value_type& X) const
   typedef Pr value_compare;
   typedef K key_type;
   typedef Pr key_compare;
   typedef A allocator_type;
   typedef Tree<K, value_type, Kfn, Pr, A> Imp;
   typedef Imp::size_type size_type;
   typedef Imp::difference_type difference_type;
   typedef Imp::const_reference reference;
   typedef Imp::const_reference const_reference;
   typedef Imp::const_iterator iterator;
   typedef Imp::const_iterator const_iterator;
   typedef Imp::const_reverse_iterator reverse_iterator;
   typedef Imp::const_reverse_iterator const_reverse_iterator;
   typedef pair<iterator, bool> Pairib;
   typedef pair<const_iterator, const_iterator> Paircc;
   explicit set(const Pr& Pred = Pr(), const A& Al = A())
   typedef const value_type *_It;
   set(_It F, It L, const Pr& Pred = Pr(), const A& Al = A())
   const_iterator begin() const
   const_iterator end() const
   const_reverse_iterator rbegin() const
   const_reverse_iterator rend() const
   size_type size() const
   size_type max_size() const
   bool empty() const
   A getAllocator() const
   _Pairib insert(const value_type& X)
   iterator insert(iterator P, const value_type& X)
   void insert(_It F, It L)
   iterator erase(iterator P)
   iterator erase(iterator F, iterator L)
   size_type erase(const K& Kv)
   void clear()
   void swap(_Myt& X)
   friend void swap(_Myt& X, Myt& Y)
   key_compare key_comp() const
   value_compare value_comp() const
   const_iterator find(const K& Kv) const
   size_type count(const K& Kv) const
   const_iterator lower_bound(const K& Kv) const
   const_iterator upper_bound(const K& Kv) const
   Paircc equal_range(const K& Kv) const
protected:
   Imp Tr;
   };
      // set TEMPLATE OPERATORS
template<class K, class Pr, class A> inline
     bool operator==(const set<K, Pr, A>& X, const set<K, Pr, A>& Y)
template<class K, class Pr, class A> inline
   bool operator<(const set<K, Pr, A>& X, const set<K, Pr, A>& Y)
      // TEMPLATE CLASS multiset
template<class K, class Pr,
   class A>
   class multiset {
public:
   typedef multiset<K, Pr, A> Myt;
   typedef K TYPE;
   typedef TYPE value_type;
   struct Kfn : public unary_function<value_type, K> {
      const K& operator()(const value_type& X) const
      };
   typedef Pr value_compare;
   typedef K key_type;
   typedef Pr key_compare;
   typedef A allocator_type;
   typedef Tree<K, value_type, Kfn, Pr, A> Imp;
   typedef Imp::size_type size_type;
   typedef Imp::difference_type difference_type;
   typedef Imp::const_reference reference;
   typedef Imp::const_reference const_reference;
   typedef Imp::const_iterator iterator;
   typedef Imp::const_iterator const_iterator;
   typedef Imp::const_reverse_iterator reverse_iterator;
   typedef Imp::const_reverse_iterator const_reverse_iterator;
   typedef pair<const_iterator, const_iterator> Paircc;
   explicit multiset(const Pr& Pred = Pr(), const A& Al = A())
   typedef const value_type *_It;
   multiset(_It F, It L, const Pr& Pred = Pr(),
   const_iterator begin() const
   const_iterator end() const
   const_reverse_iterator rbegin() const
   const_reverse_iterator rend() const
   size_type size() const
   size_type max_size() const
   bool empty() const
   A getAllocator() const
   iterator insert(const value_type& X)
   iterator insert(iterator P, const value_type& X)
   void insert(_It F, It L)
   iterator erase(iterator P)
   iterator erase(iterator F, iterator L)
   size_type erase(const K& Kv)
   void clear()
   void swap(_Myt& X)
   friend void swap(_Myt& X, Myt& Y)
   key_compare key_comp() const
   value_compare value_comp() const
   const_iterator find(const K& Kv) const
   size_type count(const K& Kv) const
   const_iterator lower_bound(const K& Kv) const
   const_iterator upper_bound(const K& Kv) const
   _Paircc equal_range(const K& Kv) const
protected:
   _Imp Tr;
   };
      // multiset TEMPLATE OPERATORS
template<class K, class Pr, class A> inline
     bool operator==(const multiset<K, Pr, A>& X, const multiset<K, Pr, A>& Y)
template<class K, class Pr, class A> inline
     bool operator<(const multiset<K, Pr, A>& X, const multiset<K, Pr, A>& Y)

16.5 vector

Note   In the definition below, the template parameter Type represents the type of data the vector will store (for example, int). The template parameter A represents the allocator object the vector will use for memory allocation.

// TEMPLATE CLASS vector
template<class TYPE, class A>
     class vector {
public:
     typedef vector<TYPE, A> Myt;
     typedef A allocatorTYPE;
     typedef A::sizeTYPE sizeTYPE;
     typedef A::differenceTYPE differenceTYPE;
     typedef A::pointer Tptr;
     typedef A::const_pointer Ctptr;
     typedef A::reference reference;
     typedef A::const_reference const_reference;
     typedef A::valueTYPE valueTYPE;
     typedef Tptr iterator;
     typedef Ctptr const_iterator;
     typedef reverse_iterator<const_iterator, valueTYPE, const_reference,
          Ctptr, differenceTYPE> const_reverse_iterator;
     typedef reverse_iterator<iterator, valueTYPE, reference, Tptr,
          differenceTYPE> reverse_iterator;
     explicit vector(const A& Al = A());
     explicit vector(sizeTYPE N, const TYPE& V = TYPE(), const A& Al = A());
     vector(const Myt& X);
     typedef const_iterator _It;
     vector(It F, It L, const A& Al = A());
     ~vector();
     Myt& operator=(const Myt& X);
     void reserve(sizeTYPE N);
     sizeTYPE capacity() const;
     iterator begin();
     const_iterator begin() const;
     iterator end();
     const_iterator end() const;
     reverse_iterator rbegin();
     const_reverse_iterator rbegin() const;
     reverse_iterator rend();
     const_reverse_iterator rend() const;
     void resize(sizeTYPE N, TYPE X = TYPE());
     sizeTYPE size() const;
     sizeTYPE max_size() const;
     bool empty() const;
     A getAllocator() const;
     const_reference at(sizeTYPE P) const;
     reference at(sizeTYPE P);
     const_reference operator[](sizeTYPE P) const;
     reference operator[](sizeTYPE P);
     reference front();
     const_reference front() const;
     reference back();
     const_reference back() const;
     void push_back(const TYPE& X);
     void pop_back();
     void assign(It F, It L);
     void assign(sizeTYPE N, const TYPE& X = TYPE());
     iterator insert(iterator P, const TYPE& X = TYPE());
     void insert(iterator P, sizeTYPE M, const TYPE& X);
     void insert(iterator P, It F, It L);
     iterator erase(iterator P);
     iterator erase(iterator F, iterator L);
     void clear();
     void swap(Myt& X);
     friend void swap(Myt& X, Myt& Y);
protected:
     void _Destroy(iterator F, iterator L);
     void _Xran() const;
     A allocator;
     iterator First, Last, End;
     };
          // vector TEMPLATE OPERATORS
template<class TYPE, class A> inline bool operator==(const vector<TYPE, A>& X,
     const vector<TYPE, A>& Y);
template<class TYPE, class A> inline bool operator<(const vector<TYPE, A>& X,
     const vector<TYPE, A>& Y);

16.6 stack

Note   In the definition below, the template parameter Type represents the type of data the stack will store (for example, int). The template parameter C represents the container the stack is adapting (for example, deque). The template parameter A represents the allocator object the stack will use for memory allocation.

      
   // TEMPLATE CLASS stack
template<class TYPE, class C, class A>
   class stack {
public:
   typedef A allocator_type;
   typedef C::value_type value_type;
   typedef C::size_type size_type;
   explicit stack(const A& Al = A());
   A get_allocator() const:
bool empty() const;
   size_type size() const;
   value_type& top();
   const value_type& top() const;
   void push(const value_type& X);
   void pop();
   bool operator==(const stack<TYPE, C, A>& X) const;
   bool operator<(const stack<TYPE, C, A>& X) const;
protected:
   C c;
};

16.7 priority_queue

Note   In the definition below, the template parameter Type represents the type of data the priority_queue will store (for example, int). The template parameter C represents the container the priority_queue is adapting (for example, deque). The template parameter Pr represents the user-defined comparator object to order the sequence (for example, less<TYPE>). The template parameter A represents the allocator object the priority_queue will use for memory allocation (for example, allocator<TYPE>).

// TEMPLATE CLASS priority_queue
template<class TYPE, class C,
   class Pr,
   class A>
   class priority_queue {
public:
   typedef A allocatorTYPE;
   typedef C::valueTYPE valueTYPE;
   typedef C::sizeTYPE sizeTYPE;
   explicit priority_queue(const Pr& X = Pr(), const A& Al = A());
   typedef const valueTYPE *It;
   priority_queue(It F, It L, const Pr& X = Pr(), const A& Al = A()):
   A getAllocator() const;
   bool empty() const;
   sizeTYPE size() const;
   valueTYPE& top();
   const valueTYPE& top() const;
   void push(const valueTYPE& X);
   void pop();
protected:
   C c;
   Pr comp;
};

16.8 queue

Note   The template parameter Type in the definition below represents the type of data the queue will store (for example, int). The template parameter C represents the container the queue is adapting (for example, deque). The template parameter A represents the allocator object the queue will use for memory allocation.

// TEMPLATE CLASS queue
template<class TYPE, class C, class A>
   class queue {
public:
   typedef A allocatorTYPE;
   typedef C::valueTYPE valueTYPE;
   typedef C::sizeTYPE sizeTYPE;
   explicit queue(const A& Al = A());
   A getAllocator() const;
   bool empty() const;
   sizeTYPE size() const;
   valueTYPE& front();
   const valueTYPE& front() const;
   valueTYPE& back();
   const valueTYPE& back() const;
   void push(const valueTYPE& X);
   void pop();
   bool operator==(const queue<TYPE, C, A>& X) const;
   bool operator<(const queue<TYPE, C, A>& X) const;
protected:
   C c;
};

17. Appendix C: STL Container Class Methods

All the STL container class methods listed apply to STL containers provided with Microsoft Visual C++ 4.2.

17.1 deque

17.2 list

17.3 map and multimap

Each element listed here is a member of both map and multimap, with exceptions noted explicitly.

References to map::[symbol] imply the existence of multimap::[symbol] with similar behavior.

17.4 set and multiset

Each element listed here is a member of both set and multiset, with exceptions noted explicitly. References to set::[symbol] imply the existence of multiset::[symbol] with similar behavior.

17.5 vector

17.6 priority_queue

17.7 queue

Note   Books online for Visual C++ 4.2 says that the queue class has a top member function (like a stack). This is an error in books online. The ANSII working papers specify that queue has a front (and not a top) member function.

17.8 stack

18. Appendix D: Allocator Class

Several STL components use Default Template Arguments. The ANSII draft specification for the STL container classes (such as vector) dictates that the template parameter that specifies the allocator must have a default value of "allocator", as follows:

template<class T, class Allocator = allocator> class vector;

The class allocator as specified by the ANSII draft standard utilizes member templates. Visual C++ version 4.2 does not support the use of member templates. (The term member template refers to one or more methods of a (possibly nontemplated) class that are defined as templated functions. It can also be used to describe a class that has an embedded template class.)

Since it is not possible to implement the class allocator directly, allocator has been implemented as a template class in the current implementation of the STL. The problem lies in attempting to use the templated allocator class as a default template argument. Consider the following:

template<class T, class Allocator = allocator<T> > class vector;

This new construct with the template allocator class creates a circular reference, because it relies on the unknown data type T to instantiate the allocator class. This makes it necessary, in the case of STL containers, to remove the default template argument for the allocator. The definition of vector now becomes:

template<class T, class Allocator> class vector;

Therefore, declaring a container will now require that you explicitly specify the allocator class as a template argument, as the following declaration of an int vector illustrates:

vector<int> myVector; 

This declaration will cause the following compiler error:

Compiler error C2976 : 'vector' : too few template parameters

To correct the error, the declaration must be changed to:

vector<int, allocator<int> > myVector; 

Note   The STL is an emerging technology. The definition of the allocator class as a templated class will undoubtedly change in a future release of Visual C++. You should always use typedefs when using any component of the STL—this will make it relatively painless to update your code if and when the templates change.