【C++】map与set的介绍与使用-创新互联
目录
超过十载行业经验,技术领先,服务至上的经营模式,全靠网络和口碑获得客户,为自己降低成本,也就是为客户降低成本。到目前业务范围包括了:成都做网站、成都网站制作,成都网站推广,成都网站优化,整体网络托管,微信小程序开发,微信开发,APP应用开发,同时也可以让客户的网站和网络营销和我们一样获得订单和生意!一、关联式容器
二、键值对
三、set
3.1 set 的介绍
3.2 set 的使用
3.3. set 的使用举例
四、map
4.1 map的介绍
3.2 map 的使用
4.3 map的使用举例
五、经典练习题
1.set的使用
2.map的使用
思路一(稳定排序):
思路二(priority_queue):
一、关联式容器
在之前,我们接触过 vector、list、deque……,这些容器被称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。那么什么是关联式容器呢?
关联式容器:关联式容器也是用来存储数据的,与序列式容器不同的是,其中存储的是
用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量 key 、value。
key代表键值,value 表示与 key 对应的信息。比如:现在要建立一个英汉互译的字典,那该字典必然有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该英文单词,在字典中就可以找到其对应的中文含义。
SGI-STL中关于键值对的定义:
templatestruct 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)
{}
};
三、set
3.1 set 的介绍这里是 set 的文档介绍:set的介绍_C++reference 以下是几个重要点。
3.2 set 的使用
- set 是按照一定次序存储的容器
- 在 set 中,元素的 value 也标识它(value 就是 Key,类型为 T),并且每个 value 必须是唯一的。set中的元素不能在容器中修改(元素总是const),但是可以从容器中插入或删除它们。
- 在内部,set 中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
- set 容器通过 key 访问单个元素的速度通常比 unordered_set 容易慢,但它们允许根据顺序对子集进行直接迭代。
- set 在底层是用二叉搜索树(红黑树)实现的。
1. set 的模板参数列表
T:set 中存放元素的类型,实际在底层存储
的键值对。 Compare:set 中元素默认按照小于来比较。
Alloc:set 中元素空间的管理方式,使用STL提供的空间配置器管理。
2. set 的构造函数
3. set 的迭代器
iterator begin() | 返回 set 中起始位置的迭代器 |
iterator end() | 返回 set 中最后一个元素的迭代器 |
iterator rbegin() | 返回第一个元素的迭代器,即end() |
iterator rend() | 返回最后一个元素的迭代器,即begin() |
4. set 的修改操作
函数声明 | 功能介绍 |
pair | 在set中插入元素x,实际是插入 |
void erase ( iterator position ) | 删除 set 中 position 位置上的元素 |
size_type erase ( const key_type& x ) | 删除 set 中值为 x 的元素,返回删除的元素的个数 |
void erase ( iterator fifirst, iterator last ) | 删除 set 中 [first, last) 区间中的元素 |
void clear ( ) | 将 set 中的元素清空 |
iterator find ( const key_type& x ) const | 返回set中值为x的元素的位置,不存在返回end() |
size_type count ( const key_type& x ) const | 返回set中值为x的元素个数(multiset中使用) |
map的文档简介 以下是几个重要点:
3.2 map 的使用
- map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
- 在map中,键值key通常用于排序和唯一的标识元素,而值value中存储与此key关联的内容。简直key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取名别称为pair
- 在内部,map中的元素总是按照及那只key进行排序的。
- map中通过简直访问但各国元素的熟读通常比unordered_map容器慢,但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时,可以得到一个有序的序列)
- map支持下标访问操作符,即在[]中放入key,就饿可以找到与key对应的value。
- map通常被实现为二叉搜索树(准确的说是红黑树)
1.map的模板参数说明
- key:键值对中key的类型
- T:键值对中value的类型
- Compare:比较器的类型。默认为less,如果存在特殊的比较,需要用户自己显示传入比较规则(函数指针或仿函数进行传递)
2.map的构造函数
3.map的迭代器
iterator begin() | 返回 map 中起始位置的迭代器 |
iterator end() | 返回 map 中最后一个元素的迭代器 |
iterator rbegin() | 返回第一个元素的迭代器,即end() |
iterator rend() | 返回最后一个元素的迭代器,即begin() |
4.insert
首先我们来看看insert的使用,首先要知道map的insert是插入pair类型的数据
然后我们举例进行插入一下
void test_map1()
{
//创建字典
mapdict1;
mapdict2;
mapdict3;
//插入数据——方式1、
pairkv1("sort", "排序");
pairkv2("insert", "插入");
dict1.insert(kv1);
dict1.insert(kv2);
//插入数据——方式2、匿名对象
dict2.insert(pair("sort", "排序"));
dict2.insert(pair("insert", "插入"));
//插入数据——方式3、make_pair()
dict3.insert(make_pair("sort", "排序"));
dict3.insert(make_pair("insert", "插入"));
}
插入方式3,make_pair其实是一个模板函数,就是为了方便我们进行pair结构的插入数据。
4. 下标访问操作符
这里我们实现一个统计水果次数功能的map,如下:
但是这样的插入方式,非常的麻烦,所以map将下标访问操作符进行了重载,让其插入数据变得十分轻松。以下是 map中下标访问操作符:
功能解析:
- map中有这个key,返回value的引用。(查找、修改value)
- map中没有这个key,会插入pair(key,V()),并返回value的引用。(插入+修改)
其实下标访问操作符的本质是调用了 insert 函数,下面的文档中的实现方式:
这种方式其实不是太好理解,这里我们可以将其分为两步,就非常好理解了。
4.3 map的使用举例因为返回的是其value的引用,所以我们可以对其进行赋值,这也是一种插入方式,也是最简单的一种插入方式。
所以,在上面实现统计水果次数的map中,我们可以将其插入方式改为 [] 插入:
五、经典练习题 1.set的使用题目链接:349. 两个数组的交集
题目介绍:
算法思路1:
- 因为是求交集,所以我们可以使用set对nums1、nums2进行排序+去重。
- 遍历set1,判断set1中的值是否存在于set2中,如果存在,则放到结果数组中,不存在则跳过(时间复杂度:O(N*N))。
算法思路2:
- 因为是求交集,所以我们可以使用set对nums1、nums2进行排序+去重。
- 同时处理两个区间,让it1指向的值与it2指向的值进行比较,如果相等则为交集,两个迭代器同时向后移动,如果不相等,结果小的迭代器进行向后移动(时间复杂度:O(N))
两种算法就是找交集的代码不同,这里一并给出源代码:
class Solution {
public:
vectorintersection(vector& nums1, vector& nums2) {
sets1;
sets2;
//去重
for(auto& e: nums1)
s1.insert(e);
for(auto& e: nums2)
s2.insert(e);
//找交集
vectorresult;
//方法1:
for(auto& e: s1)
{
if (s2.find(e)!=s2.end())
result.push_back(e);
}
//============================================
//方法2:
set::iterator it1=s1.begin();
set::iterator it2=s2.begin();
while(it1!=s1.end()&&it2!=s2.end())
{
if (*it1==*it2)
{
result.push_back(*it1);
it1++,it2++;
}
else if (*it1>*it2) it2++;
else it1++;
}
return result;
}
};
2.map的使用思路一(稳定排序):题目链接:692. 前K个高频单词
题目介绍:
这题的难点就在于出现频率相等的情况下,要按照字典序排序,这就意味着不能简单的使用一次排序解决。
算法思路:
- 使用map根据其字典序进行排序,并统计单词的出现次数。
- 通过sort根据单词的出现次数进行排序。
使用了map存储后,单词在map中都按出现次数进行排序,但是此时,如果我们使用一种稳定排序,让其在符合次数相同时,并进行字典序的排序,就可以完成最终的排序。
首先 sort 是一个的迭代器是随机迭代器(RandomAccess Iterator),而map双向迭代器(bidirectional iterator),所以我们要先将map中的数据放入到一个数组中。
因为sort是快速排序,不稳定的排序,所以我们要编写仿函数控制其排序的结果。
仿函数的比较规则:
- 如果出现次数多,则排在前面,返回true。
- 出现次数相同时再比较字典序,如果kv1的字典序小于kv2,即kv1在kv2前,则返回true,编写这条规则可以间接控制稳定性。
- 其他情况直接返回false。
class Solution {
public:
struct Greater{
bool operator()(const pair& kv1,const pair& kv2)
{
//按次数比较
if (kv1.second >kv2.second)
return true;
//次数相同,按字典序比较。
if (kv1.second==kv2.second&&kv1.first< kv2.first)
return true;
return false;
}
};
vectortopKFrequent(vector& words, int k) {
mapcountMap;
for(auto& str:words)
{
countMap[str]++;
}
//导数据,因为迭代器类型不同
vector>sortV(countMap.begin(),countMap.end());
sort(sortV.begin(),sortV.end(),Greater());
vectorresult;
for(int i=0;i
因为map中已经按照字典序进行了排序,所以我们只需要使用一种稳定的排序,将出现次数多的调整到前面,出现次数相同则不进行调整。
库中的稳定排序(stable_sort):
进行以下修改即可:
思路二(priority_queue):算法思路:
- 使用map根据其字典序进行排序,并统计单词的出现次数。
- 再将数据放入priority_queue中,通过自定义仿函数建立k的数的小堆。
- 再将前k个数放入结果数组中。
既然要使用我们自己的仿函数,则模板参数这我们要额外注意,我们要按顺序传入参数,在仿函数前要先传入存储容器,因为此题使用的vector进行的存储,所以直接传入vector即可。
注意,第三个仿函数参数我们直接传入仿函数名即可,因为我们自己实现的仿函数一般不会再设置模板。不要写浑了(hhh)。
仿函数的比较规则:
我们想每次在堆顶取出 出现次数最多并且字典序小的数据,所以如果child出现次数多则往上调整,或出现次数相同字典序位于前的,进行往上调整,每次取出堆顶数据再弹出堆顶,则结果可按照我们想要的顺序进行排序。
- kv2的出现次数多则往上调整返回true。
- 出现次数相同时再比较字典序,字典序如果kv1大于kv2,则kv2在字典序前面,进行向上调整,则返回true。
- 其他情况直接返回false。
struct Less {
bool operator()(const pair& kv1, const pair& kv2)
{
//按次数比较
if (kv1.second< kv2.second)
return true;
//次数相同,按字典序比较。
if (kv1.second == kv2.second && kv1.first >kv2.first)
return true;
return false;
}
};
然后我们将数据插入到priority_queue中,我们可以使用迭代器区间进行初始化,也可以直接push插入数据。
因为要返回前k的数据。所以使用while循环,在priority_queue中取出前k个top数据,将其pair中的first放入结果数组中。
class Solution {
public:
struct Less{
bool operator()(const pair& kv1,const pair& kv2)
{
//按次数比较
if (kv1.secondkv2.first)
return true;
return false;
}
};
vectortopKFrequent(vector& words, int k) {
mapcountMap;
for(auto& str:words)
{
countMap[str]++;
}
//迭代器区间初始化
priority_queue,vector>,Less>maxHeap(countMap.begin(),countMap.end());
vectorresult;
while(k--)
{
result.push_back(maxHeap.top().first);
maxHeap.pop();
}
return result;
}
};
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
当前文章:【C++】map与set的介绍与使用-创新互联
链接分享:http://myzitong.com/article/ijcds.html