C++中的关联容器与无序关联容器

关联容器：

关联容器将值与键关联在一起，并用键来查找值
关联容器通常是使用某种树实现的
STL提供了4中关联容器：set、multiset、map、multimap
前两种在头文件< set >中定义，后两种在头文件< map >中定义

set与multiset:

set的值类型与键相同，键是惟一的，集合中不会存在多个相同的键，因此，对于set来说，值就是键

set是关联集合，可反转，可排序，且键是唯一的，所以不能存储多个相同的值

multiset与set类似，只是可能有多个值的键相同，例如，若键和值的类型为int，则multiset对象包含的内容可以为 1,2，2,2，3,5，5,7。而set对象包含的内容可为1,2,3,5,7

set使用模板参数指定要存储的值类型：

set<string> A;  // a set of string object

set的初始化：
1.调用insert方法

set<int> s;
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
	int x;
    cin>>x;
    s.insert (x);
}

2.使用以迭代器区间作为参数的构造函数

const int N=6;
string s1[N]={"buffer","thinkers","for","heavy","can","for"};
set<string> A(s1,s1+N);

两个有用的set方法：
lower_bound(): 将键作为参数并返回一个迭代器，该迭代器指向集合中第一个第一个不小于键参数的成员
upper_bound(): 将键作为参数并返回一个迭代器，该迭代器指向集合中第一个第一个大于键参数的成员

set<int> s;
s.insert(1);
s.insert(3);
s.insert(4);
cout<<*s.lower_bound(2)<<endl;	//打印出3
cout<<*s.lower_bound(3)<<endl;	//打印出3
cout<<*s.upper_bound(3)<<endl;	//打印出4

set中常用方法：

begin()     　　 返回指向set容器的第一个元素的迭代器

end() 　　　　 返回set容器的超尾迭代器

clear()   　　     删除set容器中的所有的元素

empty() 　　　判断set容器是否为空

max_size() 　 返回set容器可能包含的元素最大个数

size() 　　　　 返回当前set容器中的元素个数

rbegin　　　　 返回的值和end()相同

rend()　　　　 返回的值和begin()相同

其他set中的方法:
count()：
用来查找set中某个键值出现的次数。由于一个键值在set中只可能出现0或1次，这样count()方法的作用就变成了判断某一键值是否在set出现过。

erase():
erase(iterator) 删除迭代器iterator指向的值

erase(first,second) 删除迭代器first和second之间的值（左闭右开，[first,second) ）

erase(key_value) 删除键值为key_value的值

find() ：
返回指示给定值的迭代器，如果没找到则返回end()

insert():
insert(key_value) ：
将key_value插入到set中，返回值是pair<set::iterator,bool>，bool标志着插入是否成功，而iterator代表插入的位置，若key_value已经在set中，则iterator表示的是key_value在set中的位置。

inset(first,second)：
将迭代器first到second之间的元素插入到set中，返回值是void.

map与multimap:

在map中，值与键的类型不同，键是惟一的，每个键只对应一个值。multimap与map类似，只是一个键可与多个值相关联

map的声明：
使用模板参数指定键的类型和存储的值的类型：

map<int,string> codes;

数据的插入：
为将信息结合在一起，实际的值类型将键类型和数据类型结合为一对。STL使用模板类pair<class T,class U>将这两种值存储到一个对象中，
即 pair< const keytype,datatype >
1.用insert方法插入pair数据：

map<int, string> mapStudent;  
mapStudent.insert(pair<int, string>(1,"student_one"));  
mapStudent.insert(pair<int, string>(2,"student_two"));  
mapStudent.insert(pair<int,string>(3,"student_three"));

2.用数组方式插入数据：

map<int, string> mapStudent;  
mapStudent[1] = "student_one";  
mapStudent[2] = "student_two";  
mapStudent[3] = "student_three";

用insert方法插入数据，在数据的插入上涉及到集合的唯一性，即当map中有这个关键字时，insert操作是插入数据不了的，即插入不成功。但是用数组方式可以覆盖以前该关键字对应的值

map中的常用方法：

size()
erase()
clear()
upper_bound()
lower_bound()
swap()			两个容器所有元素进行交换
insert()

map中数据的遍历：
1.利用迭代器：

for(iter = mapStudent.begin();iter!=mapStudent.end(); iter++)  
	cout<<iter->first<<' '<<iter->second<<endl;

2.利用数组形式：

map<int, string> mapStudent;  
mapStudent.insert(pair<int, string>(1,"student_one"));  
mapStudent.insert(pair<int, string>(2, "student_two"));  
mapStudent.insert(pair<int, string>(3, "student_three"));  
int nSize = mapStudent.size();
for(int nindex = 1; nindex <= nSize; nindex++)
 	cout<<mapStudent[nindex]<<endl;

查找并获取map中的元素：
1.count()方法：
能判断关键字是否出现，但无法定位数据出现的位置，与set类似，一对一的映射关系，决定了count函数的返回值只有两个，要么是0，要么是1，出现的情况，返回1
2.find()方法：
返回迭代器

无序关联容器:

unordered_set、unordered_multiset、unordered_map、unordered_multimap:

无序关联容器使用键和哈希表。若键为string对象，哈希函数可能将其中每个字符的数字编码相加，再将计算结果除以13的余数，从而得到一个0~12的索引。无序容器将使用13个桶(bucket)来存储string，例如所有索引为4的string都将存储在第四个桶中。若要在容器中搜索键，将对键执行哈希函数，进而只在索引对应的桶中搜索。

它们的操作及方法与关联容器类似

由于unordered_map里面的元素是以pair类型来存贮的，因此键与值的类型可以相同

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/153855.html