Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Mail Systems
Eclipse Documentation

How To Guides
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Problem Solutions
Privacy Policy




Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

A catalog of STL algorithms

This section provides a quick reference when you re searching for the appropriate algorithm. We leave the full exploration of all the STL algorithms to other references (see the end of this chapter, and Appendix A), along with the more intimate details of issues like performance. Our goal here is for you to rapidly become comfortable with the algorithms, and we ll assume you will look into the more specialized references if you need more detail.

Although you will often see the algorithms described using their full template declaration syntax, we re not doing that here because you already know they are templates, and it s quite easy to see what the template arguments are from the function declarations. The type names for the arguments provide descriptions for the types of iterators required. We think you ll find this form is easier to read, and you can quickly find the full declaration in the template header file if you need it.

The reason for all the fuss about iterators is to accommodate any type of container that meets the requirements in the standard library. So far we have illustrated the generic algorithms with only arrays and vectors as sequences, but in the next chapter you ll see a broad range of data structures that support less robust iteration. For this reason, the algorithms are categorized in part by the types of iteration facilities they require.

The names of the iterator classes describe the iterator type to which they must conform. There are no interface base classes to enforce these iteration operations they are just expected to be there. If they are not, your compiler will complain. The various flavors of iterators are described briefly as follows.

InputIterator. An input iterator only allows reading elements of its sequence in a single, forward pass using operator++ and operator*. Input iterators can also be tested with operator== and operator!=. That s the extent of the constraints.

OutputIterator. An output iterator only allows writing elements to a sequence in a single, forward pass using operator++ and operator*. OutputIterators cannot be tested with operator== and operator!=, however, because you assume that you can just keep sending elements to the destination and that you don t need to see if the destination s end marker was reached. That is, the container that an OutputIterator references can take an infinite number of objects, so no end-checking is necessary. This requirement is important so that an OutputIterator can be used with ostreams (via ostream_iterator), but you ll also commonly use the insert iterators such as are the type of iterator returned by back_inserter( )).

There is no way to determine whether multiple InputIterators or OutputIterators point within the same range, so there is no way to use such iterators together. Just think in terms of iterators to support istreams and ostreams, and InputIterator and OutputIterator will make perfect sense. Also note that algorithms that use InputIterators or OutputIterators put the weakest restrictions on the types of iterators they will accept, which means that you can use any more sophisticated type of iterator when you see InputIterator or OutputIterator used as STL algorithm template arguments.

ForwardIterator. Because you can only read from an InputIterator and write to an OutputIterator, you can t use either of them to simultaneously read and modify a range, and you can t dereference such an iterator more than once. With a ForwardIterator these restrictions are relaxed; you can still only move forward using operator++, but you can both write and read, and you can compare such iterators in the same range for equality. Since forward iterators can both read and write, they can be used in place of an InputIterator or OutputIterator.

BidirectionalIterator. Effectively, this is a ForwardIterator that can also go backward. That is, a BidirectionalIterator supports all the operations that a ForwardIterator does, but in addition it has an operator--.

RandomAccessIterator. This type of iterator supports all the operations that a regular pointer does: you can add and subtract integral values to move it forward and backward by jumps (rather than just one element at a time), you can subscript it with operator[ ], you can subtract one iterator from another, and you can compare iterators to see which is greater using operator<, operator>, and so on. If you re implementing a sorting routine or something similar, random access iterators are necessary to be able to create an efficient algorithm.

The names used for the template parameter types in the algorithm descriptions later in this chapter consist of the listed iterator types (sometimes with a 1 or 2 appended to distinguish different template arguments) and can also include other arguments, often function objects.

When describing the group of elements passed to an operation, mathematical range notation is often used. In this, the square bracket means includes the end point, and the parenthesis means does not include the end point. When using iterators, a range is determined by the iterator pointing to the initial element and by the past-the-end iterator, pointing past the last element. Since the past-the-end element is never used, the range determined by a pair of iterators can be expressed as [first, last), where first is the iterator pointing to the initial element, and last is the past-the-end iterator.

Most books and discussions of the STL algorithms arrange them according to side-effects: non-mutating algorithms don t change the elements in the range, mutating algorithms do change the elements, and so on. These descriptions are based primarily on the underlying behavior or implementation of the algorithm that is, on the designer s perspective. In practice, we don t find this a useful categorization, so instead we ll organize them according to the problem you want to solve: Are you searching for an element or set of elements, performing an operation on each element, counting elements, replacing elements, and so on? This should help you find the algorithm you want more easily.

If you do not see a different header such as <utility> or <numeric> above the function declarations, it appears in <algorithm>. Also, all the algorithms are in the namespace std.

Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire