C++STL标准模板库

STL共有6中组件：容器、容器适配器、迭代器、算法、函数对象（仿函数）和函数适配器。
最常用的是顺序容器，顺序容器内的元素按其位置进行存储和访问。除顺序容器外，标准库还定义了几种关联容器。这里我们主要讲一下顺序容器。
标准库定义了三种顺序容器类型：vector、list和deque,它们的差别在于访问元素的方式，以及添加或删除元素相关操作的运行代价。
[vector] : 向量容器，底层数据结构是内存可2倍扩容的数组 ，只能在容器末尾添加新元素。vector效率比[deque]高 因为vector内存连续
下面是容器的一些操作：vector<vector> array;
array.resize(10); array[0].resize(20);
reserve/resize/size/empty
push_back/pop_back O(1)
insert/erase O(n)

[deque] : 双端队列 动态开辟的二维数组 MAP_SIZE QUEUE_SIZE
push_back/pop_back O(1)
push_front/pop_front O(1)
insert/erase O(n)

[list] : 链表容器 带头节点的双向链表
vector<list> veclist;
push_back/pop_back O(1)
push_front/pop_front O(1)
insert/erase O(1)
splice 分片函数

容器适配器 有三种 :
stack栈 ：依赖的容器是deque，原因是空间利用率高。
stack s1;
stack<int, vector> s2;
s1.push(10); s1.pop(); s1.top(); s1.empty(); s1.size();

queue队列 ：依赖的容器是deque
queue q1;
queue<int, list> q3;
q1.push(10);
q1.pop();
q1.front();
q1.back();
q1.empty();
q1.size();
priority_queue优先级队列 ：依赖的容器是Vector ，原因是堆结构计算下标左孩子2i+1,右孩子2i+2 ,所以内存需要连续大根堆值越大，优先级越大。
priority_queue maxHeap; 大根堆
maxHeap.push(10);
maxHeap.pop();
maxHeap.top();
maxHeap.empty();
maxHeap.size();
priority_queue<int, vector, greater> minHeap;大根堆

关联容器（红黑树 哈希表）

哈希表-无序容器 O(1)
unordered_set : 单重集合 不允许值重复 key
unordered_multiset ： 多重集合 允许值重复
insert(val)
erase(val)
迭代器
find
count(val)

unordered_map : 单重映射表   [key, value]
unordered_multimap ： 多重映射表
insert(make_pair(key, value));
erase(key)
hashMap[key] = value;

迭代器
unordered_map<int, string> map;
auto it = map.find(100);
if(it != map.end())
{
	cout<<"key:"<<it->first<<" value:"<<it->second<<endl;
}


红黑树-有序容器 O(log2n)
set
multiset

map
multimap

迭代器
iterator
const_iterator
=> begin() end()

reverse_iterator
const_reverse_iterator
			   => rbegin()  rend()

泛型算法
sort(it1, it2)
sort(it1, it2, 函数对象) lambda表达式
find
find_if
binary_search

#include //使用容器
#include //使用泛型算法
#include //C++STL的函数对象