C++关联容器1——map，multimap，set，multiset介绍，pair类型

关联容器

使用关联容器

使用map

使用set

关联容器概述

定义关联容器

初始化multimap或multiset

关键字类型的要求

有序容器的关键字类型

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

pair 类型

创建pair 对象的函数

关联容器

关联容器支持高效的关键字查找和访问。

两个主要的关联容器（associative-container)类型是map和set。

map中的元素是一些关键字一值（key-value）对：关键字起到索引的作用，值则表示与索引相关联的数据。

set 中每个元素只包含一个关键字；set 支持高效的关键字查询操作——检查一个给定关键字是否在set中。

例如，在某些文本处理过程中，可以用一个set 来保存想要忽略的单词。字典则是一个很好的使用map的例子：可以将单词作为关键字，将单词释义作为值。

标准库提供8个关联容器

关联容器类型——按关键字有序保存元素
map	关联数组；保存关键字-值对
set	关键字即值，即只保存关键字的容器
multimap	关键字可重复出现的map
multiset	关键字可重复出现的set

关联容器类型——无序集合
unordered_map	用哈希函数组织的map
unordered_set	用哈希函数组织的set
unordered_multimap	哈希组织的map；关键字可以重复出现
unordered _multiset	哈希组织的set；关键字可以重复出现

这8个容器间的不同体现在三个维度上;

每个容器

或者是一个set，或者是一个map；
或者要求不重复的关键字，或者允许重复关键字；
按顺序保存元素，或无序保存。

允许重复关键字的容器的名字中都包含单词multi；不保持关键字按顺序存储的容器的名字都以单词unordered开头。

因此一个 unordered_multi_set是一个允许重复关键字，元素无序保存的集合，而一个set则是一个要求不重复关键字，有序存储的集合。无序容器使用哈希函数来组织元素，

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

使用关联容器

虽然大多数程序员都熟悉诸如vector和1ist这样的数据结构，但他们中很多人从未使用过关联数据结构。在学习标准库关联容器类型的详细内容之前，我们首先来看一个如何使用这类容器的例子，这对后续学习很有帮助。

map 是关键字——值对的集合。

例如，可以将一个人的名字作为关键字，将其电话号码作为值。我们称这样的数据结构为“将名字映射到电话号码”。

map类型通常被称为关联数组（associative array）。关联数组与“正常”数组类似，不同之处在于其下标不必是整数。我们通过一个关键字而不是位置来查找值。也就是说，我们把关键字当成下标来用。给定一个名字到电话号码的map，我们可以使用一个人的名字作为下标来获取此人的电话号码。

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

使用map

#include <iostream>  
#include <map>  
#include <string>  
  
int main() {  
    // 创建一个空的map，键是string类型，值是int类型  
    std::map<std::string, int> myMap;  
  
    // 插入元素  
    myMap["apple"] = 1;  
    myMap["banana"] = 2;  
    myMap["cherry"] = 3;  
  
    // 访问元素
    //把关键字当成下标来用  
    std::cout << "The number of apples is: " << myMap["apple"] << std::endl;  
  
    // 使用迭代器遍历map  
    for (std::map<std::string, int>::iterator it = myMap.begin(); it != myMap.end(); ++it) {  
        std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;  
    }  
  
    // 使用C++11的基于范围的for循环遍历map  
    for (const auto& pair : myMap) {  
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;  
    }  
  
    // 查找元素  
    if (myMap.find("banana") != myMap.end()) {  
        std::cout << "Banana found in the map!" << std::endl;  
    }  
  
    // 修改元素  
    myMap["apple"] = 10;  
  
    // 删除元素  
    myMap.erase("banana");  
  
    // 检查map是否为空  
    if (myMap.empty()) {  
        std::cout << "The map is empty." << std::endl;  
    } else {  
        std::cout << "The map is not empty." << std::endl;  
    }  
  
    return 0;  
}

这个示例展示了如何使用std::map执行基本的操作，如插入、访问、遍历、查找、修改和删除元素。注意，由于map中的键是唯一的，如果你尝试插入具有相同键的新元素，该键的值将被新值覆盖。

类似顺序容器，关联容器也是模板。

为了定义一个map，我们必须指定关键字和值的类型。

在此程序中，map保存的每个元素中，关键字是string类型，值是int类型。

当从map中提取一个元素时，会得到一个pair类型的对象，我们将在下面介绍它。

简单来说，pair是一个模板类型，保存两个名为first 和secona的（公有）数据成员。

map所便用的pair用first 成员保存关键字，用second成员保存对应的值。

因此，输出语句的效果是打印每个单词及其关联的计数器。

使用set

在C++中，std::set是一个关联容器，它包含唯一的元素，这些元素默认按照升序排列。std::set中的元素是唯一的，并且总是按键（即元素的值）排序。以下是一个使用std::set的简单示例：

#include <iostream>  
#include <set>  
#include <string>  
  
int main() {  
    // 创建一个空的set，元素类型为string  
    std::set<std::string> mySet;  
  
    // 插入元素  
    mySet.insert("apple");  
    mySet.insert("banana");  
    mySet.insert("cherry");  
  
    // 尝试插入重复的元素，将不会改变set  
    mySet.insert("apple"); // 这个操作是无效的，因为"apple"已经在set中  
  
    // 访问元素（注意：set不提供直接通过索引访问元素的功能）  
    // 但可以遍历所有元素  
    for (const auto& element : mySet) {  
        std::cout << element << ' ';  
    }  
    std::cout << std::endl;  
  
    // 查找元素  
    if (mySet.find("banana") != mySet.end()) {  
        std::cout << "Banana found in the set!" << std::endl;  
    }  
  
    // 删除元素  
    mySet.erase("banana");  
  
    // 再次遍历set以验证元素已被删除  
    for (const auto& element : mySet) {  
        std::cout << element << ' ';  
    }  
    std::cout << std::endl;  
  
    // 检查set是否为空  
    if (mySet.empty()) {  
        std::cout << "The set is empty." << std::endl;  
    } else {  
        std::cout << "The set is not empty." << std::endl;  
    }  
  
    // 获取set的大小  
    std::cout << "The size of the set is: " << mySet.size() << std::endl;  
  
    return 0;  
}

这个示例展示了如何使用std::set执行基本的操作，如插入、遍历、查找、删除元素以及检查set是否为空。由于std::set中的元素是唯一的，因此插入重复的元素是无效的。另外，std::set不提供通过索引直接访问元素的功能，因为它是基于红黑树实现的，元素在内存中的位置可能会随着插入和删除操作而变化。相反，你需要使用迭代器来遍历std::set中的元素。

关联容器概述

关联容器（有序的和无序的）都支持http://t.csdnimg.cn/moE16 中介绍的普通容器操作。

关联容器不支持顺序容器的位置相关的操作，例如push_front或pushback。

原因是关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义。而且，关联容器也不支持构造函数或插入操作这些接受一个元素值和一个数量值的操作。

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

关联容器的迭代器都是双向的。

定义关联容器

当定义一个map时，必须既指明关键字类型又指明值类型；
而定义一个set时，只需指明关键字类型，因为set中没有值。

每个关联容器都定义了一个默认构造函数，它创建一个指定类型的空容器。

我们也可以将关联容器初始化为另一个同类型容器的拷贝，或是从一个值范围来初始化关联容器，只要这些值可以转化为容器所需类型就可以。

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

map<string, size_t> word count；//空容器
//列表初始化
set<string> exclude =
{"the","but","and","or","an","a",
"The"，"But","And","Or","An","A"};


map<string, string> authors = { {"Joyce","James"},
                                {"Austen","Jane"},
                                {"Dickens","Charles"}};

//三个元素；authors将姓映射为名

与以往一样，初始化器必须能转换为容器中元素的类型。对于set，元素类型就是关键字类型。

当初始化一个map时，必须提供关键字类型和值类型。我们将每个关键字一值对包围在花括号中：

{key, value}

来指出它们一起构成了map中的一个元素。在每个花括号中，关键字是第一个元素，值是第二个。因此，authors将姓映射到名，初始化后它包含三个元素。

初始化multimap或multiset

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

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

例如，在我们用来统计单词数量的map中，每个单词只能有一个元素。另一方面，在一个词典中，一个特定单词则可具有多个与之关联的词义。

下面的例子展示了具有唯一关键字的容器与允许重复关键字的容器之间的区别；首先，我们将创建一个名为ivec的保存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

即使我们用整个ivec 容器来初始化iset，它也只含有10个元素：对应ivec中每个不同的元素。另一方面，miset有20个元素，与ivec中的元素数量一样多。

关键字类型的要求

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

对于有序容器——map、multimap、set以及multiset，关键字类型必须定义元素比较的方法。

默认情况下，标准库使用关键字类型的<运算符来比较两个关键字。

在集合类型中，关键字类型就是元素类型；在映射类型中，关键字类型是元素的第一部分的类型。

 std::map<std::string, int> myMap;

这个的关键字是string

传递给排序算法的可调用对象必须满足与关联容器中关键字一样的类型要求

有序容器的关键字类型

可以向一个算法提供我们自己定义的比较操作，与之类似，也可以提供自己定义的操作来代替关键字上的<运算符。

所提供的操作必须在关键字类型上定义一个严格弱序。

可以将严格弱序看作“小于等于”，虽然实际定义的操作可能是一个复杂的函数。

无论我们怎样定义比较函数，它必须具备如下基本性质：

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

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

在实际编程中，重要的是，如果一个类型定义了“行为正常”的<运算符，则它可以用作关键字类型。

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

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

为了指定使用自定义的操作，必须在定义关联容器类型时提供此操作的类型。

如前所述，用尖括号指出要定义哪种类型的容器，自定义的操作类型必须在尖括号中紧跟着元素类型给出。

在尖括号中出现的每个类型，就仅仅是一个类型而已。

当我们创建一个容器（对象）时，才会以构造函数参数的形式提供真正的比较操作（其类型必须与在尖括号中指定的类型相吻合）。

在C++中，如果你希望为关联容器（如std::map、std::set、std::multimap、std::multiset）指定自定义的操作，比如自定义比较函数或函数对象（仿函数），你可以在定义容器类型时作为第三个模板参数来提供。

这个第三个参数通常是一个可调用对象，它决定了容器中的元素如何进行比较以决定排序和唯一性。

#include <iostream>  
#include <set>  
#include <functional> // 为了使用 std::less 或 std::greater  
  
// 自定义比较函数  
struct MyLess {  
    bool operator()(const int& a, const int& b) const {  
        return a > b; // 注意这里我们使用了大于操作符，使得set中的元素按降序排列  
    }  
};  
  
int main() {  
    // 使用自定义比较函数的std::set  
    std::set<int, MyLess> mySet;  
  
    // 插入元素  
    mySet.insert(1);  
    mySet.insert(3);  
    mySet.insert(2);  
  
    // 遍历set  
    for (const auto& element : mySet) {  
        std::cout << element << ' ';  
    }  
    std::cout << std::endl;  
  
    // 输出：因为使用了自定义的比较函数MyLess，set中的元素会按降序排列  
    // 输出：3 2 1  
  
    return 0;  
}

在这个例子中，我们定义了一个名为MyLess的结构体，它重载了operator()以提供自定义的比较逻辑。然后，在定义std::set<int, MyLess>时，我们将MyLess作为比较类型的实例传递给std::set。因此，mySet中的元素会根据MyLess的比较逻辑进行排序和检查唯一性。在这个例子中，我们使用了大于操作符，所以std::set中的元素会按降序排列。

注意，你不需要总是从头开始编写自定义比较函数。C++标准库已经提供了std::less和std::greater等预定义的仿函数，你可以直接使用它们，或者将它们作为基础来编写更复杂的比较逻辑。例如，你可以通过std::greater<int>直接指定降序排列的比较函数。

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的默认构造函数对数据成员进行值初始化。

因此，anon是一个包含两个空string的pair,line 保存一个空string 和一个空vector。wordcount中的size_t成员值为0，而string成员被初始化为空。

我们也可以为每个成员提供初始化器：

pair<string, string> author{"James", "Joyce"};

这条语句创建一个名为author的pair，两个成员被初始化为"James"和"Joyce"。

与其他标准库类型不同，pair的数据成员是public的。

两个成员分别命名为first和second。我们用普通的成员访问符号来访问它们

在C++中，std::pair是一个模板类，用于将两个可能不同类型的值组合成一个单一的实体。这个类有两个公共数据成员，分别命名为first和second，你可以使用点运算符（.）或箭头运算符（->，如果pair是指针的话）来访问它们。

下面是一个简单的例子，展示了如何创建std::pair并访问其first和second成员：

#include <iostream>  
#include <utility> // 包含std::pair  
  
int main() {  
    // 创建一个std::pair，其中first是int类型，second是double类型  
    std::pair<int, double> myPair = {42, 3.14159};  
  
    // 使用点运算符访问first和second成员  
    std::cout << "First: " << myPair.first << std::endl;  
    std::cout << "Second: " << myPair.second << std::endl;  
  
    // 如果你有一个指向std::pair的指针，你可以使用箭头运算符  
    std::pair<int, double>* ptrToPair = &myPair;  
    std::cout << "First (via pointer): " << ptrToPair->first << std::endl;  
    std::cout << "Second (via pointer): " << ptrToPair->second << std::endl;  
  
    return 0;  
}

pair 上的操作
pair<Tl, T2> p;	p是一个pair，两个类型分别为T1和T2的成员都进行了值初始化
pair<Tl, T2> p(vl, v2)	p是一个成员类型为T1和 T2的pair; first和second成员分别用v1和v2进行初始化
pair<Tl,T2>p ={vl,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<pl.first) && p1.second<p2.second成立时，p1<p2为true。关系运算利用元素的<运算符来实现
p1 != p2	当first和second成员分别相等时，两个pair 相等。相等性判断利用元素的==运算符实现

创建pair 对象的函数

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

#include <iostream>  
#include <utility> // 包含std::pair  
  
// 函数返回一个std::pair<int, std::string>  
std::pair<int, std::string> getPair() {  
    // 使用列表初始化来初始化并返回pair  
    return {42, "answer"};  
}  
  
int main() {  
    // 调用函数并接收返回的pair  
    std::pair<int, std::string> result = getPair();  
  
    // 访问并打印pair的成员  
    std::cout << "First: " << result.first << std::endl;  
    std::cout << "Second: " << result.second << std::endl;  
  
    return 0;  
}

在较早的C++版本中，不允许用花括号包围的初始化器来返回pair这种类型的对象，必须显式构造返回值：

#include <iostream>  
#include <utility> // 包含std::pair  
  
// 函数显式构造并返回一个std::pair<int, std::string>  
std::pair<int, std::string> getPairExplicit() {  
    // 显式调用std::pair的构造函数  
    return std::pair<int, std::string>(42, "answer");  
}

我们还可以用make_pair来生成pair对象，pair的两个类型来自于make _pair的参数：

#include <iostream>  
#include <utility> // 包含std::pair和std::make_pair  
  
// 函数使用std::make_pair来返回一个std::pair<int, std::string>  
std::pair<int, std::string> getPairWithMakePair() {  
    // 使用std::make_pair来创建pair对象  
    return std::make_pair(42, "answer");  
}