0. What is "algorithm":
The < algorithm > header file defines a set of functions designed to be used on ranges of elements.
The so-called "element range" refers to the sequence of objects that can be accessed through iterators or pointers, such as arrays or some SLT containers. Note that the algorithm in < algorithm > directly operates on the value through the iterator and will not affect the structure of any container in any form (it will never affect the size or storage allocation of the container).
In one sentence:
The STL algorithm defined in < algorithm > operates the elements in the STL container through the "iterator" and will not affect the structure of the container.
Matters needing attention:
The parameter iterator range of the algorithm in < algorithm > is generally [first, last], that is, the "front closed and rear open" interval. Last is similar to the end tail iterator, pointing to the position behind the last element of the container.
1. Non-modifying sequence operations:
Actions that do not modify the order of elements in the container:
1.1 find: (Find value in range)
Function prototype:
template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& val)
{
while(first != last) {
if(*first == val) return first;
++first;
}
return last;
}
The find() function finds the value val in the given iterator interval [first, last].
If val exists, the iterator pointing to the first element in the interval is returned;
If val does not exist, the last iterator is returned.
Use examples:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int myints[] = { 10, 20, 30, 40 };
vector<int> myvector(myints, myints + 4);
vector<int>::const_iterator it;
it = find(myvector.cbegin(), myvector.cend(), 30);
if(it != myvector.cend()) {
cout << "Element found in myvector: " << *it << '\n';
}
else {
cout << "Element not found in myvector\n";
}
return 0;
}
------
Element found in myvector: 30
Note: the find () function does not modify the value of the element in the container, so const can be used_ Iterator iterator, but it should be noted that the types of return value and input parameter must be const type, otherwise an error will be reported due to type matching during compilation (error reason: the "=" in it = find() is not overloaded).
Time complexity:
Because the interval from first to last is traversed, the time complexity is O(n).
1.2 count: (Count appearances of value in range)
Function prototype:
template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count(InputIterator first, InputIterator last, const T& val)
{
typename iterator_traits<InputIterator>::differenct_type ret = 0;
while(first != last) {
if(*first == val) ++ret;
++first;
}
return ret;
}
The count() function counts the number of occurrences of the parameter val in the given iterator interval [first, last], and returns the number of statistics.
Use examples:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int myints[] = { 10,20,30,30,20,10,10,20 };
vector<int> myvector(myints, myints + sizeof(myints)/sizeof(int));
int mycount = count(myvector.cbegin(), myvector.cend(), 10);
cout << "10 appears times: " << mycount << '\n';
return 0;
}
------
10 appears times: 3
Time complexity:
The count() function also needs to traverse the entire container, so the time complexity is O(n).
1.3 equal: (Test whether the elements in two ranges are equal)
Function prototype:
template <class InputIterator1, class InputIterator2>
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
{
while(first1 != last1) {
if(*first1 != *first2) return false;
++first1;
++first2;
}
return true;
}
//Use the equal() version of the custom comparison function:
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator first2, bool func) {}
Compares whether the values of the specified range in two containers are equal, and returns the bool value.
The equal() function has two overloaded forms. It receives the versions of three parameters and compares the elements in the two containers with operator =; Versions that accept four parameters can use custom comparison functions.
Use examples:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool mypredicate(int i, int j) {
return (i == j);
}
int main() {
int myints[] = { 20,40,60,80,100 };
vector<int> myvector(myints, myints + sizeof(myints)/sizeof(int));
//Accept the equal version of the three parameters and compare with operator =:
if( equal(myvector.cbegin(), myvector.cend(), myints) ) {
cout << "The contents of both sequences are equal.\n";
}
else {
cout << "The contents of both sequences differ.\n";
}
//Accept the equal version of four parameters and use the custom comparison function:
if( equal(myvector.cbegin(), myvector.cend(), myints, mypredicate) ) {
cout << "The contents of both sequences are equal.\n";
}
else {
cout << "The contents of both sequences differ.\n";
}
return 0;
}
------
The contents of both sequences are equal.
The contents of both sequences are equal.
Time complexity:
It also needs to traverse the contents of the container in the iterator range, so the time complexity is O(n).
1.4 search: (Search range for subsequence)
Function prototype:
//equality (1)
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
//predicate (2)
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
The find() function is used to find whether an element exists in a range, and the search() function is used to find whether a series of elements exist in a range.
There are also two versions of the find() function: the version compared with operator = and the version compared with a custom method.
Return value: if found, the iterator pointing to the first element within the found range is returned; If not found, last1 is returned.
Use examples:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool mypredicate(int i, int j) {
return (i == j);
}
int main() {
vector<int> haystack;
for(int i = 1; i < 10; i++) {
haystack.push_back(i * 10); //haystack: 10,20,30,40,50,60,70,80,90
}
int needle[] = { 40,50,60,70 };
vector<int>::const_iterator it;
it = search(haystack.cbegin(), haystack.cend(), needle, needle + sizeof(needle)/sizeof(int));
if(it != haystack.cend()) {
cout << "needle found at position: " << (it - haystack.cbegin()) << '\n';
}
else {
cout << "needle not found\n";
}
//Method 2: use a custom comparison function:
it = search(haystack.cbegin(), haystack.cend(), needle, needle + sizeof(needle)/sizeof(int), mypredicate);
if(it != haystack.cend()) {
cout << "needle found at position: " << (it - haystack.cbegin()) << '\n';
}
else {
cout << "needle not found\n";
}
return 0;
}
------
needle found at position: 3
needle found at position: 3
Time complexity:
O(n2).
2. Modifying sequence operations:
Actions that modify the order of elements in the container:
2.1 copy: (Copy range of elements)
Function prototype:
template <class InputIterator, class OutputIterator> OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result);
The function is equivalent to:
template<class InputIterator, class OutputIterator>
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
{
while (first != last) {
*result = *first;
++result; ++first;
}
return result;
}
Copy the source data in the [first, last) range to the target location specified by result, and the return value is An iterator to the end of the destination range where elements have been copied.
Use examples:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int myints[] = { 10, 20, 30, 40, 50, 60, 70 };
vector<int> myvector(7);
copy(myints, myints + 7, myvector.begin());
cout << "myvector contains: ";
for(vector<int>::const_iterator it = myvector.cbegin(); it != myvector.cend(); ++it) {
cout << *it << ' ';
}
cout << '\n';
return 0;
}
------
myvector contains: 10 20 30 40 50 60 70
Time complexity:
O(n).
2.2 move: (move range of elements)
Function prototype:
template <class InputIterator, class OutputIterator> OutputIterator move (InputIterator first, InputIterator last, OutputIterator result);
The function is equivalent to:
template<class InputIterator, class OutputIterator>
OutputIterator move (InputIterator first, InputIterator last, OutputIterator result)
{
while (first != last) {
*result = std::move(*first);
++result; ++first;
}
return result;
}
The move() function is used to "move" the elements in the [first, last) interval to the target position specified by result.
After the move, the state of the source location [first, last] is "in an unspecified but valid state". This effect is similar to the effect of the std::move function used in the move constructor. In fact, the move function in STL does call the std::move function version of a single parameter.
"Unspecified but valid state" can be understood as an element in space that is empty because it has been removed, but its sizeof size is still.
Use examples:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
string array[] = { "air", "water", "fire", "earth" };
vector<string> foo(array, array + 4);
vector<string> bar(4);
move(foo.begin(), foo.end(), bar.begin());
cout << "foo.size(): " << foo.size() << "; " << "bar.size(): " << bar.size() << ".\n";
cout << "foo content: ";
for(auto &r : foo)
cout << r << ' ';
cout << '\n';
cout << "bar content: ";
for(auto &r : bar)
cout << r << ' ';
cout << '\n';
return 0;
}
------
foo.size(): 4; bar.size(): 4.
foo content:
bar content: air water fire earth
Time complexity:
O(n).
2.3 fill: (Fill range with value)
Function prototype:
template <class ForwardIterator, class T> void fill (ForwardIterator first, ForwardIterator last, const T& val);
The fill() function is used to fill in all the values of the [first, last) range content container as val.
The return value of the fill() function is none (void function).
Use examples:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> myvector(8);
fill(myvector.begin(), myvector.end(), 5);
cout << "after fill myvector content: ";
for(vector<int>::const_iterator it = myvector.begin(); it != myvector.end(); ++it) {
cout << *it << ' ';
}
cout << '\n';
return 0;
}
------
after fill myvector content: 5 5 5 5 5 5 5 5```
**Time complexity:**
O(n).
## 2.6 remove: (Remove value from range)
## 2.7 reverse: (Reverse range)
**Function prototype:**
```cpp
template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last);
The reverse() function reverses the order of the elements in the interval [first, last] in the container.
The return value of the reverse() function is none (void function).
Use examples:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
vector<int> myvector(array, array + sizeof(array)/sizeof(int));
reverse(myvector.begin(), myvector.end());
cout << "after reverse myvector content: ";
for(vector<int>::const_iterator it = myvector.cbegin(); it != myvector.cend(); ++it) {
cout << *it << ' ';
}
cout << '\n';
return 0;
}
------
after reverse myvector content: 9 8 7 6 5 4 3 2 1
3. Partitions:
Partition:
3.1 partition: (Partition range in two)
Function prototype:
template <class ForwardIterator, class UnaryPredicate> ForwardIterator partition (ForwardIterator first, ForwardIterator last, UnaryPredicate pred);
The partition() function is used to partition the container elements within the [first, last] range according to the custom method pred (divided into two parts). The return value is the iterator pointing to the first element of the partition in the second part.
Use examples:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool IsOdd(int i) {
return ( (i%2) ==1 );
}
int main() {
int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
vector<int> myvector(array, array + sizeof(array)/sizeof(int));
vector<int>::iterator bound;
bound = partition(myvector.begin(), myvector.end(), IsOdd);
cout << "after partition myvector content: ";
for(vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it) {
cout << *it << ' ';
}
cout << '\n';
cout << "the second partition content: ";
for(vector<int>::iterator it = bound; it != myvector.end(); ++it) {
cout << *it << ' ';
}
cout << '\n';
return 0;
}
------
1 9 3 7 5 6 4 8 2
6 4 8 2
4. Sorting:
Sort:
4.1 sort: (Sort elements in range)
Function prototype:
//default (1) template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last); //custom (2) template <class RandomAccessIterator, class Compare> void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
The sort() function is used to sort the elements within the [first, last] range. The default sorting method is operator < (i.e. "from small to large" sorting). You can also accept the custom sorting method comp.
Use examples:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool myfunction(int i, int j) {
return ( i > j );
}
int main() {
int array[] = { 32, 71, 12, 45, 26, 80, 53, 33 };
vector<int> myvector(array, array + sizeof(array)/sizeof(int));
sort(myvector.begin(), myvector.end());
cout << "after sort myvector content: ";
for(auto &r : myvector)
cout << r << ' ';
cout << '\n';
sort(myvector.begin(), myvector.end(), myfunction);
cout << "after another sort myvector content: ";
for(auto &r : myvector)
cout << r << ' ';
cout << '\n';
return 0;
}
------
after sort myvector content: 12 26 32 33 45 53 71 80
after another sort myvector content: 80 71 53 45 33 32 26 12
5. Binary Search(operating on partitioned/sorted ranges):
Binary search:
5.1 binary_search:
Function prototype:
//default (1)
template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last,
const T& val);
//custom (2)
template <class ForwardIterator, class T, class Compare>
bool binary_search (ForwardIterator first, ForwardIterator last,
const T& val, Compare comp);
6. Merge(operating on sorted ranges):
Consolidation:
6.1 merge:
Function prototype:
//default (1)
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
//custom (2)
template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
The merge() function is used to merge the container elements of the [first1, last1) interval and the [first2, last2) interval, and store the merged results in the location specified by result. The default merge order of merge() is operator < (from small to large), and it can also accept the user-defined sorting method comp.
The merge() function must merge on the basis of sort(), otherwise the merge results will be out of order. The sorting algorithms of sort () and merge () must be consistent, that is, both use operator < or the same comp function.
The return value of the merge() function is the tail iterator of the merged container (the position after the last element of the container).
Use examples:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int first[] = { 5, 10, 15, 20, 25 };
int second[] = { 50, 1, 2, 3, 4 };
vector<int> result(10);
sort(first, first + 5);
sort(second, second + 5);
vector<int>::iterator it = merge(first, first + 5, second, second + 5, result.begin());
for(vector<int>::iterator iter = result.begin(); iter != it; iter++) {
cout << *iter << ' ';
}
cout << '\n';
return 0;
}
------
1 2 3 4 5 10 15 20 25 50
7. Heap:
Heap operation:
8. Min/max:
Find the maximum / minimum value and accept the comparison method specified by the user