# 11 Algorithms library [algorithms]

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

### 11.3.1 All of [alg.all_of]

``` template <InputIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> bool all_of(I first, S last, Pred pred, Proj proj = Proj{}); template <InputRange Rng, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> bool all_of(Rng&& rng, Pred pred, Proj proj = Proj{}); ```

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

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

### 11.3.2 Any of [alg.any_of]

``` template <InputIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> bool any_of(I first, S last, Pred pred, Proj proj = Proj{}); template <InputRange Rng, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> bool any_of(Rng&& rng, Pred pred, Proj proj = Proj{}); ```

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

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

### 11.3.3 None of [alg.none_of]

``` template <InputIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> bool none_of(I first, S last, Pred pred, Proj proj = Proj{}); template <InputRange Rng, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> bool none_of(Rng&& rng, Pred pred, Proj proj = Proj{}); ```

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

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

### 11.3.4 For each [alg.foreach]

``` template <InputIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryInvocable<projected<I, Proj>> Fun> tagged_pair<tag::in(I), tag::fun(Fun)> for_each(I first, S last, Fun f, Proj proj = Proj{}); template <InputRange Rng, class Proj = identity, IndirectUnaryInvocable<projected<iterator_t<Rng>, Proj>> Fun> tagged_pair<tag::in(safe_iterator_t<Rng>), tag::fun(Fun)> for_each(Rng&& rng, Fun f, Proj proj = Proj{}); ```

Effects: Calls invoke(f, invoke(proj, *i)) for every iterator i in the range [first,last), starting from first and proceeding to last - 1. [ Note: If the result of invoke(proj, *i) is a mutable reference, f may apply nonconstant functions. — end note ]

Returns: {last, std::move(f)}.

Complexity: Applies f and proj exactly last - first times.

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

Note: The requirements of this algorithm are more strict than those specified in ISO/IEC 14882:2014 §[alg.foreach]. This algorithm requires Fun to satisfy CopyConstructible, whereas the algorithm in the C++ Standard requires only MoveConstructible.  — end note ]

### 11.3.5 Find [alg.find]

``` template <InputIterator I, Sentinel<I> S, class T, class Proj = identity> requires IndirectRelation<equal_to<>, projected<I, Proj>, const T*> I find(I first, S last, const T& value, Proj proj = Proj{}); template <InputRange Rng, class T, class Proj = identity> requires IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*> safe_iterator_t<Rng> find(Rng&& rng, const T& value, Proj proj = Proj{}); template <InputIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> I find_if(I first, S last, Pred pred, Proj proj = Proj{}); template <InputRange Rng, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> safe_iterator_t<Rng> find_if(Rng&& rng, Pred pred, Proj proj = Proj{}); template <InputIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> I find_if_not(I first, S last, Pred pred, Proj proj = Proj{}); template <InputRange Rng, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> safe_iterator_t<Rng> find_if_not(Rng&& rng, Pred pred, Proj proj = Proj{}); ```

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

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

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

``` template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2, class Proj = identity, IndirectRelation<I2, projected<I1, Proj>> Pred = equal_to<>> I1 find_end(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{}, Proj proj = Proj{}); template <ForwardRange Rng1, ForwardRange Rng2, class Proj = identity, IndirectRelation<iterator_t<Rng2>, projected<iterator_t<Rng>, Proj>> Pred = equal_to<>> safe_iterator_t<Rng1> find_end(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{}, Proj proj = Proj{}); ```

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 condition holds: invoke(pred, invoke(proj, *(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 and projection.

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

``` template <InputIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2, class Proj1 = identity, class Proj2 = identity, IndirectRelation<projected<I1, Proj1>, projected<I2, Proj2>> Pred = equal_to<>> I1 find_first_of(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); template <InputRange Rng1, ForwardRange Rng2, class Proj1 = identity, class Proj2 = identity, IndirectRelation<projected<iterator_t<Rng1>, Proj1>, projected<iterator_t<Rng2>, Proj2>> Pred = equal_to<>> safe_iterator_t<Rng1> find_first_of(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); ```

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 condition holds: invoke(pred, invoke(proj1, *i), invoke(proj2, *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 and the two projections.

``` template <ForwardIterator I, Sentinel<I> S, class Proj = identity, IndirectRelation<projected<I, Proj>> Pred = equal_to<>> I adjacent_find(I first, S last, Pred pred = Pred{}, Proj proj = Proj{}); template <ForwardRange Rng, class Proj = identity, IndirectRelation<projected<iterator_t<Rng>, Proj>> Pred = equal_to<>> safe_iterator_t<Rng> adjacent_find(Rng&& rng, Pred pred = Pred{}, Proj proj = Proj{}); ```

Returns: The first iterator i such that both i and i + 1 are in the range [first,last) for which the following corresponding condition holds: invoke(pred, invoke(proj, *i), invoke(proj, *(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, and no more than twice as many applications of the projection.

### 11.3.9 Count [alg.count]

``` template <InputIterator I, Sentinel<I> S, class T, class Proj = identity> requires IndirectRelation<equal_to<>, projected<I, Proj>, const T*> difference_type_t<I> count(I first, S last, const T& value, Proj proj = Proj{}); template <InputRange Rng, class T, class Proj = identity> requires IndirectRelation<equal_to<>, projected<iterator_t<Rng>, Proj>, const T*> difference_type_t<iterator_t<Rng>> count(Rng&& rng, const T& value, Proj proj = Proj{}); template <InputIterator I, Sentinel<I> S, class Proj = identity, IndirectUnaryPredicate<projected<I, Proj>> Pred> difference_type_t<I> count_if(I first, S last, Pred pred, Proj proj = Proj{}); template <InputRange Rng, class Proj = identity, IndirectUnaryPredicate<projected<iterator_t<Rng>, Proj>> Pred> difference_type_t<iterator_t<Rng>> count_if(Rng&& rng, Pred pred, Proj proj = Proj{}); ```

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

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

### 11.3.10 Mismatch [mismatch]

``` template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2, class Proj1 = identity, class Proj2 = identity, IndirectRelation<projected<I1, Proj1>, projected<I2, Proj2>> Pred = equal_to<>> tagged_pair<tag::in1(I1), tag::in2(I2)> mismatch(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); template <InputRange Rng1, InputRange Rng2, class Proj1 = identity, class Proj2 = identity, IndirectRelation<projected<iterator_t<Rng1>, Proj1>, projected<iterator_t<Rng2>, Proj2>> Pred = equal_to<>> tagged_pair<tag::in1(safe_iterator_t<Rng1>), tag::in2(safe_iterator_t<Rng2>)> mismatch(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); ```

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

• !invoke(pred, invoke(proj1, *i), invoke(proj2, *(first2 + (i - first1))))

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 and both projections.

### 11.3.11 Equal [alg.equal]

``` template <InputIterator I1, Sentinel<I1> S1, InputIterator I2, Sentinel<I2> S2, class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity> requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2> bool equal(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); template <InputRange Rng1, InputRange Rng2, class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity> requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2> bool equal(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); ```

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

Complexity: No applications of the corresponding predicate and projections if:

• SizedSentinel<S1, I1> is satisfied, and

• SizedSentinel<S2, I2> is satisfied, and

• last1 - first1 != last2 - first2.

Otherwise, at most min(last1 - first1, last2 - first2) applications of the corresponding predicate and projections.

### 11.3.12 Is permutation [alg.is_permutation]

``` template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2, class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity> requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2> bool is_permutation(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); template <ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity> requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2> bool is_permutation(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); ```

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 I2 begin, such that equal(first1, last1, begin, pred, proj1, proj2) returns true ; otherwise, returns false.

Complexity: No applications of the corresponding predicate and projections if:

• SizedSentinel<S1, I1> is satisfied, and

• SizedSentinel<S2, I2> is satisfied, and

• last1 - first1 != last2 - first2.

Otherwise, exactly last1 - first1 applications of the corresponding predicate and projections if equal(first1, last1, first2, last2, pred, proj1, proj2) would return true; otherwise, at worst Ο(N2), where N has the value last1 - first1.

### 11.3.13 Search [alg.search]

``` template <ForwardIterator I1, Sentinel<I1> S1, ForwardIterator I2, Sentinel<I2> S2, class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity> requires IndirectlyComparable<I1, I2, Pred, Proj1, Proj2> I1 search(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = Pred{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); template <ForwardRange Rng1, ForwardRange Rng2, class Pred = equal_to<>, class Proj1 = identity, class Proj2 = identity> requires IndirectlyComparable<iterator_t<Rng1>, iterator_t<Rng2>, Pred, Proj1, Proj2> safe_iterator_t<Rng1> search(Rng1&& rng1, Rng2&& rng2, Pred pred = Pred{}, Proj1 proj1 = Proj1{}, Proj2 proj2 = Proj2{}); ```

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 condition holds:

```invoke(pred, invoke(proj1, *(i + n)), invoke(proj2, *(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 and projections.

``` template <ForwardIterator I, Sentinel<I> S, class T, class Pred = equal_to<>, class Proj = identity> requires IndirectlyComparable<I, const T*, Pred, Proj> I search_n(I first, S last, difference_type_t<I> count, const T& value, Pred pred = Pred{}, Proj proj = Proj{}); template <ForwardRange Rng, class T, class Pred = equal_to<>, class Proj = identity> requires IndirectlyComparable<iterator_t<Rng>, const T*, Pred, Proj> safe_iterator_t<Rng> search_n(Rng&& rng, difference_type_t<iterator_t<Rng>> count, const T& value, Pred pred = Pred{}, Proj proj = Proj{}); ```

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 condition holds: invoke(pred, invoke(proj, *(i + n)), value) != false. Returns last if no such iterator is found.

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