Five new algorithms to C++11 that you should know about

C++11 added a bunch of new general purpose algorithms to the <algorithm> header. In this article we will look at five of them that C++ developers should know about.

all_of, any_of and none_of

These are actually three, not just a single algorithm, all_of, any_of, none_of, but they are very similar. They check if the supplied unary predicate return true for all, any or no element in a range.

Here are several examples:

int numbers[] = {1, 2, 42, 7, 0};

auto is_positive = [](int const n){return n >= 0;};
std::cout << std::boolalpha 
          << std::all_of(std::begin(numbers), std::end(numbers), is_positive)
          << std::endl;

auto is_zero = [](int const n) {return n == 0;};
std::cout << std::boolalpha
          << std::any_of(std::begin(numbers), std::end(numbers), is_zero)
          << std::endl;

std::vector<std::string> words = {"to", "be", "or", "not"};

auto is_empty = [](std::string const & s) {return s.empty();};
std::cout << std::boolalpha
          << std::none_of(std::begin(words), std::end(words), is_empty)
          << std::endl;

is_sorted and is_sorted_until

The first algorithm, is_sorted, checks if the elements of the range are sorted ascending. There are two overloads of the function, the first uses operator< and the second takes a comparison function (that return true if the first element is less than the second) and uses that for comparing the elements in the range.

int numbers[] = {1, 2, 42, 7, 0};

std::cout << std::boolalpha
          << std::is_sorted(std::begin(numbers), std::end(numbers))
          << std::endl;


std::vector<std::string> words = {"to", "be", "or", "not"};

auto smaller_length = [](std::string const & first, std::string const & second) 
                      {
                         return first.length() < second.length();
                      };
std::cout << std::boolalpha
          << std::is_sorted(std::begin(words), std::end(words), smaller_length)
          << std::endl;

The second algorithm, is_sorted_until, is similar in that it checks that the elements of a range are sorted ascending. However, the function does not return a boolean value, but an iterator to the upper bound of the largest sorted sub-range (starting at the beginning of the examined range), i.e. the next beyond the last sorted element. There are two overloads, the first uses operator< and the second takes a comparison function, just like is_sorted does.

int numbers[] = {1, 2, 42, 7, 0};

auto last = std::is_sorted_until(std::begin(numbers), std::end(numbers));
std::cout << "upper bound = " << *(last-1) << std::endl;
std::cout << "sort size   = " << std::distance(std::begin(numbers), last) << std::endl;

The output for this sample is:

upper bound = 42
sort size   = 3

is_partitioned

Algorithm is_partitioned checks whether a range is partitioned, i.e. sorted according to the supplied unary predicate so that all elements that satisfy the predicate come before all elements that do not satisfy the predicate. The function returns true if the range is empty.

struct message
{
   std::string text;
   bool delivered;
};

std::vector<message> messages = {
   {"first message", true},
   {"second message", true},
   {"third message", false},
   {"fourth message", false},
   {"fifth message", true},
};

auto is_delivered = [](message const & msg) {return msg.delivered;};

// is not partitioned
std::cout << std::boolalpha
          << std::is_partitioned(std::begin(messages), std::end(messages), is_delivered)
          << std::endl;

// do partition
std::partition(std::begin(messages), std::end(messages), is_delivered);

// is partitioned
std::cout << std::boolalpha
          << std::is_partitioned(std::begin(messages), std::end(messages), is_delivered)
          << std::endl;

is_permutation

Algorithm is_permutation determines whether a range is a permutation of another range. There are two overloads, the first uses operator== to compare the elements of the two ranges and the second takes a binary predicate (that returns true if two elements are equal).

int numbers[] = {1, 2, 42, 7, 0};
int numbers2[] = {0, 1, 2, 7, 42};
std::cout << std::boolalpha
          << std::is_permutation(std::begin(numbers), std::end(numbers), std::begin(numbers2))
          << std::endl;

minmax_element

The minmax_element algorithm finds both the minimum and the maximum element in a range and returns a pair of iterators to these elements. It is important to note that:

  • if the range is empty it returns std::make_pair(first, first)
  • if there is more than one element equal to the minimum value it returns an iterator to the first of these elements
  • if there is more than one element equal to the maximum value it returns an iterator to the last of these elements

There are two overloads, the first uses operator< to compare elements and the second uses a provided comparison function.

std::vector<int> numbers = {1, 2, 7, 42, 0};
std::vector<int>::iterator minimum, maximum;
std::tie(minimum, maximum) = std::minmax_element(std::begin(numbers), std::end(numbers));

std::cout << "minimum = " << *minimum << std::endl;
std::cout << "maximum = " << *maximum << std::endl;

The output is:

minimum = 0
maximum = 42

2 thoughts on “Five new algorithms to C++11 that you should know about”

Leave a Comment