C++标准库 -- 关联容器 (Primer C++ 第五版 · 阅读笔记)

谁借莪１个温暖的怀抱￠ 2024-03-23 13:01 33阅读 0赞

#### C++标准库 -- 关联容器(Primer C++ 第五版 · 阅读笔记） ####

*  第11章 关联容器------(持续更新)
 *   *  11.1、使用关联容器
     *  11.2、关联容器概述
     *   *  11.2.1、定义关联容器
         *  11.2.2、关键字类型的要求
         *  11.2.2、pair类型
     *  11.3、关联容器操作
     *   *  11.3.1、关联容器迭代器
         *  11.3.2、添加元素
         *  11.3.3、删除元素
         *  11.3.4、map的下标操作
         *  11.3.5、访问元素
         *  11.3.6、一个单词转换的map
     *  11.4、无序容器

## 第11章 关联容器------(持续更新) ##

关联容器和顺序容器有着根本的不同:关联容器中的元素是按**关键字**来保存和访问的。与之相对，顺序容器中的元素是按它们在容器中的**位置**来顺序保存和访问的。

虽然关联容器的很多行为与顺序容器相同，但其不同之处反映了**关键字**的作用。

标准库提供8个关联容器，如下表所示。这8个容器间的不同体现在三个维度上:每个容器

*  (1）或者是一个 `set`，或者是一个`map`;
 *  (2）或者要求**不重复**的关键字，或者允许**重复**关键字;
 *  (3）按**顺序**保存元素，或**无序**保存。

允许重复关键字的容器的名字中都包含单词`multi`;不保持关键字按顺序存储的容器的名字都以单词`unordered`开头。因此一个`unordered_multi_set`是一个允许重复关键字，元素无序保存的集合，而一个`set`则是一个要求不重复关键字，有序存储的集合。无序容器使用**哈希函数**来组织元素，。

![在这里插入图片描述][6a40ad753ca94921be40c43125eb1143.png]

**关联容器**：`set`、`multiset`、`map`、`multimap`，实现是使用 红黑树（高度平衡二叉树）

![在这里插入图片描述][5a5b681aadb74a8187fbdc1696951aef.jpeg]

*  `C++11`中有`Unordered`容器，但他也属于关联容器，实现使用`hashtable`做的

![在这里插入图片描述][a148ee53fa2445c3a1d5289876da8616.jpeg]

### 11.1、使用关联容器 ###

`map`是**关键字-值**对的集合。例如，可以将一个人的名字作为关键字，将其电话号码作为值。我们称这样的数据结构为“将名字映射到电话号码”。`map`类型通常被称为关联数组( `associative array`)。关联数组与“正常”数组类似，不同之处在于其下标**不必是整数**。我们通过一个**关键字**而不是位置来查找值。给定一个名字到电话号码的`map`，我们可以使用一个人的名字作为下标来获取此人的电话号码。

与之相对，`set`就是关键字的简单集合。当只是想知道一个值是否存在时，`set`是最有用的。例如，一个企业可以定义一个名为`bad_checks`的`set`来保存那些曾经开过空头支票的人的名字。在接受一张支票之前，可以查询`bad_checks`来检查顾客的名字是否在其中。

**使用map**

*  类似顺序容器，关联容器也是**模板**。为了定义一个`map`，我们必须指定**关键字和值的类型**。

一个经典的使用关联数组的例子是单词计数程序:

//统计每个单词在输入中出现的次数
    map<string, size_t> word_count;	// string到size_t的空map
    string word;
    while(cin >> word)
    	++word_count[word] ;		//提取word的计数器并将其加1
    for(const auto &w : word_count)	//对map中的每个元素
    	//打印结果
    	cout << w.first << " occurs " << w.second
    		<< ((w.second > 1) ? " times" : " time") << endl;

**使用set**

*  与其他容器类似，`set`也是**模板**。为了定义一个 `set`，必须指定其**元素类型**;
 *  与顺序容器类似，可以对一个关联容器的元素进行列表初始化

上一个示例程序的一个合理扩展是:忽略常见单词，如"the"、“and”、"or"等。我们可以使用`set`保存想忽略的单词，只对不在集合中的单词统计出现次数:

//统计输入中每个单词出现的次数
    map<string, size_t> word_count; //string到size_t的空map
    set<string> exclude = {
         "The", "But", "And", "or", "An", "A",
    						"the", "but", "and", "or", "an", "a" };
    string word;
    while (cin >> word)
    	//只统计不在exclude中的单词
    	if (exclude.find(word) == exclude.end()) // find 调用返回指向目标迭代器，找不到返回尾后迭代器
    		++word_count[word];//获取并递增word的计数器

### 11.2、关联容器概述 ###

**关联容器**（有序的和无序的）都支持 [**9.2**节][9.2] 中介绍的普通容器操作;

*  关联容器不支持顺序容器的位置相关的操作，例如 `push_front`或`push_back`。原因是关联容器中元素是根据**关键字**存储的，这些操作对关联容器没有意义。
 *  而且，关联容器也不支持**构造函数**或**插入操作**这些接受一个元素值和一个数量值的操作。
 *  关联容器的迭代器都是**双向的**。

#### 11.2.1、定义关联容器 ####

如前所示，当定义一个`map` 时，必须既指明**关键字类型**又指明**值类型**;而定义一个`set`时，只需指明**关键字类型**，因为`set`中没有值。

*  每个关联容器都定义了一个**默认构造函数**，它创建一个指定类型的空容器。
 *  我们也可以将关联容器初始化为另一个**同类型容器的拷贝**，或是**从一个值范围**来初始化关联容器，只要这些值可以转化为容器所需类型就可以。
 *  在新标准下，我们也可以对关联容器进行**值初始化**:

map<string, size_t> word_count;//空容器
    
    //列表初始化
    set<string> exclude = {
        "the", "but", "and", "or", "an", "a",
    						"The","But", "And", "Or", "An", "A"};
    						
    //三个元素;authors将姓映射为名
    map<string, string> authors = {
         {
        "Joyce", "James"},
    								{
        "Austen", "Jane"},
    								{
        "Dickens", "Charles"} };

**初始化 multimap或multiset**

一个`map` 或 `set` 中的关键字必须是唯一的，即，对于一个给定的关键字,只能有一个元素的关键字等于它。

容器`multimap`和 `multiset`没有此限制，它们都允许多个元素具有相同的关键字。

下面的例子展示了具有**唯一关键字**的容器与允许**重复关键字**的容器之间的区别。首先，我们将创建一个名为i`vec` 的保存`int`的`vector`，它包含20个元素:0到9每个整数有两个拷贝。我们将使用此`vector`初始化一个`set`和一个`multiset`:

//定义一个有20个元素的 vector，保存0到9每个整数的两个考贝
    vector<int> ivec;
    for(vector<int>::size_type i = 0; i != 10; ++i){
        
    	ivec.push_back(i);
    	ivec.push_back(i); //每个数重复保存一次
    }
    //iset包含来自ivec的不重复的元素;miset包含所有20个元素
    set<int> iset(ivec.cbegin(), ivec.cend());
    multiset<int> miset(ivec.cbegin(), ivec.cend());
    
    cout<< ivec.size() << endl;			//打印出20
    cout << iset.size() << endl;		//打印出10
    cout << miset.size() << endl;		//打印出20

#### 11.2.2、关键字类型的要求 ####

关联容器对其关键字类型有一些限制。

*  对于无序容器中关键字的要求，我们将在**11.4节**中介绍。
 *  对于有序容器—-`map`、`multimap`、`set` 以及 `multiset`，关键字类型必须定义元素**比较的方法**。默认情况下，标准库使用关键字类型的 `<` 运算符来比较两个关键字。在集合类型中，关键字类型就是元素类型;在映射类型中，关键字类型是元素的第一部分的类型。因此，11.2节中 `word_count` 的关键字类型是`string`。类似的，`exclude` 的关键字类型也是`string`。

**有序容器的关键字类型**

可以向一个算法提供我们**自己定义的比较操作**，与之类似，也可以提供**自己定义的操作**来代替关键字上的 `<` 运算符。所提供的操作必须在关键字类型上定义一个 **严格弱序**（`strict weak ordering`)。可以将严格弱序看作“**小于等于**”，虽然实际定义的操作可能是一个复杂的函数。无论我们怎样定义比较函数,它必须具备如下基本性质:

*  两个关键字不能同时“小于等于”对方; 如果 `k1` “小于等于” `k2`，那么 `k2` 绝不能“小于等于”`k1`。
 *  如果 `k1` “小于等于” `k2` ，且 `k2` “小于等于” `k3`，那么 `k1` 必须“小于等于” `k3`
 *  如果存在两个关键字，任何一个都不“小于等于”另一个，那么我们称这两个关键字是“等价”的。如果 `k1` “等价于” `k2`，且 `k2` “等价于” `k3`，那么 `k1` 必须“等价于” `k3`。

> 如果两个关键字是等价的（即，任何一个都不“小于等于”另一个)，那么容器将它们视作相等来处理。当用作`map`的关键字时，只能有一个元素与这两个关键字关联我们可以用两者中任意一个来访问对应的值。

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

用来组织一个容器中元素的操作的类型也是该容器类型的一部分。

*  为了指定使用自定义的操作，必须在**定义关联容器类型**时**提供此操作的类型**。如前所述，用尖括号指出要定义哪种类型的容器，自定义的操作类型必须在尖括号中紧跟着元素类型给出。
 *  在尖括号中出现的每个类型，就仅仅是一个类型而已。当我们创建一个容器（对象)时，才会以构造**函数参数的形式**提供真正的比较操作（其类型必须与在尖括号中指定的类型相吻合)。

例如，我们不能直接定义一个`sales_data`的 `multiset`，因为`sales_data`没有 `<` 运算符。但是，可以用10.3.1节练习(第345页）中的`compareIsbn`函数来定义一个`multiset`。此函数在`sales_data`对象的 ISBN成员上定义了一个严格弱序。函数`compareIsbn`应该像下面这样定义:

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

为了使用自己定义的操作，在定义`multiset` 时我们必须提供两个类型:

*  **关键字类型**`sales data`，
 *  以及**比较操作类型**——应该是一种**函数指针**类型,可以指向`compareIsbn`。

当定义此容器类型的对象时，需要提供想要使用的操作的指针。在本例中，我们提供一个指向`compareIsbn`的指针:

// bookstore中多条记录可以有相同的ISBN
    // bookstore中的元素以ISBN的顺序进行排列
    multiset<Sales_data, decltype(compareIsbn)*>
    	bookstore(compareIsbn);

此处，我们使用`decltype`(**类型推导工具**)来指出自定义操作的类型。记住，当用`decltype`来获得一个函数指针类型时，必须加上一个 `*` 来指出我们要使用一个给定函数类型的指针。

可以用`compareIsbn` 代替`&compareIsbn`作为构造函数的参数，因为当我们使用一个函数的名字时，在需要的情况下它会自动转化为一个指针。当然，使用`&compareIsbn`的效果也是一样的。

#### 11.2.2、pair类型 ####

在介绍关联容器操作之前，我们需要了解名为`pair`的标准库类型，它定义在头文件`utility` 中。

一个`pair`保存两个数据成员。类似容器，`pair`是一个用来生成特定类型的模板。当创建一个`pair`时，我们必须提供两个类型名，`pair`的数据成员将具有对应的类型。两个类型不要求一样:

pair<string, string> anon;				//保存两个string
    pair<string, size_t> word_count;		//保存一个string和一个size_t
    pair<string, vector<int>> line;			//保存 string和vector<int>
    
    //为每个成员提供初始化器
    pair<string, string> author{
        "James", "Joyce"};

与其他标准库类型不同，`pair` 的数据成员是 `public` 的。两个成员分别命名为 `first` 和 `second`。我们用普通的成员访问符号来访问他们：

//打印结果
    cout << w.first << " occurs " << w.second
    	<<((w.second > 1) ? " times" : " time") << endl;

![在这里插入图片描述][809f83fc70d043f3be07b045064af9d5.png]  
**创建pair对象的函数**

想象有一个函数需要返回一个`pair`。在新标准下，我们可以对返回值进行列表初始化:

pair<string, int> process(vector<string> &v)
    {
        
    	//处理v
    	if (!v.empty())
    		return {
        v.back(), v.back().size()};//列表初始化
    		//我们还可以用make_pair来生成pair对象
    		//return make_pair(v.back(), v.back().size());
    	else
    		return pair<string, int>(); //隐式构造返回值
    }

### 11.3、关联容器操作 ###

除了表[9.2（第295页）][9.2]中列出的类型，关联容器还定义了表11.3中列出的类型。这些类型表示容器关键字和值的类型。

![在这里插入图片描述][7a64c9eee2fe4bcc802b21b80084dc7a.png]

*  对于`set`类型,`key_type`和 `value_type`是一样的; `set`中保存的值就是关键字。
 *  在一个`map`中，元素是`关键字-值`对。即，每个元素是一个`pair`对象，包含一个`关键字`和一个`关联的值`。

由于我们不能改变一个元素的关键字，因此这些`pair`的关键字部分是`const`的:

set<string>::value_type vl; 		// v1是一个string
    set<string>::key_type v2;			// v2是一个string
    map<string, int>::value_type v3; 	// v3是一个pair<const string, int>
    map<string, int>::key_type v4;		// v4是一个string
    map<string,int>::mapped_type v5;	// v5是一个int

*  与顺序容器一样，我们使用作用域运算符来提取一个类型的成员——例如，`map<string, int>: : key_type`。
 *  只有`map`类型(`unordered_map`、`unordered_multimap`、`multimap`和 `map`)才定义了`mapped_type`。

#### 11.3.1、关联容器迭代器 ####

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

//获得指向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`的值,但不能改变关键字成员的值。

**set的迭代器是const的**

虽然`set`类型同时定义了`iterator`和 `const_iterator`类型，但两种类型都只允许只读访问`set`中的元素。与不能改变一个`map`元素的关键字一样，一个`set`中的关键字也是`const`的。可以用一个set迭代器来读取元素的值，但不能修改;

set<int> iset = {
        0,1,2,3,4,5,6,7,8,9};
    set<int>::iterator set_it = iset.begin();
    if(set_it != iset.end()) {
        
    	*set_it = 42;			//错误:set中的关键字是只读的
    	cout << *set_it <<endl; //正确:可以读关键字
    )

> 当使用一个迭代器遍历一个`map`,`multimap`、`set`或`multiset`时，迭代器按关键字升序遍历元素。(按字典序排列。)

**关联容器和算法**

我们通常不对关联容器使用**泛型算法**（参见第10章)。关键字是`const`这特性意味着不能将关联容器传递给**修改或重排**容器元素的算法，因为这类算法需要向元素**写入值**，而`set`类型中的元素是`const`的, `map` 中的元素是`pair`，其第一个成员是`const`的。

关联容器可用于只读取元素的算法。但是，很多这类算法都要搜索序列。由于关联容器中的元素不能通过它们的关键字进行（快速)查找，因此对其使用**泛型搜索算法几乎总是个坏主意**。

*  例如，我们将在11.3.5节（第388页）中看到，关联容器定义了一个名为`find` 的成员，它通过一个给定的关键字直接获取元素。我们可以用泛型`find`算法来查找一个元素，但此算法会进行顺序搜索。使用关联容器定义的专用的`find`成员会比调用泛型find快得多。

在实际编程中,如果我们**真要对一个关联容器便用算法**，要么是将它当作一个源序列，要么当作一个目的位置。

*  例如，可以用泛型`copy`算法将元素从一个关联容器拷贝到另一个序列。
 *  类似的，可以调用`inserter`将一个插入器绑定（参见10.4.1节，第358页)到一个关联容器。通过使用`inserter`，我们可以将关联容器当作一个**目的位置**来调用另一个算法。

#### 11.3.2、添加元素 ####

关联容器的`insert`成员（见下表11.4）向容器中添加一个元素或一个元素范围。由于`map`和 `set` (以及对应的无序类型)包含不重复的关键字，因此插入一个已存在的元素对容器没有任何影响:

vector<int> ivec = {
        2,4,6,8,2,4,6,8 };		// ivec有8个元素
    set<int> set2;								//空集合
    set2.insert(ivec.cbegin(), ivec.cend());	// set2有4个元素
    set2.insert({
        1,3,5,7,1,3,5,7});				// set2现在有8个元素

`insert`有两个版本，分别**接受一对迭代器**，或是**一个初始化器列表**，这两个版本的行为类似对应的构造函数——对于一个给定的关键字，只有第一个带此关键字的元素才被插入到容器中。

**向map添加元素**

对一个`map`进行`insert` 操作时，必须记住元素类型是`pair`。通常，对于想要插入的数据，并没有一个现成的`pair`对象。可以在`insert`的参数列表中创建一个`pair`:

//向word_count插入word的4种方法
    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));

如我们所见，在新标准下，创建一个`pair`最简单的方法是在参数列表中使用**花括号初始化**。也可以调用`make_pair`或显式构造`pair`。最后一个`insert`调用中的参数:

map<string, size_t>::value_type(s, 1)

构造一个恰当的`pair`类型，并构造该类型的一个新对象，插入到`map` 中。

![在这里插入图片描述][765160ddaa8d477db176f2e098217556.png]  
**检测insert的返回值**

`insert`（或`emplace`）返回的值依赖于容器类型和参数。对于不包含重复关键字的容器，添加单一元素的`insert`和`emplace`版本返回一个`pair`，告找我们插入操作是否成功。

*  `pair`的`first`成员是一个迭代器，指向具有给定关键字的元素;
 *  `second` 成员是一个`bool`值，指出元素是插入成功还是已经存在于容器中。

如果关键字已在容器中，则`insert`什么事情也不做，且返回值中的`bool`部分为`false`。如果关键字不存在，元素被插入容器中，且`bool` 值为`true`。

作为一个例子，我们用insert重写单词计数程序:

//统计每个单词在输入中出现次数的一种更烦琐的方法
    map<string, size_t> word_count;  // 从string 到 size_t的空map
    string word;
    while (cin >> word){
        
    	//插入一个元素，关键字等于word，值为1;
    	//若word已在word_count中， insert什么也不做
    	auto ret = word_count.insert({
        word, 1});
    	if (!ret.second) 					// word已在word_count中
    		++ret.first->second;			//递增计数器
    }

*  对于每个`word`，我们尝试将其插入到容器中，对应的值为1。若`word` 已在`map` 中，则什么都不做，特别是与`word` 相关联的计数器的值不变。若 `word` 还未在 `map` 中，则此`string`对象被添加到`map` 中，且其计数器的值被置为1。
 *  `if`语句检查返回值的 `bool`部分，若为`false`，则表明插入操作未发生。在此情况下，`word`已存在于 `word_count` 中，因此必须递增此元素所关联的计数器。

**展开递增语句**

在这个版本的单词计数程序中，递增计数器的语句很难理解。通过添加一些括号来反映出运算符的优先级，会使表达式更容易理解一些:

++((ret.first)->second); //等价的表达式

*  `ret`保存`insert`返回的值，是一个`pair`。
 *  `ret.first` 是`pair`的第一个成员，是一个`map` 迭代器，指向具有给定关键字的元素。
 *  `ret.first->`解引用此迭代器，提取`map`中的元素，元素也是一个`pair`。
 *  `ret.first->second`， `map`中元素的值部分。
 *  `++ret.first->second`递增此值。

**向multiset 或 multimap添加元素**

我们的单词计数程序依赖于这样一个事实:一个给定的关键字只能出现一次。这样，任意给定的单词只有一个关联的计数器。我们有时希望能添加具有相同关键字的多个元素。

例如，可能想建立作者到他所著书籍题目的映射。在此情况下，每个作者可能有多个条目，因此我们应该使用`multimap`而不是`map`。由于一个`multi容器`中的关键字不必唯一，在这些类型上调用`insert`总会插入一个元素:

multimap<string, string> authors;
    //插入第一个元素，关键字为 Barth,John
    authors.insert({
        "Barth,John", "Sot-Weed Factor" });
    //正确:添加第二个元素，关键字也是Barth, John
    authors.insert({
        "Barth，John","Lost in the Funhouse"});

对允许重复关键字的容器，接受单个元素的`insert`操作返回一个指向新元素的迭代器。这里无须返回一个`bool`值，因为`insert`总是向这类容器中加入一个新元素。

#### 11.3.3、删除元素 ####

关联容器定义了三个版本的`erase`，如表11.5所示。

*  与顺序容器一样，我们可以通过传递给`erase` **一个迭代器**或**一个迭代器对**来删除一个元素或者一个元素范围这两个版本的`erase`与对应的顺序容器的操作非常相似:
    
     *  指定的元素被删除，函数返回`void`。

关联容器提供一个额外的`erase`操作，它接受一个`key_type`参数。此版本删除所有匹配给定关键字的元素（如果存在的话)，返回实际删除的元素的数量。我们可以用此版本在打印结果之前从`word_count` 中删除一个特定的单词:

//删除一个关键字，返回删除的元素数量
    if(word_count.erase(removal_word))
    	cout << "ok: " << removal_word << " removedn";
    else cout << "oops: " << removal_word << " not found ! \n";

对于保存不重复关键字的容器，`erase`的返回值总是0或1。若返回值为0，则表明想要删除的元素并不在容器中；对允许重复关键字的容器，删除元素的数量可能大于1:  
![在这里插入图片描述][3e29a3937600468a964ffbb6a01227d0.png]

#### 11.3.4、map的下标操作 ####

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

*  `set`类型不支持下标，因为`set`中没有与关键字相关联的“值”。元素本身就是关键字，因此“获取与一个关键字相关联的值”的操作就没有意义了。
 *  我们不能对一个`multimap`或一个`unordered_multimap`进行下标操作，因为这些容器中可能有多个值与一个关键字相关联。

类似我们用过的其他`下标运算符`，`map` 下标运算符接受一个索引(即，一个关键字)，获取与此关键字相关联的值。但是，与其他下标运算符不同的是，如果关键字并不在`map`中，会为它创建一个元素并插入到`map`中，关联值将进行值初始化。

例如，如果我们编写如下代码

map<string, size_t> word_count; //lempty map
    //插入一个关键字为Anna的元素，关联值进行值初始化;然后将1赋予它
    word_count[ "Anna" ] = l;

将会执行如下操作:

*  在`word_count`中搜索关键字为`Anna`的元素，未找到。
 *  将一个新的关键字-值对插入到`word_count`中。关键字是一个`const string`保存`Anna`。值进行值初始化，在本例中意味着值为0。
 *  提取出新插入的元素，并将值1赋予它。

由于下标运算符可能插入一个新元素，我们只可以对非`const`的`map`使用下标操作。

> 对一个`map`使用下标操作，其行为与数组或`vector`上的下标操作很不相同:  
> 使用一个不在容器中的关键字作为下标，会添加一个具有此关键字的元素到`map`中。

![在这里插入图片描述][1275c0c1d5404992b25148e9d0ad7b81.png]

**使用下标操作的返回值**

`map`的下标运算符与我们用过的其他下标运算符的另一个不同之处是其**返回类型**。

*  通常情况下，**解引用一个迭代器**所返回的类型与**下标运算符返回的类型**是**一样**的.
 *  但对`map`则不然:当对一个`map`进行**下标操作**时，会获得一个`mapped_type`对象;
 *  但**当解引用**一个`map迭代器`时，会得到一个`value_type`对象。

与其他下标运算符相同的是，`map` **下标运算符**返回一个左值。由于返回的是一个左值，所以我们既可以读也可以写元素:

cout << word_count["Anna"];		//用Anna 作为下标提取元素;会打印出1
    ++word_count["Anna"];			//提取元素，将其增1
    cout << word_count["Anna"];	//提取元素并打印它;会打印出2

> 与 `vector` 与 `string`不同,`map` 的下标运算符返回的类型与解引用`map`迭代器得到的类型不同。

如果关键字还未在 `map` 中，下标运算符会添加一个新元素，这一特性允许我们编写出异常简洁的程序，例如单词计数程序中的循环。另一方面，有时只是想知道一个元素是否已在 `map` 中，但在不存在时并不想添加元素。在这种情况下，就不能使用下标运算符。

#### 11.3.5、访问元素 ####

关联容器提供多种查找一个指定元素的方法,如表11.7所示。应该使用哪个操作依赖于我们要解决什么问题。

*  如果我们所关心的只不过是一个**特定元素**是否已在容器中，可能`find`是最佳选择。
 *  对于不允许重复关键字的容器，可能使用`find`还是 `count`没什么区别。
 *  但对于允许重复关键字的容器，`count`还会做更多的工作:如果元素在容器中，它还会统计有多少个元素有相同的关键字。
 *  如果不需要计数，最好使用`find`:

set<int> iset = {
        0,1,2,3,4,5,6,7,8,9};
    iset.find(1);		//返回一个迭代器，指向key == 1的元素
    iset.find(11); 		//返回一个迭代器，其值等于iset.end ()
    iset.count(1);		//返回1
    iset.count(11);		//返回0

![在这里插入图片描述][a9834edc246c4248be7bf0038347c2c8.png]  
![在这里插入图片描述][3eb5f7451c794104b8c71005fdc1cf0a.png]

**对map使用find代替下标操作**

对`map`和`unordered_map`类型，**下标运算符**提供了最简单的提取元素的方法。但是，如我们所见，使用下标操作有一个严重的副作用:

*  如果关键字还未在 `map`中，下标操作会插入一个具有给定关键字的元素。这种行为是否正确完全依赖于我们的预期是什么。
 *  例如，单词计数程序依赖于这样一个特性:使用一个不存在的关键字作为下标，会插入一个新元素，其关键字为给定关键字，其值为0。也就是说，下标操作的行为符合我们的预期。

但有时，我们只是想知道一个给定关键字是否在 `map` 中，而不想改变`map`。这样就不能使用下标运算符来检查一个元素是否存在，因为如果关键字不存在的话，下标运算符会插入一个新元素。在这种情况下，应该使用`find`:

if (word_count.find("foobar") == word_count.end() )
    	cout << "foobar is not in the map" << endl;

**在multimap 或 multiset中查找元素**

在一个不允许重复关键字的关联容器中查找一个元素是一件很简单的事情——元素要么在容器中，要么不在。

但对于允许重复关键字的容器来说，过程就更为复杂:在容器中可能有很多元素具有给定的关键字。如果一个`multimap`或`multiset`中有多个元素具有给定关键字，则这些元素在容器中会相邻存储。

例如,给定一个从作者到著作题目的映射,我们可能想打印一个特定作者的**所有著作**。可以用三种不同方法来解决这个问题。最直观的方法是使用`find`和`count`:

string search_item( "Alain de Botton" );		//要查找的作者
    auto entries = authors.count(search_item);		//元素的数量
    auto iter = authors.find(search_item);			//此作者的第一本书
    //用一个循环查找此作者的所有著作
    while (entries){
        
    	cout << iter->second << endl;				//打印每个题目
    	++iter;										//前进到下一本书
    	--entries;									//记录已经打印了多少本书
    }

> 当我们遍历一个`multimap` 或 `multiset` 时，保证可以得到序列中所有具有给定关键字的元素。

**一种不同的，面向迭代器的解决方法**

我们还可以用`lower_bound`和`upper_bound`来解决此问题。这两个操作都接受一个关键字，返回一个迭代器。

*  如果关键字在容器中，`lower_bound` 返回的迭代器将指向**第一个具有给定关键字的元素**，而`upper_bound`返回的迭代器则指向**最后一个匹配**给定关键字的元素**之后的位置**。
 *  如果元素不在 `multimap` 中，则 `lower_ bound` 和 `upper_bound` 会返回相等的迭代器——指向**一个不影响排序的关键字插入位置**。

因此，用相同的关键字调用`lower_bound`和 `upper_bound`会得到一个迭代器范围，表示所有具有该关键字的元素的范围。

当然，这两个操作返回的迭代器可能是容器的**尾后迭代器**。如果我们查找的元素具有容器中最大的关键字,则此关键字的`upper_bound`返回尾后迭代器。如果关键字不存在，且大于容器中任何关键字，则`lower_bound`返回的也是尾后迭代器。

> `lower_bound`返回的迭代器可能指向一个具有给定关键字的元素,但也可能不指向。如果关键字不在容器中，则 `lower_bound`会返回关键字的第一个**安全插入点**——不影响容器中元素顺序的插入位置。

使用这两个操作，我们可以重写前面的程序:

//authors和search_item的定义，与前面的程序一样
    //beg和end表示对应此作者的元素的范围
    for (auto beg = authors.lower_bound(search_item), end = authors.upper_bound(search_item); beg != end; ++beg)
    	cout << beg->second << endl; //打印每个题目

此程序与使用`count`和 `find` 的版本完成相同的工作，但更直接。

*  对`lower_bound` 的调用将`beg`定位到第一个与`search_item` 匹配的元素(如果存在的话)。如果容器中没有这样的元素，`beg`将指向第一个 **关键字大于** `search_item的`元素，有可能是**尾后迭代器**。
 *  `upper_bound`调用将`end`指向最后一个匹配指定关键字的元素之后的元素。这两个操作并不报告关键字是否存在，重要的是它们的返回值可作为一个迭代器范围。

> 如果没有元素与给定关键字匹配,则`lower_bound`和 `upper_bound`会返回**相等的迭代器**——都指向给定关键字的插入点，能保持容器中元素顺序的插入位置。

**equal\_range函数**

解决此问题的最后一种方法是三种方法中最直接的:不必再调用`upper_bound`和 `lower_bound`，直接调用`equal_range`即可。

*  此函数接受一个关键字，返回一个迭代器`pair`。若关键字存在，则第一个迭代器指向**第一个与关键字匹配的元素**，**第二个迭代器指向最后一个匹配元素之后的位置**。
 *  若未找到匹配元素，则两个迭代器**都指向关键字可以插入的位置**。

可以用`equal_range`来再次修改我们的程序:

// authors和search_item的定义，与前面的程序一样
    // pos保存迭代器对，表示与关键字匹配的元素范围
    for (auto pos = authors.equal_range(search_item); pos.first != pos.second; ++pos.first)
    	cout<< pos.first->second <<endl; //打印每个题目

此程序本质上与前一个使用`upper_bound`和 `lower_bound` 的程序是一样的。不同之处就是，没有用局部变量 `beg`和 `end`来保存元素范围，而是使用了`equal_range`返回的`pair`。此`pair`的 `first`成员保存的迭代器与`lower_bound`返回的迭代器是一样的，`second` 保存的迭代器与`upper_bound` 的返回值是一样的。因此，在此程序中，`pos.first`等价于`beg`，`pos.second`等价于`end`。

#### 11.3.6、一个单词转换的map ####

[具体程序][Link 1]

### 11.4、无序容器 ###

新标准定义了**4个无序关联容器**(`unordered associative container`)。

*  这些容器不是使用比较运算符来组织元素，而是使用一个**哈希函数**（`hash function`）和关键字类型的`==`运算符。
 *  在关键字类型的元素没有明显的序关系的情况下，无序容器是非常有用的。在某些应用中，维护元素的序代价非常高昂，此时无序容器也很有用。

![在这里插入图片描述][a148ee53fa2445c3a1d5289876da8616.jpeg]

虽然理论上哈希技术能获得更好的平均性能，但在实际中想要达到很好的效果还需要进行一些性能测试和调优工作。因此,使用无序容器通常更为简单(通常也会有更好的性能)。

> 如果关键字类型固有就是无序的，或者性能测试发现问题可以用**哈希技术**解决,就可以使用**无序容器**。

**使用无序容器**

除了哈希管理操作之外，无序容器还提供了与有序容器相同的操作（`find`、`insert`等)。这意味着我们曾用于`map`和 `set`的操作也能用于`unordered_map`和`unordered_ set`。类似的，无序容器也有允许重复关键字的版本。

因此，通常可以用一个无序容器替换对应的有序容器，反之亦然。但是，由于元素未按顺序存储，一个使用无序容器的程序的输出（通常）会与使用有序容器的版本不同。

例如，可以用`unordered_map`重写最初的单词计数程序:

//统计出现次数，但单词不会按字典序排列
    unordered_map<string, size_t> word_count;
    string word;
    while (cin >> word)
    	++word_count[word]; 			//提取并递增word的计数器
    for (const auto &w : word_count)	// 对map中的每个元素
    	//打印结果
    	cout << w.first << " occurs " << w.second <<((w.second > 1）? " times" : " time") << endl;

对于每个单词，我们将得到相同的计数结果。但单词不太可能按字典序输出。

**管理桶**

无序容器在存储上组织为一组桶，每个桶保存零个或多个元素。

*  无序容器使用一个**哈希函数**将元素映射到桶。
 *  为了访问一个元素，容器首先计算元素的**哈希值**，它指出应该搜索哪个桶。
 *  容器将具有一个特定**哈希值**的所有元素都保存在相同的桶中。
 *  如果容器允许重复关键字，所有具有相同关键字的元素也都会在同一个桶中。因此，无序容器的性能依赖于哈希函数的质量和桶的数量和大小。

对于相同的参数，哈希函数必须总是产生相同的结果。理想情况下，哈希函数还能将每个特定的值映射到唯一的桶。但是，将不同关键字的元素映射到相同的桶也是允许的。

当一个桶保存多个元素时，需要顺序搜索这些元素来查找我们想要的那个。计算一个元素的哈希值和在桶中搜索通常都是很快的操作。但是，如果一个桶中保存了很多元素，那么查找一个特定元素就需要大量比较操作。

无序容器提供了一组管理桶的函数，下表所示。这些成员函数允许我们查询容器的状态以及在必要时强制容器进行重组。

![在这里插入图片描述][27c272aa050b48a6a279d5dc6a1004b2.png]

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

默认情况下，无序容器使用关键字类型的`==`运算符来比较元素，它们还使用一个`hash<key_type>`类型的对象来生成每个元素的哈希值。

标准库为内置类型（包括指针)提供了`hash`模板。还为一些标准库类型，包括`string`和我们将要在第12章介绍的智能指针类型定义了`hash`。因此，我们可以直接定义关键字是内置类型（包括指针类型)、`string`还是智能指针类型的无序容器。.

但是，我们不能直接定义关键字类型为自定义类类型的无序容器。与容器不同，不能直接使用哈希模板，而必须提供我们自己的`hash`模板版本。我们将在16.5节(第626页)中介绍如何做到这一点。

我们不使用默认的 `hash`，而是使用另一种方法，类似于为有序容器重载关键字类型的默认比较操作。为了能将`Sale_data`用作关键字，我们需要提供函数来替代`==`运算符和`哈希值计算函数`。我们从定义这些重载函数开始:

size_t hasher (const Sales_data &sd)
    {
        
    	return hash<string>()(sd.isbn());
    }
    bool eqOp (const Sales_data &lhs, const Sales_data &rhs)
    {
        
    	return lhs.isbn() == rhs.isbn();
    }

我们的`hasher`函数使用一个标准库`hash`类型对象来计算ISBN成员的哈希值,该`hash`类型建立在`string` 类型之上。类似的，`eqOp`函数通过比较ISBN号来比较两个`sales_data`。

我们使用这些函数来定义一个`unordered_multiset`

using SD_multiset = unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>;
    //参数是桶大小、哈希函数指针和相等性判断运算符指针
    SD_multiset bookstore(42, hasher, eqOp);

为了简化 `bookstore`的定义，首先为`unordered_multiset`定义了一个类型别名，此集合的哈希和相等性判断操作与`hasher`和`eqOp` 函数有着相同的类型。通过使用这种类型，在定义`bookstore`时可以将我们希望它使用的函数的指针传递给它。

如果我们的类定义了`==`运算符，则可以只重载哈希函数:

//使用FooHash生成哈希值;Foo必须有==运算符
    unordered_set<Foo, decltype(FooHash)*> fooSet(10, FooHash);

注：仅供学习参考，如有不足，欢迎指正！

[6a40ad753ca94921be40c43125eb1143.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/562d4877ebe14b0b8505f71481b16066.png
[5a5b681aadb74a8187fbdc1696951aef.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/60ad7d573adb4977b71c0070e46ca0e2.png
[a148ee53fa2445c3a1d5289876da8616.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/5a3f794b0537448fac85d3ce959a3eae.png
[9.2]: https://blog.csdn.net/weixin_43412762/article/details/130079228
[809f83fc70d043f3be07b045064af9d5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/94aca5ea7c70435592eff9bbb23a7921.png
[7a64c9eee2fe4bcc802b21b80084dc7a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/593ad81c52474119813693e6fb1751cf.png
[765160ddaa8d477db176f2e098217556.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/418bf5b713e84a5a93727ccd4991b454.png
[3e29a3937600468a964ffbb6a01227d0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/efe96f07ff974d1794d8271ba9da2bfa.png
[1275c0c1d5404992b25148e9d0ad7b81.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/50858f6076554882b890921c5b5d5993.png
[a9834edc246c4248be7bf0038347c2c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/1c7be442583b47f8b90341c7948bb945.png
[3eb5f7451c794104b8c71005fdc1cf0a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/f6724331434b4e48916cc70362c4fde2.png
[Link 1]: https://blog.csdn.net/weixin_43412762/article/details/130259361
[27c272aa050b48a6a279d5dc6a1004b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/324e97befc36450086ef9e31370948b4.png