Why algorithms
Standard algorithms have a prominent value in the C++ standard template library (STL). They present the great advantage of expressing an operation applied on a range of elements in a container. In this series, I am going to review all the algorithms introduced in the C++11 standard, presenting it in digestible chunks, and will provide at least an example of application for each one.
all_of
We might want to determine whether all elements in a range satisfy some property. For example, suppose we want to find out if all the persons subscribed to this blog come from Europe. We might keep a record of a Person in the form:
1  enum Continent { 
Now say that we have a std::vector
of customers. To find the answer to our previous question, we might do something like the following:
1  // declare p1, p2, p3 
Formally, the signature for all_of
is:
1  template <class InputIterator, class Predicate> 
One gotcha: the algorithms returns true if the range is empty. It runs in linear time on the number of elements in the range. You can find the complete code is at this link.
any_of
Now suppose we want to know whether at least one of the customers is American. We can accomplish this with the algorithm std::any_of
, which intuitively enough can be used like the following:
1  // ... 
As you can see, we recycled the Predicate. The pitfall here is the reverse of the one for all_of: this algorithms returns false if the range is empty. Find the gist here.
none_of
Letâ€™s change example. Say we have a vector of Shape class pointers. Shape can be derived in order to provide more specific properties:
1  struct Shape { 
Now we want to see whether in a vector of Shape pointers there is any Triangle. Since none_of
is a negative predicate, and reasoning in negative terms is generally harder, we define the predicate outside the invocation of the algorithm, to make things clearer:
1 

We use the dynamic_cast
to determine if the pointer points to a Triangle, in which case it would return a nonnull pointer. The std::none_of
algorithm, as the ones mentioned above, has linear complexity depending on the number of elements in the range. Grab the gist here.
In the next episode
We have covered three basic algorithms for testing properties of elements in a container: all_of
checks whether all the elements in a range satisfy a predicate, any_of
checks whether at least one element satisfies the predicate, while none_of
checks that none of the elements satisfies the predicate. Lambdas give us a way of expressing very clearly the predicate: if you feel uncomfortable with them, you might want to have a look at the miniseries I have written about them (part 1 and part 2).
In the next installment, we are going to get into more algorithms provided by the standard.