文章目录

1. 简介2. 不变序列算法3. 变值算法4. 删除算法5. 变序算法6. 排序算法7. 有序区间算法8. 数值算法9. 总结参考

---

1. 简介

$\mathrm{S}\mathrm{T}\mathrm{L}$中的算法主要分为不变序列算法、变值算法、删除算法、变序算法、排序算法、有序区间算法和数值算法等。大多数算法都有两个版本，第一，用常规的比较运算符判断元素间的大小关系，如等于、小于等；第二，多出一个自定义操作的运算符，可以使我们自定义元素间比较大小的准则。

---

2. 不变序列算法

该类算法不会修改算法所作用的容器或对象，适用于顺序容器和关联容器，且时间复杂度都是$O(n)$。

min 求两个对象中较小的元素（可自定义比较器）；max 求两个对象中较大的元素（可自定义比较器）；min_element 求区间中的最小值（可自定义比较器）；max_element 求区间中的最大值（可自定义比较器）；for_each 求区间中的每个元素都做某种操作；count 计算区间中等于某值的元素个数；cound_if 计算区间中符合某种条件的元素个数；find 在区间中查找等于某个值的元素；find_if 在区间中查找符合某种条件的元素；find_end 在区间中查找另一个区间最后一次出现的位置（可自定义比较器）；find_first_of 在区间中查找第一个出现在另一个区间中的元素（可自定义比较器）；adjacent_find 在区间中寻找第一次出现连续两个相等元素的位置（可自定义比较器）；search 在区间中查找另一个区间第一次出现的位置（可自定义比较器）；search_n 在区间中查找第一次出现等于某值的连续$\mathrm{n}$个元素（可自定义比较器）；equal 判断两区间是否相等（可自定义比较器）；mismatch 逐个比较两个区间的元素，返回第一次发生不相等的两个元素的位置（可自定义比较器）；lexicographical_compare 按字典序比较两个区间的大小（可自定义比较器）。

示例程序：

#include<iostream> #include<algorithm> using namespace std; class A { public: int n; A(int i) :n(i) {} // 初始化列表 }; // 重载小于符号 bool operator<(const A& a1, const A& a2) { if (a1.n == 3 && a2.n == 7) { return true; } return false; } int main() { A aa[] = { 3,5,7,2,1 }; // 3，由于小于符号已经重载，3<5为假、3<7为假、3<2为假、3<1为假 cout << min_element(aa, aa + 5)->n << endl; // 7，由于小于符号已经重载，3>5为假、3>7为真、3<2为假、3<1为假 cout << max_element(aa, aa + 5)->n << endl; return 0; }

---

3. 变值算法

此类算法会修改源区间或目标区间元素的值，且值被修改的那个区间不可以是属于关联容器的。

for_each 对区间的每个元素都做某种操作；copy 复制一个区间到别处；copy_backward 复制一个区间到别处，但目标区间是从后往前修改的；transform 将一个区间的元素变形后拷贝到另一个区间；swap_ranges 交换两个区间的内容；fill 用某个值填充区间；fill_n 用某个值替换区间中的$\mathrm{n}$个元素；generate 用某个操作的结果填充区间；generate_n 用某个操作的结果替换区间中的$\mathrm{n}$个元素；replace 将区间中的某个值替换为另一个值；replace_if 将区间中符合某种条件的值替换成另一个值；replace_copy 将一个区间拷贝到另一个区间，拷贝时某个值要换成新值拷贝过去；replace_copy_if 将一个区间拷贝到另一个区间，拷贝时符号某种条件的值要换成新值拷贝过去。

示例程序：

#include<list> #include<vector> #include<numeric> #include<iterator> #include<iostream> #include<algorithm> using namespace std; class CLessThen9 { public: // 重载圆括号，该类对象为函数对象 bool operator()(int n) { return n < 9; } }; void outputSquare(int value) { cout << value * value << " "; } int calculateCube(int value) { return value * value * value; } int main() { const int SIZE = 10; int a1[] = { 1,2,3,4,5,6,7,8,9,10 }; int a2[] = { 100,2,8,1,50,3,8,9,10,2 }; vector<int> v(a1, a1 + SIZE); // 输出迭代器对象output，使用cout和" "初始化 ostream_iterator<int> output(cout, " "); // 随机打乱元素 random_shuffle(v.begin(), v.end()); // 9 2 10 3 1 6 8 4 5 7（随机序列） copy(v.begin(), v.end(), output); // 拷贝 copy(a2, a2 + SIZE, v.begin()); // 2 cout << count(v.begin(), v.end(), 8); // 6（小于9的元素个数） cout << count_if(v.begin(), v.end(), CLessThen9()); // 1 cout << *(min_element(v.begin(), v.end())); // 100 cout << *(max_element(v.begin(), v.end())); // 193（所有元素求和） cout << accumulate(v.begin(), v.end(), 0); // 10000 4 64 1 2500 9 64 81 100 4 for_each(v.begin(), v.end(), outputSquare); // 1 8 27 64 125 216 343 512 729 1000 vector<int> cubes(SIZE); transform(a1, a1 + SIZE, cubes.begin(), calculateCube); return 0; }

copy函数的源代码：

template<class _ll, class_Ol> inline _Ol copy(__ll_F, _ll_L, _Ol_X) { for (; _F != _L; ++_X, ++_F) { *_X = *_F; } return _X; }

copy函数的示例程序：

#include<string> #include<fstream> #include<iterator> #include<iostream> #include<algorithm> using namespace std; int main() { int a[4] = { 1,2,3,4 }; My_ostream_iterator<int> oit(cout, "*"); // 1*2*3*4* copy(a, a + 4, oit); ofstream oFile("test.txt", ios::out); My_ostream_iterator<int> oitf(oFile, "*"); // 向test.txt中写入1*2*3*4* copy(a, a + 4, oitf); oFile.close(); return 0; }

现在我们需要自定义My_ostream_iterator以其可以顺利完成上述功能，这里My_ostream_iterator类应该重载++、*和=运算符。

template<class T> class My_ostream_iterator :iterator<output_iterator_tag, T> { private: string sep; // 分隔符 ostream& os; public: My_ostream_iterator(ostream& o, string s):sep(s), os(o){} // 初始化列表 void operator++() {}; // 只需要定义即可，不需要实现具体内容 // 重载"*"运算符 My_ostream_iterator& operator*() { return *this; } // 重载"="运算符 My_ostream_iterator& operator=(const T& val) { os << val << sep; // 输出内容（屏幕或文件）和分隔符 return *this; } };

---

4. 删除算法

删除算法用于删除一个容器里的某些元素，且删除不会使容器里的元素减少（使用空位置代替），删除算法不应作用于关联容器。

remove 删除区间中等于某个值的元素；remove_if 删除区间中满足某种条件的元素；remove_copy 拷贝区间到另一个区间，等于某个值的元素不拷贝；remove_copy_if 拷贝区间到另一个区间，符合某种条件的元素不拷贝；unique 删除区间中连续相等的元素，只留下一个（可自定义比较器）；unique_copy 拷贝区间到另一个区间，连续相等的元素，值拷贝第一个到目标区间（可自定义比较器）。

上述算法的时间复杂度都是$O(n)$。示例程序：

#include<vector> #include<iostream> using namespace std; int main() { int a[5] = { 1,2,3,2,5 }; int b[6] = { 1,2,3,2,5,6 }; ostream_iterator<int> oit(cout, ","); int* p = remove(a, a + 5, 2); // 1,3,5,2,5 copy(a, a + 5, oit); // 3 cout << p - a; vector<int> v(b, b + 6); remove(v.begin(), v.end(), 2); // 1,3,5,6,5,6 copy(v.begin(), v.end(), oit); // 6 cout << v.size(); return 0; }

---

5. 变序算法

变序算法用于改变容器中元素的顺序，但是不改变元素的值，并且变序算法不适用于关联容器。

reverse 颠倒区间的前后次序；reverse_copy 把一个区间颠倒后的结果拷贝到另一个区间，源区间不变；rotate 将区间进行循环左移；rotate_copy 将区间以首尾相接的形式进行旋转后的结果拷贝到另一个区间，源区间不变；next_permutation 把区间改为下一个排列（可自定义比较器）；prev_permutation 把区间改为上一个排列（可自定义比较器）；random_shuffle 随机打乱区间内元素的顺序；partition 把区间内满足某个条件的元素移到前面，不满足该条件的移到后面。

上述算法的时间复杂度都是$O(n)$。示例程序：

#include<string> #include<iostream> #include<algorithm> using namespace std; int main() { string str = "231"; char szStr[] = "324"; // 312 321（231后面的排列），且str变为"321" while (next_permutation(str.begin(), str.end())) { cout << str << " "; } // 342 423 432（324后面的排列） while (next_permutation(szStr, szStr + 3)) { cout << szStr << endl; } // str变为"123" sort(str.begin(), str.end()); // 132 213 231 312 321（123后面的排列） while (next_permutation(str.begin(), str.end())) { cout << str << endl; } return 0; }

---

6. 排序算法

排序算法需要随机访问迭代器的支持，不适用关联容器和列表。

sort 将区间从小到大排序（可自定义比较器）；stable_sort 将区间从小到大排序，并保持元素的相对位置不变（可自定义比较器）；partial_sort 对区间部分排序，直到最小的$\mathrm{n}$个元素就位（可自定义比较器）；partial_sort_copy 将区间前$\mathrm{n}$个元素的排序结果拷贝到别处，源区间不变（可自定义比较器）；nth_element 对区间部分排序，使得第$\mathrm{n}$小的元素就位，而且比它小的元素在前面，比它大的元素在后面（可自定义比较器）；make_heap 使区间称为一个堆（可自定义比较器）；push_heap 将元素加入一个堆（可自定义比较器）；pop_heap 从堆区间删除堆顶元素（可自定义比较器）；sort_heap 将一个堆区间进行排序，排序结束后，该区间就是普通的有序区间，不再是堆了（可自定义比较器）。

上述算法的时间复杂度都是$O(n\log (n))$。示例程序：

#include<iostream> #include<algorithm> using namespace std; class MyLess { public: // 重载圆括号，个位较大者较大 bool operator()(int n1, int n2) { return (n1 % 10) < (n2 % 10); } }; int main() { int a[] = { 14,2,9,111,78 }; sort(a, a + 5, MyLess()); // 111 2 14 78 9 for (int i = 0; i < 5; ++i) { cout << a[i] << " "; } sort(a, a + 5, greater<int>()); // 111 78 14 9 2 for (int i = 0; i < 5; ++i) { cout << a[i] << " "; } return 0; }

---

7. 有序区间算法

有序区间算法要求所操作的区间已经是从小到大排好序的，需要随机访问迭代器的支持，不适用关联容器和列表。

binary_search 判断区间中是否包含某个元素；includes 判断是否一个区间中的每个元素，都在另一个区间中；lower_bound 查找最后一个不小于某值的元素的位置；upper_bound 查找第一个大于某值的元素的位置；equal_range 同时获取lower_bound和upper_bound的值；merge 合并两个有序区间到第三个区间；set_union 将两个有序区间的并拷贝到第三个区间；set_intersection 将两个有序区间的交拷贝到第三个区间；set_difference 将两个有序区间的差拷贝到第三个区间；set_symmetric_difference 将两个有序区间的对称差拷贝到第三个区间；inplace_merge 将两个连续的有序区间原地合并并作为一个有序区间。

示例程序：

#include<list> #include<bitset> #include<vector> #include<numeric> #include<iostream> #include<algorithm> using namespace std; bool Greater10(int n) { return n > 10; } int main() { const int SIZE = 10; int a1[] = { 2,8,1,50,3,100,8,9,10,2 }; vector<int> v(a1, a1 + SIZE); ostream_iterator<int> output(cout, " "); vector<int>::iterator location; location = find(v.begin(), v.end(), 10); // 找到，输出8 if (location != v.end()) { cout << location - v.begin(); } location = find_if(v.begin(), v.end(), Greater10); // 找到，输出3（第一个满足Greater10的元素位置） if (location != v.end()) { cout << location - v.begin(); } sort(v.begin(), v.end()); // 找到9，输出Founded if (binary_search(v.begin(), v.end(), 9)) { cout << "Founded"; } return 0; }

---

8. 数值算法

数值算法主要是对容器类中的元素进行相应的数值操作。

accumulate 计算容器内各元素的总和；iota 用于填充容器指定范围内的元素；adjacent_difference 计算容器内相邻元素的差值；inner_product 计算容器内元素的内积；gcd 用来求两个正整数的最大公约数（辗转相除法）；lcm 用来求两个正正整数的最小公倍数。

---

9. 总结

$\mathrm{S}\mathrm{T}\mathrm{L}$为我们实现了用于容器操作的常见算法，即本文介绍的这七类算法。利用$\mathrm{S}\mathrm{T}\mathrm{L}$中自定义的算法，我们可以快速完成相关功能，如常用到的排序算法sort，它内部是通过快速排序实现；如果我们需要求一个序列的全排列，可以借助next_permutation函数实现；如果我们需要求众多数据中的最值，可以通过使用与head有关的函数快速实现。

---

参考

北京大学公开课：程序设计与算法（三）C++面向对象程序设计.

---

完

---