Tuesday, December 6, 2011

stl algorithms

stl algorithms example

The STL provides several standard algorithms for the processing of elements of collections. These algorithms offer general fundamental services, such as searching, sorting, copying, reordering, modifying, and numeric processing. 

Algorithms are not member functions of the container classes. Instead, they are global functions that operate with iterators. This has an important advantage: Instead of each algorithm being implemented for each container type, all are implemented only once for any container type. The algorithm might even operate on elements of different container types. You can also use the algorithms for user-defined container types. All in all, this concept reduces  the amount of code and increases the power and the flexibility of the library.

Note that this is not an object-oriented programming paradigm; it is a generic functional programming paradigm. Instead of data and operations being unified, as in object-oriented programming, they are separated into distinct parts that can interact via a certain interface. However, this concept also has its price: First, the usage is not intuitive. Second, some combinations of data structures and algorithms might not work. Even worse, a  combination of a container type and an algorithm might be possible but not useful (for example, it may lead to bad performance). Thus, it is important to learn the concepts and the pitfalls of the STL to benefit from it without abusing it.

Let's start with a simple example of the use of STL algorithms. Consider the following program, which shows some algorithms and their usage:

To be able to call the algorithms, you must include the header file <algorithm>:

#include <algorithm>

The first two algorithms called are min_element() and max_element(). They are called with two parameters that define the range of the processed elements. To process all elements of a container you simply use begin() and end(). Both algorithms return an iterator for the minimum and maximum elements respectively. Thus, in the statement

pos = min_element (coll.begin(), coll.end());

the min_element() algorithm returns the position of the minimum element (if there is more than one, the algorithm returns the first). The next statement prints that element:

cout << "min: " << *pos << endl;

Of course, you could do both in one statement:

cout << *max_element(coll.begin(), coll.end()) << endl;

The next algorithm called is sort(). As the name indicates, it sorts the elements of the range defined by the two arguments. As usual, you could pass an optional sorting criterion. The default sorting criterion is operator <. Thus, in this example all elements of the container are sorted in ascending order:

sort (coll.begin(), coll.end());

So afterward, the vector contains the elements in this order:

1 2 3 4 5 6

The find() algorithm searches for a value inside the given range. In this example, it searches the first element that is equal to the value 3 in the whole container:

pos = find (coll.begin(), coll.end(), //range
3); //value

If the find() algorithm is successful, it returns the iterator position of the element found. If it fails, it returns the end of the range, the past-the-end iterator, which is passed as the second argument. In this example, the value 3 is found as the third element, so afterward pos refers to the third element of coll.

The last algorithm called in the example is reverse(), which reverses the elements of the passed range. Here the third element that was found by the find() algorithms and the past-theend iterator are passed as arguments:

reverse (pos, coll.end());

This call reverses the order of the third element up to the last one. The output of the program is as follows: 

min: 1

max: 6
1 2 6 5 4 3

See Also:

No comments:

Post a Comment