Algorithms

Introduction

This chapter describes how to work with the standard algorithms and how to use them on the standard containers. These algorithms were originally part of what is often referred to as the Standard Template Library (STL), which is the set of algorithms, iterators, and containers that now belong to the standard library (Chapter 6 contains recipes for working with the standard containers). I will refer to these simply as the standard algorithms, iterators, and containers, but keep in mind that they are the same ones that other authors' refer to as part of the STL. One of the pillars of the standard library is iterators, so the first recipe explains what they are and how to use them. After that, there are a number of recipes that explain how to use and extend the standard algorithms. Finally, if what you need isn't in the standard library, Recipe 7.10 explains how to write your own algorithm.

The recipes presented here are largely biased toward working with the standard containers for two reasons. First, the standard containers are ubiquitous, and it's better to learn the standard than to reinvent the wheel. Second, the algorithms in the standard library implementations provide a good model to follow for interoperability and performance. If you watch how the pros do it in the standard library code, you are likely to learn a few valuable lessons along the way.

All standard algorithms use iterators. Even if you are already familiar with the concept of iterators, which is the subject of the first recipe, take a look at Table 7-1, which contains a list of the conventions I use in the rest of the chapter when listing function declarations for the standard algorithms.

Table 7-1. Iterator category abbreviations

Abbreviation	Meaning
In	Input iterator
Out	Output iterator
Fwd	Forward iterator
Bid	Bidirectional iterator
Rand	Random-access iterator

The standard algorithms also make use of function objects, or functors. A function object is a class that has overridden operator( ) so that it can be called like a function. A functor that returns a bool (and does not maintain state, and is therefore called pure) is called a predicate, and they are another regular feature in the standard algorithms. Generally, a predicate takes one or two arguments: if it takes one argument, it is an unary predicate; and if it takes two, it is called a binary predicate. For the sake of brevity, I use the abbreviations listed in Table 7-2 when listing function declarations.

Table 7-2. Functor types

Type Name	Description
UnPred	An unary predicate. Takes one argument and returns a bool.
BinPred	A binary predicate. Takes two arguments and returns a bool.
UnFunc	An unary function. Takes one argument and returns anything.
BinFunc	A binary function. Takes two arguments and returns anything.

In most cases, a function pointer can be used when a functor argument is required. When I use the term functor, I also mean function pointer unless otherwise noted.