[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;elsecout << x << "不存在" << endl;cout << endl;//方法2，使用count函数cin >> x;if (s.count(x))cout << x << "存在" << endl;elsecout << 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的元素，这里是30itup = myset.upper_bound(65);      //找到第一个大于65的元素，这里是70 //删除对应迭代器区间的元素[itlow,itup)myset.erase(itlow, itup);                     // 10 20 70 80 90std::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 50std::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的元素，这里是30auto 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内置类型的默认构造，其值为0count[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得到这个集合的迭代器区间，这样更加简洁。