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

---

Contents

• 1. Algorithm find. Determining if an element is in a sequence
• 2. Algorithm find_if. Determine the first value that matches the given condition
• 3. Algorithm find_first_of. Finding the first element of a subsequence that matches any other element in the sequence
• 4. Algorithm find_end. Finding the last occurrence of a subsequence contained in a given range
• 5. Algorithm adjanced_find. Search for a pair of neighboring elements that match each other
• 6. Algorithm search. Finding a subsequence in a sequence
• 7. Algorithm search_n. Finding the subsequence in a sequence with the number of elements n
• Related topics

---

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())
    cout << "\"def\" is not found" << endl;
  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
    cout << "The number is not found" << endl;
}

  ⇑

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
    cout << "Not found" << endl;
}

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
    cout << "Not found" << endl;
}

  ⇑

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())
    cout << "Subsequence not found." << endl;
  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 adjacent_find(
  ForwardIterator first,
  ForwardIterator last);

template <class ForwardIterator , class BinaryPredicate>
ForwardIterator adjacent_find(
  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
  it1 = adjacent_find(V1.begin(), V1.end());

  // 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
  it2 = adjacent_find(V1.begin(), V1.end(), Is_Less);

  // 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
  it3 = adjacent_find(
    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

  ⇑

---

Related topics

• Non-modifying algorithms. Algorithms count, count_if, equal, equal_range, mismatch
• Algorithms for working with data which are presented according to the heap principle. Algorithms make_heap, push_heap, pop_heap, sort_heap
• Algorithms for determining the minimum and maximum. Algorithms min, min_element, max, max_element, lexicographical_compare
• Permutation algorithms. Algorithms next_permutation, prev_permutation

 

---

  ⇑