Sunday, November 26, 2023

Algorithms - Non modifying

Overview
Non Modifying Algorithms  operate transparently on containers such as lists, vectors, maps, sets, arrays etc.  using a pair of iterators, These are collectively known as sequences. They perform actions such as search, find, count etc. 
These function accepts parameters like 
  • iterators such as forward, bidirectional 
  • predicates such as unary, binary 
  • function pointers and function objects.
The parameter type  UnaryPredicate  is a function that accepts a single input and returns bool value (true or false). 
For example, bool isodd(int i) {return (i % 2) == 1;} or [](int i) {return (i % 2) == 1;}

The parameter type  BinaryPredicate  is a function that accepts two inputs and returns bool value (true or false).
For example, bool issame(int i, int j) {return i == j;} or [](int i, int j) {return i == j;}

The parameter type  Function  is a function that accepts a single input and returns void.

The parameter type  Functor  is a function object whose operator()  accepts a single input and returns void.

Some functions such as find series return last iterator supplied to it if it cannot find. so the the last iterator should be the end() or +1 of the last element searched. 

Details
NameDescription
bool all_of (
InputIterator first, InputIterator last,
UnaryPredicate pred)


Returns true if pred returns true for all of the elements in the range [first,last], and false otherwise.


Example:
vector<int> v{1,3,4};
cout << boolalpha;

//prints false
cout << all_of (begin(v), end(v), [](int n){return (n%2);}) << endl;
//prints true
cout << all_of (begin(v), end(v)-1, [](int n){return (n%2);}) << endl;
bool any_of (
InputIterator first, InputIterator last,
UnaryPredicate pred)
Returns true if pred returns false for all the elements in the range [first,last] or if the range is empty, and false otherwise.  

Example:
vector<int> v{1,3,4};
cout << boolalpha;

//prints true
cout << any_of  (begin(v), end(v), [](int n){return (n%2);}) << endl;
//prints false 
cout << any_of (end(v)-1, end(v), [](int n){return (n%2);}) << endl;;
bool none_of(
InputIterator first, InputIterator last,
UnaryPredicate pred)
Returns true if pred returns false for all the elements in the range [first,last] or if the range is empty, and false otherwise.

Example:
vector<int> v{1,3,4};
cout << boolalpha;

//prints false
cout << none_of  (begin(v), end(v), [](int n){return (n%2);}) << endl;
//prints true
cout << none_of  (end(v)-1, end(v), [](int n){return (n%2);}) << endl;
UnaryPredicate  for_each(
InputIterator first, InputIterator last,
UnaryPredicate  fn)

Applies function fn or functor fnc to each of the elements in the range [first,last].  

Example:
vector<int> v{1,3,4};

auto oit = ostream_iterator<int> (cout," ");
//prints 1 3 4
for_each  (begin(v), end(v), [&oit](int n){ oit = n;}); 

//v:{2,6,8}
for_each(begin(v), end(v), [](int &n){n*=2;});
InputIterator find(
InputIterator first, InputIterator last,
const T& val)
Returns an iterator to the first element in the range [first,last] that compares equal to val. If no such element is found, the function returns last.  

Example:
vector<int> v{1,2,3,4};

//itr:begin(v)+1
auto itr = find (begin(v), end(v), 2);
    
//itr:end(v)
itr = find (begin(v), end(v), 5);
InputIterator find_if(
InputIterator first, InputIterator last, 
UnaryPredicate pred)
Returns an iterator to the first element in the range [first,last] for which pred returns true. If no such element is found, the function returns  last.

Example:
vector<int> v{1,2,3,4};

//itr:begin(v)+1
auto itr = find_if (begin(v), end(v), [](int n){return (n == 2);} );
    
//itr:end(v)
itr = find_if (begin(v), end(v), [](int n){return (n == 5);});
InputIterator find_if_not(
InputIterator first, InputIterator last, 
UnaryPredicate pred)
Returns an iterator to the first element in the range [first,last] for which pred returns false. If no such element is found, the function returns last.

Example:
vector<int> v{1,2,3,4};

//itr:begin(v)+1
auto itr = find_if_not (begin(v), end(v), [](int n){return (n % 2 == 1);} );
cout << distance(begin(v),itr) << endl;
    
//itr:end(v)
itr = find_if (begin(v), end(v), [](int n){return (n < 6);});
  1. FwdIterator find_end (
    FwdIterator first, FwdIterator last, 
    FwdIterator     first2, FwdIterator last2)
  2. FwdIterator find_end (
    FwdIterator first, FwdIterator last,
    FwdIterator first2, FwdIterator last2,
    BinaryPredicate pred)
Searches the range [first,last] for the last occurrence of the sequence defined by [first2,last2], and returns an iterator to its first element, or last if no occurrences are found. 
The elements in [first,last] are sequentially compared to each of the values in [first2,last2] using operator== in 1st version or pred, in 2nd version, until a pair matches. 
Note:- A match is called only when all the elements in [first2,last2] are found in  [first,last] in the same order.
Example
vector<int> v{1,2,3,2,3}, v2{2,3}, v3{2,2};

//1
//itr:begin(v)+3
auto itr = find_end(begin(v), end(v), begin(v2), end(v2));

//itr:end(v)
itr = find_end(begin(v), end(v), begin(v3), end(v3));

//2
//itr:begin(v)+3
itr = find_end(begin(v), end(v), begin(v2), end(v2), [](int n, int n2){return n == n2;}) 

//itr:end(v)
itr = find_end(begin(v), end(v), begin(v3), end(v3), [](int n, int n2){return n == n2;});
  1. FwdIterator find_first_of (
    FwdIterator first, FwdIterator last, 
    FwdIterator     first2, FwdIterator last2)
  2. FwdIterator find_first_of (
    FwdIterator first, FwdIterator last,
    FwdIterator first2, FwdIterator last2,
    BinaryPredicate pred)
Returns an iterator to the first element in the range [first,last] that  matches any of the elements in [first2,last2]. If no such element is found, the function returns last.
The elements  in [first,last] are sequentially compared to each of the values in [first2,last2] using operator== in 1st version or pred, in 2nd version, until a pair matches. 
Example
vector<int> v{1,2,3}, v2{2,3,4}, v3{4,5};

//1
//itr:begin(v)+1
auto itr = find_first_of(begin(v), end(v), begin(v2), end(v2));
    
//itr:end(v)
itr = find_first_of(begin(v), end(v), begin(v3), end(v3));

//2
//itr:begin(v)+1
itr = find_first_of(begin(v), end(v), begin(v2), end(v2), [](int n, int n2){return n == n2;});
    
//itr:end(v)
itr = find_first_of(begin(v), end(v), begin(v3), end(v3), [](int n, int n2){return n == n2;});
  1. FwdIterator adjacent_find(
    FwdIterator first, FwdIterator last)
  2. FwdIterator adjacent_find(
    FwdIterator first, FwdIterator last, 
    BinaryPredicate pred)

Searches the range [first,last] for the first occurrence of two consecutive elements that match, and returns an iterator to the first of these two elements, or last if no such pair is found.
Two elements match if they compare equal using operator== in the 1st version or using pred, in 2nd version.
Example
vector<int> v{1,2,2,3}, v2{1,2,3};

//1
//itr:begin(v)+1
auto itr = adjacent_find(begin(v), end(v));
    
//itr:end(v2)
itr = adjacent_find(begin(v2), end(v2));

//2    
//itr:begin(v)+1
itr = adjacent_find(begin(v), end(v), [](int n, int n2){return n == n2;});
    
//itr:end(v2)
itr = adjacent_find(begin(v2), end(v2), [](int n, int n2){return n == n2;});
int count (
InputIterator first, InputIterator last,
const T& val)
Returns the number of elements in the range [first,last] that compare equal to val. 
The function uses operator== to compare the individual elements to val.

Example:
vector<int> v{1,2,2,3};

//prints 2
cout << count(begin(v), end(v), 2) << endl;

//prints 1
cout << count(begin(v), end(v), 3) << endl;

//prints 0
cout << count(begin(v), end(v), 4) << endl;
int count_if (
InputIterator first, InputIterator last,
UnaryPredicate pred)
Returns the number of elements in the range [first,last] for which pred is true.

Example:
vector<int> v{1,2,2,3};

//prints 2
cout << count_if (begin(v), end(v), [](int n){return n == 2;}) << endl;

//prints 1
cout << count_if (begin(v), end(v), [](int n){return n == 3;}) << endl;

//prints 0
cout << count_if (begin(v), end(v), [](int n){return n == 4;}) << endl;
  1. pair<InputIterator,InputIterator> mismatch(
    InputIterator first, InputIterator last,
    InputIterator first2)
  2. pair<InputIterator,InputIterator> mismatch(
    InputIterator first, InputIterator last,
    InputIterator first2,  BinaryPredicate pred)
Compares the elements in the range [first,last] with those in the range beginning at first2, and returns the first element of both sequences that does not match.
The elements are compared using operator==in the 1st version or pred, in second version.
The function returns a pair of iterators to the first element in each range that does not match.
Example
vector<int> v{1,2,3}, v2{1,2,4}, v3{1,2}, v4{1,3};

//1
//p:{begin(v)+2,begin(v2)+2}
auto p = mismatch  (begin(v),  end(v), begin(v2));
    
//p:{begin(v)+2,end(v3)}
p = mismatch  (begin(v),  end(v), begin(v3));

//2
//p:{begin(v)+1,begin(v4)+1}
p = mismatch  (begin(v),  end(v), begin(v4), [](int n, int n2){return n == n2;});
    
//p:{end(v),end(v)}
p = mismatch  (begin(v),  end(v), begin(v), [](int n, int n2){return n == n2;});
  1. bool equal (
    InputIterator first, InputIterator last,
    InputIterator first2)
  2. bool equal  (
    InputIterator first, InputIterator last,
    InputIterator first2,  BinaryPredicate pred)
Compares the elements in the range [first,last] with those in the range beginning at first2, and returns true if all of the elements in both ranges match.
The elements are compared using operator==in the 1st version or pred, in second version.
Example
vector<int> v{1,2,3}, v2{1,2};
cout << boolalpha;
    
//1
//prints true
cout << equal (begin(v),  end(v), begin(v)) << endl;
    
//prints false
cout << equal (begin(v),  end(v), begin(v2)) << endl;

//2
//prints true
cout << equal (begin(v),  end(v), begin(v), [](int n, int n2){return n == n2;}) << endl;
    
//prints false
cout << equal (begin(v),  end(v), begin(v2), [](int n, int n2){return n == n2;}) << endl;
  1. bool is_permutation (
    InputIterator first, InputIterator last,
    InputIterator first2)
  2. bool is_permutation (
    InputIterator first, InputIterator last,
    InputIterator first2,  BinaryPredicate pred)
Compares the elements in the range [first,last] with those in the range beginning at first2, and returns true if all of the elements in both ranges match, even in a different order.
The elements are compared using operator==in the 1st version or pred, in second version.
Example
vector<int> v{1,2,3}, v2{3,2,1}, v3{1,2};
cout << boolalpha;
    
//1
//prints true
cout << is_permutation  (begin(v),  end(v), begin(v2)) << endl;
    
//prints false
cout << is_permutation  (begin(v),  end(v), begin(v3)) << endl;

//2
//prints true
cout << is_permutation (begin(v),  end(v), begin(v2), [](int n, int n2){return n == n2;}) << endl;
    
//prints false
cout << is_permutation (begin(v),  end(v), begin(v3), [](int n, int n2){return n == n2;}) << endl;
  1. FwdIterator search (
    FwdIterator first, FwdIterator last,
    FwdIterator first2, FwdIterator last2)
  2. FwdIterator search (
    FwdIterator first, FwdIterator last,
    FwdIterator first2, FwdIterator last2,
    BinaryPredicate pred)
Searches the range [first,last] for the first occurrence of the sequence defined by [first2,last2], and returns an iterator to its first element, or last if no occurrences are found. 
The elements in [first,last] are sequentially compared to each of the values in [first2,last2] using operator== in 1st version or pred, in 2nd version, until a pair matches. 
Note:- A match is called only when all the elements in [first2,last2] are found in  [first,last] in the same order. It's reverse of find_end.
Example
vector<int> v{1,2,3,2,3}, v2{2,3}, v3{2,2};
    
//1
//itr:begin(v)+1
auto itr = search (begin(v), end(v), begin(v2), end(v2));
    
//itr:end(v)
itr = search (begin(v), end(v), begin(v3), end(v3));
    
//2    
//itr:begin(v)+1
itr = search (begin(v), end(v), begin(v2), end(v2), [](int n, int n2){return n == n2;});
    
//itr:end(v)
itr = search (begin(v), end(v), begin(v3), end(v3), [](int n, int n2){return n == n2;});
  1. FwdIterator search_n (
    FwdIterator first, FwdIterator last,
    size_t   count,  const T&  val)
  2. FwdIterator search_n (
    FwdIterator first, FwdIterator last,
    size_t    count, const T&   val, 
    BinaryPredicate     pred)
Searches the range [first,last] for a sequence of count elements, each comparing equal to val in the first version  or for which pred returns true in the second version.

The function returns an iterator to the first of such elements, or last if no such sequence is found.
Example
vector<int> v{1,2,2,3};
    
//1
//itr:begin(v)+1
auto itr = search_n (begin(v), end(v), 2, 2);
    
//itr:end(v)
itr = search_n (begin(v), end(v), 3, 3);
    
//2    
//itr:begin(v)+1
itr = search_n (begin(v), end(v), 2, 2, [](int n, int n2){return n == n2;});
    
//itr:end(v)
itr = search_n (begin(v), end(v), 3, 3, [](int n, int n2){return n == n2;});

The example depicts the usage.


Summary of Examples
NameDescriptiongithubwandbox
  Example       Usage   source    output      source + output   



at
Labels:

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)