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

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

关联容器支持高效的关键字查找和访问。两个主要的关联容器类别是map和set。map中的元素是一些关键字----值对：关键字起到索引的作用，值表示与索引相关联的数据。set中每个元素只包括一个关键字；set支持高效的关键字查询操作----检查一个给定关键字是否在set中。

标准库提供8个关联容器：

类型

说明

按关键字有序保存元素

关联数组；保存关键字---值对

关键字即值，即保存关键字的容器

multimap

关键字可重复出现的map

multiset

关键字可重复出现的set

无序集合

unordered_map

用哈希函数组织的map

unordered_set

用哈希函数组织的set

unordered_multimap

哈希组织的map；关键字可以重复出现

unordered_multiset

哈希组织的set；关键字可以重复出现

这8个容器间的不同体现在3个维度上：每个容器（1）或者是一个set，或者是一个map；（2）或者规定不重复的关键字，或者允许重复关键字；（3）按次序保存元素，或无序保存。允许重复关键字的容器的名字中都包括词组multi；不保持关键字按次序存储的容器的名字都以句子unordered开头。

类型map和multimap定义在头文件map中；set和multiset定义在头文件set中；无序容器则定义在头文件unordered_map和unordered_set中。

二、关联容器概述

关联容器不支持排序容器的位置相关的操作，例如push_front或push_back。原因是关联容器中元素是按照关键字存储的，这些操作对关联容器没有意义。而且，关联容器也不支持构造函数或插入操作很多接受一个元素值和一个数量值的操作。

除了与排序容器相同的操作之外，关联容器还支持一些顺序容器不支持的操作和种类别名。此外，无序容器还提供一些拿来调整哈希性能的操作。

关联容器的迭代器时双向的。

1、定义关联容器

在新标准下，我们可以对关联容器进行值初始化：

 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 
12 
13 int main()
14 {
15     std::map<std::string, std::size_t> word_count; // 空容器
16     std::set<std::string> exclude = { "aa", "bb", "cc" }; // 列表初始化
17     std::map<std::string, std::string> authors = {
18         { "aa", "bb" },
19         { "cc", "dd" },
20         { "ee", "ff" }
21     };
22     return 0;
23 }

View Code

2、关键字类型的要求

对于有序容器----map、set、multimap、multiset，关键字类型需要定义元素非常的方式。默认状况下，标准库使用关键字类型的<运算符来非常两个关键字。

1）有序容器的关键字类型

可以提供自己定义的操作来替代关键字上的<运算符。所提供的操作需要在关键字类型上定义一个严格弱序。可以将严格弱序看作“小于等于”，虽然实际定义的操作或许是一个复杂的变量。无论我们如何定义非常函数，它需要具有如下基本性质：

a、两个关键字不能同时“小于等于”对方；如果k1“小于等于”k2，那么k2绝不能“小于等于”k1。

b、如果k1“小于等于”k2，且k2“小于等于”k3，那么k1必须“小于等于”k3。

c、如果存在两个关键字，任何一个都不“小于等于”另一个，那么我们称这两个关键字是“等价”的。如果k1“等价于”k2，且k2“等价于”k3，那么k1必须“等价于”k3。

如果两个关键字是等价的，那么容器将他们视作相等来处理。

注意：如果一个类型定义了“行为正常”的<运算符，则它可以用作关键字类型。

2）使用关键字类型的非常操作

用来组织一个容器中元素的操作的类别也有该容器种类的一部分。为了选定使用自定义的操作，必须在定义关联容器类别时提供此操作的类别。用尖括号指出要定义哪种种类的容器，自定义的操作种类（应该是一种函数指针类型）必须在尖括号中紧跟着元素类型给出。

在尖括号中发生的每个类型，就无非是一个类型而已。当我们建立一个容器（对象）时，才会以构造函数参数的方式提供真正的非常操作（其类别应当与尖括号中选定的类别相吻合），提供的是非常操作的指针。

 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 
12 bool comp(const std::string &s1, const std::string &s2)
13 {
14     return s1.size() < s2.size();
15 }
16 int main()
17 {
18     std::map<std::string, int, decltype(comp)*> mp(comp);
19     mp["abc"] = 1;
20     mp["a"] = 2;
21     mp["qaq"] = 3;
22     mp["bb"] = 4;
23     for (auto iter = mp.begin(); iter != mp.end(); ++iter)
24     {
25         std::cout << iter->first << " " << iter->second << std::endl;
26     }
27     return 0;
28 }

View Code

3、pair类型

pair定义在头文件utility中。一个pair保存两个数据成员，分别命名为first和second。类似容器，pair是一个用来生成特定种类的模版。当建立一个pair时，我们应该提供两个类型名，pair的数据成员将具备的类别。两个类型不规定一样。

pair上的操作：

操作

说明

pair<T1, T2> p;

p是一个pair，两个类型分别为T1和T2的成员都进行了值初始化

pair<T1, T2> p(v1, v2);

p是一个成员类型为T1和T2的pair；first和second分别用v1和v2进行初始化

pair<T1, T2> p = {v1, v2};

等价于p(v1, v2)

make_pair(v1, v2)

返回一个用v1和v2初始化的pair。pair的类型从v1和v2的类型判断出来

p.first

返回p的名为first的公有数据成员

p.second

返回p的名为second的公有数据成员

p1 relop p2

关系运算符（<、>、<=、>=）按字典序定义：例如，当p1.first<p2.first或!(p2.first<p1.first)&&p1.second<p2.second成立时，p1<p2为true。

关系运算符利用元素的<运算符来实现

p1==p2

当first和second成员分别相同时，两个pair分别相同。相等性利用元素的==运算符实现

p1!=p2

1）创建pair对象的变量

在新标准下，我们可以对返回值进行列表初始化：

 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 std::pair<std::string, int> func()
14 {
15     return{ "QAQ", 233 };
16 }
17 int main()
18 {
19     auto p = func();
20     std::cout << p.first << ", " << p.second << std::endl;
21     return 0;
22 }

View Code

三、关联容器操作

关联容器额外的类别别名：

类型别名

说明

key_type

此容器类别的关键字类型

mapped_type

每个关键字关联的类别：只适用于map类型（各种map）

value_type

对于set，与key_type相同。

对于map，为pair<const key_type, mapped_type>

对于set类型，key_type和value_type是一样的；set中保存的值就是关键字。在一个map中，元素是关键字----值对。即，每个元素是一个pair对象，包含一个关键字和一个关联的值。由于我们不能改变一个元素的关键字，因此很多pair的关键字部分是const的。我们使用作用域运算符提取一个类型的成员。

 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 int main()
14 {
15     std::set<std::string>::value_type v1; // v1是一个string
16     std::set<std::string>::key_type v2; // v2是一个string
17     std::map<std::string, int>::value_type v3; // v3是一个pair<const string, int>
18     std::map<std::string, int>::key_type v4; // v4是一个string
19     std::map<std::string, int>::mapped_type v5; // v5是一个int
20     return 0;
21 }

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