# C++. STL. Algorithms that do not change the values and order of elements

## Part 1. Algorithms that do not change the values and order of elements (non-modifying algorithms). Search. Examples

### Contents

Search other resources:

##### 1. Algorithm find. Determining if an element is in a sequence

The find algorithm finds the position of the first occurrence of an element with a given value within a given range. A common implementation of the algorithm has this declaration

```template <class InputIterator, class Type>
InputIterator find(
InputIterator first,
InputIterator last,
const Type& value);```

here

• first, last – input iterators specifying the beginning and end of the considered range, respectively;
• value – the value to be searched.

Example.

```#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <algorithm>
using namespace std;

void main()
{
// The find algorithm is to find a value in a container.
// 1. Finding a string in a vector array
vector<string> V;
V.push_back("abc");
V.push_back("abcd");
V.push_back("def");
V.push_back("jklmn");
V.push_back("jprst");

vector<string>::const_iterator p = find(V.begin(), V.end(), "def");

if (p == V.end())
else
cout << "\"def\" is found" << endl;

// 2. Finding a number in a list
list<double> L{ 2.8, 3.3, 4.5, 1.7, 2.2 };
list<double>::iterator pL;
pL = find(L.begin(), L.end(), 4.5);

if (pL != L.end())
cout << "The number is found." << endl;
else
}```

### ⇑

##### 2. Algorithm find_if. Determine the first value that matches the given condition

The find_if algorithm finds the position of the first occurrence of an element matching a given condition within a given range.

A common implementation of the algorithm has the following general form

```template <class InputIterator, class UnaryPredicate>
InputIterator find_if(
InputIterator first,
InputIterator last,
UnaryPredicate pred);```

where

• first, last – input iterators specifying the beginning and end of the considered range, respectively;
• pred is a unary predicate (function object) or lambda expression that specifies the condition that the element to be searched for must match.

Example 1.

Finds the first element that has a value greater than 10.

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Declare unary predicate
bool More_10(int value)
{
return value > 10;
}

void main()
{
// Algorithm find_if. Find the first number that is greater than 10
vector<int> V = { 4, 8, 9, 2, 10, 15 };
vector<int>::iterator p1;

p1 = find_if(V.begin(), V.end(), More_10);

if (p1 != V.end())
cout << "*p1 = " << *p1 << endl;
else
}```

Result

`*p1 = 15`

Example 2. A lambda expression is used to find the first number that is greater than 10.

```#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

void main()
{
// find_if algorithm. Determine first number that is greater than 10 based on lambda expression
vector<int> V = { 4, 8, 9, 2, 10, 15 };
vector<int>::iterator p1;

// Here is a lambda expression: [](int t) { return t > 10; }
p1 = find_if(V.begin(), V.end(), [](int t) { return t > 10; });

if (p1 != V.end())
cout << "*p1 = " << *p1 << endl;
else
}```

### ⇑

##### 3. Algorithm find_first_of. Finding the first element of a subsequence that matches any other element in the sequence

The find_first_of algorithm searches for any of several values in the target range. You can also specify the search criteria using a specific predicate or lambda expression.

```template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 find_first_of(
ForwardIterator1 first1,
ForwardIterator1 last1,
ForwardIterator2 first2,
ForwardIterator2 last2);

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

where

• first1, last1 – direct iterators indicating the range to be searched;
• first2, last2 – direct iterators indicating the range for comparison;
• pred – binary predicate or lambda expression that specifies the condition under which two elements are considered equivalent to each other. The predicate returns true in case of a match.

Example.

```#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;

// A predicate that defines the execution condition of the find_first_of algorithm
bool More_Than(int a, int b)
{
// Search for a match until the first value becomes greater
// than the second, that is, the element of the first sequence
// does not become greater than the element of the second sequence.
return a > b;
}

int main()
{
// The find_first_of algorithm is to find the first element
// of a subsequence that matches any other element of the sequence.

// 1. Using the algorithm without the predicate.
// 1.1. Declare two vectors and output them.
vector<int> V1 = { 2, 1, 3, 2, 4, 5, 2, 1, 3, 0 };
vector<int> V2 = { 4, 5 };

vector<int>::iterator it = V1.begin();
cout << "V1 => ";
while (it != V1.end())
{
cout << *it << " ";
it++;
}
cout << endl;

it = V2.begin();
cout << "V1 => ";
while (it != V2.end())
{
cout << *it << " ";
it++;
}
cout << endl;

// 1.2. Declare the iterator on the resulting element.
vector<int>::iterator resItem;

// 1.3. Calling an algorithm without a predicate or lambda expression.
resItem = find_first_of(V1.begin(), V1.end(), V2.begin(), V2.end());

// 1.4. Print the value pointed to by resItem.
if (resItem == V1.end())
cout << "resItem -> V1.end()" << endl;
else
cout << "resItem -> " << *resItem << endl;

// 1.5. Output sequence starting from resItem.
vector<int>::iterator it2 = resItem;
cout << "resItem: ";
while (it2 != V1.end())
{
cout << *it2 << " ";
it2++;
}
cout << endl;

// 2. Use algorithm with More_Than predicate
// 2.1. Declare new two vectors
vector<int> V3 = { 1, 3, 5, 7, 9, 10 };
vector<int> V4 = { 2, 4, 6 };

// 2.2. Output these vectors
it = V3.begin();
cout << "V3 => ";
while (it != V3.end())
{
cout << *it << " ";
it++;
}
cout << endl;

it = V4.begin();
cout << "V4 => ";
while (it != V4.end())
{
cout << *it << " ";
it++;
}
cout << endl;

// 2.3. Declare a new result iterator
vector<int>::iterator resItem2;

// 2.4. Call the find_first_of algorithm with a predicate
resItem2 = find_first_of(V3.begin(), V3.end(), V4.begin(), V4.end(), More_Than);

// 2.5. Output the value that resItem2 points to
if (resItem2 == V3.end())
cout << "resItem2 -> V3.end()" << endl;
else
cout << "resItem2 -> " << *resItem2 << endl;

// 2.6. Print the sequence starting from resItem2
vector<int>::iterator it3 = resItem2;
cout << "resItem2: ";
while (it3 != V3.end())
{
cout << *it3 << " ";
it3++;
}
}```

Result

```V1 => 2 1 3   2 4 5 2 1   3 0
V1 => 4 5
resItem -> 4
resItem: 4 5 2   1 3 0
V3 => 1 3 5   7 9 10
V4 => 2 4 6
resItem2 -> 3
resItem2: 3 5 7   9 10```

### ⇑

##### 4. Algorithm find_end. Finding the last occurrence of a subsequence contained in a given range

The find_end algorithm searches the range for the last subsequence that matches the specified sequence.

The algorithm has the following overloaded implementations

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

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

where

• first1, last1 – direct iterators indicating the range to be searched;
• first2, last2 – direct iterators specifying the range to be compared;
• pred – binary predicate or lambda expression that specifies the condition under which two elements are considered equivalent to each other. The predicate returns true in case of a match.

Example.

```#include <iostream>
#include <queue>
#include <vector>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;

int main()
{
// The find_end algorithm finds the last occurrence of a subsequence
// that is contained in a given range.

// 1. Using an algorithm without a predicate - searching for a sequence { 2, 1, 3 }
// 1.1. Declare a vector of 10 elements and output it
vector<int> V = { 2, 1, 3, 2, 4, 5, 2, 1, 3, 0 };
vector<int>::iterator it = V.begin();
cout << "V => ";
while (it != V.end())
{
cout << *it << " ";
it++;
}
cout << endl;

// 1.2. Create iterators to the beginning and end of the subsequence: { 2, 1, 3 }
vector<int>::iterator itBegin = V.begin();
vector<int>::iterator itEnd = itBegin;
itEnd++;
itEnd++; // itEnd -> V[2] = 3

// 1.3. Call the find_end algorithm - get an iterator to the beginning of a subsequence
vector<int>::iterator itRes = find_end(V.begin(), V.end(), itBegin, itEnd);

// 1.4. Print the sequence that follows before itRes
it = V.begin();
cout << "Before itRes: ";
while (it != itRes)
{
cout << *it << " ";
it++;
}
cout << endl;

// 1.5. Print the value pointed to by itRes
if (itRes == V.end())
else
cout << "itRes -> " << *itRes << endl; // 2

// 2. Using an algorithm with a lambda expression - searching for a sequence { 2, 1 }
// 2.1. Declaration of resulting iterator
vector<int>::iterator itRes2;

// 2.2. Customize iterators itBegin, intEnd
itBegin = V.begin();
itEnd = itBegin;
itEnd++;   // itBegin..itEnd => { 2, 1 }

// 2.3. Call the find_end algorithm
itRes2 = find_end(
V.begin(),
V.end(),
itBegin,
itEnd,
[](int a, int b)   // lambda expression, here you can set another condition
{
return a == b;
}
);

// 2.4. Output a vector to itRes2 iterator
it = V.begin();
cout << "Before itRes2: ";
while (it != itRes2)
{
cout << *it << " ";
it++;
}
cout << endl;

// 2.5. Output vector starting from itRes2
it = itRes2;
cout << "itRes2 -> ";
while (it != V.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}```

Result

```V => 2 1 3   2 4 5 2 1   3 0
Before itRes: 2 1 3   2 4 5
itRes -> 2
Before itRes2: 2 1 3   2 4 5
itRes2 -> 2 1 3 0```

### ⇑

##### 5. Algorithm adjanced_find. Search for a pair of neighboring elements that match each other

The general form of overloaded implementations of the algorithm

```template <class ForwardIterator>
ForwardIterator first,
ForwardIterator last);

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

where

• first – redirection of the iterator at the position of the first element in the search range;
• last – redirection of the iterator to the position after the last element in the search range;
• pred – binary predicate that specifies the condition to which the values of neighboring elements in the range [first; last-1].

Example.

```#include <iostream>
#include <vector>
#include <list>
#include <functional>
#include <algorithm>
using namespace std;

bool Is_Less(int a, int b)
{
// a pair is considered in which the previous element is greater than the next by 1
return a == b + 1;
}

int main()
{
// Algorithm adjacent_find - finding a pair of adjacent elements that match each other

// 1. Using adjanced_find without a predicate
// 1.1 Create a sequence of numbers and print it to the console
vector<int> V1 = { 6, 8, 7, 1, -1, 3, 3, 4, 5, 5, 8, 1 };
cout << "V1 => ";
for (int i : V1)
cout << i << " ";
cout << endl;

// 1.2. Declare an iterator for a pair that matches
vector<int>::iterator it1;

// 1.3. Call the adjanced_find algorithm

// 1.4. Display the result
if (it1 != V1.end())
cout << "*it1 = " << *it1 << endl; // *it1 = 3
else
cout << "it1->V1.end()" << endl;

// 2. Using adjacent_find with the Is_Less predicate
// 2.1. Declare an iterator for the matched pair
vector<int>::iterator it2;

// 2.2. Call the algorithm

// 2.3. Display the result
if (it2 != V1.end())
cout << "*it2 = " << *it2 << endl;
else
cout << "it2->V1.end()" << endl;

// 3. Using adjanent_find with lambda-expression
// 3.1. Declare the position iterator.
vector<int>::iterator it3;

// 3.2. Call the algorithm with a lambda expression
V1.begin(),
V1.end(),
[](int a, int b) {
// specify a condition: a and b - odd numbers
return (a % 2 == 1) && (b % 2 == 1);
}
);

// 3.3. Process the result
if (it3 != V1.end())
cout << "*it3 = " << *it3 << endl; // 7
else
cout << "it3->V1.end()" << endl;
}```

Result

```V1 => 6 8   7 1 -1 3 3   4 5 5 8 1
*it1 = 3
*it2 = 8
*it3 = 7```

### ⇑

##### 6. Algorithm search. Finding a subsequence in a sequence

The search method searches for a subsequence in the given sequence. The most common implementations of the algorithm are of the form

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

where

• first1, last1 – direct iterators specifying the search range;
• first2, last2 – direct iterators specifying the range for comparison;
• pred – binary predicate (function) that defines a condition that determines the equality (equivalence) of two elements with each other.

Example.

```#include <iostream>
#include <algorithm>
#include <list>
using namespace std;

// A predicate that returns the equality of two elements
bool Is_Equal(int a, int b)
{
// criterion for the equality of elements,
// element of another sequence is 1 more than the element of the first sequence
return a == b + 1;
}

int main()
{
// search algorithm - search for a subsequence in a sequence
// 1. Create a list of numbers
list<int> L1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
list<int> L2 = { 2, 3, 4 };

// 2. Invoke a lookup based on using the Is_Equal predicate
// 2.1. Get the iterator to the resulting container
list<int>::iterator it;
it = search(L1.begin(), L1.end(), L2.begin(), L2.end(), Is_Equal);

// 2.2. Process the result
if (it == L1.end())
cout << "There is no match.";
else
cout << *it << endl; // 3

// 3. Call search without using predicate
// 3.1. Get an iterator to the resulting container
it = search(L1.begin(), L1.end(), L2.begin(), L2.end());

// 3.2. Process the result
if (it == L1.end())
cout << "There is no match.";
else
cout << *it << endl; // 2
}```

Result

```3
2```

### ⇑

##### 7. Algorithm search_n. Finding the subsequence in a sequence with the number of elements n

The search_n algorithm searches for the first subsequence within a range of a given number of elements that have a certain value. The correspondence of this value can be specified by a binary predicate.

The most common implementations of the algorithm are as follows

```template <class ForwardIterator1, class Diff2, class Type>
ForwardIterator1 search_n(
ForwardIterator1 first1,
ForwardIterator1 last1,
Diff2 count,
const Type& value);

template <class ForwardIterator1, class Diff2, class Type, class BinaryPredicate>
ForwardIterator1 search_n(
ForwardIterator1 first1,
ForwardIterator1 last1,
Diff2 count,
const Type& value,
BinaryPredicate pred);```

where

• first1, last1 – direct iterators, specifying the range for the search;
• count – size of the required sequence;
• value – value of elements of the searched sequence.

Example.

```#include <iostream>
#include <algorithm>
#include <list>
using namespace std;

// A predicate that determines whether two elements are equal
bool Is_Equal(int a, int b)
{
// criterion for equality of elements,
// the element of the second sequence is 1 greater than the element of the first sequence
return a == b + 1;
}

int main()
{
// Algorithm search_n - search for a subsequence in a sequence
// 1. Create a list of numbers
list<int> L1 = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
list<int> L2 = { 2, 3, 4 };

// 2. Invoke search based on using Is_Equal predicate
// 2.1. Declare iterator on resulting container
list<int>::iterator it;

// 2.2. Determine if the number 5 occurs only once in the sequence L1: { 5 }
it = search_n(L1.begin(), L1.end(), 1, 4, Is_Equal); // 4+1 = 5

// 2.3. Process the result
if (it == L1.end())
cout << "There is no match { 5 }.";
else
cout << *it << endl; // 5

// 2.4. Determine if the number 3 occurs 2 times in a row: { 3, 3 }
it = search_n(L1.begin(), L1.end(), 2, 2, Is_Equal);

// 2.5. Process the result
if (it == L1.end())
cout << "There is no match { 3, 3 }." << endl;
else
cout << *it << endl;

// 3. Call search without using predicate
// 3.1. Determine if the number 7 occurs only once
it = search_n(L1.begin(), L1.end(), 1, 7);

// 3.2. Process the result
if (it == L1.end())
cout << "There is no match {7}. ";
else
cout << *it << endl; // 7
}```

Result

```5
There is no match { 3, 3 }.
7```