Chapter 25: Algorithms

Chapter 25 deals with the generalized subroutines for automatically transforming lemmings into gold.

Contents

Prerequisites

The neatest accomplishment of the algorithms chapter is that all the work is done via iterators, not containers directly. This means two important things:

  1. Anything that behaves like an iterator can be used in one of these algorithms. Raw pointers make great candidates, thus built-in arrays are fine containers, as well as your own iterators.
  2. The algorithms do not (and cannot) affect the container as a whole; only the things between the two iterator endpoints. If you pass a range of iterators only enclosing the middle third of a container, then anything outside that range is inviolate.

Even strings can be fed through the algorithms here, although the string class has specialized versions of many of these functions (for example, string::find()). Most of the examples on this page will use simple arrays of integers as a playground for algorithms, just to keep things simple. The use of N as a size in the examples is to keep things easy to read but probably won't be valid code. You can use wrappers such as those described in the containers chapter to keep real code readable.

The single thing that trips people up the most is the definition of range used with iterators; the famous "past-the-end" rule that everybody loves to hate. The iterators chapter of this document has a complete explanation of this simple rule that seems to cause so much confusion. Once you get range into your head (it's not that hard, honest!), then the algorithms are a cakewalk.

Return to top of page or to the FAQ.

Special swaps

If you call std::swap(x,y); where x and y are standard containers, then the call will automatically be replaced by a call to x.swap(y); instead.

This allows member functions of each container class to take over, and containers' swap functions should have O(1) complexity according to the standard. (And while "should" allows implementations to behave otherwise and remain compliant, this implementation does in fact use constant-time swaps.) This should not be surprising, since for two containers of the same type to swap contents, only some internal pointers to storage need to be exchanged.

Return to top of page or to the FAQ.

See license.html for copying conditions. Comments and suggestions are welcome, and may be sent to the libstdc++ mailing list.