• Choose a category
• All
• Classic-Fiction

By Root 1541 0

implementations of many generic algorithms. An algorithm is a strategy for performing a particular task, such as sorting or searching. These algorithms are also implemented as templates, so they work on most of the different container types. Note that the algorithms are not generally part of the containers. The STL takes the approach of separating the data (containers) from the functionality (algorithms). Although this approach seems counter to the spirit of object-oriented programming, it is necessary in order to support generic programming in the STL. The guiding principle of orthogonality maintains that algorithms and containers are independent, with (almost) any algorithm working with (almost) any container.

Although the algorithms and containers are theoretically independent, some containers provide certain algorithms in the form of class methods because the generic algorithms do not perform well on those particular containers. For example, sets provide their own find() algorithm that is faster than the generic find() algorithm. You should use the container-specific method form of the algorithm, if provided, because it is generally more efficient or appropriate for the container at hand.

Note that the generic algorithms do not work directly on the containers. They use an intermediary called an iterator. Each container in the STL provides an iterator that supports traversing the elements in the container in a sequence. The different iterators for the various containers adhere to standard interfaces, so algorithms can perform their work by using iterators without worrying about the underlying container implementation.

This section gives an overview of what kind of algorithms are available in the STL without giving all the fine points. The Standard Library Reference resource on the website (www.wrox.com) contains the exact prototypes of all the algorithms. The following chapters go deeper in on iterators, algorithms, and containers with coding examples.

Iterators mediate between algorithms and containers. They provide a standard interface to traverse the elements of a container in sequence, so that any algorithm can work on any container.

There are approximately 60 algorithms in the STL (depending on how you count them), generally divided into several different categories. In addition, C++11 adds several new algorithms to the STL. The categories tend to vary slightly from book to book. This book uses the following five categories: utility, non-modifying, modifying, sorting, and set. Some of the categories can be subdivided further. Note that whenever the following algorithms are specified as working on a “sequence” of elements, that sequence is presented to the algorithm via iterators.

When examining the list of algorithms, keep in mind that the STL was designed by a committee. The committee approach tends to add generality that might never be used, but which, if required, would be essential. You may not need every algorithm, or need to worry about the more obscure parameters which are there for anticipated generality. It is important only to be aware of what’s available in case you ever find it useful.

Utility Algorithms

Unlike the other algorithms, the utility algorithms do not work on sequences of data. We consider them part of the STL only because they are templatized.

ALGORITHM NAME ALGORITHM SYNOPSIS

min(), max() Returns the minimum or maximum of two values. C++11 allows you to use the min() and max() functions to find the minimum and maximum of more than two values.

minmax() Returns the minimum and maximum of two or more values as a pair.

swap() Swaps two values.

Non-Modifying Algorithms

The non-modifying algorithms are those that look at a sequence of elements and return some information about the elements, or execute some function on each element. As “non-modifying” algorithms, they cannot change the values of elements or the order of elements within the sequence. This category contains four types of algorithms. The following tables list and provide brief summaries of the various non-modifying