The algorithms delivered with the library are divided into four groups:
group algorithm type
1 mutating sequence
operations
2 non-mutating sequence
operations
3 sorting and related
operations
4 generalized numeric
operations
Table 6: STL algorithm types
Group 1 contains algorithms which don't change (mutate) the order of the elements in a container, this has not to be true for algorithms of group 2.
The algorithm for_each of group 1 takes two iterators and a function f of type Function as arguments:
template <class InputIterator, class Function> Function for_each (InputIterator first, InputIterator last, Function f);
The template argument f of type Function must not be mixed up with a "pure" C++ function, because such a function can only be used in a roundabout way (see section 4.4.3). The template function for_each expects a function object (section 2.2) as argument. f is assumed not to apply any non-constant function through the dereferenced iterator.
for_each applies f to the result of dereferencing every iterator in the range [first, last) and returns f. If f returns a value, it is ignored. The following example computes the sum of all elements in the range [first, last).
template <class T>
class sum_up {
public:
static T sum;
void operator() (const T& value) { sum += value; }
const T& read_sum() { return sum; }
};
int sum_up<int>::sum;
void main(void) {
deque<int> d (3,2);
sum_up<int> s;
for_each (d.begin(), d.end(), s);
cout << s.read_sum();
}
Output: 6
Note: To use a deque include deque.h
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last,
const T& value);
find takes a range and a reference to a value of arbitrary type. It assumes that operator== for the value type of the iterator and T is defined. Additionally to find an algorithm named find_if is provided, which takes a predicate pred of type Predicate.
template <class InputIterator, class Predicate>
InputIterator find_if(InputIterator first, InputIterator last,
Predicate pred);
find_if (like find) returns the first iterator i in the range [first, last), for which the following condition holds: pred(*i) = true. If such an iterator doesn't exist, a past-the end iterator is returned.
template <class T>
class find_first_greater {
public:
find_first_greater() : x(0) {}
find_first_greater(const& xx) : x(xx) {}
int operator() (const T& v) { return v > x; }
private:
T x;
};
vector<int> v;
// fill vector with 1 2 3 4 5
vector<int>::iterator i = find_if (v.begin(), v.end(), find_first_greater<int> (3));
i != v.end()? cout << *i : cout << "not found";
Output: 4
Some algorithms, like adjacent_find, take a binary predicate binary_pred of type BinaryPredicate. adjacent_find returns the first iterator i, for which the following condition holds: binary_pred (*i, *(i+1)) == true.
template <class InputIterator, class BinaryPredicate>
InputIterator adjacent_find(InputIterator first, InputIterator last,
BinaryPredicate binary_pred);
For example, if you want to find the first pair of values, whose product is odd, you could write this:
template <class T>
class prod_odd {
public:
int operator() (const T& v1, const T& v2)
{ return v1%2 != 0 && v2%2 != 0; }
};
list<int> l;
// fill list with 2 9 6 13 7
list<int>::iterator i = adjacent_find (l.begin(), l.end(),
prod_odd<int>());
if (i != l.end()) { cout << *i << " "; i++; cout << *i++; }
else cout << "not found";
Output: 13 7
template <class Iterator, class OutputIterator, class Predicate, class T>
OutputIterator replace_copy_if(Iterator first, Iterator last,
OutputIterator result, Predicate pred,
const T& new_value);
All the operations in group 3 have two versions. One that takes a function object comp of type Compare and another that uses operator< to do the comparison. operator< and comp, respectively, have to induce a total ordering relation on the values to ensure that the algorithms work correctly.
vector<int> v; // fill v with 3 7 5 4 2 6 sort (v.begin(), v.end() ); sort (v.begin(), v.end(), less<int>() ); sort (v.begin(), v.end(), greater<int>() );
Output: 2 3 4 5 6 7
Output: 2 3 4 5 6 7
Output: 7 6 5 4 3 2
All the provided function objects are derived either from unary_function or from binary_function to simplify the type definitions of the argument and result types.
template <class Arg, class Result>
struct unary_function {
typedef Arg argument_type;
typedef Result result_type;
};
template <class Arg1, class Arg2, class Result>
struct binary_function {
typedef Arg1 first_argument_type;
typedef Arg2 second_argument_type;
typedef Result result_type;
};
STL provides function objects for all of the arithmetic operations in the language. plus, minus, times, divides and modulus are binary operations whereas negate is a unary operation. As examples, look at plus and negate, the other functions objects are defined accordingly.
template <class T>
struct plus : binary_function<T, T, T> {
T operator()(const T& x, const T& y) const { return x + y; }
};
template <class T>
struct negate : unary_function<T, T> {
T operator()(const T& x) const { return -x; }
};
The mentioned comparison function objects are equal_to, not_equal_to, greater, less, greater_equal and less_equal, they are all binary function objects. less shall serve as example.
template <class T>
struct less : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x < y; }
};
Additionally, the binary function objects logical_and and logical_or exist, logical_not is a unary function object.
template <class T>
struct logical_and : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x && y; }
};
template <class T>
struct logical_not : unary_function<T, bool> {
bool operator()(const T& x) const { return !x; }
};
The rest of the function object implementations can be found in [2], 6.
In group 4, the algorithm accumulate takes a binary operation binary_op of type BinaryOperation. The algorithm accumulate does the same as for_each used with the function object sum_up (presented earlier in this section).
template <class InputIterator, class T> T accumulate(InputIterator first, InputIterator last, T init);
For each iterator i in [first, last), acc = acc + *i is computed, then acc is returned. acc can be initialized with a starting value. Instead of operator+, an arbitrary binary operation can be defined by the user, or a STL function object can be used.
vector<int> v; v.push_back (2); v.push_back (5); cout << accumulate (v.begin(), v.end(), 10, divides<int>() );
Output: 1
We decide to use a non-associative container (see section 4.1, introduction), which holds the dictionary. The dictionary is assumed to be sorted. Now, we express the spell-checker functionality in pseudo code.
for every word in text check against dictionary if not in dictionary write to output
This pseudo code can be expressed in different way:
copy every word of text to output that is not in the dictionary
The last pseudo code variation can more directly be translated into a STL program. Since we need a mechanism that tells us if a word is or is not in the dictionary, we encapsulate this functionality in a function object.
template <class bidirectional_iterator, class T>
class nonAssocFinder {
public:
nonAssocFinder(bidirectional_iterator begin,
bidirectional_iterator end) :
_begin(begin), _end(end) {}
bool operator() (const T& word) {
return binary_search(_begin, _end, word); }
private:
bidirectional_iterator _begin;
bidirectional_iterator _end;
};
The function object nonAssocFinder is initialized with the iterators begin and end that have to be at least of the bidirectional iterator category. The function call operator takes a word and returns a boolean value, which states if the word has been found in the dictionary (the type bool is defined by STL). This boolean value is returned by the STL algorithm binary_search.
template <class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last,
const T& value);
The first thing we do in our program is to define a dictionary as a vector of type string and fill it out of an input stream.
typedef vector<string> dict_type;
ifstream dictFile("dict.txt");
ifstream wordsFile("words.txt");
dict_type dictionary;
copy (istream_iterator<string, ptrdiff_t>(dictFile),
istream_iterator<string, ptrdiff_t>(),
back_inserter(dictionary));
Note: To use the string type include cstring.h
Then we use the STL algorithm remove_copy_if to achieve the functionality wanted.
template <class InputIterator, class OutputIterator, class Predicate> OutputIterator remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred);
remove_copy_if writes all elements referred to by the iterator i in the range [first, last) to the output iterator result, for which the following condition does not hold:
pred(*i) == true. The algorithm returns the end of the resulting range. The rest of the spell-checker program proves to be a single statement.
remove_copy_if (
istream_iterator<string, ptrdiff_t>(wordsFile),
istream_iterator<string, ptrdiff_t>(),
ostream_iterator<string>(cout, "\n"),
nonAssocFinder<dict_type::iterator,
dict_type::value_type>
(dictionary.begin(), dictionary.end()));
remove_copy_if reads words from the input stream wordsFile and writes the words for which nonAssocFinder returns false (i.e. which are either not found or misspelled) to cout.
Because STL provides its own operator<, operator< for the string type must be excluded from cstring.h when using Borland C++ (this is shown in section 3.3). To enable the compiler to compare strings, a template specialization for strings has to be provided, which looks exactly like the one from cstring.h. Use it to make the spell-checker example work.
inline int operator< (const string far& s1, const string far& s2) {
return s1.compare(s2) < 0;
}
The components used are:
Now you should have the basics to understand the chapter on algorithms in [2], 10. Since this document is very theoretical, the algorithms in combination with a description and examples can be found in [4], 6. A complete STL example can be found in [4], 5.
Johannes Weidl (J.Weidl@infosys.tuwien.ac.at) - Apr 16, 1996