【STL八】关联容器

关联式容器，包括 map、multimap、set 以及 multiset 这 4 种容器。
关联容器和顺序容器有着根本的不同：关联容器中的元素是按关键字来保持和访问的。与之相对，顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的。

一、简介

• 关联式容器存储的元素，都是一个一个的“键值对”（ <key,value> ）;

如果已知目标元素的键的值，则直接通过该键就可以找到目标元素，而无需再通过遍历整个容器的方式。

• 序列式容器中存储的元素默认都是未经过排序的，而使用关联式容器存储的元素，默认会根据各元素的键值的大小做升序排序。
• 联式容器所具备的这些特性，归咎于 STL 标准库在实现该类型容器时，底层选用了 「红黑树」这种数据结构来组织和存储各个键值对。
• 关联容器实现能快速查找（ O(log n) 复杂度）的数据结构。

红黑树这种数据结构，我也不太懂，后面学习。

关联容器的主要优点是，它能很快找出一个具有某特定 value 的元素，因为它具备对数复杂度（logarithmic complexity），而任何循序列容器的复杂度是线性。因此，使用关联式容器，面对1000个元素，平均而言你将有10次而不是500次比较动作。然而它有一个缺点是，你不能直接改动元素的 value ，因为那会破坏元素的自动排序。

二、分类

• C++ STL 标准库提供了 4 种关联式容器，分别为 map、set、multimap、multiset.
• 你可以将set视为一种特殊的map：元素的value等同于key.。实际产品种所有这些关联式容器通常都由二叉树实现而成。（binary tree)

红黑树是一种特定类型的二叉树

三、生成键值对方法一：map[key] = value

• demo

#include<iostream>>
#include<map>
#include<string>
using namespace std;
int main()
{
    map<string, string> m;
    m["小b"] = "家在西安";
    m["小c"] = "家在濮阳";
    m["小a"] = "家在北京";

    for (map<string, string>::iterator ite = m.begin(); ite != m.end(); ++ite) {
        //输出各个元素中的键和值
        cout << ite->first << " => " << ite->second << '\n';
    }
    return 0;
}

输出

小a => 家在北京
小b => 家在西安
小c => 家在濮阳

四、生成键值对方法二：pair、make_pair

1、pair

std::pair可将两个value视为一个单元。

• 考虑到“键值对”并不是普通类型数据，C++ STL 标准库提供了 pair 类模板，其专门用来将 2 个普通元素 first 和 second创建成一个新元素<first, second>
  模板

template<
    class T1,
    class T2
> struct pair;

2、make_pair

make_pair() 构造 std::pair 对象，从参数类型推导目标类型。

• make_pair() 函数，其功能是生成一个 pair 对象。因此，当我们将 make_pair() 函数的返回值（是一个临时对象）作为参数传递给 pair() 构造函数时，其调用的是移动构造函数，而不是拷贝构造函数

template< class T1, class T2 >
std::pair<T1,T2> make_pair( T1 t, T2 u );
(C++11 前)
template< class T1, class T2 >
std::pair<V1,V2> make_pair( T1&& t, T2&& u );
(C++11 起)
(C++14 前)
template< class T1, class T2 >
constexpr std::pair<V1,V2> make_pair( T1&& t, T2&& u );
(C++14 起)

3、pair、make_pair() 头文件

#include <utility>  

4、demo

#include <iostream>
#include <utility>      // pair
#include <string>       // string
#include<map>
using namespace std;
int main() {
    // 调用构造函数 1，也就是默认构造函数
    pair <string, string> pair1;
    pair1.first = "小b";
    pair1.second = "家在西安";
    // 调用第 2 种构造函数
    pair <string, string> pair2("小c", "家在濮阳");
    // 调用拷贝构造函数
    pair <string, string> pair3(pair2);

    pair <string, string> pair4 = make_pair("小a", "家在北京");

    cout << "输出pair:" << endl;
    cout << "pair1: " << pair1.first << " " << pair1.second << endl;
    cout << "pair2: " << pair2.first << " " << pair2.second << endl;
    cout << "pair3: " << pair3.first << " " << pair3.second << endl;
    cout << "pair4: " << pair4.first << " " << pair4.second << endl<<endl;

    map<string, string> m;
    m.insert(pair1);
    m.insert(pair2);
    m.insert(pair4);
    m.insert(make_pair("小d", "没有家"));

    cout << "输出map:" << endl;
    for (auto ite = m.begin(); ite != m.end(); ite++)
    {
        cout << ite->first << ">" << ite->second << endl;
    }

    return 0;
}

• 输出

输出pair:
pair1: 小b 家在西安
pair2: 小c 家在濮阳
pair3: 小c 家在濮阳
pair4: 小a 家在北京

输出map:
小a>家在北京
小b>家在西安
小c>家在濮阳
小d>没有家

接下来，我们会分两篇文章分别详细的介绍下这四种关联容器。

参考
1、C++ STL 容器库 中文文档
2、STL教程：C++ STL快速入门
3、https://www.apiref.com/cpp-zh/cpp/header.html
4、https://en.cppreference.com/w/cpp/container