大橙子网站建设,新征程启航

为企业提供网站建设、域名注册、服务器等服务

【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 以下是几个重要点。 

  1. set 是按照一定次序存储的容器
  2. 在 set 中,元素的 value 也标识它(value 就是 Key,类型为 T),并且每个 value 必须是唯一的。set中的元素不能在容器中修改(元素总是const),但是可以从容器中插入或删除它们。
  3. 在内部,set 中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
  4. set 容器通过 key 访问单个元素的速度通常比 unordered_set 容易慢,但它们允许根据顺序对子集进行直接迭代。
  5. set 在底层是用二叉搜索树(红黑树)实现的。
3.2 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 的修改操作

函数声明功能介绍
pairinsert (const value_type& x)

在set中插入元素x,实际是插入构成的键值对,如果插入成功,返回<该元素在set中的位置,true>,如果插入失败,说明x在set中已经存在,返回

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中使用)
3.3. set 的使用举例

四、map 4.1 map的介绍

map的文档简介 以下是几个重要点:

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

功能解析:

  1. map中有这个key,返回value的引用。(查找、修改value)
  2. map中没有这个key,会插入pair(key,V()),并返回value的引用。(插入+修改)

其实下标访问操作符的本质是调用了 insert 函数,下面的文档中的实现方式:

这种方式其实不是太好理解,这里我们可以将其分为两步,就非常好理解了。

4.3 map的使用举例

因为返回的是其value的引用,所以我们可以对其进行赋值,这也是一种插入方式,也是最简单的一种插入方式。

所以,在上面实现统计水果次数的map中,我们可以将其插入方式改为 [] 插入:

五、经典练习题 1.set的使用

题目链接:349. 两个数组的交集

题目介绍:

算法思路1:

  1. 因为是求交集,所以我们可以使用set对nums1、nums2进行排序+去重。
  2. 遍历set1,判断set1中的值是否存在于set2中,如果存在,则放到结果数组中,不存在则跳过(时间复杂度:O(N*N))。

算法思路2:

  1. 因为是求交集,所以我们可以使用set对nums1、nums2进行排序+去重。
  2. 同时处理两个区间,让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个高频单词

题目介绍:

这题的难点就在于出现频率相等的情况下,要按照字典序排序,这就意味着不能简单的使用一次排序解决。

思路一(稳定排序):

算法思路:

  1. 使用map根据其字典序进行排序,并统计单词的出现次数。
  2. 通过sort根据单词的出现次数进行排序。

使用了map存储后,单词在map中都按出现次数进行排序,但是此时,如果我们使用一种稳定排序,让其在符合次数相同时,并进行字典序的排序,就可以完成最终的排序。

首先 sort 是一个的迭代器是随机迭代器(RandomAccess Iterator),而map双向迭代器(bidirectional iterator),所以我们要先将map中的数据放入到一个数组中。

因为sort是快速排序,不稳定的排序,所以我们要编写仿函数控制其排序的结果。

仿函数的比较规则:

  1. 如果出现次数多,则排在前面,返回true。
  2. 出现次数相同时再比较字典序,如果kv1的字典序小于kv2,即kv1在kv2前,则返回true,编写这条规则可以间接控制稳定性。
  3. 其他情况直接返回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):

算法思路:

  1. 使用map根据其字典序进行排序,并统计单词的出现次数。
  2. 再将数据放入priority_queue中,通过自定义仿函数建立k的数的小堆。
  3. 再将前k个数放入结果数组中。

既然要使用我们自己的仿函数,则模板参数这我们要额外注意,我们要按顺序传入参数,在仿函数前要先传入存储容器,因为此题使用的vector进行的存储,所以直接传入vector即可。

注意,第三个仿函数参数我们直接传入仿函数名即可,因为我们自己实现的仿函数一般不会再设置模板。不要写浑了(hhh)。

仿函数的比较规则:

我们想每次在堆顶取出 出现次数最多并且字典序小的数据,所以如果child出现次数多则往上调整,或出现次数相同字典序位于前的,进行往上调整,每次取出堆顶数据再弹出堆顶,则结果可按照我们想要的顺序进行排序。

  1. kv2的出现次数多则往上调整返回true。
  2. 出现次数相同时再比较字典序,字典序如果kv1大于kv2,则kv2在字典序前面,进行向上调整,则返回true。
  3. 其他情况直接返回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://dzwzjz.com/article/ijcds.html
在线咨询
服务热线
服务热线:028-86922220
TOP