Xun
Standard Template Library (STL) defines many commonly used algorithms, which are mainly defined in <algorithm>. When programming, these algorithms can be easily used by simply adding # include < algorithm > to the file. To use these functions well, you must understand the following concepts:
- Container containers are used to store all kinds of data, and the algorithm in <algorithm> is designed for containers. Therefore, functions in <algorithm> can be correctly handled whether the data is some int, char or a custom class. vector is the most commonly used container.
- Iterator iterators are used in conjunction with containers. Its function is to traverse elements in the container, such as pointers to arrays, which can be regarded as an iterator. Iterators generally support operations such as dereference (operator * ()), operator + (), and equality (operator = ()).
- Predicate predicates are used to customize functions in <algorithm>. The predicate can be a lambda expression or a function/function pointer, and there are only one predicate and two predicates in <algorithm>, that is, the function can only receive one or two parameters. The capture function of lambda expressions can be used for predicates requiring additional parameters.
- The pair part algorithm has two return values, pair has two members first and second, which are used to package the two values back.
The following content mainly comes from Appendix A2 of the 5th edition of C++ Primer. Here are some sample programs added.
The main parameters used in each algorithm are:
- Begin and end are iterators representing element ranges.
- Begin2 is an iterator for the start position of the second input sequence, and end2 represents the end position (if any) of the second sequence. If there is no end2, it is assumed that the sequence represented by beg2 is as large as that represented by beg and end. Beg and beg2 need not be of the same type, but elements in both sequences should be able to call a given callable object. For example, beg is a vector < int >:: iterator, while beg2 can be a deque < int >:: iterator.
- dest is an iterator representing the destination sequence, which must ensure that all elements generated by the algorithm can be stored. If the size cannot be determined, the std::back_inserter() function can be called to obtain the insert iterator of the destination sequence.
- unaryPred and binayPred are unary and binary predicates. In fact, the parameters are elements in the sequence.
- comp is a binary predicate that compares two elements.
- unaryOp and binaryOp are callable objects.
In addition, some algorithms require that the sequence be ordered, and the defau lt is to use an ascending order less than the operator (<). If the predicate version is used, the order is comp ascending.
Algorithms for Finding Objects
These algorithms search for a specified value or sequence in an input sequence.
Versions that do not accept predicates use the underlying equality operator (==) for comparison elements, and versions that accept predicates use predicate comparison elements given by users.
Simple Search Algorithms
find(beg, end, val)
find_if(beg, end, unaryPred)
find_if_not(beg, end, unaryPred)
count(beg, end, val)
count_if(beg, end, unaryPred)
Find, find_if, and find_if_not return an iterator pointing to the first element that satisfies the condition, and if not, return end. Count and count_if return a counter.
std::vector<int> v{ -2,-1,0,1,2 };
std::vector<int>::iterator iter = find(v.begin(), v.end(), 5);//No, iter==v.end()
if (iter == v.end())
std::cout << "oops";
long long n = std::count_if(v.begin(), v.end(), [](int val) {return val > 0; });//Positive number 2all_of(beg, end, unaryPred)
any_of(beg, end, unaryPred)
none_of(beg, end, unaryPred)
These algorithms all return bool to indicate whether any/existing/nonexistent elements in the sequence satisfy the condition. If the sequence is empty, any_of returns false, all_of and none_of returns true.
std::string s("123abc");
std::cout << std::all_of(s.begin(), s.end(), [](char c) {return isalpha(c); });//Output 0, not all lettersAlgorithms for Finding Duplicate Values
adjacent_find(beg, end)
adjacent_find(beg, end, binaryPred)
Returns an iterator that points to the first pair of adjacent repetitive elements, and an end if there are no adjacent elements.
std::vector<int> v{ 5,2,2,3,6,10 };
std::vector<int>::iterator iter1 = std::adjacent_find(v.begin(), v.end());//iter1 points to the first 2
std::cout << *(iter1+1);
auto iter2 = std::adjacent_find(v.begin(), v.end(), [](int a, int b) {return b == 2 * a; });//Looking for the next element is twice the location of the previous element, iter2 points to 3search_n(beg, end, cnt, val)
search_n(beg, end, cnt, val, binaryPred)
Find cnt equivalent elements in the sequence, which is defined by binary Pred.
struct A { int i; char c; };
std::vector<A> vA{ {1,'v'},{2,'c'},{3,'d'},{3,'k'},{3,'o'},{5,'l'} };
auto iter = std::search_n(vA.begin(), vA.end(), 3,
A{ 3,'x' },//Find the location of three consecutive elements equal to A{3,'x'}
[](A a, A b)//Define the equality of type A as the equality of member variables i
{return a.i == b.i; });//iter points to {3,'d'} Algorithms for Finding Subsequences
search(beg1, end1, beg2, end2)
search(beg1, end1, beg2, end2, binaryPred)
Returns an iterator pointing to the first occurrence of the second sequence in the first sequence, and returns end1 if not found.
std::vector<int> v{ 1,2,3,4,6,12,5,11 };
int array[3] = { 2,2,3 };
auto iter1 = std::search(v.begin(), v.end(), std::begin(array), std::end(array));//Look for the sub-sequence array in v, not found, iter1 points to the end of V
auto iter2 = std::search(v.begin(), v.end(), std::begin(array), std::end(array),
[](int a, int b) //Find three consecutive numbers in v, divisible by 2, 2, 3, respectively
{return a % b == 0; });//iter2 points to 4find_first_of(beg1, end1, beg2, end2)
find_first_of(beg1, end1, beg2, end2, binaryPred)
Returns an iterator pointing to the first occurrence of any element in the second sequence, and returns end1 if not found.
std::vector<int> v{ 1,2,3,4,6,12,5,11 };
int array[3] = { 5,4,3 };
auto iter1 = std::find_first_of(v.begin(), v.end(), array, array + 3);//The first element in array appears in v is 3, iter1 points to 3 in v.
auto iter2 = std::find_first_of(v.begin(), v.end(), array, array + 3,
[](int a, int b)//Look for the first element in v equal to 10 added to the element in array (that is, look for 5, 6, 7)
{return a + b == 10; });//iter2 points to 6,6+4==10find_end(beg1, end1, beg2, end2)
find_end(beg1, end1, beg2, end2, binaryPred)
Similar to search, but the return of the second sequence in the first sequence in the last place, if not found the same return end1.
std::vector<int> v{ 1,2,3,4,5,6,1,2,3,7,8,9 };
int array[3] = { 1,2,3 };
std::forward_list<int> lst{ 9,8,7 };
auto iter1 = std::find_end(v.begin(), v.end(), array, array + 3);//iter1 points to the first element 1 of the second (last) {1, 2, 3} in v.
auto iter2 = std::find_end(v.begin(), v.end(), lst.begin(), lst.end());//No, iter2 points to the end of v.Other Read-Only Algorithms
for_each(beg, end, unaryOp)
Apply the callable unaryOp to each element in the sequence, and unaryOp may modify the element if the iterator allows writing values to elements in the sequence by de-referencing. However, the scope for loop achieves the same purpose and is shorter in writing.
std::vector<int> v{ 1,2,3,4,5 };
std::for_each(v.begin(), v.end(), [](int& a) {a *= 2; });//Pass in the reference and change each element in v to twice its own
for (int& i : v)//Scope for loop, using references can also modify elements
{//If there is only one statement, curly braces can be omitted
std::cout << i << ' ';
}mismatch(beg1, end1, beg2)
mismatch(beg1, end1, beg2, binaryPred)
The pair returned by an iterator represents the first mismatched element in the two sequences. If all elements match, the first iterator in the returned pair points to end1, and the second iterator points to the position where the offset in beg2 equals the length of the first sequence.
std::vector<int> v1{ 1,2,3 };
std::vector<int> v2{ 1,2,4,5 };//The length of v2 should be no less than the length of v1
std::pair<std::vector<int>::iterator, std::vector<int>::iterator>//General auto
iters1 = std::mismatch(v1.begin(), v1.end(), v2.begin());//iters1.first points to 3 in v1, iters1.second points to 4 in v2
auto iters2 = std::mismatch(v1.begin(), v1.end(), v2.begin(),//No mismatched element pairs were found
[](int a, int b)//After iters2.first points to the end of v1, iters2.second points to 5 in v2
{return abs(a - b) < 2; });//Define that the absolute value of the difference between two elements is less than 2equal(beg1, end1, beg2)
equal(beg1, end1, beg2, binaryPred)
Determine whether the two sequences are equal and return a bool value.
std::vector<int> v1{ 1,2,3 };
std::vector<int> v2{ 1,2,4,5 };
bool b = std::equal(v1.begin(), v1.end(), v2.begin(),//Returns true equally, checking only the previous v1.size() elements
[](int a, int b)
{return abs(a - b) < 2; });//The absolute value defined as the difference between two elements is less than 2.Binary search algorithm
These algorithms require that the sequence be ordered. By default, the algorithm uses less than operator for comparison. If predicates are used, the less than operator is redefined. The iterators returned by lower_bound, upper_bound and equal_range point to the correct insertion position of a given element in the sequence - the sequence after insertion is orderly. Note that the insertion of elements in the container (seq.insert(iter, val)) is done before the iterator, except for the one-way list (lst.insert_after(iter, val)).
binary_search(beg, end, val)
binary_search(beg, end, val, comp)
Returns a bool value indicating whether there is an element equal to val in the sequence.
std::vector<int> v1{ 10,9,8,7,6,4,3,2,1 };
std::vector<int> v2{ 1,2,3,4,6,7,8,9,10 };
bool b1 = std::binary_search(v1.begin(), v1.end(), 6);//b1==false, v1 is not ascending in order to make the search direction wrong
bool b2 = std::binary_search(v2.begin(), v2.end(), 6);//b2==true
struct A { int i; char c; };
std::vector<A> vA{ {1,'v'},{2,'c'},{3,'d'},{4,'k'},{5,'o'},{6,'l'} };//In ascending order i
bool b3 = std::binary_search(vA.begin(), vA.end(), A{ 3,'h' },//Return true
[](A a, A b) {return a.i < b.i; });//Redefining A less than or equal to the member variable ilower_bound(beg, end, val)
lower_bound(beg, end, val, comp)
upper_bound(beg, end, val)
upper_bound(beg, end, val, comp)
equal_range(beg, end, val)
equal_range(beg, end, val, comp)
Lower_bound returns an iterator pointing to the first value greater than or equal to val, upper_bound returns an iterator pointing to the first value greater than or equal to val, equal_range returns an iterator pair whose first member is the return value of lower_bound, and second member is the return value of upper_bound.
std::vector<double>v{ 1,2,3,4,4,4,5,6 };//Ascending order
auto iter1 = std::lower_bound(v.begin(), v.end(), 4.0);//iter1 points to the first value not less than 4.0, and the first 4 in v
auto iter2 = std::upper_bound(v.begin(), v.end(), 4.5);//iter2 points to the first value greater than 4.5, and the last five after the last four in v
auto iters = std::equal_range(v.begin(), v.end(), 4.0);//First points to the first 4, second points to 5Algorithms for Writing Container Elements
Write-Only and Read-Free Element Algorithms
fill(beg, end, val)
fill_n(dest, cnt, val)
generate(beg, end, Gen)
generate_n(dest, cnt, Gen)
Give each element in the sequence a new value. fill assigns the value value to the element, Genee executes the generator object Gen() to generate a new value, the generator is a callable object, each call generates a new value, fills and generates return void, and the _n version returns an iterator pointing to the next location of the element written to the output sequence.
std::vector<int>v(6, -2);//There are 6-2 in v.
std::fill_n(v.begin(), 3, 5);//The first three elements of v are rewritten to 5
std::fill(v.begin() + 3, v.end(), 10);//v[3] and subsequent elements are rewritten to 10
std::fill_n(std::back_inserter(v), 3, 15);//Add 3 more 15 at the end of v
std::default_random_engine e(static_cast<unsigned>(time(0)));//Random Number Generator
std::uniform_int_distribution<int> u1(0, 10);//Generating random numbers of [0,10]
std::uniform_int_distribution<int> u2(11, 20);//Generating [11,20] Random Numbers
std::generate_n(v.begin(), 5, [&]() {return u1(e); });//Rewrite the first five numbers of v to random numbers of [0,10]
std::generate(v.begin() + 5, v.end(), [&]() {return u2(e); });//Change v[5] and subsequent elements to random numbers of [11,20]Writing algorithm using input iterator
copy(beg, end dest)
copy_if(beg, end, dest, unaryPred)
copy_n(beg, n, dest)
Copy the elements in the input range to the destination sequence, copy all the elements, copy_if copies the elements that satisfy the conditions, copy_n copies the first n elements, and the input sequence must have at least n elements.
int array1[5] = { 1,2,3,4,5 };
int array2[5];
std::copy(std::begin(array1), std::end(array1), std::begin(array2));//Arrays do not allow direct replication
std::vector<int>v;
v.reserve(5);
std::copy_if(std::begin(array1), std::end(array1), std::back_inserter(v), [](int a) {return a & 1; });//Copy only odd numbers, v={1,3,5}
std::copy_n(array1 + 1, 2, v.begin());//Before v, there were three elements that did not cross the boundary. Now v={2,3,5}move(beg, end, dest)
Call std::move for each element in the input sequence and move it to the destination sequence.
std::vector<int>v(5);//There are five elements in v
{//A New Survival Area
std::vector<int>temp{ 1,2,3,4,5 };
std::move(temp.begin(), temp.end(), v.begin());
}//End of Survival Areatransform(beg, end, dest, unaryOp)
transform(beg1, end1, beg2, dest, binaryOp)
The elements in the input sequence are transformed, and the result is written into the destination sequence, and the input sequence is unchanged.
std::vector<int>v1{ 1,2,3,4,5 };
std::vector<int>v2{ 5,4,3,2,1 };
std::vector<int>v3;
std::vector<int>v4;
std::transform(v1.begin(), v1.end(), std::back_inserter(v3), [](int a) {return a * 2; });//Write 2 times the value of the element in v1 into v3
std::transform(v1.begin(), v1.end(), v2.begin(), std::back_inserter(v4), [](int a, int b) {return a * b; });//The elements in v4 are the product of the corresponding elements in v1 and v2replace_copy(beg, end, dest, old_val, new_val)
replace_copy_if(beg, end, dest, unaryPred, new_val)
The elements satisfying the conditions in the sequence are replaced by new values and written into the destination sequence without changing the input sequence.
std::vector<int>v1{ 1,2,3,4,5 };
std::vector<int>v2(v1.size());
std::vector<int>v3(v1.size());
std::replace_copy(v1.begin(), v1.end(), v2.begin(), 3, 333);//Replace 3 in v 1 with 333 and write v2, v2={1,2,333,4,5}
std::replace_copy_if(v1.begin(), v1.end(), v3.begin(),//v3={-1,-1,3,4,5}
[](int a) {return a < 3; }, -1);//Replace element less than 3 in v 1 with - 1 and write it to v3merge(beg1, end1, beg2, end2, dest)
merge(beg1, end1, beg2, end2, dest, comp)
The two ordered sequences are merged into one ordered sequence and written to dest. By default, the less than operator is used for comparison, and the less than operator can be redefined by comp.
std::vector<int> v1{ 1,3,5,7,9 };//Ascending order
std::vector<int> v2{ 2,4,6,8,10 };//Ascending order
std::vector<int>v3;
v3.reserve(v1.size() + v2.size());
std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(v3));//v3=[1-10]Writing Algorithms Using Forward Iterators
These algorithms write elements to the input sequence
iter_swap(iter1, iter2)
swap_ranges(beg1, end1, beg2)
iter_swap swaps the elements pointed by the two iterators, not the iterators. swap_ranges swaps the elements in the two ranges. The two ranges cannot overlap, returns the incremental beg2, and points to the position after the last swap element.
std::vector<int> v1{ 1,3,5,7,9 };
std::vector<int> v2{ 2,4,6,8,10 };
std::iter_swap(v1.begin(), v1.begin() + 1);//Exchange the first two elements of v1, v1={3,1,5,7,9}
std::swap_ranges(v2.begin(), v2.begin() + 2, v2.begin() + 3);//The first two elements of V2 are exchanged with the two elements starting from v2[3]. v2={8,10,6,2,4}replace(beg, end, old_val, new_val)
replace_if(beg, end, unaryPred, new_val)
Replace each matching element with a new value.
//Set non-zero elements in v to 0, 0 elements to 1
std::vector<int> v{ -2,-1,0,1,2 };
std::replace(v.begin(), v.end(), 1, 2);//Rewrite 1 in v to 2
std::replace_if(v.begin(), v.end(), [](int a) {return !a; }, 1);//Rewrite 0 in v to 1
std::replace_if(v.begin(), v.end(), [](int a) {return a != 1; }, 0);//Change the non-zero value of v to 0Writing Algorithms Using Bidirectional Iterators
copy_backward(beg, end, dest)
move_backward(beg, end, dest)
The dest is the tail iterator of the output sequence by copying/moving the elements in the sequence to the destination location. Returns an iterator pointing to the element corresponding to beg in dest. Note that these two functions do not change the location of source sequence elements in the destination sequence!
std::vector<int> v1{ -3,-2,-1 };
std::vector<int> v2{ 1,2,3,4,5,6,7,8,9 };//Rewrite the last three elements of v2 to - 3, - 2, - 1
auto iter=std::copy_backward(v1.begin(), v1.end(), v2.end());//v2={1,2,3,4,5,6,-3,-2,-1}inplace_merge(beg, mid, end)
inplace_merge(beg, mid, end, comp)
Two ordered subsequences in the same sequence are merged into a single ordered sequence and written into the original sequence. By default, less than operators are used for comparison, and less than operators can also be redefined.
std::vector<int> v{ 5,3,1,6,4,2 };//The first three elements and the last three elements of v are arranged in ascending order of predicates.
std::inplace_merge(v.begin(), v.begin() + 3, v.end(),
[](int a, int b) {return a > b; });//Define greater than as a comparison operatorPartition and Sorting Algorithms
Both partitioning and sorting algorithms provide stable and unstable versions, which ensure that the relative position of the equivalent elements remains unchanged, but may consume more time and memory.
Partition algorithm
partition(beg, end, unaryPred)
stable_partition(beg, end, unaryPred)
Using unaryPred to divide the input sequence, the elements satisfying the conditions are placed in front of the sequence and the unsatisfactory elements are placed behind the sequence. Returns a position after the last element that satisfies the condition. If all elements do not satisfy the condition, return beg.
struct A { int i; char c; };
std::vector<A>vA1{ {6,'g'},{2,'h'},{-6,'t'},{3,'s'},{4,'p'} };
auto vA2 = vA1;
//Divide by whether i of A is positive or not
std::partition(vA1.begin(), vA1.end(), [](A a) {return a.i > 0; });//The results of Visual Stdio 2019 are vA1={6,'g'}, {2,'h'}, {4,'p'}, {3,'s'}, {-6,'t'} and {3,'s'} satisfying the conditions. The {3,'s'} originally ranked before {4,'p'} satisfying the conditions, and {3,'s'} ranked behind {4,'p'} after partitioning.
std::stable_partition(vA2.begin(), vA2.end(), [](A a) {return a.i > 0; });//VA2={6,'g'}, {2,'h'}, {3,'s'}, {4,'p'}, {-6,'t'}, the relative position of elements in the two parts has not changed.is_partitioned(beg, end, unaryPred)
If all the elements satisfying the conditions are placed before the elements that do not satisfy the conditions, then return true, and if the sequence is empty, return true.
int array[5] = { 1,3,5,6,8 };
bool b = std::is_partitioned(array, array + 5, [](int i) {return i & 1; });//Are odd numbers ahead of even numbers?partition_point(beg, end, unaryPred)
The input sequence must be a tail iterator that has been partitioned by unaryPred and returns the last element that satisfies the condition.
int array[5] = { 1,3,5,6,8 };
auto iter = std::partition_point(array, array + 5, [](int i) {return i & 1; });//iter points to the next position of the last odd number 5, and iter points to 6partition_copy(beg, end, dest1, dest2, unaryPred)
The element satisfying the condition in the sequence is copied to the destination sequence 1, and the element not satisfying the condition is copied to the destination sequence 2. An iterator pair is returned. Its first member points to the next position of the element replicating to the destination sequence 1, and the second member points to the next position of the element replicating to the destination sequence 2.
//Write the odd number in array to a1 and even number to a2
int array[5] = { 1,3,5,6,8 };
int a1[5] = { 15,25,35,45,55 };//After partition a1={1,3,5,45,55}
int a2[5] = { 10,20,30,40,50 };//After partition a2={6,8,30,40,50}
auto iters = std::partition_copy(array, array + 5, a1, a2, [](int a) {return a & 1; });//iters.first points to 45, iters.second points to 30Sorting algorithm
These algorithms require random access to iterators, using less than operator comparison elements by default. All sorting algorithms except partial_sort_copy return void.
sort(beg, end)
stable_sort(beg, end)
sort(beg, end, comp)
stable_sort(beg, end, comp)
Sort the sequence.
bool comp(int a, int b)//Descending order
{ return a > b; }
int main()
{
std::vector<int> v{ 7,5,1,4,6,9,3,2,8 };
std::sort(v.begin(), v.end(), comp);//Input function pointer
}is_sorted(beg, end)
is_sorted(beg, end, comp)
is_sorted_until(beg, end)
is_sorted_until(beg, end, comp)
is_sorted returns a bool value indicating whether the entire sequence is ordered. is_sorted_until finds the longest initial ordered subsequence in the input sequence and returns the tail iterator of the subsequence.
std::vector<int> v{ 1,2,3,4,5,4,3,2,1 };
bool b = std::is_sorted(v.begin(), v.end());//Is it ascending or not?
auto iter1 = std::is_sorted_until(v.begin(), v.end(), [](int a, int b) {return a < b; });//It's ascending from start to 5, iter1 points to 4 after 5.
auto iter2 = std::is_sorted_until(v.begin(), v.end(), [](int a, int b) {return a > b; });//Only the initial element is descending, and iter2 points to the first (starting from 0) element 2.partial_sort(beg, mid, end)
partial_sort(beg, mid, end, comp)
The elements from beg to end are sorted by comp, but only the first mid-beg. After the algorithm is finished, the elements from beg to end are sorted and will not be larger than any element from mid to end.
std::vector<int> v{ 7,5,1,4,6,9,3,2,8 };
std::partial_sort(v.begin(), v.begin() + 5, v.end());//Sort the smallest five elements in V. The result of Visual Studio 2019 is v={1,2,3,4,5,9,7,6,8}.partial_sort_copy(beg, end, destBeg, destEnd)
partial_sort_copy(beg, end, destBeg, destEnd, comp)
Sort the elements in the input range and place enough sorted elements in the sequence indicated by destBeg to destEnd. If the length of the destination range is not less than the input sequence, the whole input sequence is sorted and the result is written in front of the destination sequence. If the length of the destination sequence is less than that of the input sequence, only the same number of elements in the input sequence as the destination range are copied. The algorithm returns an iterator that points to the position after the sorted element of the destination sequence.
std::vector<int> v1{ 2,5,3,4,1 };
std::vector<int> v2(7, -1);//v2={1,2,3,4,5,-1,-1}
std::vector<int> v3(3, -1);//v3={1,2,3}
std::partial_sort_copy(v1.begin(), v1.end(), v2.begin(), v2.end());
std::partial_sort_copy(v1.begin(), v1.end(), v3.begin(), v3.end());nth_element(beg, nth, end)
nth_element(beg, nth, end, comp)
The parameter nth is an iterator, and after the algorithm is finished, the iterator points to exactly the value at this position after the sequence is sorted. The elements in the sequence are divided around nth: the elements before nth are less than or equal to it, and the elements after nth are greater than or equal to it.
//Median
std::vector<int> v{ 2,5,3,4,1 };
auto iter = v.begin() + 2;
std::nth_element(v.begin(), iter, v.end());//iter points to 3General rearrangement operation
The algorithm in <algorithm> does not change the size of the container!
These algorithms rearrange the elements in the sequence. The first two algorithms remove and unique satisfy some criteria for the first part of the sequence and return the end of an iterator marking subsequence. Other algorithms rearrange the whole sequence.
The basic versions of these algorithms are in-situ operations, and the _copy version does not change the original sequence but writes the rearrangement results to the specified destination sequence.
Rearrangement algorithm using forward iterator
remove(beg, end, val)
remove(beg, end, unaryPred)
remove_copy(beg, end, dest, val)
remove_copy(beg, end, dest, unaryPred)
Returns an iterator that points to the position after the last valid element by overwriting the deleted element from the sequence. Elements after iterators are no longer available!
std::vector<int> v{ 2,5,-3,4,-1 };
auto iter = std::remove_if(v.begin(), v.end(), [](int a) {return a < 0; });//v.size()==5
v.erase(iter, v.end());//v={2,5,4}unique(beg, end)
unique(beg, end, binaryPred)
unique_copy(beg, end, dest)
unique(beg, end, dest, binaryPred)
For adjacent duplicate elements, an iterator that points to the position after the last valid element is returned by overwriting the "delete" element. Elements after iterators are no longer available!
std::vector<int> v{ 2,4,3,5,2,3,4,1,3 };//v.size()==9
std::sort(v.begin(), v.end());//Need to sort first
auto iter = std::unique(v.begin(), v.end());//v.size()==9
v.erase(iter, v.end());//v={1,2,3,4,5}rotate(beg, mid, end)
rotate_copy(beg, mid, end, dest)
Let mid be the first element, then the element before mid+1 to end, and then the element before beg to mid, returning an element that points to the original beg position.
std::string s("0123456789");
std::rotate(s.begin(), s.begin() + 2, s.end());//s="2345678901"Rearrangement algorithm using bidirectional iterators
reverse(beg, end)
reverse_copy(beg, end)
Flip the sequence element, reverse returns void, and reverse_copy returns an iterator that points to the next location of the element copied to the destination sequence.
std::string s("abc");
std::reverse(s.begin(), s.end());//s="cba"Rearrangement algorithm using random access iterator
shuffle(beg, end, uniform_rand)
Mixed sequence elements, a random arrangement of sequence elements.
std::default_random_engine e(static_cast<unsigned>(time(0)));
std::vector<int> v{ 1,2,3,4,5,6,7,8,9 };
std::shuffle(v.begin(), v.end(), e);//One possibility is that v={5,3,4,2,6,7,1,8,9}Permutation algorithm
If n elements occupy n positions, a new arrangement can be obtained by changing the relative positions of different elements. For example, the sequence consisting of ABC has 3!= 6 kinds of arrangement: abc, acb, bac, bca, cab, cba. Note that these arrangements are in ascending order. In addition, the algorithm for generating permutations requires bidirectional iterators.
is_permutation(beg1, end1, beg2)
is_permutation(beg1, end1, beg2, binaryPred)
If two sequences have the same element, regardless of location, return true or false.
std::string s1("abcd");
std::string s2("bcad");
bool b = std::is_permutation(s1.begin(), s1.end(), s2.begin(), s2.end());//truenext_permutation(beg, end)
next_permutation(beg, end, comp)
prev_permutation(beg, end)
prev_permutation(beg, end, comp)
Next_permutation converts the sequence to the next one. If the current sequence is the last one, it converts it to the first one and returns false, otherwise it returns true. prev_permutation is similar to next_permutation.
std::string s("abcd");
do
{
std::cout << s << std::endl;
} while (std::next_permutation(s.begin(), s.end()));SET ALGORITHM FOR ORDER SEQUENCES
All these algorithms require that the sequence be ordered. Except include, all other algorithms return an iterator at the position after the element written to dest.
include(beg1, end1, beg2, end2)
include(beg1, end1, beg2, end2, comp)
If each element in the second sequence is contained in the first sequence, return true or false.
std::string s1("abcd");//order
std::string s2("acd");//order
bool b = std::includes(s1.begin(), s1.end(), s2.begin(), s2.end());//trueset_union(beg1, end1, beg2, end2, dest)
set_union(beg1, end1, beg2, end2, dest, comp)
Take the union set, the destination sequence contains all the elements that have appeared in the two input sequences, and there should be no duplicate elements in the input sequence.
std::string s1("abcd");//order
std::string s2("acde");//order
std::string s3(8, ' ');
auto iter = std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), s3.begin());
s3.erase(iter, s3.end());//s3="abcde"set_intersection(beg1, end1, beg2, end2, dest)
set_intersection(beg1, end1, beg2, end2, dest, comp)
Take the intersection, the target sequence contains two elements that appear together in the input sequence.
std::string s1("abcd");//order
std::string s2("acde");//order
std::string s3(4, ' ');
auto iter = std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), s3.begin());
s3.erase(iter, s3.end());//s3="acd"set_difference(beg1, end1, beg2, end2, dest)
set_difference(beg1, end1, beg2, end2, dest, comp)
Set 1 minus set 2. The destination sequence contains elements that appear in input sequence 1 but not in sequence 2.
std::string s1("abcd");//order
std::string s2("acde");//order
std::string s3(4, ' ');
auto iter = std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), s3.begin());
s3.erase(iter, s3.end());//s3="b"set_symmetric_difference(beg1, end1, beg2, end2, dest)
set_symmetric_difference(beg1, end1, beg2, end2, dest, comp)
Set 1 plus set 2 subtracts the intersection of the two. The destination sequence contains elements that appear in one sequence but not in another.
std::string s1("abcd");//order
std::string s2("acde");//order
std::string s3(8, ' ');
auto iter = std::set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), s3.begin());
s3.erase(iter, s3.end());//s3="be"Maximum and minimum
min(val1, val2)
min(val1, val2, comp)
min(init_list)
min(init_list, comp)
max(val1, val2)
max(val1, val2, comp)
max(init_list)
max(init_list, comp)
Returns the minimum / maximum values in val1 and val2, or the minimum / maximum values in the initialization list. The two argument types must be identical. Parameters and return types are references to const.
double m1 = std::min(2.0, 6.2);//2.0
int m2 = std::max({ 2,5,6,9,-10,-8 }, [](int a, int b) {return std::abs(a) < std::abs(b); });//The maximum absolute value, -10minmax(val1, val2)
minmax(val1, val2, comp)
minmax(init_list)
minmax(init_list, comp)
Returns a pair whose first member is the minimum and second member is the maximum.
int a = 3, b = 2;
auto ms = std::minmax(a, b);
a = ms.first;//first is a reference to b, now a=2, b=2
b = ms.second;//Seconds are references to a, but a has been changed to 2, b=2
std::cout << a << ' ' << b << '\n';//2,2min_element(beg, end)
min_element(beg, end, comp)
max_element(beg, end)
max_element(beg, end, comp)
minmax_element(beg, end)
minmax_element(beg, end, comp)
The first four algorithms return an iterator to point to the minimum/maximum value in the sequence, and the second two to return an iterator pair whose first member points to the minimum value and second member points to the maximum value.
int array[10] = { 1,5,9,6,3,5,7,8,2,4 };
auto iters = std::minmax_element(array, array + 10);
long long posDiff = iters.second - iters.first;//Location distance
int valDiff = *iters.second - *iters.first;//Distance of valuesDictionary Order Comparison
lexicographical_compare(beg1, end1, beg2, end2)
lexicographical_compare(beg1, end1, beg2, end2, comp)
Determine whether the dictionary order of sequence 1 is less than sequence 2. If it is less than sequence 1, return true or false.
int array[6] = { 1,5,9,6,5,5 };
std::vector<int> v{ 1,5,9,6,4 };
std::deque<int> d{ 1,5,9,6,4 };
std::forward_list<int>l{ 1,5,9 };
bool b1 = std::lexicographical_compare(array, array + 6, v.begin(), v.end());//5 is not less than 4, false
bool b2 = std::lexicographical_compare(v.begin(), v.end(), d.begin(), d.end());//Equality requires no less than, false
bool b3 = std::lexicographical_compare(d.begin(), d.end(), l.begin(), l.end());//The list length is shorter, falsefinish