关联容器和顺序容器的不同

关联容器和顺序容器的根本不同之处在于，关联容器中的元素是按关键字来保存和访问的（比如map和set），而顺序容器中的元素是按照在容器中的位置来顺序保存和访问的(比如vector和string)。

顺序容器有

vector
deque
list
forward_list
array
string

关联容器有

按照关键字有序保存
map
set
multimap
multiset
无序保存
unordered_map
unordered_set
unordered_multimap
unordered_multiset

关联容器不支持和位置相关的操作，因为是按关键字顺序存储的，关联容器的迭代器都是双向的。

对于有序关联容器中的关键字类型要求

对与有序关联容器而言，关键字类型必须定义元素比较的方法(这一点尤其重要)，默认时，使用关键字类型的<运算符来比较两个关键字。即虽然可以向容器中保存自己定义的类或者结构体，但是如果这些类和结构体中没有定义<运算符的话，则该行为就是不合法的。

但是可以向算法提供一个自己定义的比较操作(通常是一个函数)或者对<进行重载来完成比较操作，唯一需要注意的就是，所提供的操作必须在关键字类型上严格弱序(可以看作小于等于)。

严格弱序具有反自反性（不能同时小于等于对方），也具有传递性(k1<=k2,k2<=k3则有k1<=k3)，

严格弱序上的等价关系是任何一个都不小于等于另一个，这个等价关系也具有传递性。

在使用自己定义的操作时，必须要提供该操作类型(可以使用decltype来获得函数指针类型)，比如定义一个multiset

multiset<type,decltype(CompareFunction)*>name(CompareFunction);

关联容器额外的类型别名

类型别名	含义
key_type	该容器的关键字类型
mapped_type	关键字关联的类型，只适用于map
value_type	对于set而言和key_type相同；对于map,为pair<const key_type,mapped_type>

关联容器和算法

实际使用算法时，关联容器只能是一个源序列或者目的序列。
比如：

	multiset<string>c{ "1","2","1" };
	vector<string>v;
	copy(c.begin(), c.end(), back_inserter(v));//v为目的序列,c为源序列

	multiset<string>c;
	vector<string>v{ "1","2","1" };
    copy(v.begin(), v.end(), inserter(c,c.end())); //c为目的序列，v为源序列

关联容器的操作及其返回值

插入元素

insert向容器中插入一个元素，不存在则什么也不做。emplace也是插入元素，但是只有当关键字不在容器时才插入。

insert(value_type);  //value_type对于set就是关键字，对于map而言就是一个pair
insert(args);		//arges时一个初始化列表
insert(begin,end);	//insert也可以接受一对迭代器begin,end;
insert(p,args);		//从容器的p位置开始搜索新元素args的插入位置

emplace(value_type);//当关键字不在容器时才插入
emplace(p,args);//从容器的p位置开始搜索新元素args的插入位置

对于插入一个元素的insert(value_type)和emplace(value_type)会返回一个pair< value_type::iterator,bool >,

pair的first时一个指向给定插入元素的迭代器，pair的second是一个表示是否插入成功的布尔值；

对于insert(args)和insert(begin,end),返回一个void;

对于insert(p,args)和emplace(p,args)，返回一个迭代器，指向给定元素。

删除元素

关联容器有三个版本的erase操作，分别接受一个关键字，一个迭代器和一对迭代器。

访问和查找元素

1.下标(有序无序可用)

对于map而言，可以使用下标或者一个at函数来对容器中的元素进行访问，比如m[key]或者m.at(key)这样的操作。
对于下标而言，如果该关键字在容器中不存在，那么就会被当作一个新元素加入到容器中去。at函数没有这样的作用，它只会对参数进行检查，如果不存在就抛出一个out_of_range的异常。

而对于set而言，是不能用下标进行访问的。

2.find或者count(有序无序可用)

对于map和set都有自带的find和count版本,find会返回一个迭代器，指向第一个关键字为参数的元素，但如果该关键字不存在，就返回尾后迭代器。
count会返回容器中符合要求的关键字的数量，不存在则为0；

3.lower_bound和upper_bound(有序版本)

lower_bound(k)会返回一个迭代器，指向第一个关键字不小于k的元素(即<k的上界，>=k的下界)。如果不存在则返回一个不影响排序的关键字的插入位置(即如果要将这个不存在的关键字插入到容器中时要放入的位置)。
upper_bound(k)会返回一个迭代器，指向第一个关键字大于k的元素，即>k的下界，<=k的下界。如果不存在也会返回一个不影响排序的关键字的插入位置。
比如：

multimap<string,string>words;
string k="Test";
auto b=words.lower_bound(k),e=words.upper_bound(k);
for(;b!=e;++b)cout<<b->second<<endl;

如果调用lower_bound(k)的话，如果容器中存在关键字k的话，b就会匹配到第一个k所在的元素位置，e则会指向最后一个k之后的位置，否则b和e都会指向一个相同位置，即不影响排序的关键字的插入位置。
所以对于同样的参数调用，如果lower_bound和upper_bound指向的迭代器不相同，那么两个就是一个包含所有关键字k的迭代器范围[b,e)。

4.equal_range函数(有序版本)

对于上面的版本，用equal_range函数可以改写为:

multimap<string,string>words;
string k="Test";
auto pos=words.equal_range(k);
for(;pos.first!=pos.second;++pos.first)cout<<pos.first->second<<endl;

//pos.first和words.lower_bound(k)相等
//pos.second和words.upper_bound(k)相等

equal_range接受一个关键字，返回一个pair，包含两个迭代器。当关键字存在时，两个迭代器就是刚才用lower_bound和upper_bound得到的迭代器。当不存在时，也返回不影响排序的关键字的插入位置。

无序容器

概念和性能

无序容器使用一个哈希函数和关键字类型的==运算符来组织元素，而不是<运算符。
无序容器在存储上的组织形式为一组桶，利用哈希函数将具有一个相同哈希值的元素保存在相同的桶中(即使是重复版本的无序容器也是一样)，所以无序容器的性能取决于哈希函数的性能和桶的数量和大小。

无序容器对关键字类型的要求

对于内置的类型比如int，以及标准库类型比如string,标准库都提供了默认的hash模板，所以可以直接定义，比如：

unordered_map<string, int>words;

但是对于自定义的类型，就需要提供hash模板或者提供函数来替代==运算符和哈希函数(类似重载)。
一种特别的情况时，如果关键字是一个已经自定义了==运算符的类，则只需要提供哈希函数即可。