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();