Jonathan Boccara's blog

Predicates on ranges with the STL

Published February 23, 2017 - 6 Comments

In this episode of the STL learning resource, we see algorithms that can be used in a variety of contexts but that have one thing in common: they return a boolean characteristic of one or several ranges.

The *_of series

The STL provides 3 algorithms that indicates whether all, some, or none of the elements of a range satisfy a given condition. The condition is itself expressed by a predicate, that is to say a function pointer (or object) that take an element of the range and returns a bool.

These 3 algorithms are:

  • std::all_of: checks whether all of the elements in the range satisfy the given condition. It returns true if the range is empty, so its semantic is more precisely checking if no element does not satisfy the condition.
  • std::any_of: checks whether any one of the elements in the range satisfies the given condition. It returns false if the range is empty.
  • std::none_of: checks whether no element in the range satisfy the given condition. It returns true if the range is empty.

This is it for the STL, but Boost goes a bit further and proposes the following algorithm:

  • boost::algorithm::one_of: checks whether exactly one element in the range satisfies the given condition. It (quite expectably) returns false if the range is empty.

Boost also provides “*_equal” versions of each of the above algorithms, that accept a range and a value, and have the same behaviour as their native counterpart, with the condition being that the element is equal to the passed value. The comparison is done with operator== and cannot be customised.

And in the case of an empty range, they behave the same way as their native counterparts.

std::equal

std::equal can be used to compare 2 ranges, checking if elements are respectively equal (comparison is done with operator== or with a custom comparator). Note that std::equal takes a 1.5-Range, meaning that the first range is indicated by a begin and an end iterator, while the second range misses the end iterator:

So the algorithm goes on until the end of the 1st range and performs comparisons with the 2nd range even if it shorter, because it just doesn’t know how long the second range is.

For std::equal, this is both unnatural and dangerous:

  • this is unnatural, because if the 1st range has, say, N elements, std::equal returns true as long as the first N elements of the 2nd range are equal to the N elements of the 1st range, and even if the 2nd range has more elements than the 1st range.
  • this is dangerous, because if the 2nd range is shorter than the 1st range, the algorithm will go past its end, leading to undefined behaviour.

Starting from C++14 this is corrected, with new overloads of std::equal taking 2 complete ranges with both begins and ends.

std::mismatch and std::lexicographical_compare

These 2 algorithms let you implement some sort of ordering on ranges, which you can use to compare 2 ranges.

More specifically:

std::mismatch compares respective elements of its 2 input ranges starting from their beginning, and returns the first place where they differ, in the form of an std::pair of iterators: the first element of the pair is an iterator to the first mismatching element in the 1st range, and second element of the pair is an iterator to the first mismatching element in the 2nd range.

It performs comparisons with operator== (or a custom comparator).

Note that std::mismatch also suffers from the 1.5-Range problem, so make sure you pass the shorter range first. This can be cumbersome if you do use it to make comparisons. But just as for std::equal, the 1.5-Range problem is solved for std::mismatch starting from C++14.

std::lexicographical_compare actually provides an order on ranges, and operates the same way as a dictionary would provide an order on strings, hence its name. It compares elements two by two with operator< (or a custom comparator).

std::lexicographical_compare takes 2 full ranges so it does not have the 1.5-Range problem.

std::lexicographical_compare can be quite handy for allowing a natural and easy to code order on classes wrapping a container. For instance, say when treating CSV-like data that we design an Entry class that represents all the pieces of data separated by commas on a given line in the CSV file:

This allows for an easy sort of entries in a natural way, which gives access to rapid searching and related functionalities (insertion, and so on). It also makes Entry compatible with sorted associative containers like std::map, std::set et alii.

Liked it ? Share this post ! Facebooktwittergoogle_plus    Don't want to miss out ? Follow:   twitterrss

Receive regular updates to make your code more expressive.