C++之set/multiset 和 map/multimap的使用

关联式容器

在初阶阶段，我们已经接触过STL中的部分容器:

比如：vector、list、deque、forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。

今天要了解的几个容器称为关联式容器:

关联式容器也是用来存储数据的, 与序列式容器不同的是, 其里面存储的是<key, value>结构的键值对, 在数据检索时比序列式容器效率更高。

键值对

用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代
表键值,value表示与key对应的信息。比如: 现在要建立一个英汉互译的字典, 那该字典中必然
有英文单词与其对应的中文含义, 而且, 英文单词与其中文含义是一一对应的关系, 即通过该应
该单词, 在词典中就可以找到与其对应的中文含义。

template <class T1, class T2>
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair(): first(T1()), second(T2()){}pair(const T1& a, const T2& b): first(a), second(b){}
};

pair的应用：

pair是将2个数据组合成一个数据,当需要这样的需求时就可以使用pair。
（1）STL中的map就是将key和value放在一起来保存(一般first对应key,second对应value)
（2）当一个函数需要返回2个数据的时候,可以选择pair

所以可以认为pair就是库里面提供的一个键值对的类。

树形结构的关联式容器

根据应用场景的不同,STL总共实现了两种不同结构的关联式容器: 树型结构与哈希结构。

树型结构的关联式容器主要有四种：

map、set、multimap、multiset

这四种容器的共同点是: 使用平衡二叉搜索树(即红黑树)作为其底层结构, 容器中的元素是一个有序的序列, 普通的搜索二叉树如果数据有序或接近有序二叉搜索树将退化为单支树, 查找元素相当于在顺序表中搜索元素, 效率低下。那平衡二叉树顾名思义就是在普通搜索二叉树的基础上让它变的平衡(需要对树中的结点进行调整)。

set

认识set

文档介绍

首先我们来看一下set:

set是一个类模板, 有三个模板参数, 但平时使用的时候一般只需要管第一个模板参数, 后两个都是有缺省值的, 如果想改变它底层搜索树的排序方式你可以自己传第二个比较方式的仿函数（默认是升序）。

set的介绍

1. set是按照一定次序存储元素的容器
2. 在set中, 元素的value也标识它(value就是key,类型为T), 并且每个value必须是唯一的。
set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
3. 在内部, set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对
子集进行直接迭代。
5. set在底层是用二叉搜索树(红黑树)实现的。
注意：
1. 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放
value，但在底层实际存放的是由<value, value>构成的键值对。
2. set中插入元素时，只需要插入value即可，不需要构造键值对。
3. set中的元素不可以重复(因此可以使用set进行去重)。
4. 使用set的迭代器遍历set中的元素，可以得到有序序列
5. set中的元素默认按照小于来比较
6. set中查找某个元素，时间复杂度为：O(logn)
7. set中的元素不允许修改
8. set中的底层使用二叉搜索树(红黑树)来实现。

那我们上面说到：

这几个关联式容器它们的底层结构其实就是我们之前学的二叉搜索树, 那set其实就对应我们前面学的搜索二叉树的应用里面的K模型，下面要学的map就对应KV模型。

set的使用

构造函数

构造空set然后插入元素:

#include<set>
#include <iostream>
using namespace std;
void testset1()
{set<int> s;s.insert(4);s.insert(6);s.insert(3);s.insert(5);s.insert(2);s.insert(1);s.insert(1);s.insert(1);for (set<int>::iterator it = s.begin(); it != s.end(); it++){cout << *it << " ";}cout << endl;
}int main()
{testset1();return 0;
}

迭代器区间构造:

void testset1()
{vector<int> v = { 4,6,3,5,2,1,1,1 };set<int> s(v.begin(),v.end());for (set<int>::iterator it = s.begin(); it != s.end(); it++){cout << *it << " ";}cout << endl;
}int main()
{testset1();return 0;
}

但是我们看到这里打印出来是1,2,3,4,5,6。

我们按照无序插入并且插入了3个1, 它的底层是搜索二叉树, 搜索二叉树一般是不能有重复值的, 所以如果多次插入相同的值, 插入就会失败（或者可以理解成它会自动进行去重）,另外我们知道二叉搜索树也叫做二叉排序树,中序遍历就可以得到一个升序序列,所以这里默认遍历打印出来就是有序了。所以可以认为set可以实现排序+去重

可以看到不能对set内的元素进行修改, 它的底层是搜索树, 那搜索树任意修改里面的值的话,修改之后不能保证它还是一棵搜索树,所以不能修改。

find与count

find可以搭配erase一块使用:

void testset1()
{vector<int> v = { 4,6,3,5,2,1,1,1 };set<int> s(v.begin(),v.end());set<int>::iterator it = s.find(3);if (it != s.end()){s.erase(it);}for (set<int>::iterator it = s.begin(); it != s.end(); it++){cout << *it << " ";}cout << endl;
}

其实还可以用另一个接口——count

count是统计元素的个数,但是set里面不允许重复值,所以结果只有1和0,存在就是1,不存在就是0

void testset2()
{vector<int> v = { 4,6,3,5,2,1,1,1 };set<int> s(v.begin(), v.end());if (s.count(3))cout << "3在" << endl;elsecout << "3不在" << endl;
}int main()
{testset2();return 0;
}

erase

void testset3()
{std::set<int> myset;for (int i = 1; i < 10; i++) myset.insert(i * 10);  // 10 20 30 40 50 60 70 80 90std::set<int>::iterator it=myset.begin();myset.erase(it);//删除10myset.erase(40);//删除40it = myset.find(60);myset.erase(it, myset.end());//删除60-90cout << "myset contains:";for (it = myset.begin(); it != myset.end(); ++it)cout << ' ' << *it;cout << '\n';
}

lower_bound与upper_bound

void testset4()
{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 90itlow = myset.lower_bound(25);                // 大于等于val值位置的iterator,itlow指向30itup = myset.upper_bound(70);                 // 大于val值位置的iterator,itup指向80// [25, 70]myset.erase(itlow, itup);                     // 10 20 80 90for (auto e : myset){cout << e << " ";}cout << endl;
}

eual_range:

返回一个pair,pair.first是lower_bound(val),pair.second是upper_bound(val).

由于set元素是唯一的, 所以区间长度最长就是1

void testset5()
{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(35);std::cout << "the lower bound points to: " << *ret.first << '\n';   // >= valstd::cout << "the upper bound points to: " << *ret.second << '\n';  // > valcout << endl;ret = myset.equal_range(30);std::cout << "the lower bound points to: " << *ret.first << '\n';   // >= valstd::cout << "the upper bound points to: " << *ret.second << '\n';  // > val
}

multiset

那在<set>这个头文件里面还有一个multiset,它跟set最大的区别就是允许里面存的key值冗余, 可以认为它有排序, 但没进行去重.

那允许键值冗余的话它的插入怎么做呢？

那就接着插就行了, 即使插入的是已经存在的值, 那搜索树的话我们说大的值要插入到右子树,小的插入到左子树, 那现在相等的话其实插入到哪边都可以, 可以左边也可以右边, 反正平衡二叉树插入之后会对结点进行调整使得两边平衡

find：

如果我们在multiset中find某个值的话,如果有多个相同的值,那find的时候查找的是哪一个？
规定它find的是中序遍历遇到的第一个,它遍历的时候底层走的是中序遍历,所以打印出来才是有序的。

void testset6()
{// 排序multiset<int> s;s.insert(5);s.insert(2);s.insert(6);s.insert(1);s.insert(1);s.insert(2);s.insert(1);s.insert(5);s.insert(2);cout << "multiset contains:" << endl;for (auto e : s){cout << e << " ";}cout << endl<<endl;// 如果有多个值，find返回中序第一个valcout << "multiset begins with 2:" << endl;multiset<int>::iterator it = s.find(2);while (it != s.end()){cout << *it << " ";++it;}cout << endl<<endl;cout << "the number of 1: ";cout << s.count(1) << endl << endl;// [>=val, >val)auto ret = s.equal_range(2);s.erase(ret.first, ret.second);cout << "after erasing 2, multiset contains:"<< endl;for (auto e : s){cout << e << " ";}cout << endl << endl;size_t n = s.erase(1);cout << "the number of 1: " << n;cout << "after erasing 1, multiset contains:" << endl;for (auto e : s){cout << e << " ";}cout << endl << endl;
}

map

认识map

文档介绍

map其实就对应搜索二叉树的KV模型,它里面存的是<key, value>结构的键值对。即用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代表键值,value表示与key对应的信息。

1. map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中, 键值key通常用于排序和唯一地标识元素, 而值value中存储与此键值key关联的
内容。键值key和值value的类型可能不同, 并且在map的内部, key与value通过成员类型
value_type绑定在一起，为其取别名称为pair: typedef pair<const key, T> value_type;
3. 在内部,map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序
对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

map的使用

insert：

可以看到插入的是value_type类型的值, 而value_type是一个pair,pair.first(key)是const修饰的，不能修改（即键必须是唯一的）,pair.second(value)可以。

void test_map1()
{map<string, string> dict;dict.insert(pair<string, string>("sort", "排序"));dict.insert(pair<string, string>("insert", "插入"));dict.insert(make_pair("right", "右边")); // 推荐这个dict.insert(make_pair("string", "字符串"));dict.insert(make_pair("string", "字符串11111"));for (map<string, string>::iterator it = dict.begin(); it != dict.end(); it++){cout << it->first << ":" << it->second << endl;}
}

这个make_pair是什么呢？它其实是库里面提供的一个函数模板, 它可以帮助我们创建一个pair的对象, 用它的好处是我们不需要自己去指定类型, 因为模板可以自动推导类型。

此外,map里键必须是唯一的不能重复,值可以重复, 一个键只能对应一个值，一个值可以对应多个键

insert的返回值:

insert会返回一个pair:

pair.second是bool值,插入成功bool为true,失败为false.

pair.first是一个迭代器, 插入成功迭代器指向新插入的这个键值对, 失败的话指向已经存在的那个键值对.

void test_map1()
{map<string, string> dict;dict.insert(pair<string, string>("sort", "排序"));dict.insert(pair<string, string>("insert", "插入"));dict.insert(make_pair("right", "右边")); // 推荐这个dict.insert(make_pair("string", "字符串"));auto p = dict.insert(make_pair("string", "字符串11111"));cout << p.first->first << ":" << p.first->second << endl;
}

还要注意一个问题:

insert的第一个模板参数是const key_type: 但是这段插入的是pair<string,string>类型的pair, 第一个参数并没有const修饰,为什么还能插入?

所以这个pair类型即使有差异也可以进行拷贝构造, 比如这样也行:

所以只要这两个U和V(这里都是const char*)能去初始化this->first和this->second, 都是可以拷贝的, 所以这个拷贝构造可以是构造也可以是拷贝构造:

当U和V与this->first和this->second类型相同时, 就是拷贝构造, 类型不同但是可以转化的, 就是构造.

这样就更方便地解释了为什么推荐用make_pair:

make_pair是函数模板, 可以自己推演模板参数, 而之前用pair<string,string>需要手动把模板类型写出来(显示实例化):

所以make_pair之后不管是pair<const char*, const char*> 还是 pair<stirng,stirng>类型, 都不用管, 最后都会调用默认构造函数构造出pair<const string, string>.

find:

和set的find类似, 找到返回该位置的迭代器, 找不到返回end

用map写一下统计次数的程序：

void test_map2()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (auto& str : arr){auto ret = countMap.find(str);if (ret == countMap.end()){// 没找到表示第一次出现，插入countMap.insert(make_pair(str, 1));}else{// 次数++ret->second++;}}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}
}

map中[]的理解

所以上面的查找代码可以替换为:

void test_map3()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (auto& str : arr){countMap[str]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}
}

仔细观察一下operator[]:

文档上面也解释了，调用这个重载的[]就等效于执行这句代码
(*((this->insert(make_pair(k,mapped_type()))).first)).second

这里面其实去调了一下insert，那我们来仔细研究一下insert的返回值

插入是有成功和失败两种情况, 因为键值不允许冗余, 它返回的是一个pair,其中第一个模板参数为迭代器, 第二个为bool。

当插入成功的时候，pair的first为指向新插入元素的迭代器，second为true，当插入失败的时候（其实就是插入的键已经存在了）,那它的first为容器中已存在的那个相同的等效键元素的迭代器，second为false。所以后面这个bool其实是标识插入成功还是失败

那我们再来看这个函数:

此外, 我们看到这里面insert也是使用make_pair这个函数创建一个pair对象, 第一个参数就是我们[]里面放的那个键key, 第二个参数传的是调了值value的类型的默认构造(内置类型也有构造函数), 那value是int,默认构造的值是0, 所以我们第一次插入刚好它的次数就是0了。然后返回这个次数的引用, 外面对它++, 就正好是1。
然后后续插入相同键的话,就插入失败, 不会将次数变成0，但是依然返回次数（对应pair中的second）的引用,我们从1继续往上++就行了

利用[]进行插入,修改,删除:

void test_map4()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("insert", "插入"));dict.insert(make_pair("right", "右边")); dict.insert(make_pair("string", "字符串"));dict["girl"];//插入dict["boy"] = "男孩";//插入并修改dict["girl"] = "女孩";//修改cout << dict["girl"] << endl;//查找
}

multimap

和set一样, map还有multimap

跟map相比，multimap允许键key冗余,所以它的接口里面就没有[]了

void test_map5()
{multimap<string, string> dict;dict.insert(make_pair("sort", "排序"));dict.insert(make_pair("insert", "插入"));dict.insert(make_pair("boy", "男孩"));dict.insert(make_pair("left", "左边"));dict.insert(make_pair("right", "右边"));dict.insert(make_pair("string","字符串1"));dict.insert(make_pair("string", "字符串2"));for (multimap<string, string>::iterator it = dict.begin(); it != dict.end(); it++){cout << it->first << ":" << it->second << endl;}
}