【C++】map

map

可以看到，map也有map和multimap两种。

可以看到第一个参数Key是key，第二个T其实就是value。第三个参数可以看出只有Key参与比较，value不进行比较。

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

我们可以看到它的大框架与map是类似的。

迭代器也是双向的。

和set不同的：

[]的运算符重载支持修改

迭代器也支持修改value

pair

我们可以看到插入时的参数类型是value_type，而它的value_type是一个pair的东西，这是我们之前没有遇过的。

我们查看文档对于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));
}

怎么理解呢？

我们可以回顾一下之前的key/value的二叉搜索树的代码：

namespace key_value
{
	template<class K,class V>
	struct BSTNode
	{
		K _key;
		V _value;

		BSTNode<K,V>* _left;
		BSTNode<K,V>* _right; 

		BSTNode(const K& key,const V& value)
			:_key(key)
			,_value(value)
			, _left(nullptr)
			, _right(nullptr)
		{}

	};

	template<class K,class V>
	class BSTree
	{
		using Node = BSTNode<K,V>;
	public:
		bool Insert(const K& key,const V& value)
		{
			
			if (_root == nullptr)
			{
				_root = new Node(key,value);
				return true;
			}
			
			Node* parent = nullptr;
			Node* cur = _root;

			while (cur)
			{
				if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
					return false;//避免冗余
			}
			//到这里说明cur已经找到空位置了，但是不知道是从右走的还是往左走的，得再比一次
			cur = new Node(key,value);
			if (key < parent->_key)
			{
				parent->_left = cur;
			}
			else
			{
				parent->_right = cur;
			}
			return true;
		}

		void InOrder()
		{
			_InOrder(_root);
			cout << endl;
		}

		Node* Find(const K& key)//不再是返回布尔值
		{
			Node* cur = _root;
			while (cur)
			{
				if (key < cur->_key)
				{
					cur = cur->_left;
				}
				else if (key > cur->_key)
				{
					cur = cur->_right;
				}
				else
				{
					return cur;//返回结点指针，方便以后修改value
				}
			}
			return nullptr;
		}

		bool Erase(const K& key)
		{
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (key < cur->_key)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key)
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					if (cur->_left == nullptr)
					{
						//父为空，也就是说要删的是头结点
						if (parent == nullptr)
						{
							_root = cur->_right;
						}
						else
						{
							//要判断父节点的左还是右指针指向cur的孩子
							if (parent->_left == cur)
							{
								parent->_left = cur->_right;
							}
							else
							{
								parent->_right = cur->_right;
							}
						}
						delete cur;
						return true;
					}
					//cur的右孩子为空，把cur的左孩子给父
					else if (cur->_right == nullptr)
					{
						if (parent == nullptr)
						{
							_root = cur->_left;
						}
						else
						{
							//判断父节点的左还是右指针指向cur孩子
							if (parent->_left == cur)
							{
								parent->_left = cur->_left;
							}
							else
							{
								parent->_right = cur->_left;
							}
						}
						delete cur;
						return true;
					}
					else//现在是cur的左右孩子都不为空
					{
						//第一步，找R（这里采用cur的右子树的最小结点/也就是最左结点）
						Node* p = cur;//这里如果初始给空，后面如果不进循环，会造成对空指针的解引用
						Node* r = cur->_right;
						while (r->_left)
						{
							p = r;
							r = r->_left;
						}
						//第二步，进行交换(但不用真的把cur的值再去给r）
						cur->_key = r->_key;
						//第三步，删除R——很容易考虑不全面！！删除R又要把删除的问题考虑全面,但这里不能用递归，会找不到
						//在删除R时要把R的右孩子（只可能是右孩子）给给父，但是父的左还是右指针不确定
						if (p->_right == r)
						{
							p->_right = r->_right;
						}
						else
						{
							p->_left = r->_right;
						}
						delete r;
						return true;
					}
				}
			}

			return false;
		}

	private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
				return;
			_InOrder(root->_left);
			cout << root->_key << ":" << root->_value << endl;
			_InOrder(root->_right);
		}

		Node* _root = nullptr;
	};
}

可以看到，我们原来是将key和value分开来放的，在Node的类中有两个数据成员。现在我们pair是用一个结构体将两者合成一个对象。

所以原来我们在insert时也要两个参数：

话不多说，我们马上先来学着使用一下map

使用

insert

int main()
{
	map<string, string> dict;
	//几种插入数据的方式
	//1.定义有名pair对象
	pair<string, string> kv1("first", "第一个");
	dict.insert(kv1);
	//2.定义匿名pair对象
	dict.insert(pair<string,string>("second", "第二个"));
	//3.调用make_pair
	dict.insert(make_pair("third", "第三个"));

	return 0;
}

什么是make_pair？

这是一个库中自带的函数模版。因为pair写模版参数很烦所以这个函数就是用来简化这个的。

我们往map中插入时无论是第一种有名pair还是第二种匿名pair写起来都不够简单。

我们传参数它会自动推导出类型，构造对应的pair然后返回。可以看到返回值就是一个pair对象

它的底层实现大概是：

看看这俩

其实是等价的，对于dict来说都是插入pair对象

C++11还支持多参数的隐式类型转换，所以我们map还有第四种插入数据的方式，而且是最简单的一种：

//4.多参数隐式类型转换
dict.insert({ "fourth","第四个" });

编译器遇到连续构造+拷贝构造会优化成直接构造

这里const char*->string->pair，编译器会优化

提一嘴：pair<string,string> kv1("first","第一个");有用到隐式类型转换吗？

当构造pair对象时，string类型有接受const char *类型（C - 风格字符串）的构造函数。在这里，"first"和"第一个"这两个字符串字面量（它们的类型是const char *）被用来构造string对象，这一过程涉及到从const char *到string的类型转换。

这种类型转换不是隐式类型转换，因为string类的构造函数是被显式调用的，虽然从const char到string的转换看起来好像是自动进行的，但实际上是通过string类的构造函数完成的转换。

遍历

map的遍历会更复杂一点。

因为返回值不能有多个，所以我们也能理解为什么底层实现要使用pair来将key和value变成一个对象了。

我们解引用迭代器，map的迭代器里一般也是存着结点的指针，所以解引用迭代器应该要得到pair。

但是pair是没有重载流插入和流提取的。

所以这样是得不到我们想要的效果的。

因为pair的first和second是公有的，所以一种方式我们可以通过pair对象的成员访问运算符方式来得到（因为pair是个结构体）

map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
	cout << (*it).first << ":" << (*it).second << endl;
	++it;
}
cout << endl;

但是迭代器除了重载了*，还重载了->,什么时候用->？就是存储的是个结构体的时候。

迭代器的箭头其他迭代器都不太用但是map就很适用。

cout << it->first << ":" << it->second << endl;

但这里严格来说其实省略了一层箭头，原本应该是两个箭头。

我们说operator*是返回数据的引用，operator->是返回数据的指针，所以it.operator->()返回的是pair *，所以原本其实应该是it.operaotr->()->first

第一个箭头是运算符重载，第二个箭头就是结构体的解引用。

插入只看key，value不相等不会更新

可以看到，key相同value不同，再次插入，并不会更新value。

这是因为插入的时候只去看key是否相等。看到key相等后，不会去更新。

修改

first不能改，second可以改。

底层是用const实现的

支持initializer-list初始化

可以在花括号里写有名对象和匿名对象进行初始化，但是更爽的写法是直接initializer-list初始化。

map<string, string> dict = { {"first","第一个"},{"second","第二个"}, {"third","第三个"} };

相当于是走隐式类型转换。

上面说了，C++11后多参数构造函数支持隐式类型转换

优化后，构造+拷贝构造被简化为构造。

最后调用这个版本的构造。

所以，{“first”,“第一个”}被隐式类型转换为value_type，也就是pair<const key,T>

erase

可以看到有这三种删除方式：

给一个迭代器位置、给个k值、给个迭代器区间。

swap

只交换根节点的指针，效率高。

clear

把所有数据清掉

emplace

先不说

功能类似insert

find

find和erase一样，都只跟key有关，只有insert是跟两个值都有关。

count

一样的，可以用来快速判断在不在。

lower_bound/upper_bound

一个找左闭区间，一个找右开区间。

equal_range

这个之前在set没有讲，因为返回值是一个pair。

这个在set和map上其实都价值不大。

也就是返回跟b相等的左闭右开区间，所以得到的是

这个接口主要用于multi版本。

如果只有find，我们得一直++直到不是b才能找到下一个值的区间，会很麻烦。

当然，这个接口底层也就是这么做的。

可以看出map的接口和set还是非常相似的。

不同之处

统计次数

[]重载

我们在讲二叉搜索树（下）的key_value结构时就讲过查找水果出现次数这样的代码：

但其实这种统计次数的方法并不算很常用

因为我们有一行代码解决的方式：

for(const auto& str : arr)
{
    countMap[str]++;
}

这个方括号是怎么做到统计次数的呢？

以前我们遇到的[]重载是实现像数组一样去访问，而这里我们遇到的这个方括号已经改变了[]传统的意思

这里是给key，返回value，并且返回的是引用也就是说可以修改

注意不要搞混这几个type

mapped_type才是我们说的value值，而value_type时那个pair

这是一个很综合的接口，因为给key返回value所以可以查找，又因为是引用所以可以修改，但是也可以用于插入。三重功能。

当给的key不存在时，就变成了插入功能。

可以看到insert，所以我们再把insert重新深入一下

insert

insert的返回值又是一个pair

所以除了键值对，如果有其他的两个想存储也可以用pair

文档里对insert返回值的说明：

第一个版本的insert：

我们看到有对返回值的pair的第一个参数的迭代器的说明：这个迭代器要么是插入成功后，指向那个插入的结点，要么是指向插入失败后，已经存在的那个key相同的结点。（因为map不支持键值冗余）

所以这个insert除了充当了插入的功能，还充当了查找的功能

展开来说[]的底层实现：

所以我们再回来看看刚才是怎么做到统计次数的：

str不存在时，是用到了插入+修改的功能来统计次数的。苹果不存在就把苹果先插入进去，次数是缺省值mapped_type()，是0次，返回second是次数，但是因为countMap[str]++;所以次数变为1，正确的；

str存在时，充当的就是查找+修改功能来统计次数。因为存在，insert失败了，充当的是查找到这个key值的迭代器，然后我们返回它的value也就是次数进行返回，++，也正确了。

确实有些绕，因为有两个pair。

梳理[]的几种功能：

其中单纯查找时一定要确认这个值是在的，否则就会不小心把这个值插入了！

在python中，如果这个值不在，就不能用[]。

multimap和map的差别

multimap的插入一定成功，除非没有内存了。

插入时不管key和value相同，通通插入。

erase

和multiset一样，会把一连串key相同全部删除。

也是找到中序第一个然后往后连续删除（找中序第一个的价值又体现了）

没有[]

这是mutimap的一个与map的很大区别

因为它的[]确实也没法实现

因为给key要返回value

但是有多个key，不知道返回哪个value

find

查找中序的第一个

equal_range

multimap用这个就很有意义了

给它一个值，可以给出一段区间

但可能也用的比较少。

map题目

学map之前C语言写的版本：
代码参考：

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
Node* BuyNode(int x)//创建结点
{
    Node* newnode = (Node*)malloc(sizeof(Node));
 /*   if (newnode == NULL)
    {
        perror("malloc fail!");
        return NULL;
    }*/
    newnode->val = x;
    newnode->next = newnode->random = NULL;
    return newnode;
}
void CopyNode(Node* phead)//赋值链表
{
    Node* pcur = phead;
    while (pcur != NULL)
    {
        Node* newnode = BuyNode(pcur->val);
        newnode->next = pcur->next;//没创建Next，直接这样生写了
        pcur->next = newnode;

        pcur = newnode->next;//往后走
    }
}
void RandomSet(Node* head)//置random指针
{
    Node* pcur = head;
    Node* copy = head->next;
    while (pcur!=NULL)
    {
        Node* copy=pcur->next;
        if(pcur->random != NULL)
        {
            copy->random=pcur->random->next;
        }
        pcur = copy->next;
        
    }
}
struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)
        return NULL;
    //先复制链表
    CopyNode(head);
    //置random指针
    RandomSet(head);
    //断开原链表和新链表——没封装了
    Node* pcur = head;
    Node* newtail = head->next;
    Node* newhead = head->next;
    while (newtail->next!=NULL)///这个地方尤其要注意！！！
    {
        pcur=newtail->next;//
        newtail->next=pcur->next;
        newtail=newtail->next;
    }
    return newhead;
}

**解释：**这种方法就是在每个原结点之后复制一个和原节点存的值相同的新节点，并将原结点的next指针指向这个新节点，这个新节点的next指向原结点原本next指向的结点。

这个步骤做完后，我们再来置新链表的random指针，这也是最关键的一步，新节点的random就是原来结点的random的next（注意防范空指针解引用的问题），原来结点的random就是我们新链表该结点映射的random位置，而它的next恰好就是复制它本身的新链表中的对应结点，所以这样我们就找到新链表结点的random。

但这种将原链表与新链表先连成一体再将新链表拆下来的方法要想到挺难的。

我们的目标是在找拷贝的结点的random时要对应原结点的random，所以我们需要一种映射关系，而这正是map的特点。

这里我们直接让{原结点，拷贝结点}建立映射关系放到map中，控制随机指针会很方便，这也体现了map在解决一些问题时的降维打击。

map版本参考代码：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*,Node*> m;
        Node* cur = head;
        Node* newhead=NULL;
        Node* parent = NULL;
        while(cur!=NULL)
        {
            Node* copy = new Node(cur->val);
            
            m[cur]=copy;
            if(parent==NULL)
            {
                newhead=copy;
                parent=copy;   
            }
            else
            {
                parent->next=copy;
                parent=copy;
            }
            cur=cur->next;
        }
        Node* ncur = newhead;
        //置random
        cur=head;
        while(cur!=NULL)
        {
            ncur->random=m[cur->random];