Visual Cpp Template Library

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 runtime 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 ALGORITHM

BITSET

CASSERT

CCTYPE

CERRNO

CFLOAT

CISO646

CLIMITS

CLOCALE

CMATH

COMPLEX

CSETJMP

CSIGNAL

CSTDARG

CSTDDEF

CSTDIO

CSTDLIB

CSTRING

CTIME

CWCHAR

CWCTYPE

DEQUE

EXCEPTION

FSTREAM

FUNCTIONAL IOMANIP

IOS

IOSFWD

IOSTREAM

ISTREAM

ITERATOR

LIMITS

LIST

LOCALE

MAP

MEMORY

NEW

NUMERIC

OSTREAM

QUEUE

SET

SSTREAM

STACK

STDEXCEPT

STREAMBUF

STRING

STRSTREAM

TYPEINFO

UTILITY

VALARRAY

VECTOR

XIOSBASE

XLOCALE

XLOCINFO

XLOCMON

XLOCNUM

XLOCTIME

XMEMORY

XSTDDEF

XSTRING

XTREE

XUTILITY

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 Library types and related compiler switches

Basic C run-time library

Standard C++ Library

Old iostream library

Single Threaded (ML)

LIBC.LIB

LIBCP.LIB

LIBCI.LIB

Multithreaded (MT)

LIBCMT.LIB

LIBCPMT.LIB

LIBCIMT.LIB

Multithreaded DLL version (MD)

MSVCRT.LIB (import library for MSVCRT.DLL)

MSVCPRT.LIB (also uses MSVCRT.DLL)

MSVCIRT.LIB (import library for MSVCIRT.DLL)

Debug Single Threaded (MLd)

LIBCD.LIB

LIBCPD.LIB

LIBCID.LIB

Debug Multithreaded (MTd)

LIBCMTD.LIB

LIBCPMTD.LIB

LIBCIMTD.LIB

Debug Multithreaded DLL (MDd)

MSVCRTD.LIB (import library for MSVCRTD.DLL)

MSVCPRTD.LIB (also uses MSVCRTD.DLL)

MSVCIRTD.LIB (import library for MSVCIRTD.DLL)

Case 1. Consider the following sample C++ program where test.cpp uses the Standard C++ Library iostream to print "Hello World". // test.cpp #include void main() { cout << "Hello World" << endl ; }

Building test.cpp using

Will cause test.cpp to link with

cl /ML /GX test.cpp

LIBC.LIB, LIBCP.LIB

cl /MLd /GX test.cpp

LIBCD.LIB, LIBCPD.LIB

cl /MT /GX test.cpp

LIBCMT.LIB, LIBCPMT.LIB

cl /MTd /GX test.cpp

LIBCMTD.LIB, LIBCPMTD.LIB

cl /MD /GX test.cpp

MSVCRT.LIB, MSVCPRT.LIB

cl /MDd /GX test.cpp

MSVCRTD.LIB, MSVCPRTD.LIB

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 . 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() { }

Building test.cpp using

Will cause test.cpp to link with

cl /ML test.cpp

LIBC.LIB

cl /MLd test.cpp

LIBCD.LIB

cl /MT test.cpp

LIBCMT.LIB

cl /MTd test.cpp

LIBCMTD.LIB

cl /MD test.cpp

MSVCRT.LIB

cl /MDd test.cpp

MSVCRTD.LIB

Case 3. Consider the following sample program: // test.cpp #include void main() { }

Building test.cpp using

Will cause test.cpp to link with

cl /ML test.cpp

LIBC.LIB, LIBCI.LIB

cl /MLd test.cpp

LIBCD.LIB, LIBCID.LIB

cl /MT test.cpp

LIBCMT.LIB, LIBCIMT.LIB

cl /MTd test.cpp

LIBCMTD.LIB, LIBCIMTD.LIB

cl /MD test.cpp

MSVCRT.LIB, MSVCIRT.LIB

cl /MDd test.cpp

MSVCRTD.LIB, MSVCIRTD.LIB

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 reusability. 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 template that has a T type parameter. T can be replaced with actual types. For example, if the type parameter is , C++ will generate the class Queue. Therefore, changing the implementation of the Queue becomes relatively simple. In our example, once the changes are implemented in the template Queue, they are immediately reflected in the classes Queue, Queue<Messages>, and Queue. 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 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, 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 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 b { public: b() ; ~b() ; } ;

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

//main.cpp #include “B.h” void main() { b bi ; b 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 and B. 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 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 Stack::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 int Stack::push(const T& item) { if (!isFull()) { stackPtr[++top] = item ; return 1 ; // push successful } return 0 ; // push unsuccessful

} //Pop an element off the Stack. template int Stack::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 #include “stack.h” void main() { typedef Stack FloatStack ; typedef Stack 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 1.1 2.2 3.3 4.4 5.5 Stack Full. Popping elements from 5.5 4.4 3.3 2.2 1.1 Stack Empty Pushing elements onto 1 2 3 4 5 6 7 8 9 10 Stack Full Popping elements from 10 9 8 7 6 5 4 3 2 1 Stack Empty

fs fs is is

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 > 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 > INTVECTOR ; INTVECTOR vi1 ;

In a future version, the second parameter may not be required, for example, typedef vector 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 //max returns the maximum of the two elements template 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 //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 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 #include <string.h> //max returns the maximum of the two elements template 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 Class Template

Friend declaration in class template X

Result of giving friendship

template class class friend void f1() ; X

makes f1() a friend of all instantiations of template X. For example, f1() is a friend of X, X, and X.

template class class friend void f2(X&) ; X

For a particular type T for example, float, makes f2(X&) a friend of class X only. f2(x&) cannot be a friend of class X.

template class class friend A::f4() ; X // A is a user defined class

makes A::f4() a friend of all instantiations of template X. For example, A::f4() is a friend of X, X, and X.

//with a //member function f4() ; template class class friend C::f5(X&) ; X // C is a class // template // with a member

A particular type T (for example, float) makes C::f5(X&) a friend of class X only. C::f5(x&) cannot be a friend of class X.

// function f5 template class class friend class Y ; X

makes every member function of class Y a friend of every template class produced from the class template X.

template class class friend class Z ; X

when a template class is instantiated with a particular type T, such as a float, all members of class Z become friends of template class X.

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 Stack ;

Then, a declaration such as: Stack 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.

3.8 Default Template Parameters Let us look at the Stack class template again: template Stack { ....} ;

C++ allows you to specify a default template parameter, so the definition could now look like: template 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.

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 class types; // member class template template class 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 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 >

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 > 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 >

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 > 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 >

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 > 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

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", 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, allocator > 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;

sorted)

// print the contents of the set (note the values are 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

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-toone 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, 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, (1, (2, (3, (4, (5, (6, (7, (8, (9,

Zero) One) Two) Three) Four) Five) Six) Seven) Eight) 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 Iterator category

Characteristics

input

Can read one item at a time; can only move forward (increment)

output

Can write one item at a time; can only move forward (increment)

forward

Multiply derived from input and output iterators; combines their characteristics (read or write)

bidirectional

Derived from forward iterator; adds ability to move backwards (decrement)

random access

Derived from bidirectional; adds ability to jump forward or backward by an arbitrary distance

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 >, 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 Operator/function

Required behavior

Copy Constructor

X(a) == a X b(a) must result in a == b

operator=

X b = a and a = b both must result in a == b

operator==

The return type must be convertible to bool and ‘==’ must be an equality relation (such as reflexive, transitive, or associative.)

operator!=

The return type must be convertible to bool and a != b must be the same as !(a == b)

operator*

The return type must be convertible to T. If a == b then *a == *b. Dereferencing an input stream returns a read-only reference of type T. This means that operator* can only appear on the right-hand side of an assignment statement (is an rvalue). t = *a results in t being assigned a value through a.

operator++ (prefix)

The return type must be convertible to type const X&. It is also assumed that the return type is dereferenceable or is the “past-theend” value of the container.

operator++(int) (postfix)

The return must be convertible to type const X&. The result must be identical to

{X tmp = r; ++r; return tmp; }.

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 Operator/function Required behavior Copy Constructor

*a = t and *X(a) = t. The result of X b(a) is that b is a copy of a (Note that equality and inequality are not necessarily defined for output iterators).

operator=

The result of X b = a is that b is a copy of a.

operator*

*a = t results in the value of t being written to the location referenced by a. The return value of the operation is meaningless. Note that the only valid use of operator* on output iterators is on the left-hand side of an assignment (as an lvalue).

operator++ (prefix)

The return type must be convertible to type const X&. It is also assumed that the return type is dereferenceable or is the “past-theend” value of the container.

operator++(int) (postfix)

The return type must be convertible to type const X&. The result must be identical to: {X tmp = r; ++r; return tmp; }

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 Operator/function

Required behavior

Default Constructor

X() and X a both create an iterator whose position is undefined

Copy Constructor

X(a) == a and X b(a) must result in a == b

operator=

X b = a and a = b must result in a == b

operator==

The return type must be convertible to bool, and ‘==’ must be an equality relation (reflexive, transitive, associative, etc.)

operator!=

The return type must be convertible to bool, and a != b must be the same as !(a == b)

operator*

The return type must be convertible to T. If a == b, then *a == *b. If X is mutable (writable), then *a = t is valid and results in the value of t being written to the location referenced by a.

operator++ (prefix)

The return type must be convertible to type const X&. It is also assumed that the return type is dereferenceable or is the “past-theend” value of the container. In addition, r == s implies that ++r == ++s.

operator++(int) (postfix)

The return type must be convertible to type const X&. The result must be identical to: {X tmp = r; ++r; return tmp; }

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 Operator/function Required behavior operator-(prefix)

The return type must be convertible to type const X&. In addition, the following properties must hold: --(++r) == r, and r == s implies that --r == --s.

operator--(int) (postfix)

The return type must be convertible to type const X&. The result must be identical to: {X tmp = r; --r; return tmp;}

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 Operator/function Required behavior operator+=

The return type must be convertible to X&. The result of r += n must be the same as computing ‘r++’ n times if n > 0 or ‘r--‘ abs(n) times if n < 0 (trivially, r+=0 == 0).

operator+

The return type must be convertible to X. The result of a + n must be identical to: {X tmp = a; return tmp += n; }. The result of n + a must be the same as a + n (reflexive).

operator-=

The return type must be convertible to X&. The result of r -= n must be the same as the result of r += (-n)

operator-

The result of a - n must be convertible to X, and identical to {X tmp = a; return tmp -= n; }. The result of a - b must be convertible to an integral type that can describe the difference between two locations (difference_type). If a - b = n, then: a + n = b;

operator[]

The return type must be convertible to T. The result of a[n] must be identical to *(a + n).

operator<

The return type must be convertible to bool and operator< must be a total ordering relation

operator>

The return type must be convertible to bool. The result of a > b must be identical to: a < b.

operator>=

The return type must be convertible to bool. The result of a >= b must be identical to: !(a < b).

operator<=

The return type must be convertible to bool. The result of a <= b must be identical to: !(a > b).

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 STL container Type of iterator vector

random access

deque

random access

list

bidirectional

multiset

bidirectional

set

bidirectional

multimap

bidirectional

map

bidirectional

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

iterator (mutable)

•

const_iterator (nonmutable)

To declare an iterator, simply use the syntax C::iterator or C::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 #include typedef vector > 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 is derived from the base class iterator 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. 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 > 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 is derived from the base class iterator 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 > STRING_INPUT; // STRING_OUTPUT is an ostream_iterator for objects of type string typedef ostream_iterator<string, char, char_traits > 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, supplies typedefs for reverse iterators: •

reverse_iterator (mutable)

•

const_reverse_iterator (nonmutable)

to declare an iterator, simply use the syntax C::reverse_iterator or C::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 #include typedef vector > 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 > v1; // d1 holds 100 1’s deque > 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 > 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 > 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, allocator > 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 IALLOC; typedef deque IDQ; typedef stack 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 IALLOC; typedef deque IDQ; typedef queue 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 IALLOC; typedef vector IV; typedef priority_queue, 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, allocator > 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 Member function

Description

string& append(const char *s);

Appends the sequence specified by *s to the end of the sequence controlled by *this, then returns *this.

string& append(const char *s, size_type n);

Appends n characters of the sequence specified by *s to the end of the sequence controlled by *this, then returns *this.

string& append(const string& str, size_type pos, size_type n);

Appends n characters of the sequence specified by str starting at position pos to the end of the sequence controlled by *this, then returns *this.

string& append(const string& str);

Appends the sequence specified by str to the

end of the sequence controlled by *this, then returns *this. string& append(size_type n, char c);

Appends n copies of the character specified by c to the end of the sequence controlled by *this, then returns *this.

string& append(const_iterator first, const_iterator last);

Appends the sequence specified by [first, last) to the end of the sequence controlled by *this, then returns *this.

string&assign(const char *s);

Replaces the sequence controlled by *this with the sequence specified by *s, then returns *this.

string& assign(const char *s, size_type n);

Replaces the sequence controlled by *this with n characters of the sequence specified by *s, then returns *this.

string& assign(const string& str, size_type pos, size_type n);

Replaces the sequence controlled by *this with n characters of the sequence specified by str, starting at position pos, then returns *this.

string& assign(const string& str);

Replaces the sequence controlled by *this with the sequence specified by str, then returns *this.

string& assign(size_type n, char c);

Replaces the sequence controlled by *this with n copies of the character specified by c, then returns *this.

string& assign(const_iterator first, const_iterator last);

Replaces the sequence specified by [first, last) to the end of the sequence controlled by *this, then returns *this.

const_reference at(size_type pos) const; reference at(size_type pos) ;

Returns a reference to the element of the controlled sequence at position pos, or reports an out-of-range error.

const_iterator begin() const; iterator begin();

Returns a random-access iterator that points at the first element of the sequence (or just beyond the end of an empty sequence).

const char *c_str() const;

Returns a pointer to a nonmodifiable C string constructed by adding a terminating null element (traits_type:: eos()) to the controlled sequence. Calling any non-const

member function for *this can invalidate the pointer. size_type capacity() const;

The member function returns the storage currently allocated to hold the controlled sequence, a value at least as large as size().

int compare(const string& str) const;

Compares elements of the controlled sequence, if these arguments are not supplied, to the sequence specified by str. The function returns: · a negative value if the first differing element in the controlled sequence compares less than the corresponding element in str , or if the two have a common prefix but str is longer. · zero if the two compare equal, element by element, and are the same length. ·

int compare(size_type p0, size_type n0, const string& str);

a positive value otherwise.

Compares up to n0 elements of the controlled sequence, beginning with position p0, to the sequence specified by str. The function returns: · a negative value if the first differing element in the controlled sequence compares less than the corresponding element in str, or if the two have a common prefix but str is longer. · zero if the two compare equal, element by element, and are the same length. ·

int compare(size_type p0, size_type n0, const string& str, size_type pos, size_type n);

a positive value otherwise.

compares up to n0 elements of the controlled sequence beginning with position p0, to n elements of str beginning with position pos. The function returns: · a negative value if the first differing element in the controlled sequence compares less than the corresponding element in str, or

if the two have a common prefix but str is longer. · zero if the two compare equal, element by element, and are the same length. · int compare(const char *s) const;

a positive value otherwise.

Compares elements of the controlled sequence, if these arguments are not supplied, to the sequence specified by *s. The function returns: · a negative value if the first differing element in the controlled sequence compares less than the corresponding element in *s , or if the two have a common prefix but *s is longer. · zero if the two compare equal, element by element, and are the same length. ·

int compare(size_type p0, size_type n0, const char *s);

a positive value otherwise.

Compares up to n0 elements of the controlled sequence, beginning with position p0, to the sequence specified by *s. The function returns: · a negative value if the first differing element in the controlled sequence compares less than the corresponding element in *s , or if the two have a common prefix but *s is longer. · zero if the two compare equal, element by element, and are the same length. ·

int compare(size_type p0, size_type n0, const char *s, size_type pos, size_type n);

a positive value otherwise.

Compares up to n0 elements of the controlled sequence beginning with position p0, to n elements of *s beginning with position pos. The function returns:

· a negative value if the first differing element in the controlled sequence compares less than the corresponding element in *s , or if the two have a common prefix but *s is longer. · zero if the two compare equal element by element and are the same length. ·

a positive value otherwise.

size_type copy(char *s, size_type n, size_type pos = 0) const;

Copies up to n elements from the controlled sequence, beginning at position pos, to the array of char beginning at *s. It returns the number of elements actually copied.

const E *data() const;

The member function returns a pointer to the first element of the sequence (or, for an empty sequence, a non-null pointer that cannot be dereferenced).

bool empty() const;

The member function returns true for an empty controlled sequence.

const_iterator end() const; iterator end();

The member functions each return a randomaccess iterator that points just beyond the end of the sequence.

iterator erase(iterator first, iterator last); Removes the elements of the controlled sequence in the range [first, last). Returns an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists. iterator erase(iterator it);

Removes the element of the controlled sequence pointed to by it. Return an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists.

string& erase(size_type p0 = 0, size_type n = npos);

Removes up to n elements of the controlled sequence beginning at position p0, then returns *this.

size_type find(char c, size_type pos = 0) const;

Finds the first character in the controlled sequence, beginning on or after position pos, that matches the character specified by c. If

it succeeds, it returns the position where the matching character was found. Otherwise, the function returns npos. size_type find(const char *s, size_type pos = 0) const;

Finds the first subsequence in the controlled sequence, beginning on or after position pos, that matches the sequence specified by *s. If it succeeds, it returns the position where the matching subsequence begins. Otherwise, the function returns npos.

size_type find(const char *s, size_type pos, size_type n) const;

Finds the first subsequence in the controlled sequence, beginning on or after position pos, that matches the first n characters of sequence *s. If it succeeds, it returns the position where the matching subsequence begins. Otherwise, the function returns npos.

size_type find(const string& str, size_type pos = 0) const;

Finds the first subsequence in the controlled sequence, beginning on or after position pos, that matches the sequence specified by str. If it succeeds, it returns the position where the matching subsequence begins. Otherwise, the function returns npos.

size_type find_first_not_of(char c, size_type pos = 0) const;

Finds the first (lowest position) element of the controlled sequence, at or after position pos, that does not match with the character c. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_first_not_of(const char *s, size_type pos = 0) const;

Finds the first (lowest position) element of the controlled sequence, at or after position pos, that matches none of the elements in the sequence specified by *s. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_first_not_of(const char *s, size_type pos, size_type n) const;

Finds the first (lowest position) element of the controlled sequence, at or after position pos, that matches none of the elements in the sequence specified by the first n characters of *s. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_first_not_of (const string& str,

Finds the first (lowest position) element of the controlled sequence, at or after position

size_type pos = 0) const;

pos, that matches none of the elements in the sequence specified by str. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_first_of(char c, size_type pos = 0) const;

Finds the first (lowest position) element of the controlled sequence, at or after position pos, that does matches with the character c. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_first_of(const char *s, size_type pos = 0) const;

Finds the first (lowest position) element of the controlled sequence, at or after position pos, that matches any of the elements in the sequence specified by *s. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_first_of(const char *s, size_type pos, size_type n) const;

Finds the first (lowest position) element of the controlled sequence, at or after position pos, that matches any of the elements in the sequence specified by the first n characters of *s. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_first_of (const string& str, size_type pos = 0) const;

Finds the first (lowest position) element of the controlled sequence, at or after position pos, that matches any of the elements in the sequence specified by str. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_last_not_of(char c, size_type pos = 0) const;

Finds the last (highest position) element of the controlled sequence, at or after position pos, that does not match with the character c. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_last_not_of(const char *s, size_type pos = 0) const;

Finds the last (highest position) element of the controlled sequence, at or after position pos, that matches none of the elements in the sequence specified by *s. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_last_not_of(const char *s, size_type pos,

Finds the last (highest position) element of the controlled sequence, at or after position

size_type n) const;

pos, that matches none of the elements in the sequence specified by last n characters of *s. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_last_not_of (const string& str, size_type pos = 0) const;

Finds the last (highest position) element of the controlled sequence, at or after position pos, that matches none of the elements in the sequence specified by str. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_last_of(char c, size_type pos = 0) const;

Finds the last (highest position) element of the controlled sequence, at or after position pos, that does matches with the character c. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_last_of(const char *s, size_type pos = 0) const;

Finds the last (highest position) element of the controlled sequence, at or after position pos, that matches any of the elements in the sequence specified by *s. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_last_of(const char *s, size_type pos, size_type n) const;

Finds the last (highest position) element of the controlled sequence, at or after position pos, that matches any of the elements in the sequence specified by the last n characters of *s. If it succeeds, it returns the position. Otherwise, the function returns npos.

size_type find_last_of (const string& str, size_type pos = 0) const;

Finds the last (highest position) element of the controlled sequence, at or after position pos, that matches any of the elements in the sequence specified by str. If it succeeds, it returns the position. Otherwise, the function returns npos.

string& insert(size_type p0, const char *s);

Inserts, after position p0 or after the element it points to in the controlled sequence, the sequence specified by *s. It returns *this.

string& insert(size_type p0, const char *s, size_type n);

Inserts, after position p0 or after the element it points to in the controlled sequence, the first n characters of the sequence specified by *s. It returns *this.

string& insert(size_type p0, const string& str, size_type pos, size_type n);

Inserts, after position p0 or after the element itpoints to in the controlled sequence, n characters of the sequence specified by str, beginning at position pos. It returns *this.

string& insert(size_type p0, const string& str);

Inserts, after position p0 or after the element it points to in the controlled sequence, the sequence specified by str It returns *this.

string& insert(size_type p0, size_type n, char c);

Inserts, after position p0 or after the element it points to in the controlled sequence, n copies of character c. It returns *this.

void insert(iterator it, const_iterator first, const_iterator last);

Inserts, after position it in the controlled sequence, the sequence specified by [first, last).

iterator insert(iterator it, char c);

Inserts, after position it in the controlled sequence, the character specified by c.

void insert(iterator it, size_type n, char c);

Inserts, after position it in the controlled sequence, n copies of the character specified by c.

size_type length() const;

Returns the length of the controlled sequence (same as size()).

size_type max_size() const;

Returns the length of the longest sequence that the object can control.

string& operator+=(const char *s);

Appends the sequence specified by *s to the end of the sequence controlled by *this, then returns *this.

string& operator+=(const string& str);

Appends the sequence specified by str to the end of the sequence controlled by *this, then returns *this.

string& operator+=(char c);

Appends the character specified by c to the end of the sequence controlled by *this, then returns *this.

string& operator=(const char *s);

Replaces the sequence specified by *s to the end of the sequence controlled by *this, then returns *this.

string& operator=(const string& str);

Replaces the sequence specified by str to the end of the sequence controlled by *this, then returns *this.

string& operator=(char c);

Replaces the character specified by c to the end of the sequence controlled by *this, then returns *this.

const_reference operator[] (size_type pos) const; reference operator[](size_type pos);

Returns a reference to the element of the controlled sequence at position pos. If that position is invalid, the behavior is undefined.

const_reverse_iterator rbegin() const; reverse_iterator rbegin();

Returns a reverse iterator that points just beyond the end of the controlled sequence. Hence, it designates the beginning of the reverse sequence.

const_reverse_iterator rend() const; reverse_iterator rend();

Returns a reverse iterator that points at the first element of the sequence (or just beyond the end of an empty sequence). Hence, it designates the end of the reverse sequence.

string& replace(size_type p0, size_type n0, const char *s);

Replaces up to n0 elements of the controlled sequence beginning with position p0. The replacement is the sequence specified by *s. The function then returns *this.

string& replace(size_type p0, size_type n0, const char *s, size_type n);

Replaces up to n0 elements of the controlled sequence beginning with position p0. The replacement is the first n specified by *s. The function then returns *this.

string& replace(size_type p0, size_type n0, const string& str);

Replaces up to n0 elements of the controlled sequence beginning with position p0. The replacement is the first n characters of str. The function then returns *this.

string& replace(size_type p0, size_type n0, const string& str, size_type pos, size_type n);

Replaces up to n0 elements of the controlled sequence beginning with position p0. The replacement is n characters of str, beginning at position pos. The function then returns *this.

string& replace(size_type p0, size_type n0, size_type n, char c);

Replaces up to n0 elements of the controlled sequence beginning with position p0. The replacement is n copies of character c. The function then returns *this.

string& replace(iterator first0, iterator last0, const char *s);

Replaces the elements of the controlled sequence beginning with the one pointed to by first0, up to but not including last0. The replacement is the sequence specified by *s.

The function then returns *this. string& replace(iterator first0, iterator last0, const char *s, size_type n);

Replaces the elements of the controlled sequence beginning with the one pointed to by first0, up to but not including last0. The replacement is first n characters of the sequence specified by *s. The function then returns *this.

string& replace(iterator first0, iterator last0, const string& str);

Replaces the elements of the controlled sequence beginning with the one pointed to by first0, up to but not including last0. The replacement is the sequence specified by str. The function then returns *this.

string& replace(iterator first0, iterator last0, size_type n, char c);

Replaces the elements of the controlled sequence beginning with the one pointed to by first0, up to but not including last0. The replacement is n copies of the character c. The function then returns *this.

string& replace(iterator first0, iterator last0, const_iterator first, const_iterator last);

Replaces the elements of the controlled sequence beginning with the one pointed to by first0, up to but not including last0. The replacement is the elements of the sequence beginning with the one pointed to by first, up to but not including last. The function then returns *this.

void reserve(size_type n);

The member function ensures that capacity() henceforth returns at least n.

void resize(size_type n, char c = char());

The member function ensures that size() henceforth returns n. If it must make the controlled sequence longer, it appends elements with value c.

size_type rfind(char c, size_type pos = 0) const;

Finds the last character in the controlled sequence, beginning on or after position pos, that matches the character specified by c. If it succeeds, it returns the position where the matching character was found. Otherwise, the function returns npos.

size_type rfind(const char *s, size_type pos = 0) const;

Finds the last subsequence in the controlled sequence, beginning on or after position pos, that matches the sequence specified by *s. If it succeeds, it returns the position where the

matching subsequence begins. Otherwise, the function returns npos. size_type rfind(const char *s, size_type pos, size_type n) const;

Finds the last subsequence in the controlled sequence, beginning on or after position pos, that matches the first n characters of sequence *s. If it succeeds, it returns the position where the matching subsequence begins. Otherwise, the function returns npos.

size_type rfind(const string& str, size_type pos = 0) const;

Finds the last subsequence in the controlled sequence, beginning on or after position pos, that matches the sequence specified by str. If it succeeds, it returns the position where the matching subsequence begins. Otherwise, the function returns npos.

size_type size() const;

Returns the length of the controlled sequence.

string substr(size_type pos = 0, size_type n = npos) const;

Returns an object whose controlled sequence is a copy of up to n elements of the controlled sequence beginning at position pos.

void swap(string& str);

Swaps the controlled sequences between *this and str.

string()

Constructs an empty string.

string(char* s)

Constructs a string from the sequence specified by *s.

string(const string& str size_t pos, size_t n)

Constructs a string from n characters of the sequence specified by str, beginning at position pos.

string(const char* s, size_t n)

Constructs a string from n characters of the sequence specified by *s.

string(const string& str)

Constructs a string from the sequence specified by str.

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 //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:

private:

Matrix(int, int) ; //… int operator(int, int) const ; Array 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 . Table 12. STL Function Objects divides

logical_and

equal_to

logical_not

greater

logical_or

greater_equal

minus

less

modulus

less_equal

negate

plus

not_equal_to

times

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 as demonstrated in the following example: #include #include #include #include void main() { typedef vector > VECTOR_INT ; typedef ostream_iterator > 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()) ; 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())(10, 20) ; // sets n1 to value 200 int n2 = (minus())(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 and binder2nd. 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, and bind2nd returns a function object of type binder2nd. Here are the function prototypes for the bind1st and bind2nd functions: template binder1st bind1st(const Operation& f, const T& x) ; template binder2nd bind2nd(const Operation& f, const T& x) ;

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

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

Assume i is an integer. You can rewrite the above expression as follows: int result = (greater())(i, 200)

The expression "bind2nd(greater(), 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 f ; // b is a unary function object; it returns true if its argument is > 200. binder2nd< greater > 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(), 200)"? Consider the following example: int a1[1000] ; //code to initialize a1 … int* where = find_if(a1, a1+1000, bind2nd(greater(), 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())(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 and binary_negate. 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. The function not2 takes a binary function object f as its argument and returns a function object of type binary_negate. Here are the function prototypes for the not1 and not2 functions: template unary_negate not1(const Operation& f) ; template binary_negate 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(), 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())) ;

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 and pointer_to_binary_function. 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. 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. Here are the function prototypes for the ptr_fun functions:

template inline pointer_to_unary_function ptr_fun(Result (*F)(Arg)) template inline pointer_to_binary_function 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 #include #include #include // 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 > 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(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);

• • •

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

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

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: , , .

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 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 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 #include #include #include

<list> <string>

void main() { typedef list<string, allocator<string> > STRINGLIST ; typedef STRINGLIST::iterator STRINGLIST_ITERATOR ; typedef ostream_iterator<string, char, char_traits > 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 void sort(RandomAccessIterator first_, RandomAccessIterator last_) ; template 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 #include #include #include



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 > VECTOR_INT ; typedef ostream_iterator > 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()) ; 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 void distance(InIt first, InIt last, Dist&n);

However, it actually takes two parameters and returns a value, as follows: template Dist distance(InIt first, InIt last)

12.3 Using the distance() Function The following example demonstrates the distance() function: #include #include

#include #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 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 Member function

Description

has_denorm

Stores true for a floating-point type that has denormalized values (effectively a variable number of exponent bits).

has_denorm_loss

Stores true for a type that determines whether a value has lost accuracy because it is delivered as a denormalized result (too small to represent as a normalized value) or because it is inexact (not the same as a result and not subject to limitations of exponent range and precision).

has_infinity

The member stores true for a type that has a representation for positive infinity. True if is_iec559 is true.

has_quiet_NaN

Stores true for a type that has a representation for a quiet NaN, an encoding that is "Not a Number'' which does not signal its presence in an expression. True if is_iec559 is true.

has_signaling_NaN

The member stores true for a type that has a representation for a signaling NaN, an encoding that is ``Not a Number'' which signals its presence in an expression by reporting an exception. True if is_iec559 is true.

is_bounded

Stores true for a type that has a bounded set of representable values (which is the case for all predefined types).

is_exact

Stores true for a type that has exact representations for all its values (which is the case for all predefined integer types). A fixed-point or rational representation is also considered exact, but not a floating-point representation.

is_iec559

Stores true for a type that has a representation conforming to IEC 559, an international standard for representing floating-point values (also known as IEEE 754 in the USA).

is_integer

Stores true for a type that has an integer representation.

is_modulo

Stores true for a type that has a modulo representation, where all results are reduced modulo some value.

is_signed

Stores true for a type that has a signed representation (which is the case for all predefined floating-point and signed integer types).

is_specialized

Stores true for a type that has an explicit specialization defined for template class numeric_limits.

tinyness_before

Stores true for a type that determines whether a value is ``tiny'' (too small to represent as a normalized value) before rounding.

traps

Stores true for a type that generates some kind of signal to report

certain arithmetic exceptions. round_style

Stores a value that describes the various methods that an implementation can choose for rounding a floating-point value to an integer value. The round styles are: enum float_round_style { round_indeterminate = -1, round_toward_zero = 0, round_to_nearest = 1, round_toward_infinity = 2, round_toward_neg_infinity = 3

digits

The member stores the number of radix digits that the type can represent without change (which is the number of bits other than any sign bit for a predefined integer type, or the number of mantissa digits for a predefined floating-point type).

digits10

Stores the number of decimal digits that the type can represent without change.

max_exponent

The member stores the maximum positive integer that the type can represent as a finite value radix raised to that power (which is the value FLT_MAX_EXP for type float). Meaningful only for floating-point types.

max_exponent10

The member stores the maximum positive integer that the type can represent as a finite value 10 raised to that power (which is the value FLT_MAX_10_EXP for type float). Meaningful only for floating-point types.

min_exponent

The member stores the minimum negative integer that the type can represent as a normalized value radix raised to that power (which is the value FLT_MIN_EXP for type float). Meaningful only for floating-point types.

min_exponent10

The member stores the minimum negative integer that the type can represent as a normalized value 10 raised to that power (which is the value FLT_MIN_10_EXP for type float). Meaningful only for floating-point types.

radix;

The member stores the base of the representation for the type (which is 2 for the predefined integer types), and the base to which the exponent is raised(which is FLT_RADIX for the predefined floating-point types).

denorm_min()

The function returns the minimum value for the type (which is the same as min() if has_denorm is False).

epsilon()

The function returns the difference between 1 and the smallest value greater than 1 that is representable for the type (which is the value FLT_EPSILON for type float).

infinity()

The function returns the representation of positive infinity for the type. The return value is meaningful only if has_infinity is true.

max()

The function returns the maximum finite value for the type (which is INT_MAX for type int and FLT_MAX for type float). The return value is meaningful if is_bounded is true.

min()

The function returns the minimum normalized value for the type (which is INT_MIN for type int and FLT_MIN for type float). The return value is meaningful if is_bounded is true or is_signed is False.

quiet_ Nan()

The function returns a representation of a quiet NaN for the type. The return value is meaningful only if has_quiet_NaN is true.

round_error()

The function returns the maximum rounding error for the type.

Signaling_Nan()

The function returns a representation of a signaling NaN for the type. The return value is meaningful only if has_signaling_NaN is true.

12.6 Using the numeric_limits Class Member Functions The following example demonstrates the numeric_limits class member functions: #include #include void main() { cout << " 1 The minimum value for char is " << (int)numeric_limits::min() << endl; cout << " 2 The minimum value for int is " << numeric_limits::min() << endl; cout << " 3 The maximum value for char is " << (int)numeric_limits::max() << endl; cout << " 4 The maximum value for int is " << numeric_limits::max() << endl; cout << " 5 The number of bits to represent a char is " << numeric_limits::digits << endl; cout << " 6 The number of bits to represent an int is " << numeric_limits::digits << endl; cout <<" 7 The number of digits representble in base 10 for float is" << numeric_limits::digits10 << endl; cout << " 8 Is a char signed? " << numeric_limits::is_signed << endl; cout << " 9 Is an unsigned integer signed? " <<

numeric_limits::is_signed << endl; cout << "10 Is a integer an integer? " << numeric_limits::is_integer << endl; cout << "11 Is a float an integer? " << numeric_limits::is_integer << endl; cout << "12 Is a integer exact? " << numeric_limits::is_exact << endl; cout << "13 Is a float exact? " << numeric_limits::is_exact << endl; cout << "14 The radix for float is " << numeric_limits::radix << endl; cout << "15 The epsilon for float is " << numeric_limits::epsilon() << endl; cout << "16 The round error for float is " << numeric_limits::round_error() << endl; cout << "17 The minimum exponent for float is " << numeric_limits::min_exponent << endl; cout << "18 The minimum exponent in base 10 " << numeric_limits::min_exponent10 << endl; cout << "19 The maximum exponent is " << numeric_limits::max_exponent << endl; cout << "20 The maximum exponent in base 10 " << numeric_limits::max_exponent10 << endl; cout << "21 Can float represent positive infinity? " << numeric_limits::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::has_infinity << endl; cout << "24 Can float represent a NaN? " << numeric_limits::has_quiet_NaN << endl; cout << "25 Can float represent a signaling NaN? " << numeric_limits::has_signaling_NaN << endl; cout << "26 Does float allow denormalized values? " << numeric_limits::has_denorm << endl; cout << "27 Does float detect denormalization loss? " << numeric_limits::has_denorm_loss << endl; cout << "28 Representation of positive infinity for float numeric_limits::infinity() << endl; cout << "29 Representation of quiet NaN for float numeric_limits::quiet_NaN() << endl; cout << "30 Minimum denormalized number for float numeric_limits::denorm_min() << endl; cout << "31 Minimum positive denormalized value for float numeric_limits::denorm_min() << endl; cout << "32 Does float adhere to IEC 559 standard? " << numeric_limits::is_iec559 << endl; cout << "33 Is float bounded? " << numeric_limits::is_bounded << endl; cout << "34 Is float modulo? " << numeric_limits::is_modulo << endl; cout << "35 Is int modulo? " << numeric_limits::is_modulo << endl; cout << "36 Is trapping implemented for float? " << numeric_limits::traps << endl; cout << "37 Is tinyness detected before rounding? " << numeric_limits::tinyness_before << endl;

" << " << " << " <<

cout << "38 What is the rounding style for float? " << (int)numeric_limits::round_style << endl; cout << "39 What is the rounding style for int? " << (int)numeric_limits::round_style << endl; }

Output: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

The minimum value for char is -128 The minimum value for int is -2147483648 The maximum value for char is 127 The maximum value for int is 2147483647 The number of bits to represent a char is 7 The number of bits to represent an int is 31 The number of digits representable in base 10 for float is 6 Is a char signed? 1 Is an unsigned integer signed? 0 Is a integer an integer? 1 Is a float an integer? 0 Is a integer exact? 1 Is a float exact? 0 The radix for float is 2 The epsilon for float is 1.19209e-007 The round error for float is 0.5 The minimum exponent for float is -125 The minimum exponent in base 10 -37 The maximum exponent is 128 The maximum exponent in base 10 38 Can float represent positive infinity? 1 Can double represent positive infinity? 1 Can int represent positive infinity? 0 Can float represent a NaN? 1 Can float represent a signaling NaN? 1 Does float allow denormalized values? 1 Does float detect denormalization loss? 1 Representation of positive infinity for float 1.#INF Representation of quiet NaN for float -1.#IND Minimum denormalized number for float 1.4013e-045 Minimum positive denormalized value for float 1.4013e-045 Does float adhere to IEC 559 standard? 1 Is float bounded? 1 Is float modulo? 0 Is int modulo? 0 Is trapping implemented for float? 1 Is tinyness detected before rounding? 1 What is the rounding style for float? 1 What is the rounding style for int? 0

Additional values defined from the and header files which include and float.h, respectively, are: CHAR_BIT UCHAR_MAX CHAR_MAX UINT_MAX

INT_MAX INT_MIN

LONG_MIN MB_LEN_MAX

SCHAR_MIN SHRT_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 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 . Table 14 lists the functions specified. Table 14. Functions Specified in cstdlib Function

Description

void abort( void );

Aborts the current process and returns an error code.

int atexit( void ( __cdecl *func ) ( void ) );

Processes the specified function at exit.

void exit( int status );

Terminate the calling process after cleanup (exit) or immediately (_exit).

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 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 void void void

*operator *operator *operator *operator

new(size_t n, const nothrow&) throw(); new(size_t n, void *p) throw(); new[](size_t n, const nothrow&) throw(); 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 #include 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 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 // No Errors. #include #include // No errors - returns #include #include // No errors - returns #include #include // Throws an exception #include // Throws an exception

a NULL. a NULL. instead of returning NULL. 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 #include // No Errors. #include #include // No Errors. #include // No Errors. #include //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 #include // 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 #include // 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 //C:\MSDEV\Projects\defcon\Text5.cpp(47) : error C2061: syntax error : identifier 'bad_alloc'

//C:\MSDEV\Projects\defcon\Text5.cpp(47) : error must specify one type //C:\MSDEV\Projects\defcon\Text5.cpp(48) : error undeclared identifier //C:\MSDEV\Projects\defcon\Text5.cpp(48) : error must hav class/struct/union type //C:\MSDEV\Projects\defcon\Text5.cpp(52) : error starting on line '44' has no catch handlers //C:\MSDEV\Projects\defcon\Text5.cpp(52) : error undeclared identifier //C:\MSDEV\Projects\defcon\Text5.cpp(52) : error function does not take 2 parameters

C2310: catch handlers C2065: 'a' : C2228: left of '.what' C2317: 'try' block C2065: 'nothrow' : C2660: 'new' :

12.9 Type Identification: typeinfo The 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: csetjmp Macro:

va_arg Types: setjmp Types: Function:

va_end va_start va_list

ctime Macros: Types: Functions:

jmp_buf longjmp

CLOCKS_PER_SEC clock_t clock

csignal Macros: SIG_IGN Types: Functions:

SIGABRT SIGILL SIGFPE SIGINT sig_atomic_t raise signal

SIGSEGV SIGTERM

SIG_DFL SIG_ERR

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 ctorinitializer // 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); void (*fp)() throw (int); void g(void pfa() throw(int)); typedef int (*pf)() throw(int);

// // // //

OK OK OK 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 illformed. 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 typeid-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(); if (n) throw Z(); throw W();

// OK // also OK // 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 illformed. 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: Exception classes <stdexcept> Assertions



Error numbers



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 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 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:: 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 template class Vector { T* pT; int sz; public: Vector (int s=1); ~Vector(); class ExceptionRange {}; T& operator [] (int i);

//Exception class

int size () const { return sz;} }; template inline Vector::Vector(int s) { pT = new T[sz=s];} template inline Vector::~Vector() { delete [] pT;} void range_error (Vector & v) { v[v.size()+10]; // trigger range error }

template T& Vector::operator [] (int i) { if (0<=i && i <sz) return pT[i]; throw ExceptionRange (); return pT[0]; } void Do_Vector (Vector& v) { range_error(v); } void main (void) { Vector v(10); try { Do_Vector (v); } // Catch (Vector::ExceptionRange) catch (Vector ::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 errorproducing 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 #include template class MyVector : public vector > { public: typedef allocator A; explicit MyVector(const A& al = A()) : vector(al) {}; explicit MyVector(size_type n, const T& v = T(), const A& al = A()) : vector(n, v, al) {} MyVector(const MyVector& x) : vector(x) {} MyVector(const_iterator first, const_iterator last, const A& al = A()) : vector(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 #include "MyVector.h" void main()

{ MyVector intVect; MyVector::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 ::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. Header Type

Name(s)

Macro

assert

The contents are the same as the Standard C library. 14.4.3 Error numbers Header

:

Type

Name(s)

Macros

EDOM ERANGE errno

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 #include //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 Domain Error: : sqrt(-1,-3.10504e+231) returns -1.#IND Floating point math error occurred in your program. More Singularity Error:: log(0,-3.10504e+231) returns -1.#INF Floating point math error occurred in your program. More Total loss of significance:: sin(1.5e+025,-3.10504e+231) Floating point math error occurred in your program. More Total loss of significance:: tan(1.5e+025,-3.10504e+231) Floating point math error occurred in your program. More Domain Error: : acos(2,-3.10504e+231) returns -1.#IND

details below: details below: details returns details returns details

below: -1.#IND below: -1.#IND below:

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 deque { public: typedef deque 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 { public: friend class deque; 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 reverse_iterator; typedef reverse_bidirectional_iterator 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 inline bool operator==(const deque& X, const deque& Y); template inline bool operator<(const deque& X, const deque& 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 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 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 { 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 reverse_iterator; typedef reverse_bidirectional_iterator 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 > Pr1; void remove_if(Pr1 Pr) void unique() typedef not_equal_to Pr2;

void unique(Pr2 Pr) void merge(Myt& X) typedef greater 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 inline bool operator==(const list& X, const list& Y) template inline bool operator<(const list& X, const list& 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). The template parameter A represents the allocator object the map will use for memory allocation.

// TEMPLATE CLASS map template class map { public: typedef map Myt; typedef pair value_type; struct Kfn : public unary_function { const K& operator()(const value_type& X) const }; class value_compare : public binary_function { friend class map; 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 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 Pairib; typedef pair Pairii; typedef pair 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 inline bool operator==(const map& X,

const map& Y) template inline bool operator<(const map& X, const map& Y) // TEMPLATE CLASS multimap template class multimap { public: typedef multimap Myt; typedef pair value_type; struct Kfn : public unary_function { const K& operator()(const value_type& X) const }; class value_compare : public binary_function { 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 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 Pairii; typedef pair 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 inline bool operator==(const multimap& X, const multimap& Y) template inline bool operator<(const multimap& X, const multimap& 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). The template parameter A represents the allocator object the set will use for memory allocation.

// TEMPLATE CLASS set template class set { public: typedef set Myt; typedef K TYPE; typedef TYPE value_type; struct Kfn : public unary_function { 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 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 Pairib; typedef pair 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 inline bool operator==(const set& X, const set& Y) template inline bool operator<(const set& X, const set& Y) // TEMPLATE CLASS multiset template class multiset { public: typedef multiset Myt; typedef K TYPE; typedef TYPE value_type; struct Kfn : public unary_function { 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 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 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 inline bool operator==(const multiset& X, const multiset& Y) template inline bool operator<(const multiset& X, const multiset& 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 vector { public: typedef vector 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_reverse_iterator; typedef reverse_iterator 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 inline bool operator==(const vector& X, const vector& Y); template inline bool operator<(const vector& X, const vector& 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 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& X) const; bool operator<(const stack& 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). The template parameter A represents the allocator object the priority_queue will use for memory allocation (for example, allocator).

// TEMPLATE CLASS priority_queue template 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 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& X) const; bool operator<(const queue& 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 Member

Description

typedef A allocator_type

deque::allocator_type describes the stored allocator object (same as the second template argument).

void assign(const_iterator first,const_iterator . . . last)void assign(size_type n, const T& x = T())

The first version of deque::assign replaces the sequence controlled by *this with the sequence [first, last). The second version replaces the sequence controlled by *this with a repetition of n elements of value x.

const_reference at(size_type pos) constreference . . . at(size_type pos)

deque::at returns a reference to the element of the deque at position pos. If that position is invalid, the function throws an object of class out_of_range (throws an exception).

reference back() const_reference back() const

deque::back returns a reference to the last element of the deque, which must be nonempty.

const_iterator begin() const iterator begin()

deque::begin returns a random-access iterator that points at the first element of the sequence (or just beyond the end of an empty sequence).

void clear() const

deque::clear calls erase( begin(), end()).

typedef A::const_iterator const_iterator

deque::const_iterator describes an object that can serve as a constant random-access iterator for the deque. It is described here as a synonym for the const_iterator member of the allocator object.

Typedef A::const_reference const_reference

deque::const_reference describes an object that can serve as a constant reference to an element of the deque.

typedef reverse_iterator const_reverse_iterator

deque::const_reverse_iterator describes an object that can serve as a constant reverse iterator for the deque.

explicit deque(const A& al = A()) explicit deque(size_type n, const T& v = T(), const A& al = A()) deque(const deque& x) deque(const_iterator first, const_iterator last, const A& al = A())

All constructors store the allocator object al (or, for the copy constructor, x.get_allocator()) in allocator and initialize the controlled sequence. The first constructor specifies an empty initial controlled sequence. The second constructor specifies a repetition of n elements of value x. The third constructor specifies a copy of the sequence controlled by x. The last constructor specifies the sequence[first, last).

typedef A::difference_type difference_type

deque::difference_type is a signed integer type that describes an object that can represent the difference between the addresses of any two elements in the deque.

bool empty() const

deque::empty returns true if the deque is empty.

const_iterator end() const iterator end()

deque::end returns a random-access iterator that points just beyond the end of the sequence.

iterator erase(iterator it) iterator erase(iterator first, iterator last)

The first version of deque::erase removes the element of the controlled sequence pointed to by it. The second version removes the elements of the controlled sequence in the range [first, last). Both return an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists. Erasing N elements causes N destructor calls and an assignment (operator=) for each of the elements between the insertion point and the nearer end of the sequence. Removing an element at either end invalidates only iterators and references that designate the

erased elements. Otherwise, erasing an element invalidates all iterators and references. reference front() const_reference front() const

deque::front returns a reference to the first element of the controlled sequence, which must be nonempty.

A get_allocator() const

The member function returns allocator.

iterator insert(iterator it, const T& x = T()) void insert(iterator it, size_type n, const T& x) void insert(iterator it, const_iterator first, const_iterator last)

Each version of deque::insert inserts, after the element pointed to by it in the controlled sequence, a sequence specified by the remaining operands. The first version inserts a single element with value x> and returns an iterator that points to the newly inserted element. The second version inserts a repetition of n elements of value x. The third version inserts the sequence [first, last). When inserting a single element, the number of element copies is linear in the number of elements between the insertion point and the nearer end of the sequence. When inserting a single element at either end of the sequence, the amortized number of element copies is constant. When inserting N elements, the number of element copies is linear in N plus the number of elements between the insertion point and the nearer end of the sequence. Inserting an element at either end invalidates all iterators, but no references, that designate existing elements. Otherwise, inserting an element invalidates all iterators and references.

typedef A::pointer iterator

Iterator describes an object that can serve as a random-access iterator for the controlled sequence. It is described here as a synonym for the pointer member of the allocator object.

size_type max_size() const

deque::max_size returns the length of the longest sequence that the object can control.

const_reference operator[](size_type pos) operator[] returns a reference to the element const of the controlled sequence at position pos. If reference operator[](size_type pos) that position is invalid, the behavior is

undefined. void pop_back()

deque::pop_back removes the last element of the controlled sequence, which must be nonempty. Removing the element invalidates only iterators and references that designate the erased element.

void pop_front()

deque::pop_front removes the first element of the controlled sequence, which must be nonempty. Removing the element invalidates only iterators and references that designate the erased element.

void push_back(const T& x)

deque::push_back inserts an element with value x at the end of the controlled sequence. Inserting the element invalidates all iterators, but no references, to existing elements.

void push_front(const T& x)

deque::push_front inserts an element with value x at the beginning of the controlled sequence. Inserting the element invalidates all iterators, but no references, to existing elements.

const_reverse_iterator rbegin() const reverse_iterator rbegin()

deque::rbegin returns a reverse iterator that points just beyond the end of the controlled sequence. Hence, it designates the beginning of the reverse sequence.

typedef A::reference reference

deque::reference describes an object that can be used as a reference to an element of the controlled sequence. It is described here as a synonym for the reference member of the allocator object.

const_reverse_iterator rend() const reverse_iterator rend()

deque::rend returns a reverse iterator that points at the first element of the sequence (or just beyond the end of an empty sequence). Hence, it designates the end of the reverse sequence.

void resize(size_type n, T x = T())

deque::resize ensures that size() henceforth returns n. If it must make the controlled sequence longer, it appends elements with value x.

typedef reverse_iterator
The type describes an object that can serve

value_type, reference, A::types::pointer, difference_type> reverse_iterator

as a reverse iterator for the controlled sequence.

size_type size() const

deque::size returns the length of the controlled sequence.

typedef A::size_type size_type

size_type is an unsigned integer type that describes an object that can represent the length of any controlled sequence.

void swap(deque& str)

deque::swap swaps the controlled sequences between *this and str. If allocator == str.allocator, it does so in constant time. Otherwise, it performs a number of element assignments and constructor calls proportional to the number of elements in the two controlled sequences.

typedef A::types::value_type value_type

The type describes an element of the controlled sequence (same as the template parameter T).

17.2 list Member

Description

typedef A allocator_type

list::allocator_type describes the stored allocator object (same as the second template argument).

void assign(const_iterator first,const_iterator The first version of list::assign replaces last) the sequence controlled by *this with the void assign(size_type n, const T& x = T()) sequence [first, last). The second version replaces the sequence controlled by *this with a repetition of n elements of value x. reference back() const_reference back() const

list::back returns a reference to the last element of the list, which must be nonempty.

const_iterator begin() const iterator begin()

list::begin returns a random-access iterator that points at the first element of the sequence (or just beyond the end of an empty sequence).

void clear() const

list::clear calls erase( begin(), end()).

typedef A::const_iterator const_iterator

list::const_iterator describes an object that can serve as a constant randomaccess iterator for the list. It is described here as a synonym for the const_iterator member of the allocator object.

typedef A::const_reference const_reference

list::const_reference describes an object that can serve as a constant reference to an element of the list.

typedef reverse_iterator const_reverse_iterator

list::const_reverse_iterator describes an object that can serve as a constant reverse iterator for the list.

typedef A::difference_type difference_type

list::difference_type is a signed integer type that describes an object that can represent the difference between the addresses of any two elements in the list.

bool empty() const

list::empty returns true if the list is empty

const_iterator end() const iterator end()

list::end returns a random-access iterator that points just beyond the end of the sequence.

iterator erase(iterator it) iterator erase(iterator first, iterator last)

The first version of list::erase removes the element of the controlled sequence pointed to by it. The second version removes the elements of the controlled sequence in the range [first, last). Both return an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists. Erasing N elements causes N destructor calls. No reallocation occurs, so iterators and references become invalid only for the erased elements.

reference front() const_reference front() const

list::front returns a reference to the first element of the controlled sequence, which must be nonempty.

A get_allocator() const

The member function returns allocator.

iterator insert(iterator it, const T& x = T()) void insert(iterator it, size_type n,const T& x) void insert(iterator it, const_iterator first, const_iterator last)

Each version of list::insert inserts, after the element pointed to by it in the controlled sequence, a sequence specified by the remaining operands. The first version inserts a single element with value x> and returns an iterator that points to the newly inserted element. The second version inserts a repetition of n elements of value x. The third version inserts the sequence [first, last). Inserting N elements causes N copies. No reallocation occurs, so no iterators or references become invalid.

typedef A::pointer iterator

Iterator describes an object that can serve as a random-access iterator for the controlled sequence. It is described here as a synonym for the pointer member of the allocator object.

explicit list(const A& al = A()) explicit list(size_type n, const T& v = T(), const A& al = A()) list(const list& x) list(const_iterator first, const_iterator last, const A& al = A())

All constructors store the allocator object al (or, for the copy constructor, x.get_allocator()) in allocator and initialize the controlled sequence. The first constructor specifies an empty initial controlled sequence. The second constructor specifies a repetition of n elements of value x. The third constructor specifies a copy of the sequence controlled by x. The last constructor specifies the sequence [first, last). None of the constructors perform any interim reallocations.

size_type max_size() const

list::max_size returns the length of the longest sequence that the object can control.

void merge(list& x) void merge(list& x, greater pr)

Both versions of list::merge remove all elements from the sequence controlled by x and insert them in the controlled sequence. Both sequences must be ordered by the same predicate, described below. The resulting sequence is also ordered by that predicate. For the iterators Pi and Pj designating elements at positions i and j, the first member

function imposes the order !(*Pj < *Pi) whenever i < j. The second version imposes the order !pr(*Pj, *Pi) whenever i < j. No pairs of elements in the original controlled sequence are reversed in the resulting controlled sequence. If a pair of elements in the resulting controlled sequence compares equal (!(*Pi < *Pj) && !(*Pj < *Pi)), an element from the original controlled sequence appears before an element from the sequence controlled by x. void pop_back()

list::pop_back removes the last element of the controlled sequence, which must be nonempty.

void pop_front()

list::pop_front removes the first element of the controlled sequence, which must be nonempty.

void push_back(const T& x)

list::push_back inserts an element with value x at the end of the controlled sequence.

void push_front(const T& x)

list::push_front inserts an element with value x at the beginning of the controlled sequence.

const_reverse_iterator rbegin() const reverse_iterator rbegin()

list::rbegin returns a reverse iterator that points just beyond the end of the controlled sequence. Hence, it designates the beginning of the reverse sequence.

typedef A::reference reference

list::reference describes an object that can be used as a reference to an element of the controlled sequence. It is described here as a synonym for the reference member of the allocator object.

void remove(const T& x)

list::remove removes from the controlled sequence all elements, designated by the iterator P, for which *P == x.

void remove_if( binder2nd<not_equal_to > pr)

list::remove_if removes from the controlled sequence all elements, designated by the iterator P, for which

pr(*P) is true. const_reverse_iterator rend() const reverse_iterator rend()

list::rend returns a reverse iterator that points at the first element of the sequence (or just beyond the end of an empty sequence). Hence, it designates the end of the reverse sequence.

void resize(size_type n, T x = T())

list::resize ensures that size() henceforth returns n. If it must make the controlled sequence longer, it appends elements with value x.

void reverse()

list::reverse reverses the order in which elements appear in the controlled sequence.

typedef reverse_iterator::pointer, difference_type> reverse_iterator

The type describes an object that can serve as a reverse iterator for the controlled sequence.

size_type size() const

list::size returns the length of the controlled sequence.

typedef A::size_type size_type

size_type is an unsigned integer type that describes an object that can represent the length of any controlled sequence.

void sort() void sort(greater pr)

Both versions of list::sort order the elements in the controlled sequence by a predicate. For the iterators Pi and Pj designating elements at positions i and j, the first member function imposes the order !(*Pj < *Pi) whenever i < j. The second version imposes the order ! pr(*Pj, *Pi) whenever i < j. No pairs of elements in the original controlled sequence are reversed in the resulting controlled sequence. "void splice(iterator it, list& x)"

void splice(iterator it, list& x, iterator first) void splice(iterator it,iterator first,iterator last)

The first version of list::splice inserts the sequence controlled by x after the element in the controlled sequence pointed to by it. It also removes all elements from x. (&x must not equal this). The second version removes the

element pointed to by the first in the sequence controlled by x and inserts it after the element in the controlled sequence pointed to by it. (If it == first || it == ++first, no change occurs). The third version function inserts the subrange designated by [first, last) from the sequence controlled by x after the element in the controlled sequence pointed to by it. It also removes the original subrange from the sequence controlled by x. (If &x == this, the range [first, last) must not include the element pointed to by it). If the third version inserts N elements, and &x != this, an object of class iterator is incremented N times. In no case do any copies or destructor calls occur for any elements. void swap(list& str)

list::swap swaps the controlled sequences between *this and str. If allocator == str.allocator, it does so in constant time. Otherwise, it performs a number of element assignments and constructor calls proportional to the number of elements in the two controlled sequences.

void unique() void unique(not_equal_topr)

The first version of list::unique removes from the controlled sequence every element that compares equal to its preceding element. For the iterators Pi and Pj designating elements at positions i and j, the second version removes every element for which i + 1 == j && pr(*Pi, *Pj). For a list of length N (> 0), the predicate pr(*Pi, *Pj) is evaluated N - 1 times.

typedef A::types::value_type value_type

The type describes an element of the controlled sequence (same as the template parameter T).

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. Member:

Description

typedef A allocator_type

map::allocator_type describes the stored allocator object (same as the fourth template argument).

const_iterator begin() const iterator begin()

map::begin returns a bidirectional iterator that points at the first element of the sequence (or just beyond the end of an empty sequence).

void clear() const

map::clear calls erase( begin(), end()).

typedef A::const_iterator const_iterator

map::const_iterator describes an object that can serve as a constant bidirectional iterator for the map. It is described here as a synonym for the const_iterator member of the allocator object.

typedef A::const_reference const_reference

map::const_reference describes an object that can serve as a constant reference to an element of the map.

typedef reverse_iterator const_reverse_iterator

map::const_reverse_iterator describes an object that can serve as a constant reverse bidirectional iterator for the map.

size_type count(const Key& key) const

map::count returns the number of elements x in the range [lower_bound(key), upper_bound(key)).

typedef A::difference_type difference_type

map::difference_type is a signed integer type that describes an object that can represent the difference between the addresses of any two elements in the map. Note that such differences are not meaningful within the context of the map.

bool empty() const

map::empty returns true if the map is empty.

const_iterator end() const iterator end()

map::end returns a bidirectional iterator that points just beyond the end of the sequence.

pair equal_range(const Key& key) const

map::equal_range returns a pair of iterators x such that x.first == lower_bound(key) and x.second == upper_bound(key).

iterator erase(iterator it) The first version of map::erase removes the iterator erase(iterator first, iterator last) element of the controlled sequence pointed to size_type erase(const Key& key) by it. The second version removes the elements in the range [first, last). Both return an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists. The third version removes the elements with sort keys in the range [lower_bound(key), upper_bound(key)), and returns the number of elements it removes. const_iterator find(const Key& key) const

map::find returns an iterator that designates the earliest element in the controlled sequence whose sort key equals key. If no such element exists, the iterator equals end().

A get_allocator() const

The member function returns allocator.

pair insert(const value_type& x) iterator insert(iterator obptr, const value_type& x) void insert(const value_type *first, const value_type *last)

The first version of map::insert determines whether an element y exists in the sequence whose key matches that of x. (The keys match if ! key_comp()(x, y) && !key_comp()(y, x).) If not, it creates such an element y and initializes it with x. The function then determines the iterator obptr that designates y. If an insertion occurred, the function returns pair(obptr, true). Otherwise, it returns pair(obptr, false). The second version returns insert(x), using obptr as a starting place within the controlled sequence to search for the insertion point. (Insertion can occur in amortized constant time, instead of logarithmic time, if the insertion point immediately follows obptr.) The third version inserts the sequence of element values in the range [first, last).

typedef A::pointer iterator

Iterator describes an object that can serve as a bidirectional iterator for the controlled

sequence. It is described here as a synonym for the pointer member of the allocator object. key_compare key_comp() const

map::key_comp returns the stored function object that determines the order of elements in the controlled sequence. The stored object defines the member function bool operator(const Key& x, const Key& y) which returns true if x strictly precedes y in the sort order.

typedef Pred key_compare

map::key_compare describes a function object that can compare two sort keys to determine the relative order of any two elements in the controlled sequence. It is described here in terms of the user-defined comparator object (second template parameter).

typedef Key key_type

map::key_type describes the sort key object stored in each element of the map.

const_iterator lower_bound (const Key& key) const

map::lower_bound returns an iterator that designates the earliest element x in the controlled sequence for which key_comp()(x, key) is False. If no such element exists, the function returns end().

explicit map(const Pred& comp = Pred(), const A& al=A()) map(const map& x) map(const value_type *first,const value_type *last, const Pred& comp=Pred(), const A& al=A())

The constructors with an argument named comp store the function object so that it can be later returned by calling key_comp(). All constructors also store the allocator object al (or, for the copy constructor, x. get_allocator()) in allocator and initialize the controlled sequence. The first constructor specifies an empty initial controlled sequence. The second constructor specifies a copy of the sequence controlled by x. The third constructor specifies the sequence of element values [first, last). This method is a member of map only.

typedef TYPE mapped_type

map::mapped_type describes the value object stored in each element of the map. It is described here in terms of the second template parameter.

size_type max_size() const

map::max_size returns the length of the longest sequence that the object can control.

explicit multimap(const Pred& comp = Pred(), const A& al=A()) multimap(const multimap& x) multimap(const value_type *first, const value_type *last, const Pred& comp=Pred(), const A& al=A())

The constructors with an argument named comp store the function object so that it can be later returned by calling key_comp(). All constructors also store the allocator object al (or, for the copy constructor, x. get_allocator()) in allocator and initialize the controlled sequence. The first constructor specifies an empty initial controlled sequence. The second constructor specifies a copy of the sequence controlled by x. The third constructor specifies the sequence of element values [first, last). This method is a member of multimap only.

A::types::reference operator[](const Key& key);

map::operator[] determines the iterator it as the return value of insert( value_type(key, T()). (It inserts an element with the specified key if no such element exists.) It then returns a reference to (*it). second. This method is a member of map only.

const_reverse_iterator rbegin() const reverse_iterator rbegin()

map::rbegin returns a reverse iterator that points just beyond the end of the controlled sequence. Hence, it designates the beginning of the reverse sequence.

typedef A::reference reference

map::reference describes an object that can be used as a reference to an element of the controlled sequence. It is described here as a synonym for the reference member of the allocator object.

const_reverse_iterator rend() const reverse_iterator rend()

map::rend returns a reverse iterator that points at the first element of the sequence (or just beyond the end of an empty sequence). Hence, it designates the end of the reverse sequence.

typedef reverse_bidirectional_iterator ::pointer, difference_type> reverse_iterator

map::reverse_iterator describes an object that can serve as a reverse bidirectional iterator for the controlled sequence.

explicit map(const Pred& comp=Pred(),

The constructors with an argument named

const A& al=A()) map(const map& x) map(const value_type *first,const value_type *last, const Pred& comp = Pred(), const A& al = A())

comp store the function object so that it can be later returned by calling key_comp(). All constructors also store the allocator object al (or, for the copy constructor, x.get_allocator()) in allocator and initialize the controlled sequence. The first constructor specifies an empty initial controlled sequence. The second constructor specifies a copy of the sequence controlled by x. The third constructor specifies the sequence of element values [first, last). This method is a member of map only.

size_type size() const

map::size returns the length of the controlled sequence.

typedef A::size_type size_type

size_type is an unsigned integer type that describes an object that can represent the length of any controlled sequence.

void swap(map& str)

map::swap swaps the controlled sequences between *this and str. If allocator == str.allocator, it does so in constant time. Otherwise, it performs a number of element assignments and constructor calls proportional to the number of elements in the two controlled sequences.

const_iterator upper_bound(const Key& map::upper_bound returns an iterator that key) const designates the earliest element x in the controlled sequence for which key_comp()(key, x) is true. If no such element exists, the function returns end(). value_compare value_comp() const

map::valuecomp returns a function object that determines the order of elements in the controlled sequence.

class value_compare : public binary_function { friend class map; public: bool operator()(const value_type& x, const value_type& y) {return (comp(x.first, x.second)); } protected:

map::value_compare describes a function object that can compare the sort keys in two elements to determine their relative order in the controlled sequence. The function object stores an object comp of type key_type. The member function operator() uses this object to compare the sort-key components of two elements.

value_compare(key_compare pr) : comp(pr) {} key_compare comp; }; typedef pair value_type;

The type describes an element of the controlled sequence (a key/data pair).

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. Member

Function

typedef A allocator_type

set::allocator_type describes the stored allocator object (same as the second template argument).

const_iterator begin() const iterator begin()

set::begin returns a bidirectional iterator that points at the first element of the sequence (or just beyond the end of an empty sequence).

void clear() const

set::clear calls erase( begin(), end()).

typedef A::const_iterator const_iterator

set::const_iterator describes an object that can serve as a constant bidirectional iterator for the set. It is described here as a synonym for the const_iterator member of the allocator object.

typedef A::const_reference const_reference

set::const_reference describes an object that can serve as a constant reference to an element of the set.

typedef reverse_iterator const_reverse_iterator

set::const_reverse_iterator describes an object that can serve as a constant reverse bidirectional iterator for the set.

size_type count(const Key& key) const

set::count returns the number of elements x in the range [lower_bound(key), upper_bound(key)).

typedef A::difference_type difference_type set::difference_type is a signed integer type that describes an object that can represent the difference between the addresses of any two elements in the set. Note that such differences are not meaningful within the context of the set. bool empty() const

set::empty returns true if the set is empty

const_iterator end() const iterator end()

set::end returns a bidirectional iterator that points just beyond the end of the sequence.

pair equal_range(const Key& key) const

set::equal_range returns a pair of iterators x such that x.first == lower_bound(key) and x.second == upper_bound(key).

iterator erase(iterator it) iterator erase(iterator first, iterator last) size_type erase(const Key& key)

The first version of set::erase removes the element of the controlled sequence pointed to by it. The second version removes the elements in the range [first, last). Both return an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists. The third version removes the elements with sort keys in the range [lower_bound(key), upper_bound(key)), and returns the number of elements it removes.

const_iterator find(const Key& key) const

set::find returns an iterator that designates the earliest element in the controlled sequence whose sort key equals key. If no such element exists, the iterator equals end().

A get_allocator() const

The member function returns allocator.

pair insert(const value_type& x) iterator insert(iterator obptr, const value_type& x) void insert(const value_type *first, const value_type *last)

The first version of set::insert determines whether an element y exists in the sequence whose key matches that of x. (The keys match if ! key_comp()(x, y) && ! key_comp()(y, x).) If not, it creates such an element y and initializes it with x. The function then determines the iterator obptr that designates y. If an insertion occurred, the function returns pair(obptr, true). Otherwise, it returns pair(obptr, false). The

second version returns insert(x), using obptr as a starting place within the controlled sequence to search for the insertion point. (Insertion can occur in amortized constant time, instead of logarithmic time, if the insertion point immediately follows obptr.) The third version inserts the sequence of element values in the range [first, last). typedef A::pointer iterator

Iterator describes an object that can serve as a bidirectional iterator for the controlled sequence. It is described here as a synonym for the pointer member of the allocator object.

key_compare key_comp() const

map::key_comp returns the stored function object that determines the order of elements in the controlled sequence. The stored object defines the member function bool operator(const Key& x, const Key& y), which returns true if x strictly precedes y in the sort order.

typedef Pred key_compare

map::key_compare describes a function object that can compare two sort keys to determine the relative order of any two elements in the controlled sequence. It is described here in terms of the user-defined comparator object (second template parameter).

typedef Key key_type

map::key_type describes the sort key object that constitutes each element of the controlled sequence. It is described here in terms of the data type of the objects the set contains (first template parameter).

const_iterator lower_bound(const Key& key) const

set::lower_bound returns an iterator that designates the earliest element x in the controlled sequence for which key_comp()(x, key) is False. If no such element exists, the function returns end().

size_type max_size() const

set::max_size returns the length of the longest sequence that the object can control.

explicit multiset(const Pred& comp = Pred(), const A& al=A()) multiset(const multiset& x) multiset(const value_type *first, const value_type *last, const Pred& comp=Pred(), const A& al=A())

The constructors with an argument named comp store the function object so that it can be later returned by calling key_comp(). All constructors also store the allocator object al (or, for the copy constructor, x. get_allocator()) in allocator and initialize the controlled sequence. The first constructor specifies an empty initial controlled sequence. The second constructor specifies a copy of the sequence controlled by x. The third constructor specifies the sequence of element values [first, last). This method is a member of multiset only

const_reverse_iterator rbegin() const reverse_iterator rbegin()

set::rbegin returns a reverse iterator that points just beyond the end of the controlled sequence. Hence, it designates the beginning of the reverse sequence.

typedef A::reference reference

set::reference describes an object that can be used as a reference to an element of the controlled sequence. It is described here as a synonym for the reference member of the allocator object.

const_reverse_iterator rend() const reverse_iterator rend()

set::rend returns a reverse iterator that points at the first element of the sequence (or just beyond the end of an empty sequence). Hence, it designates the end of the reverse sequence.

typedef reverse_bidirectional_iterator::pointer, difference_type> reverse_iterator

set::reverse_iterator describes an object that can serve as a reverse bidirectional iterator for the controlled sequence.

explicit set(const Pred& comp=Pred(), const A& al=A()) set(const set& x) set(const value_type *first, const value_type *last, const Pred& comp = Pred(), const A& al = A())

The constructors with an argument named comp store the function object so that it can be later returned by calling key_comp(). All constructors also store the allocator object al (or, for the copy constructor, x.get_allocator()) in allocator and initialize the controlled sequence. The first constructor specifies an empty initial controlled sequence. The second

constructor specifies a copy of the sequence controlled by x. The third constructor specifies the sequence of element values [first, last). This method is a member of set only. size_type size() const

set::size returns the length of the controlled sequence.

typedef A::size_type size_type

size_type is an unsigned integer type that describes an object that can represent the length of any controlled sequence.

void swap(set& str)

set::swap swaps the controlled sequences between *this and str. If allocator == str.allocator, it does so in constant time. Otherwise, it performs a number of element assignments and constructor calls proportional to the number of elements in the two controlled sequences.

const_iterator upper_bound(const Key& key) const

set::upper_bound returns an iterator that designates the earliest element x in the controlled sequence for which key_comp()(key, x) is true. If no such element exists, the function returns end().

value_compare value_comp() const

set::valuecomp returns a function object that determines the order of elements in the controlled sequence.

typedef Pred value_compare

set::value_compare describes a function object that can compare two elements as sort keys to determine their relative order in the controlled sequence. It is described herein as the user-defined comparator object (second template parameter).

typedef A::types::value_type value_type

The type describes an element of the controlled sequence (same as the template parameter T).

17.5 vector Member

Description

typedef A allocator_type

vector::allocator_type describes the stored allocator object (same as the second template argument).

void assign(const_iterator first, const_iterator last) void assign(size_type n, const T& x = T())

The first version of vector::assign replaces the sequence controlled by *this with the sequence [first, last). The second version replaces the sequence controlled by *this with a repetition of n elements of value x.

const_reference at(size_type pos) const reference at(size_type pos)

vector::at returns a reference to the element of the vector at position pos. If that position is invalid, the function throws an object of class out_of_range (throws an exception).

reference back() const_reference back() const

vector::back returns a reference to the last element of the vector, which must be nonempty.

const_iterator begin() const iterator begin()

vector::begin returns a random-access iterator that points at the first element of the sequence (or just beyond the end of an empty sequence).

size_type capacity() const

vector::capacity returns the storage currently allocated to hold the vector, a value at least as large as vector::size().

void clear() const

vector::clear calls erase( begin(), end()).

typedef A::const_iterator const_iterator

vector::const_iterator describes an object that can serve as a constant random-access iterator for the vector. It is described here as a synonym for the const_iterator member of the allocator object.

typedef A::const_reference const_reference vector::const_reference describes an object that can serve as a constant reference to an element of the vector. typedef reverse_iterator const_reverse_iterator

vector::const_reverse_iterator describes an object that can serve as a constant reverse iterator for the vector.

typedef A::difference_type difference_type

vector::difference_type is a signed

integer type that describes an object that can represent the difference between the addresses of any two elements in the vector. bool empty() const

vector::empty returns true if the vector is empty

const_iterator end() const iterator end()

vector::end returns a random-access iterator that points just beyond the end of the sequence.

iterator erase(iterator it) iterator erase(iterator first, iterator last)

The first version of vector::erase removes the element of the controlled sequence pointed to by it. The second version removes the elements of the controlled sequence in the range [first, last). Both return an iterator that designates the first element remaining beyond any elements removed, or end() if no such element exists. Erasing N elements causes N destructor calls and an assignment (operator=) for each of the elements between the insertion point and the end of the sequence. No reallocation occurs, so iterators and references become invalid only from the first element erased through the end of the sequence.

reference front() const_reference front() const

vector::front returns a reference to the first element of the controlled sequence, which must be nonempty.

A get_allocator() const

The member function returns allocator.

iterator insert(iterator it, const T& x = T()) void insert(iterator it, size_type n, const T& x) void insert(iterator it, const_iterator first, const_iterator last)

Each version of vector::insert inserts, after the element pointed to by it in the controlled sequence, a sequence specified by the remaining operands. The first version inserts a single element with value x> and returns an iterator that points to the newly inserted element. The second version inserts a repetition of n elements of value x. The third version inserts the sequence [first, last). When inserting a single element, the

number of element copies is linear in the number of elements between the insertion point and the end of the sequence. When inserting a single element at the end of the sequence, the amortized number of element copies is constant. When inserting N elements, the number of element copies is linear in N plus the number of elements between the insertion point and the end of the sequence. If reallocation occurs, the size of the controlled sequence at least doubles, and all iterators and references become invalid. If no reallocation occurs, iterators become invalid only from the point of insertion through the end of the sequence. typedef A::pointer iterator

Iterator describes an object that can serve as a random-access iterator for the controlled sequence. It is described here as a synonym for the pointer member of the allocator object.

size_type max_size() const

vector::max_size returns the length of the longest sequence that the object can control.

const_reference operator[](size_type pos) const reference operator[](size_type pos)

operator[] returns a reference to the element of the controlled sequence at position pos. If that position is invalid, the behavior is undefined.

void pop_back()

vector::pop_back removes the last element of the controlled sequence, which must be nonempty.

void push_back(const T& x)

vector::push_back inserts an element with value x at the end of the controlled sequence.

const_reverse_iterator rbegin() const reverse_iterator rbegin()

vector::rbegin returns a reverse iterator that points just beyond the end of the controlled sequence. Hence, it designates the beginning of the reverse sequence.

typedef A::reference reference

vector::reference describes an object that can be used as a reference to an element of

the controlled sequence. It is described here as a synonym for the reference member of the allocator object. const_reverse_iterator rend() const reverse_iterator rend()

vector::rend returns a reverse iterator that points at the first element of the sequence (or just beyond the end of an empty sequence). Hence, it designates the end of the reverse sequence.

void reserve(size_type n)

vector::reserve ensures that capacity() henceforth returns at least n.

void resize(size_type n, T x = T())

vector::resize ensures that size() henceforth returns n. If it must make the controlled sequence longer, it appends elements with value x.

typedef reverse_iterator
The type describes an object that can serve as a reverse iterator for the controlled sequence.

reference, A::types::pointer, difference_type> reverse_iterator size_type size() const

vector::size returns the length of the controlled sequence.

typedef A::size_type size_type

size_type is an unsigned integer type that describes an object that can represent the length of any controlled sequence.

void swap(vector& str)

vector::swap swaps the controlled sequences between *this and str. If allocator == str.allocator, it does so in constant time. Otherwise, it performs a number of element assignments and constructor calls proportional to the number of elements in the two controlled sequences.

typedef A::types::value_type value_type

The type describes an element of the controlled sequence (same as the template parameter T).

explicit vector(const A& al = A()) explicit vector(size_type n, const T& v = T(), const A& al = A())

All constructors store the allocator object al (or, for the copy constructor, x.get_allocator()) in allocator and initialize the controlled sequence. The first

vector(const vector& x) vector(const_iterator first, const_iterator last, const A& al = A())

constructor specifies an empty initial controlled sequence. The second constructor specifies a repetition of n elements of value x. The third constructor specifies a copy of the sequence controlled by x. The last constructor specifies the sequence [first, last). Constructors copy N elements and perform no interim reallocation.

17.6 priority_queue Member

Description

typedef A allocator_type

priority_queue::allocator describes the allocator object used to construct the stored container object (specified by the second template parameter). The allocator is specified by the third template parameter.

bool empty() const

priority_queue::empty returns true if the priority_queue is empty. Returns C.empty(), where C is the stored container object specified by priority_queue’s second template parameter.

A get_allocator() const;

priority_queue::get_allocator returns C.get_allocator(), where C is the stored container object specified by priority_queue’s second template parameter.

void pop();

priority_queue::pop removes the first element of the controlled sequence, which must be nonempty, then reorders it.

explicit priority_queue(const Pred& pr=Pred(), const A& al = A()); priority_queue(const value_type *first, const value_type *last, const Pred& pr = Pred(), const A& al = A());

Both constructors store pr in comp and effectively initialize the stored object with c(al), to specify an empty initial controlled sequence. The second constructor then calls push(x) where x is an iterator of class InIt in the range [first, last).

void push(const T& x);

priority_queue::push inserts an element with value x at the end of the controlled sequence,

then reorders it. size_type size() const;

priority_queue::size returns the number of items on the priority_queue. Calls C.size, where C is the stored container object specified by priority_queue’s second template parameter.

typedef C::size_type size_type;

priority_queue::size_type describes an unsigned integer type describes an object that can represent the length of any controlled sequence. It is defined here in terms of the size_type defined for the stored container object specified by priority_queue’s second template parameter.

value_type& top(); const value_type& top() const;

priority_queue::top returns a reference to the last element of the priority_queue, which must be nonempty. Calls C.back(), where C is the stored container object specified by the second template parameter.

typedef Cont::value_type value_type;

priority_queue::value_type describes an element of the controlled sequence. In this context, it is the same as priority_queue’s first template parameter.

17.7 queue Member

Description

typedef A allocator_type

queue::allocator describes the allocator object used to construct the stored container object (specified by the second template parameter). The allocator is specified by the third template parameter.

bool empty() const

queue::empty returns true if the queue is empty. Returns C.empty(), where C is the stored container object specified by queue’s second template parameter.

value_type& front(); const value_type& front() const;

queue::front returns a reference to the first element of the queue, which must be nonempty. Calls C.back(), where C is the

stored container object specified by the second template parameter. (see note at the bottom of this table) A get_allocator() const;

queue::get_allocator returns C.get_allocator(), where C is the stored container object specified by queue’s second template parameter.

void pop();

queue::pop removes the first element from the queue, which must be nonempty. Calls C.pop_front, where C is the stored container object specified by queue’s second template parameter.

void push(const T& x);

queue::push(x) pushes an item with value x onto the queue. Calls C.push_back(x), where C is the stored container object specified by queue’s second template parameter.

explicit queue(const A& al = A());

The constructor initializes the stored container object C, by calling C.C(al), to specify an empty initial controlled sequence.

size_type size() const;

queue::size returns the number of items on the queue. Calls C.size, where C is the stored container object specified by queue’s second template parameter.

typedef C::size_type size_type;

queue::size_type describes an unsigned integer type that describes an object that can represent the length of any controlled sequence. It is defined here in terms of the size_type defined for the stored container object specified by queue’s second template parameter.

typedef Cont::value_type value_type;

queue::value_type describes an element of the controlled sequence. In this context, it is the same as queue’s first template parameter.

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

Member

Description

typedef A allocator_type

stack::allocator describes the allocator object used to construct the stored container object (specified by the second template parameter). The allocator is specified by the third template parameter.

bool empty() const

stack::empty returns true if the stack is empty. Returns C.empty(), where C is the stored container object specified by stack’s second template parameter.

A get_allocator() const;

stack::get_allocator returns C.get_allocator(), where C is the stored container object specified by stack’s second template parameter.

void pop();

stack::pop removes the last element pushed onto the stack, which must be nonempty. Calls C.pop_back, where C is the stored container object specified by stack’s second template parameter.

void push(const T& x);

stack::push(x) pushes an item with value x onto the stack. Calls C.push_back(x), where C is the stored container object specified by stack’s second template parameter.

size_type size() const;

stack::size returns the number of items on the stack. Calls C.size, where C is the stored container object specified by stack’s second template parameter.

typedef C::size_type size_type;

stack::size_type describes an unsigned integer type that describes an object that can represent the length of any controlled sequence. It is defined here in terms of the size_type defined for the stored container object specified by stack’s second template parameter.

explicit stack(const A& al = A());

The constructor initializes the stored container object C, by calling C.C(al), to specify an empty initial controlled sequence.

value_type& top(); const value_type& top() const;

stack::top returns a reference to the last element of the stack, which must be nonempty. Calls C.back(), where C is the stored

container object specified by the second template parameter. typedef Cont::value_type value_type;

stack::value_type describes an element of the controlled sequence. In this context, it is the same as stack’s first template parameter.

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 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 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 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 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 > 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.