C++. STL. Non-modifying algorithms

Non-modifying algorithms. Examples


Contents


Search other resources:

1. Algorithm count. Determine the number of occurrences of a given element in a sequence

The count algorithm returns the number of elements in a sequence whose value matches the given value. The general form of the algorithm declaration is as follows

template <class InputIterator, class Type>
typename iterator_traits<InputIterator>::difference_type count(
  InputIterator first,
  InputIterator last,
  const Type& value);

where

  • first, last – iterators that define the limits of the sequence;
  • value – element value for counting.

Example.

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

void main()
{
  // The count algorithm is the number of values in the array.
  // 1. Create a dynamic array of random numbers from 0 to 9
  vector<int> v;
  for (int i = 0; i < 10; i++)
    v.push_back(rand() % 10);

  // 2. Output array on the screen
  cout << "V => ";
  for (int i = 0; i < v.size(); i++)
    cout << v[i] << " ";
  cout << endl;

  // 3. Apply the count() algorithm
  // 3.1. Determine the number of numbers 5
  int num7 = count(v.begin(), v.end(), 7);
  cout << "Number 7 - " << num7 << endl;

  // 3.2. Determine the number of numbers 2
  int num2 = count(v.begin(), v.end(), 2);
  cout << "Number 2 - " << num2 << endl;
}

Result

V => 1 7 4 0 9 4 8 8 2 4
Number 7 - 1
Number 2 - 1

 

2. Algorithm count_if. Determine the number of occurrences of an element in a sequence based on a given condition

The count_if algorithm returns the number of elements in a range that match a given condition (a given criterion). The condition (criterion) can be specified using a unary predicate or a lambda expression.

The declaration of a common implementation of the algorithm is:

template <class InputIterator, class UnaryPredicate>
typename iterator_traits<InputIterator>::difference_type count_if(
  InputIterator first,
  InputIterator last,
  UnaryPredicate pred);

here

  • first, last – input iterators that define the boundaries of the range;
  • pred – unary predicate that specifies the calculation condition.

Example.

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

// A predicate that defines the evaluation condition for the count_if algorithm
bool Multiple_3(int a)
{
  // If a is a number that is a multiple of 3
  return a % 3 == 0;
}

int main()
{
  // The count_if algorithm - determine the number of occurrences of element
  // in a sequence that meets a given condition.

  // 1. Using the algorithm based on a lambda expression.
  // 1.1. Declare a list of strings
  list<string> LS = { "abc", "def", "dabc", "bcdemks", "fjidj", "def", "jklmn" };

  // 1.2. Declare a result variable
  list<string>::iterator::difference_type res; // type res - long long

  // 1.3. Determine the number of lines in the list that are less than 5 in length
  res = count_if(
    LS.begin(),
    LS.end(),
    [](string s) // lambda-expression
    {
      return s.length() < 5;
    }
  );

  // 1.4. Display the result
  cout << "res = " << res << endl;

  // 2. The use of algorithm based on the Multiple_3 predicate.
  // 2.1. Declare array of numbers
  vector<int> V = { 2, 8, 4, 1, 7, -3, 0, 9, 11 };

  // 2.2. Declare variable-result
  vector<int>::iterator::difference_type res2;

  // 2.3. Call the algorithm with a predicate
  res2 = count_if(
    V.begin(),
    V.end(),
    Multiple_3
  );

  // 2.4. Display the result
  cout << "res2 = " << res2 << endl;
}

Result

res = 4
res2 = 3

 

3. Algorithm equal. Determine if the elements of two ranges are the same

The equal algorithm performs an element-by-element comparison of two ranges for equality or equivalence. This equality (equivalence) can be given by a predicate. Common algorithm implementations have the following declarations

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

here

  • first1, last1 – input iterators that set the limits of the output range;
  • first2 – input iterator pointing to the first element of the second range, which is compared with the source;
  • pred – binary predicate or lambda expression that specifies the comparison condition.

Example.

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

// A predicate that defines the evaluation condition for the equal algorithm
bool Is_Equal(string s1, string s2)
{
  // Only the lengths of the elements are compared
  return s1.length() == s2.length();
}

int main()
{
  // The equal algorithm determines if the elements of two ranges are the same

  // 1. Using the algorithm without a predicate
  // 1.1. Declare list of strings
  list<string> LS1 = { "00", "11", "22", "33", "44" };

  // 1.2. Create a new list of length LS1 – the length of the LS2 list
  // must be at least as long as the length of the LS1 list.
  list<string> LS2(LS1.size());

  // 1.3. Copy values from LS1 to LS2
  copy(LS1.begin(), LS1.end(), LS2.begin()); // lists are equals

  // 1.4. Declare the result variable
  bool f_equal;

  // 1.5. Call the equal algorithm without a predicate or lambda expression.
  // In this case, the length of the LS1 sequence is taken as the basis.
  f_equal = equal(LS1.begin(), LS1.end(), LS2.begin());

  // 1.6. Process the result
  if (f_equal)
    cout << "LS1 == LS2" << endl;
  else
    cout << "LS1 != LS2" << endl;

  // 2. Using algorithm with predicate
  // 2.1. In the list LS1, change the first element from "00" to "AA"
  list<string>::iterator it = LS1.begin();
  *it = "AA";

  // 2.2. Call the algorithm based on the Is_Equal predicate
  f_equal = equal(LS1.begin(), LS1.end(), LS2.begin(), Is_Equal);

  // 2.3. Process the result
  if (f_equal)
    cout << "LS1 == LS2" << endl;
  else
    cout << "LS1 != LS2" << endl;

  // 3. Using the algorithm with lambda expression
  // 3.1. Read two arrays of numbers of the same length
  vector<double> V1 = { 1.7, 2.8, 3.9 };
  vector<double> V2 = { -1.7, 2.8, -3.9 };

  // 3.2. Call the algorithm, the lambda expression specifies the comparison condition
  f_equal = equal(
    V1.begin(),
    V1.end(),
    V2.begin(),
    [](double a, double b) {
      // modules of numbers are compared
      return fabs(a) == fabs(b);
    }
  );

  // 3.3. Process the result
  if (f_equal)
    cout << "LS1 == LS2" << endl;
  else
    cout << "LS1 != LS2" << endl;
}

Result

LS1 == LS2
LS1 == LS2
LS1 == LS2

 

4. Algorithm equal_range. Return a range that allows elements to be inserted without breaking the order

In an ordered range, finds a range in which all elements are equivalent to a given value. According to the documentation of the algorithm declaration the following:

template <class ForwardIterator, class Type>
pair<ForwardIterator, ForwardIterator> equal_range(
  ForwardIterator first,
  ForwardIterator last,
  const Type& value);

template <class ForwardIterator, class Type, class Compare>
pair<ForwardIterator, ForwardIterator> equal_range(
  ForwardIterator first,
  ForwardIterator last,
  const Type& value,
  Compare pred);

here

  • first, last – source range;
  • value – searched value;
  • pred – predicate function that sets a condition when one element is less than another.

Example.

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

int main()
{
  // Algorithm equal_range - returns a range that allows elements to be inserted
  // without breaking the order. Elements must first be sorted.

  // 1. Declare vector of numbers
  vector<int> V = { 1, 2, 8, 4, 5, 6, 7 };

  // 2. Sort the vector
  sort(V.begin(), V.end());

  // 3. Display on screen
  cout << "V => ";
  for (int i : V)
    cout << i << " ";
  cout << endl;

  // 4. Объявить переменную-результат
  //    первое значение пары - начало диапазона;
  //    второе значение пары - конец диапазона.
  pair<typename vector<int>::iterator, typename vector<int>::iterator> it;

  // 5. Call the equal_range algorithm
  it = equal_range(V.begin(), V.end(), 4);

  // 6. Display the pair value
  cout << "it->first = " << *it.first << endl;
  cout << "it->second = " << *it.second << endl;

  // 7. Display the array
  cout << endl << "V+ => ";

  for (vector<int>::iterator i = V.begin(); i != V.end(); ++i)
  {
    cout << *i << " ";
  }
  cout << endl;
}

Result

V => 1 2 4 5 6 7 8
it->first = 4
it->second = 5

V+ => 1 2 4 5 6 7 8

 

5. Algorithm mismatch. Element-by-element comparison of two ranges

The mismatch algorithm performs an element-by-element comparison of two ranges for equality or equivalence based on a given binary predicate. The algorithm returns the first position where differences are found.

The general form of the algorithm declaration is as follows

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

where

  • first1, last1 – input iterators specifying the first testing range;
  • first2, last2 – input iterators specifying the second testing range;
  • pred – predicate function object that compares the current elements in each range and determines their equivalence.

Example.

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

// Predicate used in the mismatch algorithm
bool Is_Equal(double a, double b)
{
  // The element of the second sequence is 1 greater than the element of the first sequence.
  return a + 1 == b;
}

void main()
{
  // The mismatch algorithm – compare two ranges.

  // 1. Using algorithm without a predicate.
  // 1.1. Declare two arrays
  vector<double> v1 = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6 };
  vector<double> v2 = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6 };

  // 1.2. Call the mismatch algorithm
  auto mismatchPair = mismatch(v1.begin(), v1.end(), v2.begin(), v2.end());

  // 1.3. Process the result
  bool is_mismatch = mismatchPair.first != v1.end();
  if (is_mismatch)
    cout << "v1 != v2" << endl;
  else
    cout << "v1 == v2" << endl;

  // 2. Using algorithm with predicate
  // 2.1. Declare two lists
  list<int> l1 = { 1, 8, 4, 3, 2 };
  list<int> l2 = { 2, 9, 5, 4, 3 };

  // 2.2. Call the algorithm
  auto mismatchPair2 = mismatch(l1.begin(), l1.end(), l2.begin(), l2.end(), Is_Equal);

  // 2.3. Process the result
  is_mismatch = mismatchPair2.first != l1.end();
  if (is_mismatch)
    cout << "l1 != l2" << endl;
  else
    cout << "l1 == l2" << endl;
}

Result

v1 == v2
l1 == l2

 


Related topics