10.1.1Introduction

The goal of generic programming is to represent abstract concepts and algorithms in generic codes without losing efficiency. Generic programming is a different technique from object-oriented programming. In some cases, there are even conflicts between good generic programming design and good object-oriented programming design. But the combination of these two techniques results in a powerful tool for building complex software systems. STL is an excellent example of it. For example, with the help of STL, programmers do not need to write array classes for integers, reals, and characters; writing a generic template is sufficient. These techniques allow heavy code reuses and improve the efficiency of software production.

Recall the array, linked list, and the queues template implementation, searching, and sorting algorithm discussed in Chapter 9. In object-oriented programming, it is good practice to encapsulate these algorithms into classes. However, a better solution is to write generic algorithms independent of implementation such as “finding an element sequentially in a linear collection”. That is the goal of generic programming.

The iterator is the adaptive layer between the algorithms and the data structure. Algorithms can use the iterator interface to access the data structure to perform specific operations. That is the key scheme for decoupling the data structure and the algorithm used by generic programming.

STL is the core component of the C++ standard library. STL implements general containers and iterators, which are the basis of algorithm templates. There are four key components in STL: containers, iterators, algorithms, and function objects as shown in Figure 10.1. As indicated, the algorithm is in the center of the structure. The algorithm uses iterators to obtain data from the container, operates on it with the function objects, and then sends the result to another container through another iterator.

10.1.2Namespace

There are many modules in complex software, including different libraries and classes provided by different programmers. These might contain naming conflicts among these modules, i.e., different things represented by the same identifier. A namespace is the way of resolving this problem in C++.

A namespace restricts a set of identifiers in a named scope. So it is possible to have the same identifier in a different named scope. Programmers use “the name of namespace” + “::” to refer an object in the named scope. For example, the following code declares a namespace NS and some identifiers in it:

The way to refer to these identifiers is the following:

There is a special anonymous namespace that can be used directly. Most examples in this book do not declare namespace explicitly, so the identifiers in these examples are in the scope of the default anonymous namespace.

Programmer can write the “using” statement to avoid writing the lengthy prefixes of the identifiers. For example, if programmer writes the following statement in the code:

then all references of File in the current scope mean NS::File.

However, if the programmer writes the following statement:

then the program can use all identifiers in the named scope of NS without any prefixes.

The standard library in C++ is in the namespace “std”. Programmers can refer to identifiers in the standard library directly with the “std::” prefix, e.g., “std::cout”, or use the “using” statement to enable the program to use these identifiers directly.

Namespaces are represented in a package graph in UML. A package contains classes and other elements, whose identifiers must be unique. All elements in the package are destroyed if the package is destroyed.

Packages are represented by folders in a UML graph. The inner classes of the package can be hidden by writing the package name in the middle of the folder. To show the details of the package, the package name should be written at the label part of the folder. Figure 10.2 shows how to represent a package in these two ways.

The dependencies between packages represent the references among objects in different namespaces. The access dependency describes a package with the privilege of accessing all public interfaces in another package. For example, objects in package P2 are able to access class C in P1 if class C is in the public interface. The relationship between P2 and C is an access dependency, as shown in Figure 10.3.

Import dependency represents merging the public interfaces between two packages. For example, if there is an import dependency between P1 and P2, then P2 can use class C directly, i.e., adding “using namespace P1” in P2’s codes.

10.1.3Differences of Naming Conventions Between C/C++

The C++ standard library declares all identifiers in the namespace “std”. There is no extension name in the header filename; for example, the following statement includes the string library in the program:

It also works for C’s standard library, but the programmer should add the prefix “c” rather than the suffix “.h”:

The old style of the include statement still works in order to be backwards compatible with C:

Notice that the header declares the identifiers in both the global namespace and the “std” namespace.

The STL library is scattered in a series of header files. Here is a quick reference of objects in STL:

10.1.4Concepts of STL

10.1.5Containers

Containers are objects that contain a set of objects. There are two kinds of containers: heterogeneous containers where the container can hold elements of different types; and homogenous containers where the container can only hold elements of the same type.

There are seven types of containers in the STL library: vector, double queue, list, set, multiset, map, and multimap. They can be divided into two groups: sequential containers and associative containers. Sequential containers, such as vectors, double queues, and lists organize elements linearly, while associative containers, such as sets, multisets, maps, and multimaps organize elements based on indexes.

10.1.6Adapters

Adapters provide new interfaces for existing classes and enable two classes to work cooperatively. There are three types of adapters in STL: adapters of containers, adapters of iterators, and adapters of function objects. Adapters are very powerful tools for code reuse. For example, STL uses adapters of containers to implement stacks, queues, and priority queues based on corresponding containers.

10.1.7Iterators

Iterators can be seen as pointers in an object-oriented view. Iterators provide methods like current(), previous(), and next() to allow programmers to access the container via the iterators.

10.1.8Algorithms

There re more than 70 algorithm implementations in STL, including sorting, eliminating, counting, comparing, transforming, and container managing, which covers a wide range of applications. The implementations are generic so that they can be applied to different objects and primitive types.

10.1.9Interfaces of Containers

There are several common interfaces in the STL containers. These containers overload the comparison operator to perform comparison between containers (Table 10.1). There are also methods to access iterators (Table 10.2) and methods to access the status of the container (Table 10.3).

Tab. 10.1: All Operators in STL Containers.

Note: x is a container class, and a and b are instances of class x, r is the value of type x&.

Tab. 10.2: Iterator and Access Methods of Each Container.

Tab. 10.3: Immutable Access to Container Elements.

10.2.1Sequential Containers

The most widely used sequential container in C++ is the array. However, sometimes more powerful tools are needed. To meet this need, STL implements three sequential containers: vectors, lists, and double queues.

The vector is a powerful extension of the static array. It is very similar to the static array, but it can enlarge its storage on demand at runtime.

The list is an implementation of the double-linked list. It is quick to add or remove an element to or from a list.

The double queue is an extension of the data structure queue. Compared to a standard queue, it can add or remove elements from both ends of the queue.

2.Vectors

The vector is a variable length linear collection designed to provide rapid random access for objects. It is very similar to the static array, but vectors can change their storage size on demand at runtime.

Vectors are powerful containers. They can be used to implement queues, stacks, lists, or other complicated data structures.

a)Constructors and Destructors

There are four default constructors in a vector:

As in all containers in STL, vectors accommodate the object-oriented mechanism for memory management. All memory used by the vector itself, and the memory used by elements in the vector, are reclaimed by calling their destructors appropriately when the instance is out of scope.

One thing to notice is that removing an element from a vector just removes the element from the vector. It only calls its destructor but does not reclaim the memory used by the element.

b)Using Vector

1. Querying Status of Vector

There are four methods for querying the status of a vector: size(), max_size(), capacity(), and empty(). Here are their prototypes:

2. Adding Elements into a Vector

There are a number of ways to add an element into a vector: the constructor, push_back(), insert(), and swap() methods, the subscript operator, and the assignment operator. We have introduced some methods before. Here are the prototypes of push_back(), insert(), and swap():

The reverse() method reserves memory space to hold a certain number of elements. The reverse() method reallocates memory only if it finds its need is beyond the current capacity of the vector. Please notice that reallocation invalidates all references and iterators of a vector.

3. Deleting Elements from Vector

Programmers can use pop_back(), erase(), or clear() methods to remove an element from a vector. Here are their prototypes:

4. Accessing Elements in Vector

Methods front() and back() return the first and the last element in the vector respectively. The subscript operator can access the elements via the position directly.

c)Application

Example 10.1: Find all primes between 2 − N.

We now use a vector to rewrite the program in Example 9.4 and here is the program:

The result of the program is as follows:

3.Double Queues

A double queue is an extension of the queue data structure. Elements can be added or removed at both ends of double queues. Programmers can use the subscript operator “[]” to access an element directly.

a)Constructors and Destructors

There are four constructors in a double queue:

b)Using a Double Queue

1. Query the Status of a Double Queue

The size() method returns the number of elements in the double queue. The max_size() method returns the maximum number of elements that the double queue can hold. Method empty() tests whether the double queue is empty or not.

2. Adding Elements into the Double Queue

Adding elements into a double queue is very similar to adding them into a vector. Programmers can add elements via the constructor, push_back()/insert()/swap() methods, the subscript operator, and the assignment operator. Moreover, double queue provides an additional push_front() method to add an element at the head of the queue:

3. Removing Elements in the Double Queue

Methods pop_back()/pop_front()/erase()/clear() can remove elements in a double queue. Their semantics are the same as the ones for vectors. Moreover, double queues provide an additional method pop_front() for removing the first element of the double queue:

4. Access Elements

There are a number of ways to access elements in a double queue. Programmer can use methods like pop_front()/pop_back()/front()/back() to access an element in a queue. They can also use iterators to traverse the queue and access the element directly via subscript operator.

c)Application

Example 10.2: Store doubles with a double queue.

Results:

4.Lists

A list is a sequential container designed for adding/ removing elements quickly. It supports splicing, which adds all elements in a list to another one. Lists do not support random access, so some algorithms do not work on lists. Lists are implemented as double-linked lists in STL, so they can be traversed in both directions.

a)Constructors and Destructors

There are four constructors in a list:

b)Using Lists

1. Accessing the List

There are some minor differences between the interfaces of lists and vectors. There are no capacity()/subscript operators and at() methods, since lists do not support random access. Other interfaces are the same.

2. Adding Elements

The semantics of the method insert() are the same as the ones for vectors and queues but the insert() method in lists does not affect any iterators of a list. The splice() method can also add elements to a list:

3. Removing Elements

The erase() method removes both the element and the iterator pointing to it. The remove() method removes all elements equal to x in a list. Here is the prototype of remove():

c)Application

Example 10.3: Rewrite Example 9.7 with a list in STL.

Read 10 integers from the keyboard, create a linked list whose nodes hold these integers, and output the numbers in order. Then get another number from the keyboard, delete all nodes containing the number and output the data in the linked list. Clear the linked list before exiting.

Here is the program:

Results:

10.2.2Adapters of Containers

Adapters of containers do not implement the mechanism of storing the data and other functionalities like iterators. They just implement different interfaces based on the containers provided by STL.

1.Stacks

A stack is a linear collection with restricted access. Elements can only be added or removed from one end of a stack. Such operations are called push and pop respectively. In theory, there is no limit on the number of elements in a stack. In practice, a stack will overflow if it exceeds the memory limit of the computer, and it will underflow if one tries to pop an element from an empty stack. STL catches these exceptions to keep the program from crashing.

Stacks are based on the implementation of a certain container, which is specified at the declaration. Here is an example of declaration of a stack using a deque as its underlying implementation of storage:

Stacks only implement the primitives of the stack data structure. Methods push()/pop() add or remove an element at the top of stack, respectively. The method top() returns the reference of the element at the top of the stack. The method empty() checks whether a stack is empty. The method size() returns the number of elements in the stack. The underlying storage can be a vector, list, or deque, and the deque is the default implementation. Please refer to related documents like MSDN for detailed information. Here is a simple example of a stack.

Example 10.4: Initialize a stack holding integers.

Results:

2.Queues

Queue adapters provide interfaces for First In First Out (FIFO) services, i.e., adding an element to the tail of the container (enqueuing) and removing the first element of the container (dequeuing). Queues are implemented based on an underlying storage, typically a list or deque. The default underlying implementation of storage is the deque. Here is an example of a declaration of a queue, using the deque as the underlying storage implementation:

The method push() adds an element to the tail of the queue, the method pop() removes the first element of the queue, and the methods front() and back() return the reference of the head and the tail of the queue respectively. The method empty() checks whether the queue is empty, and the method size() returns the number of elements in the queue. Please refer to related documents like MSDN for detailed information. Here is a simple example of using a queue.

Example 10.5: Initialize a queue with integers.

Results:

Similar to stacks and queues, a priority queue is another adapter for implementing an advanced data structure. Priority queues are designed as ordered queues, which are able to extract the highest priority element from a queue.

10.3.1Types of Iterators

There are five basic types of iterators: the input iterator, output iterator, forward iterator, bidirectional iterator, and random access iterator. There are two iterator adapters: the reverse iterator adapter and insert iterator adapter.

2.Iterator Adapters

An iterator adapter is an adapter that extends or adjusts the functions of an iterator. There are two types of iterator adapters:

The reverse iterator adapter reverses the functionalities of the increment operator and decrement operator, so that the algorithm processes the elements in a reversed order. All standard containers can be used with reverse iterators.

The insert iterator adapter overloads the assignment operator and turns it into insertions, so algorithms running on it inserts elements into the collections rather than overwriting the value of the elements. There are three types of insert iterators: back inserters, front inserters, and general inserters. Back inserters append an element to the end of a collection, and front inserters add an element at the head of a collection. General inserters decide the inserting position based on its parameters. Vectors, deques, links, and strings support back inserters, while deques supports front inserters, and all standard collections support general inserters.

Here is an example of an iterator adapter.

Example 10.6: Example of using iterator adapter.

Results:

10.3.2Auxiliary Functions in Iterators

There are three auxiliary functions in iterators: advance(), distance(), and iter_swap(). advance() and distance() emulate the power of random access iterators such as advancing and going back for several positions and calculating the distances of two iterates, through basic iterator primitives. Iter_swap() allows programmers to swap the values that the two iterators are pointing to.

1. advance() move the position of an iterator forward or backward by n position. Here is the prototype:

In bidirectional or random access iterators, n can be negative so that the iterator goes back for n elements.

2. distance() calculates the distances between two iterators:

pos1 and pos2 should point to the same container. If the iterators are not random access iterates, then pos1 must be able to reach pos2 via advancing pos1.

3. iter_swap() swaps the values that two iterators are pointing to:

pos1 and pos2 may point to different containers, but the elements they are pointing to must be able to be assigned to each other.

Here is an example:

Example 10.7: Example of auxiliary function of adapters.

Results:

10.4.1Using the Algorithms

We have used the copy algorithm in Section 10.3; here is the prototype of it:

The algorithm copies all elements in range [first, last) to [result, result + (last − first)), and it returns result + (last − first).

Here is the related code from Example 10.7:

Line 1 initializes an output stream iterator output and transfers all elements in col1 to the output iterator, which outputs the data to the console. Col1.begin() and col1.end() points to the first and the last element of col1 respectively.

Many algorithms take function objects as an input parameter for customizing the behaviors of the algorithms. Here are two prototypes of the sort algorithm:

The first prototype uses the operator < for comparison, so the result is in ascending order. The second prototype compares the elements with the function object comp, so that programmers can write their own rules for sorting, making the implementation flexible.

Here is an example of the sort algorithm:

Example 10.8: Example of sort algorithm.

Results:

10.4.2Nonmutating Sequence Algorithms

Nonmutating Sequence Algorithms do not modify the elements of the input containers, such as algorithms for finding an element in a container, checking whether two sequences are equal, and counting the occurrence of elements.

Tab. 10.4: List of Nonmutating Sequence Algorithms in STL.

Table 10.4 lists Nonmutating Sequence Algorithms in STL.

Here is an example of using Nonmutating Sequence Algorithms:

Example 10.9: An example of using Nonmutating Sequence Algorithms.

Results:

10.4.3Mutating Sequence Algorithms

Mutating Sequence Algorithms change the elements in the input containers. Table 10.5 lists Mutating Sequence Algorithms in STL.

Here is an example of a mutating algorithm.

Example 10.10: An example of mutating algorithm.

Tab. 10.5: Mutating Sequence Algorithms.

Results:

10.4.4Sorting Related Algorithms

There are a number of sorting related algorithms in STL, including sorting a sequence, merging two sorted sequences, setting algorithms, and heaping algorithms for sorted sequences. Here is an overview of these algorithms:

Four sorting algorithms: sort, partial_sort, partial_sort_copy, and stable_sort;

Four binary searching algorithms: binary_search, lower_bound, upper_bound, and equal_range;

Two algorithms of merging two sorted sequences: merge and inplace_merge;

Four algorithms to find maximum/minimum:

min, max, min_element and max_element;

Three sorting related algorithm:

lexicographical_compare, next_permutation, and prev_permutation;

Five set algorithms:

includes, set_union, set_ intersection, set_difference, and set_symmetric_difference;

Four heap algorithms: make_heap, pop_heap, push_heap, and sort_heap.

Algorithm nth_element resorts the sequence based on a particular rule. Table 10.6 lists sorting-related algorithms.

Tab. 10.6: STL Sorting-Related Algorithms.

Here is an example of these algorithms:

Example 10.11: Example of sorting related algorithms.

Results:

10.4.5Numerical Algorithms

There are four generic numerical algorithms; Table 10.7 lists numerical algorithms in STL.

Here is an example of numerical algorithms in STL:

Example 10.12: An example of numerical algorithms.

Tab. 10.7: STL Numerical Algorithms.

Results:

1.Function Objects

A function object is a design pattern used in STL for maximal flexibility. Function objects are an abstraction layer to hide the implementation detail. They behave like functions; they can return a value or perform some operations with side effects (like opening a file). In C++, all functions and any classes overloading the operator () can be used as function objects.

Now we use the numerical algorithm accumulate() as an example to discuss the design and usage of function objects. There are two prototypes of accumulate(): one uses the addition operator “+” to calculate the sum of the sequence, the other uses a customized function object to calculate the result.

Here is an example of using a function as a function object to implement a multiplication operation:

Example 10.13: Use a function as a function object.

Results:

Besides functions, function objects could be objects of a class that overloaded the operator doing the calling . The following example is another implementation of Example 10.13. In this example, the object of a class is used instead of a function.

Example 10.14: Define function objects using classes.

Results:

The class multclass overloads the operator () to implement the multiplication. The compiler generates an instance of multclass with its default constructor and passes it to the accumulate() algorithm. The programmer can create a customized instance to provide additional information for the algorithm.

Tab. 10.8: STL Function Objects in Standard Library.

STL defines a number of standard function objects, including arithmetic operations, boolean operations, and logical operations (as shown in Table 10.8). All of them are defined as inline functions to maximize the performance.

You can also use the multiplication function object provide by STL to implement the same functionalities. Here is the program:

Example 10.15: Using the STL function object multiplies to implement multiplication.

Everything is the same except we changed the multclass in Example 10.14 to multiplies<int>.

STL defines two basic classes of function objects, one for unary functions and one for binary functions for simplifying the design of function objects. For advanced topics please refer to related materials.

2.Function Adapters

Using function adapters is an easier way to create function objects. Interested readers might refer to advanced materials for details