bitset

A significant subset of the C++ class library is formed by the standard template library, or STL. The STL provides general-purpose templatized classes and functions that implement many popular and commonly used algorithms and data structures. For example, it includes support for vectors, lists, queues, and stacks. It also defines various routines that access them. Because the STL is constructed from template classes, the algorithms and data structures can be applied to nearly any type of data.

The version of the STL described here is the one specified by ANSI/ISO C++ Standard. Older compilers may present a slightly different version of the STL.

An Overview of the STL

At the core of the Standard Template Library are three foundational items: containers, algorithms, and iterators. These items work in conjunction with one another to provide off-the-shelf solutions to a variety of programming problems.

Containers

Containers are objects that hold other objects. There are several different types of containers. For example, the vector class defines a dynamic array, deque creates a double-ended queue, and list provides a linear list. These containers are called sequence containers because in STL terminology, a sequence is a linear list. In addition to the basic containers, the STL also defines associative containers, which allow efficient retrieval of values based on keys. For example, a map provides access to values with unique keys. Thus, a map stores a key/value pair and allows a value to be retrieved given its key.

Each container class defines a set of functions that can be applied to the container. For example, a list container includes functions that insert, delete, and merge elements. A stack includes functions that push and pop values.

Algorithms

Algorithms act on containers. They provide the means by which you will manipulate the contents of containers. Their capabilities include initialization, sorting, searching, and transforming the contents of containers. Many algorithms operate on a range of elements within a container.

Iterators

Iterators are objects that act, more or less, like pointers. They give you the ability to cycle through the contents of a container in much the same way that you would use a pointer to cycle through an array. There are five types of iterators:

Iterator	Access Allowed
Random Access	Store and retrieve values. Elements may be accessed randomly.
Bidirectional	Store and retrieve values. Forward and backward moving.
Forward	Store and retrieve values. Forward moving only.
Input	Retrieve, but not store, values. Forward moving only.
Output	Store, but not retrieve values. Forward moving only.

In general, an iterator that has greater access capabilities can be used in place of one that has lesser capabilities. For example, a forward iterator can be used in place of an input iterator.

Iterators are handled just like pointers. You can increment and decrement them. You can apply the * operator to them. Iterators are declared using the iterator type defined by the various containers.

The STL also supports reverse iterators. Reverse iterators are either bidirectional or random access iterators that move through a sequence in the reverse direction. Thus, if a reverse iterator points to the end of a sequence, incrementing that iterator will cause it to point one element before the end.

When referring to the various iterator types in template descriptions, this section will use the following terms:

Term	Represents
BiIter	Bidirectional iterator
ForIter	Forward iterator
InIter	Input iterator
OutIter	Output iterator
RandIter	Random access iterator

Other STL Elements

In addition to containers, algorithms, and iterators, the STL relies upon several other standard components for support. Chief among these are allocators, predicates, comparison functions, and function objects.

Each container has defined for it an allocator. Allocators manage memory allocation for a container. The default allocator is an object of class allocator, but you can define your own allocators if needed by specialized applications. For most uses, the default allocator is sufficient.

Several of the algorithms and containers use a special type of function called a predicate. There are two variations of predicates: unary and binary. A unary predicate takes one argument. A binary predicate has two arguments. These functions return true/false results, but the precise conditions that make them return true or false are defined by you. For the rest of this chapter, when a unary predicate function is required, it will be notated using the type UnPred. When a binary predicate is required, the type BinPred will be used. In a binary predicate, the arguments are always in the order of first,second. For both unary and binary predicates, the arguments will contain values of the type of objects being stored by the container.

Some algorithms and classes use a special type of binary predicate that compares two elements. Comparison functions return true if their first argument is less than their second. Comparison functions will be notated using the type Comp.

In addition to the headers required by the various STL classes, the C++ standard library includes the <utility> and <functional> headers that provide support for the STL. For example, in <utility> is defined the template class pair, which can hold a pair of values.

The templates in <functional> help you to construct objects that define operator( ). These are called function objects, and they can be used in place of function pointers in many places. There are several predefined function objects declared within <functional>. They are shown here:

plus	minus	multiplies	divides	modulus
negate	equal_to	not_equal_to	greater	greater_equal
less	less_equal	logical_and	logical_or	logical_not

Perhaps the most widely used function object is less, which determines when one object is less than another. Function objects can be used in place of actual function pointers in the STL algorithms described later. Using function objects rather than function pointers allows the STL to generate more efficient code.

Two other entities that populate the STL are binders and negators. A binder binds an argument to a function object. A negator returns the complement of a predicate.

Programming Tip 

The best way to understand how containers and iterators work together is to see an example. The following program demonstrates the vector container. A vector is similar to an array. However, it has the advantage that it automatically handles its own storage requirements, growing if necessary. A vector provides methods so that you can determine its size and add or remove elements.

The following program illustrates the use of a vector class:

// A short example that demonstrates vector. #include <iostream> #include <vector> using namespace std; int main() {   vector<int> v; // create zero-length vector   int i;   // display original size of v   cout << "size = " << v.size() << endl;   /* put values onto end of vector —      vector will grow as needed. */   for(i=0; i<10; i++) v.push_back(i);   // display current size of v   cout << "size now = " << v.size() << endl;   // can access vector contents using subscripting   for(i=0; i<10; i++) cout << v[i] << " ";   cout << endl;   // can access vector's first and last element   cout << "front = " << v.front() << endl;   cout << "back = " << v.back() << endl;   // access via iterator   vector<int>::iterator p = v.begin();   while(p != v.end()) {     cout << *p << " ";     p++;   }   return 0; }

The output from this program is

 size = 0 size now = 10 0 1 2 3 4 5 6 7 8 9  front = 0 back = 9 0 1 2 3 4 5 6 7 8 9 

In this program, the vector is initially created with zero length. The push_back( ) member function puts values onto the end of the vector, expanding its size as needed. The size( ) function displays the size of the vector. The vector can be indexed like a normal array. It can also be accessed using an iterator. The function begin( ) returns an iterator to the start of the vector. The function end( ) returns an iterator to the end of the vector.

One other point: notice how the iterator p was declared. The type iterator is defined by several of the container classes.

One final term to know is adaptor. In STL terms, an adaptor transforms one thing into another. For example, the container queue (which creates a standard queue) is an adaptor for the deque container.