Tag Archives: algorithm

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:

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.

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.

The output for this sample is:

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.

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).

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.

The output is:

Assigning algorithms in the C++ Standard Library

The C++ Standard Library provides several algorithms for assigning values to a range (such as a container or a C-array).

fill and fill_n

std::fill assigns a given value to all the elements in a range. It is available in the header <algorithm>. In the following example all elements of a vector of integers are assigned the value 1.

std::fill_n is similar, but instead taking the bounds of a range it takes the beginning and a count and initializes N elements starting from the specified first element. You must make sure that first + count does not exceed the bounds of the range. The following example is an equivalent of the first:

generate and generate_n

These algorithms are similar to the first, but instead of taking a value to assign they take a function and assign the value returned by the function. They are also available in the header <algorithm>.

std::generate assigns the elements in a range the values returned by a function.

In the following example we initialize a vector of 10 elements with random numbers (using a Marsenne twister engine).

The result may look like this:

You can use lambdas as the function whose return value is stored into the range. The following example generates random numbers ranging from 1 to 100 with a uniform distribution.

Result may look like this:

std::generate_n is similar, but instead of taking the limits of the range it takes the beginning and a count and assigns the first N values returned by the function to the range. You must makes sure that first + count does not exceeds the bounds of the range.

In the following example we initialize the elements of a vector with values from 1 to N, where N is the size of the range.

The result is:

iota

std::iota is a new algorithm to C++11. It assigns the elements of a range with sequentially increasing values starting from a given value. The algorithm is available in header <numeric>.

The following example initializes the elements of a vector with values from 1 to N, where N is the size of the range (basically the same thing we did in the last example).

The result is:

Notice that the term iota is taken from the APL programming language and denotes the Greek letter used in various mathematical notations.