STL对比解说——关联容器
1. 概述
关联容器会根据某种准则自动排序容器中元素。operator<为默认的排序准则，也可以提供自己的排序准则。
关联容器典型的实现是二叉树(red-black tree)，每个元素都有a parent 和 two children。左子树为小值，右子树为大值。
关联容器的优势是查找更快的(对数复杂度，顺序容器线性复杂度)。
关联容器的key是常量不能直接更改，因为这样会破坏元素的自动排序。因此所有algorithm中变动性算法都不能用。
关联容器包含set, multiset, map, multimap。
(1) set, multiset
#include <set>
namespace std {
template <typename T,
typename Compare = less<T>, //默认使用小于，可以自己提供排序准则
typename Allocator = allocator<T> >
class set;
template <typename T,
typename Compare = less<T>,
typename Allocator = allocator<T> >
class multiset;
}
set和multiset的key，value是同样的类型T。since C++11 插入和删除multiset保持相等元素的相对顺序不变。
不提供直接的元素访问，只能通过迭代器间接访问，元素值是常量。
要改变set的值必须先删除old value，再插入new value。
(2) map, multimap
#include <map>
namespace std ｛
template <typename Key, typename T,
typename Compare = less<Key>, //按Key进行排序
typename Allocator = allocator<pair<const Key, T> > > //allocator作为默认内存模型， value_type：pari<const Key, T>
class map;
template <typename Key, typename T,
typename Compare = less<Key>,
typename Allocator = allocator<pair<const Key, T> > >
class multimap;
｝
注意：Key和value必须是copyable or movalbe
Key 必须是可根据排序准则比较的
C++11保证相等元素插入和删除时的相对顺序。
Key为const，要修改Key必须先移除老的Key,在插入新的Key。
2. 初始化
//提供排序准则, 必须为函数对像，一个类型，不能为函数指针。
set<int, greater<int> >, map<int, int, greater<int> >, 改为准则greater<int>, 默认less<int>
//以比较函数作为排序准则，作为等价的定义。如：使用if （！（elem1<elem2 || elem2 < elem1））（比较函数less）作为等价（equivalence）的判断标准，判断是否元素重复
//常见初始化方式
set/map c; //创建空容器
set/map c(op); //创建以op为排序准则的空容器
//copy constructor
set/map c(c2);
set/map c = c2;
//区间初始化
set/map c(beg, end); //常见的用另一个容器的iterator
set/map c(beg, end, op);
Since C++11:
//move constructor
set/map c(rv);
set/map c = rv;
//initlist
set/map c(initlist); //最好的初始化方式
set/map c = initlist;
//set/map需要相应的类型
set<elem>, map<key, value> //默认less<>
set<elem, op>, map<key, value, op> //比较函数op
multiset<elem>, multimap<key, value>
multiset<elem, op>, multimap<key, value, op>
2. 插入元素
//赋值
C=C2；
c=rv;
c=initlist;
c1.swap(c2);
swap(c1, c2);
//插入, 只能用insert，顺序容器有assign
c.insert(val); //插入一个值的方式，平时常用的
c.insert(pos, val);
c.insert(beg, end); //可以替换copy的方式，速度更好， c.insert(istream_iterator(cin), istream_iterator());
c.insert(initlist); //最好的给予初值方式
since C++11
c.emplace(args...);
c.emplace_hint(pos, args...);
3. 访问
通过iterator访问，（c/r/cr）begin(), (c/r/cr)end()。
4. 查找
c.count(val);
c.find(val);
c.lower_bound(val); //>=val的第一个值
c.upper_bound(val); //>val的第一个值
c.equal_range(val); //>=val...>val值的范围，pair类型。
5. 属性
//基本的比较==，！=，>都支持。
//大小
c.empty();
c.size();
//比较准则
c.key_comp();
c.value_comp(); //set与key_comp()相同。map为pair<const key, value>的比较
6. 删除元素
c.erase(val); //删除所有值，multiset,multimap删除第一个可以find后再erase
c.erase(pos);
c.erase(beg, end);
c.clear();