关联容器操作 | 彩潭有鲤的札记

type

status

date

slug

summary

关联容器迭代器

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

map 的 value_type是一个 pair 对象，可以改变second数据成员，而不能改变first成员

set 的迭代器是 const 的

虽然 set同时定义了iterator和const_iterator类型，但两种迭代器都只允许只读访问set中的元素。类似map，set中的关键字也是const 的。

遍历关联容器

map 和 set 都支持begin和end操作。使用迭代器遍历 map、multimap、set 或 multiset 时，迭代器按关键字升序遍历元素。

关联容器和算法

通常是不将通用算法用于关联容器的。关联容器的 key 是 const 的意味着不能将关联容器的迭代器传递给那些需要修改元素或者对容器元素进行重排序的算法。这些算法需要对元素进行写操作。而 set 类型中的元素是 const 的，map的元素是pair类型，其first 成员是const的。

关联容器可以用于读元素的算法。然而，这些算法中的大部分都适用于搜索顺序容器。由于关联容器中的元素可以通过其键快速被查找到，使用通用搜索算法几乎总是错误的想法。每个关联容器都定义了名为 find 的成员函数，可以用于直接从关联容器中查找与给定 key 相关联的元素。也可以使用通用 find 算法来查找元素，但是算法执行的是顺序搜索。使用 find 成员函数明显是更加快的方式。

在实践中，如果真的将关联容器用于通用算法，要么将其用于源序列要么用于目的位置。如，调用通用 copy 算法从一个关联容器拷贝元素到另一个序列中。类似的，可以调用 inserter 来绑定一个插入迭代器到关联容器上。使用inserter，可以将关联容器作为另外一个算法的目的位置。

添加元素

使用 insert 成员可以向关联容器中添加一个元素或一个元素范围。由于map和set包含不重复的关键字，因此向 map 和 set 中添加已存在的元素对容器没有影响：

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

关联容器的 insert 操作：

insert 或 emplace 的返回值依赖于容器类型和参数：

对于不包含重复关键字的容器，添加单一元素的 insert 和 emplace 版本返回一个 pair，表示操作是否成功。pair 的 first 成员是一个迭代器，指向具有给定关键字的元素；second 成员是一个 bool 值。如果关键字已在容器中，则 insert 直接返回，bool 值为 false。如果关键字不存在，元素会被添加至容器中，bool 值为 true。

对于允许包含重复关键字的容器，添加单一元素的 insert 和 emplace 版本返回指向新元素的迭代器。

添加元素到 map 中

当给 map 插入元素时，需要记住元素的类型是 pair。通常对于想要插入的数据，并没有现成的 pair对象。相反，可以在insert的参数中创建一个新的 pair 对象：

在新标准下创建 pair 最简单的方式是使用括弧初始化于参数列表。作为另外一种选择，也可以调用 make_pair 或者显式构建 pair。最后一个 insert 中的参数：

构建一个合适的pair类型的新对象用于插入到map中去

检查 insert 的返回值

insert 或者 emplace 的返回值将根据容器类型和参数的不同而不同。对于 key 是唯一的容器，insert和emplace的添加一个元素的版本将返回一个 pair 对象用于判断插入是否发生。pair 的 first 成员是一个与给定 key 关联的元素迭代器；second 成员是一个 bool 值用于指示元素是否被插入，或者是否已经存在。如果键已经存在于容器中，那么 insert 将不做任何事，并且返回值的 bool 部分是 false，如果键不存在，那么元素将被插入并且 bool 是 true。

添加元素到 multiset 和 multimap 中

有时希望一个 key 可以关联多个值，比如希望映射作者到其所写的书的名字上。在这种情况下，一个作者可能有个条目，所以使用 multimap 而不是 map。用于multi容器中的key不需要是唯一的，在这些键上insert总是插入元素：

对于允许多个key的容器，只插入一个元素的insert操作将返回新元素的迭代器。没有必要返回bool，因为insert总是添加新的元素

删除元素

关联容器的删除操作：

与顺序容器不同，关联容器提供了一个额外的 erase 操作。它接受一个 key_type 参数，删除所有匹配给定关键字的元素（如果存在），返回实际删除的元素数量。

对于不包含重复关键字的容器，erase 的返回值总是1或0。若返回值为0，则表示想要删除的元素并不在容器中。

map的下标操作

map 和unordered_map 容器提供了一个下标运算符和一个对应的at函数。set类型不支持下标，因为set中没有与关键字相关联的“值”。元素本身就是关键字，因此“获取与一个关键字相关联的值”的操作就没有意义了。不能对一个multimap或一个unordered_multimap进行下标操作，因为这些容器中可能有多个值与一个关键字相关联。

由于下标运算符可能向容器中添加元素，所以只能对非 const 的 map 使用下标操作。

对 map 进行下标操作时，返回的是 mapped_type 类型的对象；解引用 map 迭代器时，返回的是 value_type 类型的对象。

map 和 unordered_map 的下标操作：

与别的下标操作符一样，map 的下标取一个索引（键 key）然后提取出与这个键关联的值。然而，与别的下标操作符不一样的是，如果键不存在，一个新的元素将被创建出来与这个 key 关联并且插入到map中去。关联的值是值初始化的。

注：map 的下标运算与数组和 vector 的下标操作有非常大的不同：使用不存在于容器中的 key，将导致与之关联的元素添加到map 中。

使用下标操作返回的值

map的下标操作与别的下标操作符的不同之处在于其返回值。通常，对迭代器进行解引用得到的类型与下标操作符得到的类型是一样的。但对于 map 来说是不成立的：当对 map 进行下标运算时，得到一个 mapped_type 类型的对象；当解引用map的迭代器时，得到一个 value_type 类型的对象。

与别的下标运算一样的是，map的下标运算返回一个左值。由于返回的值是左值，对元素进行读或写：

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

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

访问元素

关联容器提供了许多中方式来查找一个给定的元素。使用哪个操作取决于我们尝试解决什么样的问题。如果只关心一个特定的元素是否在容器中，最好是使用find。对于键是唯一的容器来说，使用 find 或者 count 都是一样的。然而，对于具有multi键的容器来说，count所做的工作更多：如果一个元素是存在的，它依然必须对有多少个元素具有相同的键进行计数。如果不需要计数，那么最好是使用 find：

关联容器的查找操作：

使用 find 替换 map 的下标

对于 map 和 unordered_map 类型，下标操作符是最简单的获取一个值的方式。然而，使用下标有一个重要的副作用：如果 key 当时不在 map 中，那么下标操作会插入一个与这个 key相关联的元素。这个行为是否正确取决于我们的期望。

有时我们仅仅只是想知道一个给定的 key 是否在 map 中而不想改变这个关联容器。就不能用下标操作符来确认元素是否包含在容器中，这是由于下标操作符会在键不在容器中时插入一个新的与之相关的元素。在这种情况下，应该使用 find 函数：

在 multimap 和 multiset 中查找元素

在键是唯一的关联容器中查找一个元素是十分简单的——元素要么在要么不在容器中。对于允许多个相同的键存在的容器，这个过程就更为复杂了：与给定 key 关联的元素可能多个。当 multimap 或者 multiset 有多个与给定 key 关联的元素时，这些元素在容器中是相邻存储的。如上面提到的作者和标题之间的 multimap，我们想要打印跟特定作者关联的所有书名，至少有三种方式来解决这个问题，最简单而明显的方式使用 find 和 count：

find 返回与给定 key 关联的第一个元素的迭代器。标准库保证迭代 multimap 或 multiset 将顺序返回与给定键关联的所有元素。

迭代器方式的解决方案

另一种选择是使用 lower_bound 和 upper_bound 来解决问题。

lower_bound 和 upper_bound 操作都接受一个关键字，返回一个迭代器。如果关键字在容器中，lower_bound 返回的迭代器会指向第一个匹配给定关键字的元素，而 upper_bound 返回的迭代器则指向最后一个匹配元素之后的位置。如果关键字不在 multimap 中，则 lower_bound 和 upper_bound 会返回相等的迭代器，指向一个不影响排序的关键字插入位置。因此用相同的关键字调用 lower_bound 和 upper_bound 会得到一个迭代器范围，表示所有具有该关键字的元素范围。

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

lower_bound 和 upper_bound 有可能返回尾后迭代器。如果查找的元素具有容器中最大的关键字，则 upper_bound 返回尾后迭代器。如果关键字不存在，且大于容器中任何关键字，则 lower_bound 也返回尾后迭代器。

如果 lower_bound 和 upper_bound 返回相同的迭代器，则给定关键字不在容器中。

`equal_range` 函数

剩下的解决方案是最直接的：相较于调用 upper_bound 和 lower_bound，可以调用 equal_range

equal_range 操作接受一个关键字，返回一个迭代器 pair。若关键字存在，则第一个迭代器指向第一个匹配关键字的元素，第二个迭代器指向最后一个匹配元素之后的位置。若关键字不存在，则两个迭代器都指向一个不影响排序的关键字插入位置。

equal_range的返回值 pair 中的 first 成员包含的迭代器与 lower_bound的返回值一样，second 成员与 upper_bound函数的返回值一样。因此，在这个程序中，pos.first与 beg是一样的，pos.second与 end是一样的。