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所对应的pairmymap.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()默认初始化为0map<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;}
};