关联容器----关联容器概述，关联容器操作，无序容器(3)

有时只是想知道一个元素是否已在map中，但在不存在时并不想添加元素。在这些状况下，就不能使用数组运算符。

5、访问元素

在一个关联容器中查找元素的操作：

lower_bound和upper_bound不适用于无序容器。

下标和at操作只适用于非const的的map和unordered_map。

操作

说明

c.find(k)

返回一个迭代器，指向一个关键字为k的元素，若k不在容器中，则返回尾后迭代器

c.count(k)

返回关键字等于k的元素的数目。对于不允许重复关键字的容器，返回值永远是0或1

c.lower_bound(k)

返回一个迭代器，指向第一个关键字不小于k的元素

c.upper_bound(k)

返回一个迭代器，指向第一个关键字大于k的元素

c.equal_range(k)

返回一个迭代器pair，表示关键字等于k的元素的范围。若k不存在，pair的两个成员均等于c.end()

有序容器的迭代器通过关键字有序访问容器中的元素。无论在有序容器中而是在无序容器中，具有同样关键字的元素都是相邻存储的。

四、无序容器

新标准定义了4个无序关联容器。这些容器不是使用比较运算符来组织元素，而是使用一个哈希函数和关键字类型的==运算符。在关键字类型的元素没有明显的有序关系的状况下，无序容器时特别有用的。在这种应用中，维护元素的序代价比较高，此时无序容器也很有用。

1、使用无序容器

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

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

2、管理桶

无序容器在储存组织为一组桶，每个桶储存零个或多个元素。无序容器使用一个哈希函数将元素映射到桶。为了访问一个元素，容器首先计算元素的哈希值，它强调必须搜索什么桶。容器将带有一个特定哈希值的所有元素都存放在相似的桶中。如果容器允许重复关键字，所有带有同样关键字的元素也就会在同一个桶中。因此，无序容器的功耗依赖于哈希函数的品质和桶的总量和大小。

对于同样的参数，哈希函数必须总是产生同样的结果。理想状况下，哈希函数还能降每个特定的值映射到唯一的桶。但是，将不同关键字的元素映射到同样的桶只是允许的。当一个个桶保存多个元素时，需要排序搜索那些元素来查找我们想要的哪个。计算一个元素的哈希值和在桶中搜索一般都是很快的操作。但是，如果一个桶中保存了好多元素，那么查找一个特定元素就应该长期比较操作。

无序容器管理操作：

操作

说明

桶接口

c.bucket_count()

正在使用的桶数目

c.max_bucket_count()

容器能容纳的最多的桶的数量

c.bucket_size(n)

第n个桶中有多少个元素

c.bucket(k)

关键字为k的元素在那个桶中

桶迭代

local_iterator

可以用来访问桶中元素的迭代器类型

const_local_iterator

桶迭代器的const版本

c.begin(n), c.end(n)

桶n的首元素迭代器和尾后迭代器

c.cbegin(n),c.cend(n)

与前两个函数类似，但返回const_local_iterator

哈希策略

c.load_factor()

每个桶的平均元素总数，返回float值

c.max_load_factor()

c试图维护的平均桶大小，返回float值。c会在必须时添加新的桶，以使得load_factor<=max_load_factor

c.rehash(n)

重组存储，使得bucket_count>=n且bucket_count>size/max_load_factor

c.reserve(n)

重组存储，使得c可以存放n个元素且不必rehash

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

默认状况下，无序容器使用关键字类型的==运算符来非常元素，它还使用一个hash<key_type>类型的对象来生成每个元素的哈希值。标准库为内嵌类型（包括指针）提供了hash模板。还有一些标准库类型，包括string和智能指针类型定义了hash。因此我们可以直接定义关键字是内嵌类型、string还是智能指针类型的无序容器。

但是，我们不能直接定义关键字类型为自定义类型的无序容器。与容器不同，不能直接使用哈希模板，而应该提供我们自己的hash模板版本。

我们不使用默认的hash，而是使用此外一种方法，类似为有序容器重载关键字类型的非常操作。为了能降自定义类型用作关键字，我们应该提供变量来代替==运算符和哈希值计算数组。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <iterator>
 6 #include <functional>
 7 #include <map>
 8 #include <set>
 9 #include <unordered_map>
10 #include <unordered_set>
11 #include <utility>
12 
13 class Sale_data
14 {
15 public:
16     Sale_data() = default;
17     Sale_data(std::string _id) :id(_id){}
18     std::string id;
19 };
20 
21 std::size_t hasher(const Sale_data &sd)
22 {
23     return std::hash<std::string>()(sd.id);
24 }
25 
26 bool eqop(const Sale_data &sd1, const Sale_data &sd2)
27 {
28     return sd1.id == sd2.id;
29 }
30 
31 int main()
32 {
33     // 参数分别指桶大小、哈希函数指针、相等性判断函数指针
34     std::unordered_map<Sale_data, int, decltype(hasher)*, decltype(eqop)*> book(42, hasher, eqop);
35     // 如果类定义了==运算符，则可以只重载哈希函数
36     book.insert({ Sale_data("a"), 1 });
37     book.insert({ Sale_data("b"), 233 });
38     for (auto iter = book.begin(); iter != book.end(); ++iter)
39     {
40         std::cout << iter->first.id << "  " << iter->second << std::endl;
41     }
42     return 0;
43 }

View Code

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-124191-3.html