关联容器和顺序容器的不同：关联容器中的元素时按照关键字来保存和访问的。 关联容器支持通过关键字来高效地查找和读取元素，基本的关联容器类型是 map和 set。

关联容器类型：

一、使用关联容器

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

//map
map<int , size_t> word_count;
string word;
while(cin>>word)
	++word_count[word];
for(const auto &w : word_count)
	cout<<w.first<<" occurs "<<w.second
	    <<((w.second>1)?"times":"time")<<endl;

//set
map<string, size_t> word_count; // string 到 size_t 的空 map 
set<string> exclude = ("The", "But", "And”， MOr'*, "An", "A”， "the”， “but”， "and”， norn , "ann , "a"};
string word;
while (cin>>word)
//只统计不在exclude中的单词
if (exclude.find(word) == exclude.end())
	++word_count [word] ; //获取并递增word的计数器

二、关联容器概述

• 关联容器基本支持普通容器的所有操作，但是不支持顺序容器的位置相关操作，例如push_back，push_front
• 关联容器还支持特有的操作和类型别名
• 无序容器还支持一些来调整哈希性能的操作

1、定义关联容器

• 必须需要指定元素类型，并且值符合要求或者可以转化。
• 默认构造
• 关联容器初始化为另一个同类型容器的拷贝
• 值范围初始化
• 列表初始化：
  • map：map<string, int> word_count = {{"a", 1}, {"b", 2}};
  • set：set<string> exclude = {"the", "a"};

2、关键字类型的要求

• 对于有序容器，关键字类型必须定义元素比较的方法。默认是<。
• 如果想传递一个比较的函数，可以这样定义：multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);

3、pair

• 在utility头文件中定义。
• 一个pair保存两个数据成员，两个类型不要求一样。

pair的操作

三、关联容器操作

关联容器额外的类型别名：

1、关联容器迭代器

• 解引用一个关联容器迭代器时，会得到一个类型为容器的value_type的值的引用。
• map中的迭代器解引用返回一个pair<const value_type , value_type>
• set的迭代器是const的。
• 遍历关联容器：使用begin和end，遍历map、multimap、set、multiset时，迭代器按关键字升序遍历元素。

2、添加元素

关联容器insert操作：

向map添加元素：

• word_count.insert({word, 1});
• word_count.insert(make_pair(word, 1));
• word_count.insert(pair<string, size_t>(word, 1));
• word_count.insert(map<string, size_t>::value_type (word, 1));

3、删除元素

从关联容器中删除元素：

4、下标操作

map和unordered_map的下标操作：

• set不支持下标操作，multimap也不支持
• 对map使用下标操作
  • 关键字存在，返回mapped_type
  • 关键字不存在，添加下标元素

5、查找元素

在一个关联容器中查找元素:

• lower_bound和upper_bound不适用于无序容器。
• 下标和at操作只适用于非const的map和unordered_map。

四、无序容器

• 有序容器使用比较运算符来组织元素；无序容器使用哈希函数和关键字类型的==运算符。
• 理论上哈希技术可以获得更好的性能。
• 无序容器在存储上组织为一组桶(bucket)，每个桶保存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。

无序容器管理操作：