0. < algorithm> 是什么：
< algorithm> 头文件定义了一组专门用于操作元素范围的函数（designed to be used on ranges of elements）。
所谓“元素范围”指的是可以通过 迭代器 或 指针 进行访问的对象序列，例如数组或某些SLT容器。注意，< algorithm>中的算法通过迭代器直接对值进行操作，不会以任何形式影响任何容器的结构（它永远不会影响容器的大小或存储分配）。
一句话概括：
?? < algorithm> 中定义的STL算法通过 “迭代器” 来操作STL容器中的元素，且不会影响容器的结构。
需要注意的事：
?? < algorithm> 中的算法的参数迭代器范围一般都是 [first, last)，即“前闭后开”区间，last类似于end尾迭代器，指向容器最后一个元素后面的位置。
1. Non-modifying sequence operations：
不会修改容器中元素的顺序的操作：
1.1 find：（Find value in range）
函数原型：
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;
}
find()函数在给定的迭代器区间[first, last) 中查找值 val。
如果val存在，则返回区间内的指向第一个元素的迭代器；
如果val不存在，则返回 last迭代器。
使用举例：
#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
注意：find()函数不会修改容器中元素的值，所以可以使用 const_iterator 迭代器，但需要注意返回值、入参的类型必须都是const类型的，否则编译时会因类型匹配报错（报错原因：it = find() 中的 “=” 没有重载）。
时间复杂度：
因为要从first到last的区间遍历，所以时间复杂度是 O(n)。
1.2 count：（Count appearances of value in range）
函数原型：
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;
}
count() 函数在给定的迭代器区间 [first, last) 中统计参数 val出现的次数，返回统计到的个数。
使用举例：
#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
时间复杂度：
count()函数同样需要遍历整个容器，所以时间复杂度是 O(n)。
1.3 equal：（Test whether the elements in two ranges are equal）
函数原型：
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;
}
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator first2, bool func) {}
比较两个容器中指定范围的值是否相等，返回bool值。
equal()函数有两种重载形式，接收三个参数的版本使用 operator= 对两个容器中的元素进行比较；接受四个参数的版本可使用自定义的比较函数。
使用举例：
#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));
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";
}
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.
时间复杂度：
同样需要遍历迭代器范围的容器内容，所以时间复杂度是 O(n)。
1.4 search：（Search range for subsequence）
函数原型：
template <class ForwardIterator1, class ForwardIterator2>
ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2);
template <class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred);
find()函数是用于在一个范围内查找某一个元素是否存在，search()函数是用于一个范围内查找一个一连串的元素是否存在。
find()函数同样存在两个版本：使用 operator=进行比较的版本 及 使用自定义方法进行比较的版本。
返回值：如果找到，则返回指向找到的范围内的第一元素的迭代器；如果未找到，则返回last1。
使用举例：
#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);
}
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";
}
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
时间复杂度：
O(n2).
2. Modifying sequence operations：
会修改容器中元素顺序的操作：
2.1 copy：（Copy range of elements）
函数原型：
template <class InputIterator, class OutputIterator>
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result);
作用相当于：
template<class InputIterator, class OutputIterator>
OutputIterator copy (InputIterator first, InputIterator last, OutputIterator result)
{
while (first != last) {
*result = *first;
++result; ++first;
}
return result;
}
将 [first, last) 范围到的源数据 拷贝到 result 指定的目标位置，返回值是目标位置的末尾迭代器（An iterator to the end of the destination range where elements have been copied）。
使用举例：
#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
时间复杂度：
O(n).
2.2 move：（move range of elements）
函数原型：
template <class InputIterator, class OutputIterator>
OutputIterator move (InputIterator first, InputIterator last, OutputIterator result);
作用相当于：
template<class InputIterator, class OutputIterator>
OutputIterator move (InputIterator first, InputIterator last, OutputIterator result)
{
while (first != last) {
*result = std::move(*first);
++result; ++first;
}
return result;
}
move()函数的作用是将 [first, last) 区间内的元素 “移动” 到 result 指定的目标位置。
移动后，源位置 [first, last) 的状态是“未指定但有效的状态”（in an unspecified but valid state），这个作用类似于 移动构造函数中使用的 std::move 函数的效果，事实上 STL中的move函数中也确实调用了 单个参数的 std::move 函数版本。
“未指定但有效的状态” 可以理解为空间上的元素因为被移走已经为空，但对其求 sizeof 大小仍在。
使用举例：
#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
时间复杂度：
O(n).
2.3 fill：（Fill range with value）
函数原型：
template <class ForwardIterator, class T>
void fill (ForwardIterator first, ForwardIterator last, const T& val);
fill()函数的作用是将 [first, last) 范围内容器的值全部填写为 val。
fill()函数的返回值是none（void函数）。
使用举例：
#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```
**时间复杂度：**
O(n).
## 2.6 remove：（Remove value from range）
## 2.7 reverse：（Reverse range）
**函数原型：**
```cpp
template <class BidirectionalIterator>
void reverse (BidirectionalIterator first, BidirectionalIterator last);
reverse()函数的作用是将区间 [first, last) 内的元素在容器内的顺序进行反转。
reverse()函数的返回值是 none（void函数）。
使用举例：
#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：
分区：
3.1 partition：（Partition range in two）
函数原型：
template <class ForwardIterator, class UnaryPredicate>
ForwardIterator partition (ForwardIterator first, ForwardIterator last,
UnaryPredicate pred);
partition() 函数的作用是将 [first, last) 范围内的容器元素 按照自定义的方法 pred 进行分区（分成 两个部分），返回值是指向第二部分分区的首元素的迭代器。
使用举例：
#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：
排序：
4.1 sort：（Sort elements in range）
函数原型：
template <class RandomAccessIterator>
void sort (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
sort() 函数的作用是将 [first, last) 范围内的元素进行排序，默认的排序方式为 operator<（即“从小到大”排序），也可以接受自定义的排序方式 comp。
使用举例：
#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）：
二分查找：
5.1 binary_search：
函数原型：
template <class ForwardIterator, class T>
bool binary_search (ForwardIterator first, ForwardIterator last,
const T& val);
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）：
合并：
6.1 merge：
函数原型：
template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result);
template <class InputIterator1, class InputIterator2,
class OutputIterator, class Compare>
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
OutputIterator result, Compare comp);
merge() 函数的作用是将 [first1, last1)区间 及 [first2, last2) 区间的容器元素合并到一起，合并后的结果存储到 result指定的位置上。 merge() 默认的合并顺序为 operator< （从小到大），也可接受用户自定义的排序方式 comp。
merge() 函数必须在 sort() 的基础上进行合并，否则合并的结果会出现乱序。且sort()与merge() 的排序算法必须保持一致，即都使用 operator< 或相同的 comp函数。
merge()函数返回值是合并后的容器的尾迭代器（容器最后一个元素的后面的位置）。
使用举例：
#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：
堆操作：
8. Min/max：
求最大/最小值，可接受用户指定的比较方法
9. Other：
|