[C++]set和map的介绍及使用

    关于set和map的接口函数部分，只重点介绍一些相较于别的容器有特殊地方的接口，set和map的接口可以触类旁通。

一、概念

（一）、关联式容器

    **关联式容器****存储的元素是一个个的****键值对<key,value>**。**通过键（key）可以快速索引到其对应的value值。**关联容器可以快速查找、读取或者删除所存储的元素，同时该类型的容器插入元素的效率比序列容器（如vector）高。

（二）、键值对

    **键值对用来表示具有一一对应关系的一种结构，该结构中只包含两个成员变量key和value，key代表键值，value表示与key对应的信息，可以通过键值key快速索引到其对应的信息value**。比如说英汉词典，查询单词的中文释义就需要通过英文单词快速索引到中文释义，**这里的键key是英文单词，key的类型为string，key对应的信息value是中文释义，value的类型也为string，这样，英文单词和中文释义就构成了一个<string,string>的键值对。**

    键值对可以用**pair类**来表示，pair是C++的STL提供的一个类。pair - C++ Reference (cplusplus.com)https://legacy.cplusplus.com/reference/utility/pair/        **pair存储了公有的两个成员变量，一个叫做first，一个叫做second，可以在外部访问，这两个成员变量的类型通过用户指定。**我们可以用**pair的first存储键key，用second存储key对应的信息value。**

（三）、关联式容器的结构

    根据应用场景的不同，STL总共实现了两种不同结构的关联式容器：**树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。**这四种容器的共同点是：**使用平衡二叉搜索树(红黑树)作为其底层结果，容器中的元素是一个有序的序列，迭代器遍历得到的是一个有序的序列。**

二、set和multiset

（一）set

set - C++ Reference (cplusplus.com)https://legacy.cplusplus.com/reference/set/set/

set的简介

模板类型

**template < **

** class T, // set::key_type/value_type**

** class Compare = less<T>, // set::key_compare/value_compare**

** class Alloc = allocator<T> // set::allocator_type**

** >**

T：set存储的元素类型。

Compare：仿函数，用于提供元素之间的比较方法。

Alloc：空间配置器

1、set是按照特定次序存储的没有重复元素的容器。

2、在set中，一个元素value就对应其本身的值(value本身就是键key，类型为T)，并且每个元素在set中必须是不能重复的。set中元素的值在容器中不能被再次修改(元素的类型总是const类型)，但是可以从容器中插入或删除。

3、在内部，set中的元素总是按照其内部比较对象(类型为Compare)所指示的特定严格弱排序标准进行排序。

4、set容器在通过key访问单个元素时通常比unordered_set容器慢，但set迭代到的序列是有序的。

5、set通常以平衡二叉搜索树的形式实现。

set的接口

1、插入insert

    对于set的insert，**第一个（single element）和第三个（range）版本的插入最常用**，而中间的第二个（with hint）版本不是很常用，这个接口并不是在指定位置插入，而是在插入时提供一个接近最终插入的位置的迭代器，对插入元素时的效率进行优化，但这种优化效果并不总是显著的，因为用户提示不好，则会忽略用户的提示从头开始搜索插入位置进行插入，且红黑树的平衡性会影响搜索提示时的效率。

    注意到第一个（single element）版本的insert的返回值不是指向新插入位置的迭代器，而是**pair<iterator,bool>**类型。因为set中的元素都是唯一的，set不允许插入已经存在的元素，若插入的元素存在时，则插入失败，将返回一个**pair<iterator,bool>**的对象，**其first成员为指向set中现有元素位置的迭代器，second成员bool值为false表示插入失败**；**若插入的元素不存在，其first成员为指向新插入元素位置的迭代器，second成员bool值为true，表示插入成功。**

代码例子：

#include <iostream>
#include <set>
using namespace std;

int main()
{
    set<int> s;

    int arr[] = { 2,3,5,6,7,1,2,0,5};

    //将arr的元素依次插入到s中
    for (auto e : arr)
    {
        auto ret = s.insert(e);
        if (ret.second == false)//插入失败
        {
            cout << *(ret.first) << "已存在，插入失败。" << endl;
        }
    }

    //打印s的元素
    for (auto e : s)
    {
        cout << e << " ";
    }
    
    return 0;
}

**运行结果： **

2已存在，插入失败。
5已存在，插入失败。
0 1 2 3 5 6 7

2、查找并计数count

** 这个函数的功能是在容器中搜索与val相等的元素，并返回匹配次数。因为每个元素在set中都是唯一的，所以返回值只能为0和1。**如果只想查找某个元素在不在set容器内，可以考虑不使用find函数而使用count函数，如果返回值为1，那么存在，为0则不存在。

代码例子：

int main()
{
    set<int> s;

    int arr[] = {1,2,3,4,5,6,7,8,9,10};
    
    for (auto e : arr)
    {
        s.insert(e);
    }

    //查找某个值在不在s中
    int x;
 
    //方法1：使用find函数
    cin >> x;
    auto it = s.find(x);
    if (it != s.end())
        cout << *it << "存在!" << endl;
    else
        cout << x << "不存在" << endl;

    cout << endl;

    //方法2，使用count函数
    cin >> x;
    if (s.count(x))
        cout << x << "存在" << endl;
    else
        cout << x << "不存在" << endl;

    return 0;
}

3、lower_bound和upper_bound

lower_bound：得到下界

** 指定一个值x，返回一个迭代器，该迭代器指向容器中的第一个满足条件的元素，条件是该元素大于或等于x。**如果使用默认比较类型 （less） 实例化 set 类，则该函数将返回一个迭代器，该迭代器指向的值不小于x。

upper_bound：得到上界

** 指定一个值y，返回一个迭代器，该迭代器指向容器中的第一个满足条件的元素，条件是该元素大于y。**如果使用默认比较类型 （less） 实例化 set 类，则该函数将返回一个迭代器，该迭代器指向的值大于y。

    通过上面两个函数可以获得到两个迭代器，当x < y 时，这两个迭代器维护一个区间，**区间范围是[x,y)，左闭右开，可以用于删除指定范围的子序列。**

代码例子：

int main()
{
    std::set<int> myset;
    std::set<int>::iterator itlow, itup;

    for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90

    //删除区间位于 [25,65) 的元素 
    itlow = myset.lower_bound(25);     //找到第一个大于等于25的元素，这里是30
    itup = myset.upper_bound(65);      //找到第一个大于65的元素，这里是70 

    //删除对应迭代器区间的元素[itlow,itup)
    myset.erase(itlow, itup);                     // 10 20 70 80 90

    std::cout << "myset contains:";
    for (std::set<int>::iterator it = myset.begin(); it != myset.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << '\n';

    return 0;
}

运行结果：

myset contains: 10 20 70 80 90

4、equal_range

** 功能：指定一个值val，返回一对迭代器，该迭代器维护着一段区间，该区间内的元素的值都为相同，为val。由于set的元素是唯一的，所以该区间内最多只能有一个元素。若val值不存在，两个迭代器都指向位于val之后的第一个元素。**

代码例子：

int main()
{
    std::set<int> myset;

    for (int i = 1; i <= 5; i++) myset.insert(i * 10);   // myset: 10 20 30 40 50

    std::pair<std::set<int>::const_iterator, std::set<int>::const_iterator> ret;
    ret = myset.equal_range(30);

    std::cout << "the lower bound points to: " << *ret.first << '\n';
    std::cout << "the upper bound points to: " << *ret.second << '\n';

    return 0;
}

**运行结果： **

the lower bound points to: 30
the upper bound points to: 40

（二）multiset

multiset - C++ Reference (cplusplus.com)https://legacy.cplusplus.com/reference/set/multiset/** multiset功能和set相似，但是multiset允许元素有冗余，可以存储多个相同的元素，而set里的每个元素都是唯一的。这里直接介绍multiset和set使用上的不同。**

1、insert

** 因为multise允许有重复的数据，所以用insert插入数据时不会存在插入失败的情况，其返回值不是pair<iterator,bool>类型，而直接就是iterator类型。**

2、erase

    **如果通过erase删除值为value的元素，那么在容器中所有与value相等的元素都会被删除。**

代码例子：

int main()
{
    multiset<int> myMultiset;

    int arr[] = { 10,10,20,20,20,30,40,50,60 };

    for (auto e : arr)
    {
        myMultiset.insert(e);
    }

    for (auto e : myMultiset)
    {
        cout << e << " ";
    }

    cout << endl;
    cout << "删除20" << endl;
    myMultiset.erase(20);

    for (auto e : myMultiset)
    {
        cout << e << " ";
    }
    return 0;
}

**运行结果： **

10 10 20 20 20 30 40 50 60
删除20
10 10 30 40 50 60

**3、count **

    由于元素在multise中不再唯一，count的返回值是大于等于0的。

int main()
{
    multiset<int> myMultiset;

    int arr[] = { 10,10,20,20,20,30,40,50,60 };

    for (auto e : arr)
    {
        myMultiset.insert(e);
    }

    for (auto e : myMultiset)
    {
        cout << e << " ";
    }

    cout << endl;

    cout << "20出现了" << myMultiset.count(20) << "次" << endl;
    return 0;
}

**运行结果： **

10 10 20 20 20 30 40 50 60
20出现了3次

4、lower_bound和upper_bound

** 功能和上面介绍的set的lower_bound和upper_bound一样，不过lower_bound和upper_bound在multiset用得更多一些。**

代码例子：

int main()
{
    multiset<int> myMultiset;

    int arr[] = { 10,10,20,20,20,30,40,50,60,60,60,70,80,90,100};

    //插入数据
    for (auto e : arr)
    {
        myMultiset.insert(e);
    }

    //打印
    for (auto e : myMultiset)
    {
        cout << e << " ";
    }
    cout << endl;

    //删除区间位于 [25,65) 的元素 
    auto itlow = myMultiset.lower_bound(25);     //找到第一个大于等于25的元素，这里是30
    auto itup = myMultiset.upper_bound(65);      //找到第一个大于65的元素，这里是70 

    myMultiset.erase(itlow, itup);

    for (auto e : myMultiset)
    {
        cout << e << " ";
    }

    return 0;
}

运行结果：

10 10 20 20 20 30 40 50 60 60 60 70 80 90 100
10 10 20 20 20 70 80 90 100

** 5、equal_range**

** 功能和上面介绍的set的equal_range一样，不过equal_range在multiset用得更多一些，可以得到一个迭代器区间，该区间内的元素都和指定key相同。**

代码例子：

int main()
{
    multiset<int> myMultiset;

    int arr[] = { 10,10,20,20,20,30,40,50,60,60,60,70,80,90,100 };

    //插入数据
    for (auto e : arr)
    {
        myMultiset.insert(e);
    }

    //打印
    for (auto e : myMultiset)
    {
        cout << e << " ";
    }
    cout << endl;

    //得到重复元素60的迭代器区间
    pair<multiset<int>::iterator, multiset<int>::iterator> ret = myMultiset.equal_range(60);

    //删除
    myMultiset.erase(ret.first, ret.second);

    //打印
    for (auto e : myMultiset)
    {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

运行结果：

10 10 20 20 20 30 40 50 60 60 60 70 80 90 100
10 10 20 20 20 30 40 50 70 80 90 100

三、map和multimap

（一）map

map - C++ Reference (cplusplus.com)https://legacy.cplusplus.com/reference/map/map/

map的简介

模板类型

template <

       class Key,                                     // map::key_type

       class T,                                       // map::mapped_type

       class Compare = less<Key>,                     // map::key_compare

       class Alloc = allocator<pair<const Key,T> >    // map::allocator_type

       >

key：键key的类型。

T：映射值value的类型。

Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)

Alloc：空间配置器

1、map是一种关联容器，用于存储由键key和映射值value组合而成的元素,按照特定顺序存储。

2、在map中，键值通常用于对元素进行排序和唯一标识，而映射值存储与此键相关的内容。键和映射值的类型可以不同，键和映射值在成员中用一个value_type类型的变量组合在一起，value_type是将两者组合在一起的pair类型:typedef pair<const Key, T> value_type;

3、在内部，映射中的元素总是按照其内部比较对象(类型为Compare)所指示的特定严格弱排序标准的键进行排序。

4、map容器在通过键key访问单个元素时通常比unordered_map容器慢，但map迭代到的序列是有序的。

5、map中的映射值value可以使用括号操作符((operator[])通过对应的键key直接访问到。

6、map通常以二叉搜索树的形式实现。

map的接口

1、插入insert

    **map存储的元素类型是pair<K,V>类型，插入元素时需要传入pair<K,V>类型的对象进行插入。**

插入例子：

void test1()
{
    //英汉词典
    map<string, string> dict;

    //插入方法1:实例化pair对象插入
    pair<string, string> kv1("abandon", "v.放弃");
    dict.insert(kv1);

    //插入方法2:构造函数生成匿名对象
    dict.insert(pair<string, string>("ability", "n. 能力； 才能"));

    //插入方法3：使用make_pair函数返回pair类型变量
    dict.insert(make_pair("able", "a. 能够；有能力的"));

    //插入方法4：多参数构造函数的类型转换
    pair<string, string> kv2 = { "abnormal"," a. 不正常的" };
    dict.insert(kv2);
    dict.insert({ "abnormal"," a. 不正常的" });

    //插入方法5: 初始化列表initializer_list + 多参数构造函数的类型转换
    initializer_list<pair<const string, string>> l = { {"aboard","ad.在船、飞机上"} ,{"abolish","v.废除"},{"about","ad. 大约；到处；四处"} };
    dict.insert(l);
    dict.insert({ {"aboard","ad.在船、飞机上"} ,{"abolish","v.废除"},{"about","ad. 大约；到处；四处"} });

    //打印词库
    for (auto& e : dict)
    {
        cout << e.first << " -> " << e.second << endl;
    }
}

void test2()
{
    //插入方法5: 初始化列表initializer_list + 多参数构造函数的类型转换
    //一步到位
    //英汉词典
    map<string, string> dict = { {"abandon", "v.放弃"},
        {"ability", "n. 能力； 才能"},
        {"abnormal"," a. 不正常的"},
        {"aboard","ad.在船、飞机上"},
        {"abolish","v.废除"},
        {"about","ad. 大约；到处；四处"}
    };

    //打印词库
    for (auto& e : dict)
    {
        cout << e.first << " -> " << e.second << endl;
    }
}

int main()
{
    test1();
    cout << endl;
    test2();
    
    return 0;
}

运行结果：

abandon -> v.放弃
ability -> n. 能力； 才能
able -> a. 能够；有能力的
abnormal -> a. 不正常的
aboard -> ad.在船、飞机上
abolish -> v.废除
about -> ad. 大约；到处；四处

abandon -> v.放弃
ability -> n. 能力； 才能
abnormal -> a. 不正常的
aboard -> ad.在船、飞机上
abolish -> v.废除
about -> ad. 大约；到处；四处

2、下标访问operator[]和at

    **功能：使map可以像数组通过下标访问到数据一样，通过对应的键key访问到其对应映射的值value。**

    如果key与容器中元素的键匹配，则该函数将返回对其映射值的引用。
     如果key与容器中任何元素的键不匹配，则该函数将插入一个该键的新元素，并返回对其映射值的引用。请注意， 本操作会让容器大小增加 1，即使没有为该元素分配映射值来初始化（该新元素会在构造时使用映射值类型的默认构造进行初始化），

功能：和operator[]功能类似，通过键key访问其映射值，返回key对应的映射值的引用。**但是，如果键key不存在，则会抛异常。 **

代码例子：

int main()
{
    //统计选民的投票次数
    string arr[] = { "张三","李四","张三","李四","王某","王某","李四","李四","王某" };

    //键：名字 映射值：投票次数
    map<string, int> count;

    //计数
    for (auto& e : arr)
    {
        //通过名字索引对应的投票次数并加一，代表投票次数加一
        //如果该名字不在count里，则用该名字作为key新插入一个元素，其映射值使用的是int内置类型的默认构造，其值为0
        count[e]++; 
    }

    //打印选民和对应的投票次数
    for (auto e : count)
    {
        cout << e.first << " -> " << e.second << endl;
    }

    return 0;
}

运行结果：

李四 -> 4
王某 -> 3
张三 -> 2

3、其他接口

    map的count、lower_bound、upper_bound以及equal_range的功能和set的是一样的，其功能在set部分已经着重介绍过了，这里不再赘述。 

（二）、multimap

    multimap和map功能类似，这里也不再赘述。**需要注意的是multimap允许元素冗余，容器中可以存在多个相同key的元素，并且multimap中没有重载operator[]和at操作**，因为multimap中可以有多个相同的key对应不同的映射值，使用operator[]的话返回值的类型应该是一个引用映射值的数组，这样的话会使内存更加复杂化，如果需要得到所有相同key的元素，可以通过equal_range得到这个集合的迭代器区间，这样更加简洁。