Non-modifying algorithms. Examples
Contents
- 1. Algorithm count. Determine the number of occurrences of a given element in a sequence
- 2. Algorithm count_if. Determine the number of occurrences of an element in a sequence based on a given condition
- 3. Algorithm equal. Determine if the elements of two ranges are the same
- 4. Algorithm equal_range. Return a range that allows elements to be inserted without breaking the order
- 5. Algorithm mismatch. Element-by-element comparison of two ranges
- Related topics
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
- 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
- Non-modifying algorithms. Search. Examples. Algorithms find, find_if, find_first_of, find_end, adjanced_find, search, search_n
⇑