STL，全称Standard Template Library（标准模板库），是C++标准库的重要组成部分。
说到C++的STL，让人就不免想到六大组件：
容器
迭代器
算法
仿函数
空间配置器
适配器
从容器开始逐个描述。
容器
容器分为关联式容器和序列式容器
关联式容器
关联式容器使用键来唯一标识元素。
包括set、map、unordered_set、unordered_map。
而这四个又有各自的multi版本，就是允许键值冗余。
set/map
需要熟练掌握基本的方法，增删改查：
1.insert
set和map的insert都重载了三种方法：单个元素插入，迭代器位置插入，迭代器范围插入
single element (1) with hint (2) range (3)
第一种 insert使用set/map的元素类型插入，返回值为一个pair类型，pair的元素为迭代器和bool值
第二种 insert使用迭代器的位置插入 应用场景是先通过迭代器寻找指定元素，找不到时，pair的返回值元素中的bool是false，这时可以在迭代器的位置插入指定元素
第三种 范围插入，从另一个set/map容器中用迭代器选定一个范围，通过插入进新的set/map
2.find
const_iterator find (const value_type& val) const; iterator find (const value_type& val);参数是指定元素，返回值是迭代器
3.erase
(1) (2) (3)
第一种 是迭代器位置删除，一般需要先将迭代器初始化为需要删除的元素节点，然后直接传入迭代器就可删除（ 迭代器会失效，想继续使用这个迭代器需要用返回值更新迭代器）
第二种 是删除指定元素 ，并返回删除元素的数量
第三种 是范围删除，给定一个迭代器的范围，再给特定的一个条件去删除迭代器所指向元素，不过要 注意迭代器失效，要用返回值更新迭代器，才能在接下来的遍历过程中防止迭代器失效
map: operator[]
mapped_type& operator[] (const key_type& k);
operator[]是map独特的一种[ ]重载，参数是键值key，
返回值是map存储的键值对中的 值的引用(mapped_type&)
operator[ ]的用法：
一、可以用来查找[key]位置的值
二、如果[key]为空，可以用来插入新的键值对
三、如果[key]已经存在，可以修改值
iterator
要谈论set和map的迭代器，就必须要先谈它们的底层结构：红黑树
简单看一下红黑树中iterator的定义(自实现):
//红黑树迭代器类
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;__RBTreeIterator(Node* node)
:_node(node)
{}
__RBTreeIterator(const __RBTreeIterator<T, T&, T*>& it)
:_node(it._node)
{}Ref operator*()
{
return _node->_data;
}Ptr operator->()
{
return &_node->_data;
}bool operator!=(const Self& it)
{
return _node != it._node;
}Self& operator++()
{
// 1、右不为空，下一个就是右子树的最左节点
if (_node->_right)
{
Node* subleft = _node->_right;
while (subleft->_left)
{
subleft = subleft->_left;
}
_node = subleft;
}
else// 2、右为空，沿着到根的路径，找孩子是父亲左的那个祖先
{
Node* cur = _node;
Node* parent = _node->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}_node = parent;
}return *this;
}Self& operator--()
{
if (_node->_left)
{
// 1、左不为空，找左子树最右节点
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}_node = subRight;
}
else
{
// 2、左为空，孩子是父亲的右的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}_node = parent;
}return *this;
}
};
//红黑树类
template<class K, class T, class KofT>
class RBTree
{
typedef __RBTreeIterator<T, T&, T*> iterator;
typedef __RBTreeIterator<T, const T&, const T*> const_iterator;/*......*/
};
set::iterator
set底层封装了RBTree的结构，这是set的iterator 定义（自实现）：
template<class K>
class set{
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;// .........................................................................///
}；
直接封装RBTree就可。
这里要提一下set::iterator模版的第三个参数：SetKeyOfT
主要是为了让set能够和map共用一个底层红黑树而做的一步，SetKeyOfT本质是一个仿函数：
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
值得注意的是： 仿函数返回的值是const key&
这说明迭代器再返回key时，不管是const类型还是 非const类型，都会返回const的类型
map::iterator
和set一样封装了BRTree，直接看map中的定义（自实现）：
template<class K, class V>
class map{
typedef typename RBTree<K, pair<const K, V>, MapKeyofT>::iterator iterator;
}
