# 25 Algorithms library [algorithms]

## 25.2 Non-modifying sequence operations [alg.nonmodifying]

### 25.2.1 All of [alg.all_of]

``` template <class InputIterator, class Predicate> bool all_of(InputIterator first, InputIterator last, Predicate pred); ```

Returns: true if [first,last) is empty or if pred(*i) is true for every iterator i in the range [first,last), and false otherwise.

Complexity: At most last - first applications of the predicate.

### 25.2.2 Any of [alg.any_of]

``` template <class InputIterator, class Predicate> bool any_of(InputIterator first, InputIterator last, Predicate pred); ```

Returns: false if [first,last) is empty or if there is no iterator i in the range [first,last) such that pred(*i) is true, and true otherwise.

Complexity: At most last - first applications of the predicate.

### 25.2.3 None of [alg.none_of]

``` template <class InputIterator, class Predicate> bool none_of(InputIterator first, InputIterator last, Predicate pred); ```

Returns: true if [first,last) is empty or if pred(*i) is false for every iterator i in the range [first,last), and false otherwise.

Complexity: At most last - first applications of the predicate.

### 25.2.4 For each [alg.foreach]

``` template<class InputIterator, class Function> Function for_each(InputIterator first, InputIterator last, Function f); ```

Requires: Function shall meet the requirements of MoveConstructible (Table [moveconstructible]). [ Note: Function need not meet the requirements of CopyConstructible (Table [copyconstructible]).  — end note ]

Effects: Applies f to the result of dereferencing every iterator in the range [first,last), starting from first and proceeding to last - 1. [ Note: If the type of first satisfies the requirements of a mutable iterator, f may apply nonconstant functions through the dereferenced iterator. — end note ]

Returns: std::move(f).

Complexity: Applies f exactly last - first times.

Remarks: If f returns a result, the result is ignored.

### 25.2.5 Find [alg.find]

``` template<class InputIterator, class T> InputIterator find(InputIterator first, InputIterator last, const T& value); template<class InputIterator, class Predicate> InputIterator find_if(InputIterator first, InputIterator last, Predicate pred); template<class InputIterator, class Predicate> InputIterator find_if_not(InputIterator first, InputIterator last, Predicate pred); ```

Returns: The first iterator i in the range [first,last) for which the following corresponding conditions hold: *i == value, pred(*i) != false, pred(*i) == false. Returns last if no such iterator is found.

Complexity: At most last - first applications of the corresponding predicate.

### 25.2.6 Find end [alg.find.end]

``` template<class ForwardIterator1, class ForwardIterator2> ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); ```

Effects: Finds a subsequence of equal values in a sequence.

Returns: The last iterator i in the range [first1,last1 - (last2 - first2)) such that for every non-negative integer n < (last2 - first2), the following corresponding conditions hold: *(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false. Returns last1 if [first2,last2) is empty or if no such iterator is found.

Complexity: At most (last2 - first2) * (last1 - first1 - (last2 - first2) + 1) applications of the corresponding predicate.

### 25.2.7 Find first [alg.find.first.of]

``` template<class InputIterator, class ForwardIterator> InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2); template<class InputIterator, class ForwardIterator, class BinaryPredicate> InputIterator find_first_of(InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate pred); ```

Effects: Finds an element that matches one of a set of values.

Returns: The first iterator i in the range [first1,last1) such that for some iterator j in the range [first2,last2) the following conditions hold: *i == *j, pred(*i,*j) != false. Returns last1 if [first2,last2) is empty or if no such iterator is found.

Complexity: At most (last1-first1) * (last2-first2) applications of the corresponding predicate.

### 25.2.8 Adjacent find [alg.adjacent.find]

``` template<class ForwardIterator> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last); template<class ForwardIterator, class BinaryPredicate> ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate pred); ```

Returns: The first iterator i such that both i and i + 1 are in the range [first,last) for which the following corresponding conditions hold: *i == *(i + 1), pred(*i, *(i + 1)) != false. Returns last if no such iterator is found.

Complexity: For a nonempty range, exactly min((i - first) + 1, (last - first) - 1) applications of the corresponding predicate, where i is adjacent_find's return value.

### 25.2.9 Count [alg.count]

``` template<class InputIterator, class T> typename iterator_traits<InputIterator>::difference_type count(InputIterator first, InputIterator last, const T& value); template<class InputIterator, class Predicate> typename iterator_traits<InputIterator>::difference_type count_if(InputIterator first, InputIterator last, Predicate pred); ```

Effects: Returns the number of iterators i in the range [first,last) for which the following corresponding conditions hold: *i == value, pred(*i) != false.

Complexity: Exactly last - first applications of the corresponding predicate.

### 25.2.10 Mismatch [mismatch]

``` template<class InputIterator1, class InputIterator2> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); template<class InputIterator1, class InputIterator2, class BinaryPredicate> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred); template<class InputIterator1, class InputIterator2> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template <class InputIterator1, class InputIterator2, class BinaryPredicate> pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate pred); ```

Remarks: If last2 was not given in the argument list, it denotes first2 + (last1 - first1) below.

Returns: A pair of iterators i and j such that j == first2 + (i - first1) and i is the first iterator in the range [first1,last1) for which the following corresponding conditions hold:

• j is in the range [first2, last2).

• !(*i == *(first2 + (i - first1)))

• pred(*i, *(first2 + (i - first1))) == false

Returns the pair first1 + min(last1 - first1, last2 - first2) and first2 + min(last1 - first1, last2 - first2) if such an iterator i is not found.

Complexity: At most last1 - first1 applications of the corresponding predicate.

### 25.2.11 Equal [alg.equal]

``` template<class InputIterator1, class InputIterator2> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2); template<class InputIterator1, class InputIterator2, class BinaryPredicate> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred); template<class InputIterator1, class InputIterator2> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2); template<class InputIterator1, class InputIterator2, class BinaryPredicate> bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate pred); ```

Remarks: If last2 was not given in the argument list, it denotes first2 + (last1 - first1) below.

Returns: If last1 - first1 != last2 - first2, return false. Otherwise return true if for every iterator i in the range [first1,last1) the following corresponding conditions hold: *i == *(first2 + (i - first1)), pred(*i, *(first2 + (i - first1))) != false. Otherwise, returns false.

Complexity: No applications of the corresponding predicate if InputIterator1 and InputIterator2 meet the requirements of random access iterators and last1 - first1 != last2 - first2. Otherwise, at most min(last1 - first1, last2 - first2) applications of the corresponding predicate.

### 25.2.12 Is permutation [alg.is_permutation]

``` template<class ForwardIterator1, class ForwardIterator2> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2); template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate pred); template<class ForwardIterator1, class ForwardIterator2> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); ```

Requires: ForwardIterator1 and ForwardIterator2 shall have the same value type. The comparison function shall be an equivalence relation.

Remarks: If last2 was not given in the argument list, it denotes first2 + (last1 - first1) below.

Returns: If last1 - first1 != last2 - first2, return false. Otherwise return true if there exists a permutation of the elements in the range [first2,first2 + (last1 - first1)), beginning with ForwardIterator2 begin, such that equal(first1, last1, begin) returns true or equal(first1, last1, begin, pred) returns true; otherwise, returns false.

Complexity: No applications of the corresponding predicate if ForwardIterator1 and ForwardIterator2 meet the requirements of random access iterators and last1 - first1 != last2 - first2. Otherwise, exactly distance(first1, last1) applications of the corresponding predicate if equal(first1, last1, first2, last2) would return true if pred was not given in the argument list or equal(first1, last1, first2, last2, pred) would return true if pred was given in the argument list; otherwise, at worst Ο(N2), where N has the value distance(first1, last1).

### 25.2.13 Search [alg.search]

``` template<class ForwardIterator1, class ForwardIterator2> ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred); ```

Effects: Finds a subsequence of equal values in a sequence.

Returns: The first iterator i in the range [first1,last1 - (last2-first2)) such that for every non-negative integer n less than last2 - first2 the following corresponding conditions hold: *(i + n) == *(first2 + n), pred(*(i + n), *(first2 + n)) != false. Returns first1 if [first2,last2) is empty, otherwise returns last1 if no such iterator is found.

Complexity: At most (last1 - first1) * (last2 - first2) applications of the corresponding predicate.

``` template<class ForwardIterator, class Size, class T> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value); template<class ForwardIterator, class Size, class T, class BinaryPredicate> ForwardIterator search_n(ForwardIterator first, ForwardIterator last, Size count, const T& value, BinaryPredicate pred); ```

Requires: The type Size shall be convertible to integral type ([conv.integral], [class.conv]).

Effects: Finds a subsequence of equal values in a sequence.

Returns: The first iterator i in the range [first,last-count) such that for every non-negative integer n less than count the following corresponding conditions hold: *(i + n) == value, pred(*(i + n),value) != false. Returns last if no such iterator is found.

Complexity: At most last - first applications of the corresponding predicate.