——Common sorting algorithms
Algorithm Introduction
- Sort / / sort the elements in the container
- random_shuffle / / (shuffle) randomly adjust the order of elements within the specified range
- Merge / / merge container elements and store them in another container
- reverse / / reverses the elements in the specified range
sort algorithm
Function description
Sort the elements in the container
Function prototype
sort(iterator begin, iterator end, _Pred);
As follows, sort algorithm is used to sort a group of data stored in the vector container
#include <iostream>
using namespace std;
#Include < vector > / / used to create a vector container
#Include < algorithm > / / for_each and sort algorithms
#Include < functional > / / used for greater < int > () functor
void Print(int value) {
cout << value << " ";
}
void PrintVector(vector<int> &v) {
for_each(v.begin(), v.end(), Print);
cout << endl;
}
void RandomInsert(vector<int> &v) {
for (int i = 0; i < 5; i++) {
v.push_back(rand() % 10 + 1); // 1 ~ 10
}
}
class Dec {
public:
bool operator()(int value1, int value2) {
return value1 < value2;
}
};
int main() {
// Create container array
vector<int> v;
// Insert 5 data randomly
RandomInsert(v);
// Print elements in container
PrintVector(v); // 2 8 5 1 10
// 1. Arrange containers v in ascending order
sort(v.begin(), v.end());
PrintVector(v); // 1 2 5 8 10
// 2. Arrange containers v in descending order -- with the help of built-in imitation function
sort(v.begin(), v.end(), greater<int>());
PrintVector(v); // 10 8 5 2 1
// Custom functor -- ascending
sort(v.begin(), v.end(), Dec());
PrintVector(v); // 1 2 5 8 10
system("pause");
return 0;
}
random_shuffle algorithm
Function description
Adjust the order of elements within the specified range (shuffle)
Function prototype
random_shuffle(iterator begin, iterator end);
Use random as follows_ The shuffle algorithm disrupts a set of data stored in the vector container
#include <iostream>
using namespace std;
#Include < vector > / / used to create a vector container
#Include < algorithm > / / for_each and random_shuffle algorithm
#Include < CTime > / / used for random number seed
void Print(int value) {
cout << value << " ";
}
void PrintVector(vector<int> &v) {
for_each(v.begin(), v.end(), Print);
cout << endl;
}
void RandomInsert(vector<int> &v) {
for (int i = 0; i < 5; i++) {
v.push_back(rand() % 10 + 1); // 1 ~ 10
}
}
int main() {
// Random number seed
srand((unsigned int)time(NULL));
// Create container array
vector<int> v;
// Insert 5 data randomly
RandomInsert(v);
// Print elements in container
PrintVector(v); // 9 3 5 3 3
// 1. Disrupt the elements within the specified range in the container
random_shuffle(v.begin(), v.end());
PrintVector(v); // 3 5 3 3 9
system("pause");
return 0;
}
merge algorithm
Function description
Important: the two containers must be (in the same direction) orderly!
Container elements are merged and stored in another container
Function prototype
merge(iterator begin1, iterator end1, iterator begin2, iterator end2, iterator dest_begin);
As follows, the merge algorithm is used to reorganize two ordered containers into a new container (ordered)
#include <iostream>
using namespace std;
#Include < vector > / / used to create a vector container
#Include < algorithm > / / for_each and merge algorithms
void Print(int value) {
cout << value << " ";
}
void PrintVector(vector<int> &v) {
for_each(v.begin(), v.end(), Print);
cout << endl;
}
int main() {
// Create container array
vector<int> v1;
vector<int> v2;
vector<int> dest;
for (int i = 0; i < 5; i++) {
v1.push_back(i);
v2.push_back(i + 3);
}
// Print elements in containers v1 and v2
PrintVector(v1); // 0 1 2 3 4
PrintVector(v2); // 3 4 5 6 7
// This container needs to be expanded before inserting data from two containers
dest.resize(v1.size() + v2.size());
// Merge the two containers into container dest
merge(v1.begin(), v1.end(), v2.begin(), v2.end(), dest.begin());
PrintVector(dest); // 0 1 2 3 3 4 4 5 6 7
system("pause");
return 0;
}
reverse algorithm
Function description
Inverts the elements in the specified range
Function prototype
reverse(iterator begin, iterator end);
The reverse algorithm is used to reverse the elements in an interval of the container
#include <iostream>
using namespace std;
#Include < vector > / / used to create a vector container
#Include < algorithm > / / for_each and reverse algorithms
void Print(int value) {
cout << value << " ";
}
void PrintVector(vector<int> &v) {
for_each(v.begin(), v.end(), Print);
cout << endl;
}
int main() {
// Create container array
vector<int> v;
for (int i = 0; i < 5; i++) {
v.push_back(i);
}
// Before reversal
PrintVector(v); // 0 1 2 3 4
reverse(v.begin(), v.end());
// After reversal
PrintVector(v); // 4 3 2 1 0
system("pause");
return 0;
}
——Common copy and replace algorithms
Algorithm Introduction
- Copy / / copy the elements of the specified range in the container to another container
- replace / / modify the old element of the specified range in the container to a new element
- replace_if / / modify the old elements that meet the conditions within the specified scope of the container to new elements
- Swap / / swap elements of two containers
copy algorithm
Function description
Key: remember to expand the capacity before copying!
Copies the specified range of elements in a container to another container
Function prototype
copy(iterator begin, iterator end, iterator dest_begin);
As follows, use the copy algorithm to copy the elements in the container to another container
#include <iostream>
using namespace std;
#Include < vector > / / used to create a vector container
#Include < algorithm > / / for_each and copy algorithms
void Print(int value) {
cout << value << " ";
}
void PrintVector(vector<int> &v) {
for_each(v.begin(), v.end(), Print);
cout << endl;
}
int main() {
// Create container array
vector<int> v;
vector<int> dest;
for (int i = 0; i < 5; i++) {
v.push_back(i);
}
// Copy algorithm is used to copy the elements of container v into dest
dest.resize(v.size());
copy(v.begin(), v.end(), dest.begin());
PrintVector(dest); // PrintVector
system("pause");
return 0;
}
replace algorithm
Function description
Modifies the old element of the specified range in the container to a new element
Function prototype
replace(iterator begin, iterator end, oldvalue, newvalue);
Use the replace algorithm to modify the old element of the specified range in the container into a new element
#include <iostream>
using namespace std;
#Include < vector > / / used to create a vector container
#Include < algorithm > / / for_each and replace algorithms
void Print(int value) {
cout << value << " ";
}
void PrintVector(vector<int> &v) {
for_each(v.begin(), v.end(), Print);
cout << endl;
}
int main() {
vector<int> v;
v.push_back(1);
v.push_back(1);
v.push_back(1);
v.push_back(2);
v.push_back(3);
PrintVector(v); // 1 1 1 2 3
// If we want to replace all element 1 in container v with element 100, we need to use the algorithm replace
// The first (second) parameters represent the start (end) position pointed to by the iterator
// The third parameter represents the old element to be replaced, and the fourth parameter represents the new element to replace the old element
replace(v.begin(), v.end(), 1, 100);
PrintVector(v); // 100 100 100 2 3
system("pause");
return 0;
}
replace_if algorithm
Function description
Modify the old elements that meet the conditions within the specified scope of the container to new elements
Function prototype
replace_if(iterator begin, iterator end, _Pred, newvalue);
Using algorithm replace_if modifies the old element that meets the conditions within the specified scope of the container to a new element
#include <iostream>
using namespace std;
#Include < vector > / / used to create a vector container
#Include < algorithm > / / for_each and replace_if algorithm
void Print(int value) {
cout << value << " ";
}
void PrintVector(vector<int> &v) {
for_each(v.begin(), v.end(), Print);
cout << endl;
}
class GreaterOne {
public:
bool operator()(int value) {
return value > 1;
}
};
int main() {
vector<int> v;
v.push_back(1);
v.push_back(1);
v.push_back(1);
v.push_back(2);
v.push_back(3);
PrintVector(v); // 1 1 1 2 3
// If we want to replace all elements greater than 1 in container v with element 200, we need to use the algorithm replace_if
// The first (second) parameters represent the start (end) position pointed to by the iterator
// The third parameter represents the predicate (imitation function -- bool), and the fourth parameter represents the new element that replaces the old element
replace_if(v.begin(), v.end(), GreaterOne(), 200);
PrintVector(v); // 1 1 1 200 200
system("pause");
return 0;
}
swap algorithm
Function description
Swap elements of two containers
Function prototype
swap(container v1, container v2);
Swap the elements of two containers using the algorithm swap
#include <iostream>
using namespace std;
#Include < vector > / / used to create a vector container
#Include < algorithm > / / for_each and swap algorithms
void Print(int value) {
cout << value << " ";
}
void PrintVector(vector<int> &v) {
for_each(v.begin(), v.end(), Print);
cout << endl;
}
int main() {
vector<int> v;
vector<int> v1;
for (int i = 0; i < 5; i++) {
v.push_back(i + 1);
v1.push_back(10 - i);
}
PrintVector(v); // 1 2 3 4 5
PrintVector(v1); // 10 9 8 7 6
// If we want to replace the elements in containers v and v1, we can use the algorithm swap
// Both parameters represent the container. After replacement, the elements in the container are exchanged
swap(v, v1);
PrintVector(v); // 10 9 8 7 6
PrintVector(v1); // 1 2 3 4 5
system("pause");
return 0;
}
——Common arithmetic generation algorithms
be careful
Arithmetic generation is a small algorithm that contains header files < numeric > when used
Algorithm Introduction
- Calculate / / calculate the sum of elements in the container
- fill / / add element to container
Calculate algorithm
Function description
Calculate the cumulative sum of interval content container elements
Function prototype
accumulate(iterator begin, iterator end, value);
Calculate the cumulative sum of elements in the container using the algorithm accumulate
#include <iostream>
using namespace std;
#Include < vector > / / used to create a vector container
#Include < numeric > / / used for the calculate algorithm
int main() {
vector<int> v;
for (int i = 0; i < 10; i++) {
v.push_back(i);
}
// If we want to calculate the sum of all elements in the container, we can use the algorithm calculate
// The first two parameters represent the start (end) position pointed to by the iterator
// The latter parameter represents the value added based on the cumulative sum
int total = accumulate(v.begin(), v.end(), 0);
cout << total << endl; // 45
total = accumulate(v.begin(), v.end(), 100);
cout << total << endl; // 145
system("pause");
return 0;
}
fill algorithm
Function description
Fills the container with the specified element
Function prototype
fill(iterator begin, iterator end, value);
Fill the container with the specified elements using the algorithm fill
#include <iostream>
using namespace std;
#Include < vector > / / used to create a vector container
#Include < algorithm > / / for_each algorithm
#Include < numeric > / / used for fill algorithm
void Print(int value) {
cout << value << " ";
}
void PrintVector(vector<int> &v) {
for_each(v.begin(), v.end(), Print);
cout << endl;
}
int main() {
vector<int> v;
for (int i = 0; i < 5; i++) {
v.push_back(i);
}
PrintVector(v); // 0 1 2 3 4
// Filling the container v with elements -- overwrites the original data
fill(v.begin(), v.end(), 100);
PrintVector(v); // 100 100 100 100 100
system("pause");
return 0;
}
——Common set algorithm
Algorithm Introduction
- set_intersection / / find the intersection of two containers
- set_union / / find the union of two containers
- set_difference / / find the difference set of two containers
set_intersection algorithm
Function description
Key: the target container needs to open up space in advance! The space size is not explained in detail
Find the intersection of two containers
Function prototype
set_intersection(iterator begin1, iterator end1, iterator begin2, iterator end2, iterator dest_begin);
Using algorithm set_intersection finding the intersection of two containers
#include <iostream>
using namespace std;
#Include < vector > / / used to create a vector container
#Include < algorithm > / / for_each min and set_intersection algorithm
void Print(int value) {
cout << value << " ";
}
void PrintVector(vector<int> &v) {
for_each(v.begin(), v.end(), Print);
cout << endl;
}
int main() {
vector<int> v;
vector<int> v1;
vector<int> dest;
for (int i = 0; i < 5; i++) {
v.push_back(i);
v1.push_back(i + 3);
}
PrintVector(v); // 0 1 2 3 4
PrintVector(v1); // 3 4 5 6 7
// If we want to find the intersection of container v and v1 and store the result in another target container, we can use the algorithm set_intersection
// The first four parameters are the start (end) iterators of the two containers, and the last parameter is the start position of the target iterator
dest.resize(min(v.size(), v1.size()));
vector<int>::iterator End = set_intersection(v.begin(), v.end(), v1.begin(), v1.end(), dest.begin());
for (vector<int>::iterator pos = dest.begin(); pos != End; pos++) {
cout << *pos << " "; // 3 4
}
cout << endl;
system("pause");
return 0;
}
set_union algorithm
Function description
Key: the target container needs to open up space in advance! The space size is not explained in detail
Find the union of two containers
Function prototype
set_union(iterator begin1, iterator end1, iterator begin2, iterator end2, iterator dest_begin);
Using algorithm set_union to find the union of two containers
#include <iostream>
using namespace std;
#Include < vector > / / used to create a vector container
#Include < algorithm > / / for_each and set_union algorithm
void Print(int value) {
cout << value << " ";
}
void PrintVector(vector<int> &v) {
for_each(v.begin(), v.end(), Print);
cout << endl;
}
int main() {
vector<int> v;
vector<int> v1;
vector<int> dest;
for (int i = 0; i < 5; i++) {
v.push_back(i);
v1.push_back(i + 3);
}
PrintVector(v); // 0 1 2 3 4
PrintVector(v1); // 3 4 5 6 7
// If we want to find the union of containers v and v1 and store the results in another target container, we can use the algorithm set_union
// The first four parameters are the start (end) iterators of the two containers, and the last parameter is the start position of the target iterator
dest.resize(v.size() + v1.size());
vector<int>::iterator End = set_union(v.begin(), v.end(), v1.begin(), v1.end(), dest.begin());
for (vector<int>::iterator pos = dest.begin(); pos != End; pos++) {
cout << *pos << " "; // 0 1 2 3 4 5 6 7
}
cout << endl;
system("pause");
return 0;
}
set_difference algorithm
Function description
Key: the target container needs to open up space in advance! The space size is not explained in detail
Find the difference set of two containers
Function prototype
set_difference(iterator begin1, iterator end1, iterator begin2, iterator end2, iterator dest_begin);
Using algorithm set_difference finding the difference set of two containers
#include <iostream>
using namespace std;
#Include < vector > / / used to create a vector container
#Include < algorithm > / / for_each and max and set_difference algorithm
void Print(int value) {
cout << value << " ";
}
void PrintVector(vector<int> &v) {
for_each(v.begin(), v.end(), Print);
cout << endl;
}
int main() {
vector<int> v;
vector<int> v1;
vector<int> dest;
for (int i = 0; i < 5; i++) {
v.push_back(i);
v1.push_back(i + 3);
}
PrintVector(v); // 0 1 2 3 4
PrintVector(v1); // 3 4 5 6 7
// 1. If we want to find the difference set between containers v and v1 and store the result in another target container, we can use the algorithm set_union
// The first four parameters are the start (end) iterators of the two containers, and the last parameter is the start position of the target iterator
dest.resize(max(v.size(), v1.size()));
vector<int>::iterator End = set_difference(v.begin(), v.end(), v1.begin(), v1.end(), dest.begin());
for (vector<int>::iterator pos = dest.begin(); pos != End; pos++) {
cout << *pos << " "; // 0 1 2
}
cout << endl;
// 2. If we want to find the difference set between containers v1 and v and store the result in another target container, we can also use the algorithm set_union
End = set_difference(v1.begin(), v1.end(), v.begin(), v.end(), dest.begin());
for (vector<int>::iterator pos = dest.begin(); pos != End; pos++) {
cout << *pos << " "; // 5 6 7
}
cout << endl;
system("pause");
return 0;
}