STL 是惠普实验室开发的一系列软件的统称，可以理解为一些容器的集合。STL的目的是标准化组件，这样就不用重新开发，可以使用现成的组件。STL 现在是C++的一部分，因此不用额外安装什么。
STL 中的库在 C++标准中，STL 被组织为下面的 17 个头文件：****、、
它主要是对数组类型（或类似）的数据结构进行操作。
for_each(start , end , function) 解释这个我只在 C++ primer 见过。意思是，从某个容器的 start 指针，到这个容器的 end 指针，均执行 function 函数。
实例#include#include #include using namespace std; int ia[] = { 1,2,3 }; vector ivec(ia, ia + sizeof(ia) / sizeof(int)); void print(int& x) { cout << x << endl; } int main() { for_each(ivec.begin(), ivec.end(), print); return 0; }
输出结果
1 2 3
相当于：将这个容器内的一个元素传入第一个未被占用的参数。缺参数?看一下这个例子。
#include#include #include using namespace std; int ia[] = { 1,2,3 }; vector ivec(ia, ia + sizeof(ia) / sizeof(int)); struct print { const char* _prefix; print(const char* prefix) :_prefix(prefix) {} void operator()(int elem) { cout << _prefix << elem << endl; } }; int main() { for_each(ivec.begin(), ivec.end(), print("Element:")); return 0; }
输出结果
Element:1 Element:2 Element:3is_sorted(start,end) 解释
返回一个 bool 值，判断这个区间是否排序。
#include#include #include using namespace std; int main() { int a[5] = { 1,3,4,2,5 }; cout << is_sorted(a, a + 5); }
输出结果
0is_sorted_until(start,end) 解释
std::is_sorted_until用于查找范围 [first，last) 中的第一个未排序元素。它将迭代器返回到范围中的第一个未排序元素，因此在first和返回的迭代器之间的所有元素都进行了排序。
#include输出结果#include #include using namespace std; int main() { int a[5] = { 1,3,4,2,5 }; cout << is_sorted_until(a, a + 5) << endl; cout << *is_sorted_until(a, a + 5); }
0078F870 2sort(start,end,function) 和 stable_sort(start,end,function) 解释
使得 start~end 按 function 规则排序。无返回值。复杂度为稳定 O(nlogn)，其中 sort 为不稳定排序。function 当且仅当该容器为数组且 function 未定义时默认为从小到大。
#include输出#include #include using namespace std; int main() { int a[5] = { 1,3,4,2,5 }; sort(a, a+5); for (int i = 0; i < 5; i++) cout << a[i] << " "; }
1 2 3 4 5lower_bound(start,end,val) & upper_bound(start,end,val) 解释
- lower_bound(start,end,val)：返回一个不小于 value 的最小指针
- upper_bound(start,end,val)：返回一个大于 value 的最小指针。
#include输出结果#include #include using namespace std; int main() { int a[5] = { 1,3,4,2,5 }; cout << lower_bound(a, a + 5, a[1]) << endl; cout << *lower_bound(a, a + 5, a[1]) << endl; cout << upper_bound(a, a + 5, a[1]) << endl; cout << *upper_bound(a, a + 5, a[1]) << endl; }
012FF7A4 3 012FF7A8 4heap
heap（堆）就是用数组实现的二叉树，所以它没有使用父指针或者子指针。堆根据 “堆属性” 来排序，“堆属性” 决定了树中节点的位置。
堆的常用方法：
- 构建优先队列
- 支持堆排序
- 快速找出一个集合中的最小值（或者最大值）。
堆属性分为两种：
- 最大堆。在最大堆中，父节点的值比每一个节点的值都要大。
- 最小堆。在最小堆中，父节点的值比每一个子节点的值都要小。
但是heap没有迭代器，heap的所有元素都必须遵循特别的 complete binary tree（完全二叉树，整棵binary tree除了最底层的叶节点之外是填满的，而最底层的叶节点由左至右不得有空隙）排序规则，所以heap不提供遍历功能，也不提供迭代器。
堆和普通树的区别- 节点的顺序：
- 在二叉搜索树中，左子节点必须比父节点小，右子节点必须比父节点大。
- 但是，在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。
- 内存占用
- 普通树占用的内存空间比它们存储的数据要多，必须为节点对象以及左右子节点指针分配足够的内存。
- 堆仅仅使用一个数据来村塾数组，且不使用指针。
push_heap()要求新加入的元素一定要放在最下一层作为叶节点，并填补在由左至右的第一个空格，也就是把新元素插入在底层vector的end()处，如下图所示。
pop_heap()在max-heap中，最大值必然在根节点，pop操作取走根节点之后，为了满足complete binary tree的条件，需要将最下一层最右边的叶节点拿掉，而取走的根节点其实是移至底部容器vector的最后一个元素。为满足max-heap的条件，执行下溯程序：
- 将根节点（最大值被取走后形成一个“洞”）填入失去生存空间的叶节点值，
- 再将它拿来和其两个子节点比较键值，并与较大子节点对调位置，直到这个“洞”的键值大于左右两个子节点，或者到下放至叶节点为止。如下图所示：
注意：pop_heap之后，最大值只是被置放在底部容器的最尾端，尚未被取走。如果要取其值，可使用底部容器（vector）所提供的back()操作函数。如果要移除它，可使用底部容器（vector）所提供的pop_back()操作函数。
sort_heap()每次使用pop_heap可获得heap中键值最大的元素，如果持续对整个heap做pop_heap操作，每次将操作范围从后向前缩减一个元素，因为pop_heap会把键值最大的元素放在底部容器的最尾端，当整个程序执行完毕时，就形成一个递增序列，如下图所示。
注意：排序后，原来的heap就不再是一个合法的heap。
make_heap()这个算法用来将一段现有的数据转化为一个heap。
例1 底层以vector完成#include输出结果#include #include using namespace std; void TestHeap1() { int arr[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 }; vector v1(arr, arr + 9); cout << "vector data:"; for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } cout << endl; //make_heap make_heap(v1.begin(), v1.end()); cout << "make heap后："; for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } cout << endl; //push_heap v1.push_back(7); push_heap(v1.begin(), v1.end()); cout << "push 7 heap后："; for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } cout << endl; //pop_heap pop_heap(v1.begin(), v1.end()); cout << "pop heap:"; cout << v1.back() << endl; //最大值9被放在vector的最尾端，但是没有取走 v1.pop_back(); cout << "pop back后："; for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } cout << endl; //sort_heap sort_heap(v1.begin(), v1.end()); cout << "sort heap后："; for (int i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } cout << endl; } int main() { TestHeap1(); system("pause"); return 0; }
vector data:0 1 2 3 4 8 9 3 5 make heap后：9 5 8 3 4 0 2 3 1 push 7 heap后：9 7 8 3 5 0 2 3 1 4 pop heap:9 pop back后：8 7 4 3 5 0 2 3 1 sort heap后：0 1 2 3 3 4 5 7 8例2 底层以array完成
#include输出结果#include using namespace std; void TestHeap2() { int arr[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 }; make_heap(arr, arr + 9); cout << "make heap后："; for (int i = 0; i < 9; i++) { cout << arr[i] << " "; } cout << endl; //sort_heap sort_heap(arr, arr + 9); cout << "sort make后："; for (int i = 0; i < 9; i++) { cout << arr[i] << " "; } cout << endl; //经过排序之后的heap，不再是个合法的heap //重新再做一个heap make_heap(arr, arr + 9); cout << "再一次make heap后："; for (int i = 0; i < 9; i++) { cout << arr[i] << " "; } cout << endl; //pop_heap pop_heap(arr, arr + 9); cout << "pop heap后，查看arr[8]的值："; cout << arr[8] << endl; } int main() { TestHeap2(); system("pause"); return 0; }
make heap后：9 5 8 3 4 0 2 3 1 sort make后：0 1 2 3 3 4 5 8 9 再一次make heap后：9 8 5 3 3 4 2 1 0 pop heap后，查看arr[8]的值：9最大(max/max_element)/最小操作(min/min_element)。 解释
- max(num1,num2)
- min(num1,num2);
- max_element(start,end)
- min_element(start,end);
#include输出结果#include #include using namespace std; int main() { int a[5] = { 1,3,4,2,5 }; cout << max_element(a, a + 5) << endl; cout << *max_element(a, a + 5) << endl; cout << min_element(a, a + 5) << endl; cout << *min_element(a, a + 5) << endl; }
00AFF7A4 5 00AFF794 1#include
是在 C++标准模板库中的部分内容，它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。可以为一大堆有序容器建立容器， 这是一个动态数组，节约空间。
vector#inlcudevec; //创建 vec.push_back(a); //尾部插入元素：a 为一个元素 vec[0]; //访问：使用数组[] vec.size(); //求大小 vec.clear(); //清空 vec.insert(pos, val); //v.插入：在 pos 的位置的前面插入 val 元素 vec.reverse(start, end); //反转：将[start,end)之间的元素顺序颠倒。需要头文件 vec.erase(pos); //vi.删除：删除第 pos + 1 个元素。 vec.erase(start, end); //或者：删除[start, end)之间的所有元素。 //迭代器： vector ::iterator it; for (it = vec.begin(); it != vec.end(); it++)cout << *it << endl;
