CPPprimer第十一章关联容器

关联容器和顺序容器有着根本的不同，关联容器的元素是按照关键字来访问的，顺序容器的元素是按照他们在容器中的位置来顺序保存和访问的

关联容器支持高效的关键字查找和访问，两个主要的关联容器是map和set

使用关联容器

提取map

当从 map 中提取一个元素时，会得到一个 pair 类型的对象。简单来说， pair 是一个模板类型，保存两个名为 first 和 second 的（public）数据成员。 map 所使用的 pair 用数据成员 first 保存关键字，用 second 成员保存对应的值。

使用关键字类型的比较函数

用来组织一个容器中元素的操作的类型也是该容器类型的一部分。为了指定使用自定义的操作，必须在定义关联容器类型时，提供此操作的类型。 如前所述，用尖括号指出要定义哪种类型的容器，自定义的操作类型必须在尖括号中紧跟着元素类型给出。

在尖括号中出现的每个类型，就仅仅是一个类型而已。当创建一个容器（对象）时，才会以构造函数参数的形式提供真正的比较操作（比较操作需要的类型，必须与在尖括号中指定的类型相吻合）。

例如，我们不能直接定义一个Sales_data的 multiset ，因为Sales_data没有 < 运算符。但是，可以定义一个名叫compareIsbn函数来定义一个 multiset ，因为此函数在Sales_data对象的ISBN成员上定义了一个严格弱序。函数compareIsbn应该像下面这样定义：

1
2
3
bool compareIsbn(const Sales_data &lhs, const Sales_data &rhs){
	return lhs.isbn() < rhs.isbn();
}

为了使用程序员自己定义的操作，在定义 multiset 时必须提供两个类型：关键字类型，以及比较操作的类型——应该是一种函数指针类型，可以指向对应的操作（在这里是compareIsbn）。当定义此容器类型的对象时，需要提供想要使用的操作的指针。

1
2
3
4
// bookstore中的元素以ISBN的顺序进行排列
// 在这里提供给<>操作的类型，然后在构造函数中传入函数的指针
multiset<Sales_data, decltype(compareIsbn)*> bookstore(compareIsbn);
multiset<Sales_data, decltype(compareIsbn)*> bookstore(&compareIsbn);	// 等价

关联容器操作

关联容器迭代器

当解引用一个关联容器迭代器时，我们会得到一个类型为容器的 value_type 的值的引用。对 map 而言， value_type 是一个 pair 类型，其数据成员 first 保存 const 的关键字，数据成员 second 保存值：

1
2
3
4
5
6
7
8
9
// 获得指向word_count中一个元素的迭代器
auto map_it = word_count.begin();
// *map_it是指向一个pair<const string,size_t>对象的引用

cout << map_it->first; // 打印此元素的关键字
cout << " " <<map_it->second;	// 打印此元素的值

map_it->first = "new key"; 	// 错误:关键字是const的
++map_it->second; 		// 正确：我们可以通过迭代器改变元素

必须记住，一个 map 的 value_type 是一个 pair ，我们可以改变 pair 的 second 数据成员的值，但不能改变关键字成员 first 的值。

向map添加元素

1
2
3
4
5
6
//向word_count插入word的4种方法
//也是四种创建一个pair对象的方式
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));	// 与上一句相同

map的下标操作

map 和 unordered_map 容器提供了下标运算符和一个对应的 at 成员函数 ，如下表所示。

map 和 unordered_map 的下标操作
c[k] 返回关键字为 k 的元素；如果 k 不在 c 中，添加一个关键字为k的元素，对其进行值初始化
c.at(k) 访问关键字为 k 的元素，带参数检查；若 k 不在 c 中，抛出一个 out_of_range 异常

访问操作

关联容器提供多种查找一个指定元素的方法

  • find
  • count
  • lower_bound
  • upper_bound
  • equal_range

成员函数 lower_bound 和 upper_bound 不适用于无序（multi）容器。