Overview
Merge algorithms operate on various types of containers such as sequence, associative and unordered to perform actions such as merging sorted sequences, set union, intersection and differences.
These function accepts parameters like
- iterators such as Input, Output, bidirectional
- predicates such as binary
The parameter type Compare 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;}
Details
| Name | Description |
|---|---|
| Combines the elements in the sorted ranges [first,last] and [first2,last2], into a new range beginning at result with all its elements sorted. The elements are compared using operator< for the first version, and comp for the second. Returns an iterator pointing to the element that follows the last element written in the result sequence. |
Example auto il = {1,2,4}; auto il2 = {3,4,5,6}; vector<int> v(7); //1 //v:{1, 2, 3, 4, 4, 5, 6 } //itr:end(v) auto itr = merge (begin(il), end(il), begin(il2), end(il2), begin(v)); //2 //v:{6, 5, 4, 4, 3, 2, 1 } //itr:end(v) itr = merge (rbegin(il), rend(il),rbegin(il2), rend(il2),begin(v),greater<int>()); | |
| Merges two consecutive sorted ranges: [first,middle] and [middle,last], putting the result into the combined sorted range [first,last]. Note that elements from second range are added to the first range. The elements are compared using operator< for the first version, and comp for the second. |
Example vector<int> v{5,10,15,20,25,20,30,30,40,50}; //1 //v:{5, 10, 15, 20, 20, 25, 30, 30, 40, 50} inplace_merge (begin(v), begin(v)+5, end(v)); //2 v.assign({5,10,15,20,25,20,30,30,40,50}); //v:{50, 40, 30, 30, 20, 25, 20, 15, 10, 5 } reverse(begin(v),end(v)); //v:{50, 40, 30, 30, 25, 20, 20, 15, 10, 5 } inplace_merge (begin(v), begin(v)+5, end(v), greater<int>()); | |
| Returns true if the sorted range [first,last] contains all the elements in the sorted range [first2,last2]. The elements are compared using operator< for the first version, and comp for the second. |
Example vector<int> v{1,2,3,4,4,5,6}, v2{3,4,5,6}; cout << boolalpha; //1 //prints true cout << includes (begin(v), end(v), begin(v2), end(v2)) << endl; //2 //prints true cout << includes (rbegin(v), rend(v), rbegin(v2), rend(v2), greater<int>()) << endl; | |
| Constructs a sorted range beginning in the location pointed by result with the set union of the two sorted ranges [first,last] and [first2,last2]. Duplicate values in the first range, also present in the second range are removed. The elements are compared using operator< for the first version, and comp for the second. Returns an iterator pointing to the element that follows the last element written in the result sequence. |
Example vector<int> v(7), v2{1,2,4,4}, v3{3,4,5,6}; //1 //v:{1,2,3,4,4,5,6} //itr:end(v) auto itr = set_union (begin(v2), end(v2), begin(v3), end(v3), begin(v)); //2 //v:{6, 5, 4, 4, 3, 2, 1} //itr:end(v) itr = set_union (rbegin(v2), rend(v2), rbegin(v3), rend(v3), begin(v), greater<int>()); | |
| Constructs a sorted range beginning in the location pointed by result with the set intersection of the two sorted ranges [first,last] and [first2,last2]. The intersection of two sets is formed only by the elements that are present in both sets. The elements copied by the function come always from the first range, in the same order. The elements are compared using operator< for the first version, and comp for the second. Returns an iterator pointing to the element that follows the last element written in the result sequence. |
Example vector<int> v(2), v2{2,4,4,6}, v3{3,4,5,6}; //1 //v:{4,6} //itr:end(v) auto itr = set_intersection (begin(v2), end(v2), begin(v3), end(v3), begin(v)); //2 //v:{6,4} //itr:end(v) itr = set_intersection (rbegin(v2), rend(v2), rbegin(v3), rend(v3), begin(v), greater<int>()); | |
| Constructs a sorted range beginning in the location pointed by result with the set difference of the sorted range [first,last] with respect to the sorted range [first2,last2]. The difference of two sets is formed by the elements that are present in the first set, but not in the second one. The elements copied by the function come always from the first range, in the same order. For containers supporting multiple occurrences of a value, the difference includes as many occurrences of a given value as in the first range, minus the amount of matching elements in the second, preserving order. The elements are compared using operator< for the first version, and comp for the second. Returns an iterator pointing to the element that follows the last element written in the result sequence. |
Example vector<int> v(3), v2{1,2,4,4}, v3{3,4,5,6}; //1 //v:{1,2,4} //itr:end(v) auto itr = set_difference (begin(v2), end(v2), begin(v3), end(v3), begin(v)); //2 //v:{4,2,1} //itr:end(v) itr = set_difference (rbegin(v2), rend(v2), rbegin(v3), rend(v3), begin(v), greater<int>()); | |
| Constructs a sorted range beginning in the location pointed by result with the set symmetric difference of the two sorted ranges [first,last] and [first2,last2]. The symmetric difference of two sets is formed by the elements that are present in one of the sets, but not in the other. Among the equivalent elements in each range, those discarded are those that appear before in the existent order before the call. The existing order is also preserved for the copied elements. The elements are compared using operator< for the first version, and comp for the second. Returns an iterator pointing to the element that follows the last element written in the result sequence. |
Example vector<int> v(6), v2{1,2,4,4}, v3{3,4,5,6}; //1 //v:{1,2,3,4,5,6} //itr:end(v) auto itr = set_symmetric_difference (begin(v2), end(v2), begin(v3), end(v3), begin(v)); //2 //v:{6,5,4,3,2,1} //itr:end(v) itr = set_symmetric_difference (rbegin(v2), rend(v2), rbegin(v3), rend(v3), begin(v), greater<int>()); | |
The example depicts the usage.
No comments:
Post a Comment