首页 > 编程语言 >面向对象程序设计——mapの简析

面向对象程序设计——mapの简析

时间:2024-09-23 22:23:44浏览次数:11  
标签:map insert 面向对象 简析 key pair mymap first

1.map的定义

Key就是map底层关键字的类型,T是map底层value的类型,set默认要求Key⽀持⼩于⽐较,如果不⽀持或者需要的话可以⾃⾏实现仿函数传给第⼆个模版参数,map底层存储数据的 内存是从空间配置器申请的。⼀般情况下,我们都不需要传后两个模版参数。map底层是⽤红⿊树实现,增删查改效率是O(logN) ,迭代器遍历是⾛的中序,所以是按key有序顺序遍历的

1.1map的构造

显式实例化直接构造 

//map
int main()
{
	//显式定义
	map<string, string> dict;
	pair<string, string> key("first", "第一个");
	dict.insert(key);

	return 0;
}

匿名对象构造 

//map
int main()
{
	//显式定义
	map<string, string> dict;
	pair<string, string> key("first", "第一个");
	dict.insert(key);

	//匿名对象
	dict.insert(pair<string, string>("second", "第二个"));

	return 0;
}

 函数模版构造

//map
int main()
{
	//显式定义
	map<string, string> dict;
	pair<string, string> key("first", "第一个");
	dict.insert(key);

	//匿名对象
	dict.insert(pair<string, string>("second", "第二个"));

	//make_pair函数模版直接插入
	dict.insert(make_pair("sort", "排序"));

	return 0;
}

 多参数类型转换

//map
int main()
{
	//显式定义
	map<string, string> dict;
	pair<string, string> key("first", "第一个");
	dict.insert(key);

	//匿名对象
	dict.insert(pair<string, string>("second", "第二个"));

	//make_pair函数模版直接插入
	dict.insert(make_pair("sort", "排序"));

	//C++11支持多参数类型转换
	dict.insert({ "hello","泥嚎" });
	//key相同的情况下,value不相等不会更新,而且key不可以被修改而value可以
	dict.insert({ "hello","泥嚎xixixixixi" });

	//遍历,这里需要显式打印key与value,因为他们是公有的
	//map<string, string>::iterator it = dict.begin();
	auto it = dict.begin();
	while (it != dict.end())
	{
		//使用.访问
		//cout << (*it).first << ":" << (*it).second << endl;
		
		//使用->访问结构体,这里实际上就是重载了一个->
		//cout << it.operator->()->first << ":" << it.operator->()->second << endl;
		cout << it->first << ":" << it->second << endl;
		++it;
	}

	return 0;
}

 小tips:

1.在map中有一个pair存储key与value,后面我们使用的first就是key,second就是value

2.当新插入一个数据与原来某个数据相同时,如果key相同value不同的情况下,该数据不会更新,且key不可以被修改而value可以被修改

3.通常使用迭代器遍历map时需要显式的使用.或者->访问pair中的first与second,不能直接解引用

2.pair

map底层的红⿊树节点中的数据,使⽤pair存储键值对数据 

pair的代码解释 

typedef pair<const Key, T> value_type;
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)
   {}
 
   template<class U, class V> 
   pair (const pair<U,V>& pr): first(pr.first), second(pr.second)
   {}
};
template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y)
{
 return ( pair<T1,T2>(x,y) );
}

3.map的增删查 

 3.1插入 

insert插⼊⼀个pair<key, T>对象 
1、如果key已经在map中,插⼊失败,则返回⼀个pair<iterator,bool>对象,返回pair对象
first是key所在结点的迭代器,second是false 
2、如果key不在在map中,插⼊成功,则返回⼀个pair<iterator,bool>对象,返回pair对象
first是新插⼊key所在结点的迭代器,second是true 
也就是说⽆论插⼊成功还是失败,返回pair<iterator,bool>对象的first都会指向key所在的迭
代器 
那么也就意味着insert插⼊失败时充当了查找的功能,正是因为这⼀点,insert可以⽤来实现
operator[]
需要注意的是这⾥有两个pair,不要混淆了,⼀个是map底层红⿊树节点中存的pair<key, T>,另
⼀个是insert返回值pair<iterator,bool> 

这里我们只介绍最常用并且较为重要的一种插入,即在插入后会返回一个pair,注意这里的pair与map底层的pair不同,若插入成功就会返回pair<插入后的key的迭代器,true>,插入失败就返回pair<原来就存在相同key的迭代器,false>,这对后面的operator[]有很大作用

//单个数据插⼊,如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败 
pair<iterator, bool> insert(const value_type& val);
//列表插⼊,已经在容器中存在的值不会插⼊ 
void insert(initializer_list<value_type> il);
//迭代器区间插⼊,已经在容器中存在的值不会插⼊ 
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
//插入
int main()
{
	map<int, string> mymap;
	//1.单个数据插⼊,如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败 
    //pair<iterator, bool> insert(const value_type& val);
	mymap.insert({ 1, "first" });
	mymap.insert({ 1,"first_change" });
	auto it = mymap.begin();
	while (it != mymap.end())
	{
		cout << it->first << ":" << it->second << endl;
		it++;
	}

	return 0;
}

 3.2删除

// 删除⼀个迭代器位置的值 
iterator erase (const_iterator position);
// 删除k,k存在返回0,存在返回1 
size_type erase (const key_type& k);
// 删除⼀段迭代器区间的值 
iterator erase (const_iterator first, const_iterator last);
//删除
int main()
{
	map<int, string> mymap;
	mymap.insert({ 1, "first" });
	mymap.insert({ 2,"second" });
	mymap.insert({ 3,"three" });
	mymap.insert({ 4,"four" });
	mymap.insert({ 5,"five" });
	auto it1 = mymap.begin();
	while (it1 != mymap.end())
	{
		cout << it1->first << ":" << it1->second << " ";
		it1++;
	}
	cout << endl;
    //迭代器删除
	mymap.erase(mymap.begin());
	auto it2 = mymap.begin();
	while (it2 != mymap.end())
	{
		cout << it2->first << ":" << it2->second << " ";
		it2++;
	}
	cout << endl;
    //删除指定的key所对应的pair
	mymap.erase(4);
	auto it3 = mymap.begin();
	while (it3 != mymap.end())
	{
		cout << it3->first << ":" << it3->second << " ";
		it3++;
	}
	cout << endl;

	return 0;
}

 3.3查找 

//查找k,返回k所在的迭代器,没有找到返回end() 
iterator find(const key_type& k);
//查找k,返回k的个数 
size_type count(const key_type& k) const;
int main()
{
	//这里使用int()默认初始化为0
	map<string, int> mymap;
	mymap.insert({ "苹果",int() });
	mymap.insert({ "香蕉",int() });
	mymap.insert({ "西瓜",int() });
	mymap.insert({ "菠萝",int() });
	mymap.insert({ "苹果",int() });
	mymap.insert({ "柑橘",int() });
	mymap.insert({ "苹果",int() });
	auto it1 = mymap.begin();
	while (it1 != mymap.end())
	{
		cout << it1->first << ":" << it1->second << " ";
		it1++;
	}
	cout << endl;

	auto it = mymap.find("苹果");
	cout << it->first << ":" << it->second << endl;

	int count = mymap.count("苹果");
	if (count)
	{
		cout << "苹果存在" << endl;
	}
	else
	{
		cout << "苹果不存在" << endl;
	}

	return 0;
}

4.operatpr[]间接实现增删查改

1、如果k不在map中,insert会插⼊k和mapped_type默认值,同时[]返回结点中存储 mapped_type值的引⽤,那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊+修改功能

//operator[]
int main()
{
	map<int, string> mymap;
	mymap.insert({ 1,"first" });

	//1.原来的key不存在->插入+修改
	//key不存在->插入{2,""};
	mymap[2];

	//key不存在->插入+修改{3,"third"};
	mymap[3] = "third";

	return 0;
}

2、如果k在map中,insert会插⼊失败,但是insert返回pair对象的first是指向key结点的迭代器,返回值同时[]返回结点中存储mapped_type值的引⽤,所以[]具备了查找+修改的功能 

//operator[]
int main()
{
	map<int, string> mymap;
	mymap.insert({ 1,"first" });

	//2.原来的key存在->查找+修改
	//key存在->查找,但是必须确定要查找的元素一定存在
	cout << mymap[2] << endl;

	//key存在->修改
	mymap[3] = "third_change";
	cout << mymap[3] << endl;

	return 0;
}

5.multimap和map的差异

multimap和map的使⽤基本完全类似,主要区别点在于multimap⽀持关键值key冗余,那么 insert/find/count/erase都围绕着⽀持关键值key冗余有所差异,这⾥跟set和multiset完全⼀样,⽐如 find时,有多个key,返回中序第⼀个。其次就是multimap不⽀持[],因为⽀持key冗余,[]就只能⽀持插⼊了,不能⽀持修改 

6.实战代码练习

 138.随机链表的复制

思路解析:

本题的难点就是如何深拷贝一个随机链表,随机链表的定义就是每一个节点都有两个指针,一个指针next指向下一个节点,另一个随机指针指向任意节点,难点就是拷贝这两个指针

不过在学习了map后我们可以使用映射拷贝,即首先创建一个新的链表首先拷贝原链表以及next指针,然后将该链表存储在一个map中,使用每个节点本身当做key,random指针当做value,之后处理拷贝而来的新链表中的random指针,使用map中的key做映射,保证random在拷贝后链表中的相对位置与原链表的相同,最后返回拷贝而来的新链表的头结点

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) 
    {
        map<Node*,Node*> mapNode;
        Node* copyhead = nullptr;
        Node* copytail = nullptr;
        Node* cur = head;

        //拷贝原链表映射到map中并且创建一个新链表拷贝原链表
        while(cur)
        {
            //初始时刻
            if(copytail == nullptr)
            {
                copyhead = copytail = new Node(cur->val);
            }
            else
            {
                //从尾节点开始接入新节点
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            //映射拷贝到map中
            mapNode[cur] = copytail;
            cur = cur->next;
        }
        
        //处理random指针,copy与cur指针同时运动
        cur = head;
        Node* copy = copyhead;
        while(cur)
        {
            if(cur->random == nullptr)
            {
                copy->random = nullptr;
            }
            else
            {
                //使用映射处理random节点
                copy->random = mapNode[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};

 

标签:map,insert,面向对象,简析,key,pair,mymap,first
From: https://blog.csdn.net/2301_80689220/article/details/142444337

相关文章

  • std::vector 和 std::map 都支持以下比较运算符
    在C++标准库中,std::vector和std::map都支持以下比较运算符:==(相等运算符)!=(不等运算符)<(小于运算符)<=(小于等于运算符)>(大于运算符)>=(大于等于运算符)1.std::vector的比较对于std::vector,这些运算符通过词典序比较(lexicographicalcomparison)进行。词典序比较类似于字......
  • Java集合类面试题:Map接口(链表、HashMap、红黑树)
    收集大量Java经典面试题目......
  • map&unordered_map<key,value>key使用自定义类的要求
    std::unordered_map的键要求:std::unordered_map是基于哈希表的数据结构。它要求键类型必须支持哈希计算,也就是必须有对应的std::hash函数。另外,键类型还必须支持相等比较(通过operator==)。如果键类型没有定义哈希函数(例如你自定义的Json类型),std::unordered_map就无......
  • C10-05-1-Nmap常用参数说明
    一、Nmap免责声明本文仅是个人对该工具的学习测试过程记录,不具有恶意引导意向。本文工具仅面向合法授权的企业安全建设行为,如您需要测试本工具的可用性,请自行搭建靶机环境。在使用本工具进行检测时,您应确保该行为符合当地的法律法规,并且已经取得了足够的授权。请勿对非授......
  • 面向对象基本方法
    一、面向对象需求分析的相关概念对象在开发时会将人、物等都抽象为对象,人、物的特性会变成对象的属性,对象还有相关的操作方法,即这个人(物)在系统内部可以做些什么;对象由标识属性和服务构成,他们被封装为一个整体以接口的形式对外提供服务类将多个对象的共性抽取出来形成类,一个类......
  • 科研绘图系列:R语言树结构聚类热图(cluster heatmap)
    文章目录介绍加载R包导入数据数据预处理画图修改图形导出数据系统信息介绍热图结合树结构展示聚类结果通常用于展示数据集中的模式和关系,这种图形被称为聚类热图或层次聚类热图。在这种图中,热图部分显示了数据矩阵的颜色编码值,而树结构(通常称为树状图......
  • Java面向对象——内部类(成员内部类、静态内部类、局部内部类、匿名内部类,完整详解附有
    文章目录内部类17.1概述17.2成员内部类17.2.1获取成员内部类对象17.2.2成员内部类内存图17.3静态内部类17.4局部内部类17.5匿名内部类17.5.1概述内部类17.1概述写在一个类里面的类叫内部类,即在一个类的里面再定义一个类。如,A类的里面的定义B类,B类就称内部类......
  • Cpp学习 -- <unordered_map>
    参考网站https://www.runoob.com/cplusplus/cpp-libs-unordered_map.html#include<unordered_map>在C++中,<unordered_map>是标准模板库(STL)的一部分,提供了一种基于哈希表的键值对容器。与std::map不同,unordered_map不保证元素的排序,但通常提供更快的查找速度。unord......
  • INTERNAL ERROR: cannot create temporary directory! /dev/mapper/centos-root满了
    一.问题现象磁盘空间不足[root@dockerfileharbor]#docker-composeup-d[2216]INTERNALERROR:cannotcreatetemporarydirectory![root@dockerfileharbor]#docker-composeupstopFailedtowriteallbytesforcryptography/hazmat/bindings/_openssl.abi3.sofwrite......
  • C++: 使用红黑树模拟实现STL中的map和set
    目录1.红黑树的迭代器++和--2.改造红黑树3.set的模拟实现4.map的模拟实现5.RBTree的改造代码博客主页:酷酷学正文开始1.红黑树的迭代器迭代器的好处是可以方便遍历,是数据结构的底层实现与用户透明打开C++的源码我们可以发现,其实源码中的底层大概如下......