关联容器


类别: 容器	组件类型: 概念

描述

关联容器是一种可变大小的容器，它支持基于键高效地检索元素（值）。它支持插入和删除元素，但与序列不同的是，它没有提供在特定位置插入元素的机制。 [1]

与所有容器一样，关联容器中的元素类型为value_type。此外，关联容器中的每个元素都有一个类型为key_type的键。在某些关联容器中，简单关联容器，value_type和key_type是相同的：元素本身就是它们的键。在其他情况下，键是值的某个特定部分。由于元素是根据它们的键存储的，因此与每个元素关联的键必须是不可变的。在简单关联容器中，这意味着元素本身是不可变的，而在其他类型的关联容器（例如配对关联容器）中，元素本身是可变的，但元素中作为其键的部分不可修改。这意味着关联容器的值类型不是可赋值的。

关联容器的值类型不是可赋值的这一事实有一个重要的后果：关联容器不能拥有可变迭代器。这仅仅是因为可变迭代器（如平凡迭代器要求中定义的）必须允许赋值。也就是说，如果i是一个可变迭代器，并且t是i的值类型的一个对象，那么*i = t必须是一个有效的表达式。

在简单关联容器中，元素是键，元素是完全不可变的；嵌套类型iterator和const_iterator因此是相同的。然而，其他类型的关联容器确实具有可变元素，并且确实提供了可以通过它们修改元素的迭代器。例如，配对关联容器具有两个不同的嵌套类型iterator和const_iterator。即使在这种情况下，iterator也不是一个可变迭代器：如上所述，它不提供表达式*i = t。然而，可以通过这样的迭代器修改元素：例如，如果i是类型map<int, double>，那么(*i).second = 3是一个有效的表达式。

在某些关联容器中，唯一关联容器，保证没有两个元素具有相同的键。 [2] 在其他关联容器中，多重关联容器，允许存在多个具有相同键的元素。

对以下内容的细化

前向容器，默认可构造

关联类型

除了前向容器要求中定义的类型之外，还引入了另一种新类型。

键类型 X::key_type 与X::value_type关联的键的类型。请注意，键类型和值类型可能相同。

符号

`X`	关联容器的模型类型
`a`	类型为`X`
`t`	类型为`X::value_type`
`k`	类型为`X::key_type`
`p`, `q`	类型为`X::iterator`

定义

如果a是一个关联容器，那么p是a 中的有效迭代器，如果它是一个有效的迭代器，并且可以从a.begin().

如果a是一个关联容器，那么[p, q)是a 中的有效范围，如果[p, q)是一个有效范围，并且p是a.

中的有效迭代器

有效表达式

名称	表达式	返回类型
默认构造函数	X() X a;
擦除键	`a.erase(k)`	`size_type`
擦除元素	`a.erase(p)`	`void`
擦除范围	`a.erase(p, q)`	`void`
清除	`a.clear()`	`void`
查找	`a.find(k)`	`iterator`如果`a`是可变的，否则`const_iterator`
计数	`a.count(k)`	`size_type`
相等范围	`a.equal_range(k)`	`pair<iterator, iterator>`如果`a`是可变的，否则`pair<const_iterator, const_iterator>`.

表达式语义

名称	表达式	前置条件	语义	后置条件
默认构造函数	X() X a;		创建一个空容器。	容器的大小为`0`.
擦除键	`a.erase(k)`		销毁所有键与`k`相同的元素，并从`a`中删除它们。 [2] 返回值为擦除的元素数量，即`a.count(k)`.	`a.size()`减少了`a.count(k)`. `a`不包含键为`k`.
擦除元素	`a.erase(p)`	`p`的元素`a`.	是`p`中可解引用的迭代器`a`.	`a.size()`销毁由
擦除范围	`a.erase(p, q)`	`[p, q)`指向的元素，并将其从`a`.	中删除。减少了 1。`是`中的有效范围`a`.	`a.size()`销毁范围`i`[p,q)`中的元素，并将其从`.
清除	`a.clear()`		中删除。减少了从`到`
查找	`a.find(k)`		j`k`的距离。`等效于`a.erase(a.begin(), a.end())	返回一个指向键与`等效于`相同的元素的迭代器，或者返回`k`.
计数	`a.count(k)`		a.end()`a`，如果不存在这样的元素。`k`.
相等范围	`a.equal_range(k)`		返回值是`，或者返回值的键与`相同`返回`中键与`a`，如果不存在这样的元素。`k`相同的元素数量。`k`返回一个配对	P`，使得`和`[P.first, P.second)`是一个包含`a.count(k)`中所有元素的范围。 [3] 如果没有元素的键与`p`的元素`a`相同，则返回值是一个空范围。`p`之间的距离`返回`P.first`P.second`等于`k`.

。如果

，那么要么位于范围.

中，要么

*p的键与不同复杂度保证擦除键的平均复杂度最多为

O(log(size()) + count(k))位于范围.

擦除元素的平均复杂度为常数时间。

擦除范围的平均复杂度最多为

O(log(size()) + N)

，其中	N`p`和`q`是范围内元素的数量。`p`计数的平均复杂度最多为`q`查找的平均复杂度最多为对数时间。`[p, q)`相等范围的平均复杂度最多为对数时间。
不变量	连续存储

所有具有相同键的元素彼此相邻。也就是说，如果

multiset

hash_set

hash_multisetmapmultimap

hash_map

hash_multimap

注释

[1] 没有这种机制的原因是，元素在关联容器中的排列方式通常是类不变量；例如，排序关联容器中的元素始终按升序存储，而哈希关联容器中的元素始终根据哈希函数存储。允许任意选择元素的位置将毫无意义。 [2] 键不需要是相等可比较的：关联容器不一定使用