STL标准模版库
STL是Standard Template Library的缩写，中文名标准模版库，由惠普实验室提供
（使用C++模板语言封装的常用的数据结构与算法）
STL中有六大组件:
算法：以函数模板形式实现的常用算法，例如：swap\max\min\find\sort
容器：以类模板的形式实现的常用的数据结构，例如：vector\list\array\deque\map\set\mulitimap
\multiset
迭代器（iterator）：泛型指针，是一种智能指针，它是容器的成员，用于帮助访问容器中的元素，使用方法类似于指针
适配器（配置器\配接器）：一种用于修饰容器、仿函数、迭代器的东西，例如stack、queue（底层借助dqueue实现）、
priority_queue(底层借助vector实现)
仿函数：行为类似函数的类，通过重载()运算符实现效果，目的为了让算法功能更加灵活
空间适配器（分配器）：为容器提供自定义分配内存的管理和配置，由于只是高级用户才能有改变内存分配策略的权限，因此
对于一般用户而言不常用，按照默认管理方式执行
六大组件之间的关系：
容器通过空间适配器获取数据的存储空间，容器中必定存在空间适配器
算法通过迭代器获取容器的元素和内存，容器必须提供迭代器，算法才能操作容器
仿函数协助完成算法的策略变化
适配器用于修饰容器、迭代器、仿函数
就目前而言，需要理解使用的算法、容器（部分适配器）、迭代器
学习STL的三部曲：能用、明理（了解泛型编程技术内涵、STL的底层源码）、能扩展
候捷 STL
一、常用的算法
1、max\min 找出两个数据中的最大，最小值
2、max_element\min_element 找出[start，end)范围内的最大、最小值
注意：待比较的元素必须支持 < 运算符，而且类型要完全相同
注意：例如max("123","1234")这个是报错的，因为类型并非是相同的，一个是const char[4],后面为const char[5]
例如：max("123","234"),比的不是字符串内容的大小，而是地址编号的大小
3、swap 交换两个数据，数据类型必须支持 = 运算符
4、 #include <algorithm>
iterator find( iterator start, iterator end, const TYPE& val );
功能：顺序查找，[start，end)
start:指向待查找的第一个元素的指针\迭代器
end：指向待查找的最后一个元素的下一个位置的指针\迭代器
val：待查找的数据
返回值：
找到 返回[start,end)范围内的第一个值为val迭代器
找不到返回，end位置的迭代器
5、
void sort( iterator start, iterator end );
void sort( iterator start, iterator end, StrictWeakOrdering cmp );
功能：对[start，end)范围排序
注意：元素要支持<运算符（也就是从小到大），否则后面需要提供比较回调函数
注意：默认升序，如果想要降序，也是提供比较的回调函数
cmp例子:
bool cmp( int a, int b ) {
return a > b;
}
sort采用什么排序算法？
用到了快排，但不只是快排，会根据数据状态结合上插入排序、堆排序
数据量很大时，采用快排进行分段排序，一旦分段后的数据量小于一个阈值（16），为了
避免快排递归调用额外消耗，改用插入排序如果递归层次数过深，
二、vector 向量容器
#include
采用顺序结构存储数据，可以使用下标进行随机访问，有时候也叫做数组容器
(C++11中增加了array容器，定长数组容器，相比普通数组它是类类型，增加
成员函数，提高安全性)
vector是可变长的顺序表结构，可以自动扩容，容器中的元素存储在连续内存，
支持随机访问，尾插入、尾删除效率O(1),但是在指定位置进行插入、删除效率O(n),
因为要保证数据的连续性。
构造函数：
vector( size_type num, const TYPE& val = TYPE() );
num:数组的长度
val:初始化数据，全部初始化，不给默认0，自建类型通过该类型的
无参构造的结构来初始化
vector( input_iterator start, input_iterator end );
功能：使用一段[start,end)范围中的数据进行初始化向量
支持的运算符
== != <= >= < > 这些运算符是对容器整体比较，会对两个容器中的
元素按顺序依次比较，一旦某个元素比较出结果就立即返回
元素需要支持 < 运算符才能比较
[]是跟普通数组一样不会检查下标是否合法，如果访问的下标>=
size()的个数，可能段错误
成员函数
void assign( size_type num, const TYPE& val );
功能：给向量的前num个元素赋值为val
void assign( input_iterator start, input_iterator end );
功能：使用一组范围[start,end)的数据给向量赋值
TYPE& at( size_type loc );
const TYPE& at( size_type loc ) const;
功能：访问向量loc下标的元素，功能相当于[]，当loc越界时at函数会
抛出异常，相比[]更加的安全
TYPE& back();
const TYPE& back() const;
功能：访问向量的最后一个元素
TYPE& front();
const TYPE& front() const;
功能：访问向量的第一个元素
iterator begin();
功能：返回指向第一个元素的正向迭代器
const_iterator begin() const;
功能：返回指向第一个元素的正向常迭代器
iterator end();
功能：返回指向最后一个元素的下一个位置的正向迭代器
const_iterator end() const;
功能：回指向最后一个元素的下一个位置的正向常迭代器
注意：需要通过容器中的迭代器来操作容器的数据和内存
vector<类型> v;
vector<类型>::iterator it = v.begin();
在C++11中auto可以用于自动识别数据类型，并定义该类型的变量，
可以很方便地定义迭代器类型
auto num = 10; //num int
auto it = v.begin(); //int verctor<类型>::iterator
注意：虽然迭代器在vector用处不大，但是对于其它容器，迭代器是唯一一种遍历的方式
reverse_iterator rbegin();
功能：返回一个逆向迭代器，它指向最后一个元素
const_reverse_iterator rbegin() const;
功能：返回一个逆向常迭代器，它指向最后一个元素
reverse_iterator rend();
功能：返回一个逆向迭代器，它指向第一个元素的前一个位置
const_reverse_iterator rend() const;
功能：返回一个逆向常迭代器，它指向第一个元素的前一个位置
注意：逆向迭代器也是指向一个位置，与正向迭代器的区别是，执行++操作时是往前一个元素逆向移动
size_type capacity() const;
功能：获取向量的容量
void clear();
功能：清空向量中所有元素
容量不变，删除所有元素，如果元素是类类型，会执行析构函数，元素数量变为0
bool empty() const;
功能：当向量为空返回真
iterator erase( iterator loc );
功能：删除loc位置的元素
返回值：是当前未删除的loc位置的下一个元素，例如：1，2，3，4，5 删除2后，返回指向的是3
iterator erase( iterator start, iterator end );
功能：删除[start,end)范围的元素
返回删除后start位置的迭代器
注意：只能提供迭代器进行删除，数量-1，释放，容量不变
iterator insert( iterator loc, const TYPE& val );
功能：在loc位置插入值为val的元素
返回值：获取loc的迭代器，loc会随着函数结束有可能发生变化，如果
要连续往同一loc位置插入，需要重新接收
void insert( iterator loc, size_type num, const TYPE& val );
功能；在loc位置插入num个值为val的元素
void insert( iterator loc, input_iterator start, input_iterator end );
功能：在loc位置插入一组[start，end)元素
注意：如果插入、添加数据时向量刚好没有空余位置时，向量会自动扩容，一般是在原容量基础上
翻倍
size_type max_size() const;
功能：用于计算理论上向量能存储的最大元素数量，受到元素的类型影响
void pop_back();
功能：在末尾位置删除元素
void push_back( const TYPE& val );
功能：在末尾添加一个值为val的元素
效率：O(1)
void reserve( size_type size );
功能：修改向量的容量为size，只能比原来容量大才能修改
可以进行预分配，提高效率，减少扩容的次数(耗时)
但是也意味着内存可能会闲置
每次扩容可能会拷贝原向量中的所有对象进行拷贝构造，还要把原向量中的对象
进行析构，如果频繁的扩容会严重影响vector性能，因此需要在合适的时候进行
reserve
shrink_to_fit() 取消闲置的内存
void resize( size_type num, const TYPE& val = TYPE() );
功能：修改向量的元素数量
如果num > size() 在末尾增加到num个为val元素
如果num < size() 相当于在末尾删除到num个元素
size_type size() const;
功能：获取向量的元素数量
void swap( container& from );
功能：交换两个向量的元素
vector扩容的步骤：
1、完全弃用现有的内存空间，重新申请更大的内存空间；
2、将旧内存空间中的数据，按原有顺序移动到新的内存空间中；
3、最后将旧的内存空间释放。
三、list链表容器
#include
是一个功能齐全的双向链表
支持的运算符：
== != <= >= < > =
也是链表与链表之间的比较和赋值
注意：链表中元素必须支持 < 运算符才能使用
void assign( size_type num, const TYPE& val );
功能：向链表中添加num个值为val的元素
void assign( input_iterator start, input_iterator end );
功能：向链表中添加[start,end)范围的元素
注意：它是对整个链表进行赋值，可以在已经有的链表上进行赋值，相当于原本链表变成一个新链表
back 访问最后一个元素
front 访问第一个元素
begin 返回第一个位置正向迭代器
end 返回最后一个位置下一个位置的正向迭代器
rbegin 返回最后一个位置的逆向迭代器
rend 返回第一个位置的前一个位置的逆向迭代器
clear 清空链表中的元素
empty 判断是否为空链表
max_size 理论上存储的最大元素个数
iterator erase( iterator loc );
功能：删除位置loc的元素，只能提供迭代器，不能直接提供地址
iterator erase( iterator start, iterator end );
注意：list的迭代器不允许 it+n it+=n it-n it-=n 语法，因为list是链式结构不支持随机访问
但是it++ 或者++it 是通过节点的next找下一个节点 是允许的
iterator insert( iterator loc, const TYPE& val );
功能：在loc位置插入val
void insert( iterator loc, size_type num, const TYPE& val );
功能：在loc位置插入num个val
template<TYPE> void insert( iterator loc, input_iterator start,input_iterator end );
功能：在loc位置插入[start,end)范围的元素
void merge( list &lst );
功能：按照顺序合并两个链表
如果合并前是无序的，则合并后也是无序的
如果合并两个有序链表，合并后也有序
默认下只对升序链表合并后才是升序有序
void merge( list &lst, BinPred compfunction );
如果想要进行降序排序，需要以回调形式提供compfunction比较
方式
想要有序合并，链表元素必须支持 < 运算符，否则也需要提供比较
方法才能合并
合并结束后，list的元素数量为0
void pop_front();
功能：链表的头添加
void pop_front();
功能：链表的头删除
void remove( const TYPE &val );
功能：删除链表中所有值为val的元素
void remove_if( UnPred pr );
功能：删除符合条件pr的所有元素
pr例子：
bool cmp(const TYPE& val)
{
return val >= left && val <= right;
//符合[left,right]范围的数据删除
}
void resize( size_type num, const TYPE& val = TYPE() );
功能：修改list的元素的数量
如果num > size() 在末尾增加到num个为val元素
如果num < size() 相当于在末尾删除到num个元素
void sort();
功能：对list进行升序排序，要求元素支持 < 运算符
void sort( BinPred p );
功能：对list进行排序，可能通过提供二元谓词 > 运算符比较进行降序
排序，如果元素不支持 < 运算符，也需要提供比较回调函数
p:
bool cmp(TYPE& a,TYPE& b)
{
return a > b;
}
void splice( iterator pos, list& lst );
功能：把链表lst合并到当前链表的pos位置，结束后lst数量为0
void splice( iterator pos, list& lst, iterator del );
功能：把lst的del位置开始合并到当前链表的pos位置，并且lst中del位置会删除
void splice( iterator pos, list& lst, iterator start, iterator end );
功能：把lst的[start,end)位置合并到当前链表的pos位置，并且lst中[start,end)位置会删除
void swap( container& from );
功能：交换两个链表
void unique();
功能：删除链表中的重复元素
void unique( BinPred pr );
功能：删除链表中满足条件pr的重复元素
作业:使用list实现C++通讯录 增删改查
补充：
支持+=运算符的迭代器只有支持随机访问的容器才具备，例如，向量容器vector和双端队列，deque。