十八.STL库
主要包括三大组件：容器、算法、迭代器。
容器：序列式容器：vector、deque、list；关联式容器：set、multiset、map、multimap；
1.vector：相当于动态数组
用法：push_back、pop_back、begin、end（得到数组的最后一个单元+1的指针）、capacity（当前vector分配的大小，每次扩充当前1.5-2倍的容量）、size（当前使用数据的大小）、resize、reserve、reverse(vec.begin(),vec.end())（元素翻转）、erase、clear、empty、swap、rbegin（原来的end-1）、rend（原来的begin-1）、insert（在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器, 在指定位置loc前插入num个值为val的元素 在指定位置loc前插入区间[start, end)的所有元素）；
实现：动态数组，里面有一个指针指向一片连续的内存空间，当空间装不下的时候会自动申请一片更大的空间（空间配置器）将原来的数据拷贝到新的空间，然后就会释放旧的空间。当删除的时候空间并不会被释放只是清空了里面的数据。
优点：方便的进行随机存取，可以不用定义大小；
缺点：内存连续，在中间插入或删除元素时需要复制移动现有的元素；只能在一端进行push和pop；若插入内存空间不够时，需要重新申请一块足够大的内存并进行拷贝，若对象比较大则执行效率比较低；
reserve和resize的区别：reserve: 分配空间，更改capacity但不改变size；resize: 分配空间，更改capacity也改变size
2.list：循环双向链表
用法：begin()和end()、push_back()和push_front()、pop_back和pop_front()、front()和back()、empty()、resize()、clear()、reverse()（逆置）、swap()、insert()、erase()、merge()(合并两个有序链表并使之有序)、sort()、unique()（容器内相邻元素若有重复的，则仅保留一个）
实现： 底层数据结构为双向链表，内存空间是不连续的，通过指针来进行数据的访问；
优点：内存不连续，在内部方便进行插入和删除操作，可在两端进行push和pop；
缺点：不能进行内部的随机访问，相对vector占用内存较多；
3.deque
用法：begin()和end()、push_back()和push_front()、pop_back和pop_front()、front()和back()、empty()、resize()、clear()、swap()、insert()、erase()、at();
实现：是一个双端队列
优点：随机访问方便，在内部方便的进行插入和删除操作，可在两端进行push、pop；
缺点：占用内存多；
vector、list、deque使用对比：
1 如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
2 如果你需要大量的插入和删除，而不关心随即存取，则应使用list
3 如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque
4.set
用法：count()-返回某个值元素的个数（set中最多为1）、find()-返回一个指向被查找到元素的迭代器、equal_range()-返回集合中与给定值相等的上下限的两个迭代器、
实现：红黑树；
特点：元素不允许有重复，在默认情况下会对元素进行自动排序，数据被组织成一棵红黑树，查找的速度非常快（二分），时间复杂度是O(logN)，set中的元素不能被修改，只能删除后再添加。
缺点：set不能存储无法比较大小的数据，不可以通过set的迭代器改变set的元素值，会破坏排序规则
5.map：建立Key－value的对应
用法：数据插入（1、用insert函数插入pair数据，如：a.insert(pair(1, "student_one"))；2、用insert函数插入value_type数据，如：insert(map::value_type (1, "student_one"))；3、用数组方式插入数据，如：a[1]="student_one"）;元素查找（find()函数返回一个迭代器指向键值为key的元素，如果没找到就返回指向map尾部的迭代器）；元素删除（iterator erase（iterator it);//通过一个条目对象删除，size_type erase(const Key&key);//通过关键字删除）；swap()（map中的swap不是一个容器中的元素交换，而是两个容器所有元素的交换。）；
实现：按照key值组织成一棵红黑树
特点：自动建立Key－value的对应，key的类型必须支持<操作符，key值排序且不重复，根据key值快速查找记录（二分），查找的复杂度基本是Log(N)，增加和删除节点对迭代器的影响很小，除了操作节点，对其他的节点都没有什么影响。对于迭代器来说，不可以修改键值，只能修改其对应的实值。
6.hash_map与map的区别？什么时候用hash_map，什么时候用map？
构造函数：hash_map需要hash function和等于函数，而map需要比较函数（大于或小于）。
存储结构：hash_map以hashtable为底层，而map以RB-TREE为底层。
总的说来，hash_map查找速度比map快，而且查找速度基本和数据量大小无关，属于常数级别。而map的查找速度是logn级别。但不一定常数就比log小，而且hash_map还有hash function耗时。
如果考虑效率，特别当元素达到一定数量级时，用hash_map。
考虑内存，或者元素数量较少时，用map。
7.map和set的3个问题
1）为何map和set的插入删除效率比其他序列容器高。
因为不需要内存拷贝和内存移动
2）为何map和set每次Insert之后，以前保存的iterator不会失效？
因为插入操作只是结点指针换来换去，结点内存没有改变。而iterator就像指向结点的指针，内存没变，指向内存的指针也不会变。
3）当数据元素增多时（从10000到20000），map的set的查找速度会怎样变化？
RB-TREE用二分查找法，时间复杂度为logn，所以从10000增到20000时，查找次数从log10000=14次到log20000=15次，多了1次而已。
8.STL的底层数据结构实现
1）vector：底层数据结构为数组，支持快速随机访问。
2）list：底层数据结构为双向链表，支持快速增删。
3）deque：底层数据结构为一个中央控制器和多个缓冲区，支持首尾（中间不能）快速增删，支持随机访问。
4）stack：底层用deque或者list实现，不用vector的原因是扩容耗时。
5）queue：底层用deque或者list实现，不用vector的原因是扩容耗时。
6）priority_queue：底层数据结构一般以vector为底层容器，heap为处理规则来管理底层容器实现。
7）set：底层数据结构为红黑树，有序，不重复。
8）multiset：底层数据结构为红黑树，有序，可重复。
9）map：底层数据结构为红黑树，有序，不重复。
10）multimap：底层数据结构为红黑树，有序，可重复。
11）hash_set：底层数据结构为hash表，无序，不重复。
12）hash_map：底层数据结构为hash表，无序，不重复。
13）hashtable：底层数据结构是vector。
迭代器：
迭代器提供了一种方法，使它能够按照顺序访问某个容器所含的各个元素，但无需暴露该容器的内部结构1.vector::const_iterator 和 const vector::iterator的区别
前者不能修改容器中的元素，如：*newiter=11 属于错误，可以修改迭代器自身，如：newiter++正确；后者可以修改指向容器的元素，如：*newiter=11正确，迭代器本身不能被修改，如：newiter++错误；
2.迭代器的删除操作
vector、list、map、deque用erase（it）后，迭代器的变化。
vector和deque是序列式容器，其内存分别是连续空间和分段连续空间，删除迭代器it后，其后面的迭代器都失效了，此时it及其后面的迭代器会自动加1，使it指向被删除元素的下一个元素。
list删除迭代器it时，其后面的迭代器都不会失效，将前面和后面连接起来即可。
map也是只能使当前删除的迭代器失效，其后面的迭代器依然有效。
在迭代容器的时候删除元素，可能导致迭代器失效，解决方法：
for (it != my_container.end(); ) {
if (*it % 2 == 1) {
it = my_container.erase(it); //让erase() 返回一个新的迭代器，指向被删除元素的后面的元素
}
else{
it++;
}
}
或者 for( it = List.begin(); it != List.end(); )
{
if( WillDelete( *it) )
{
List.erase( it++); //使迭代器在删除前自加
}
else
it++;
}
算法：
std::sort()
1.stl set map 使用红黑树 avl树作为底层数据结构的实现，不支持随机迭代器，所以不能使用sort来排序,能用std::sort()的有vector, deque, string；
2.排序是通过多次内存的copy来实现的，所以链表不能使用stl算法sort来对其排序(next指针修改问题)，list自带排序算法list::sort()；
