【C++指南】你真的了解map和set吗？【下】

map系列的使用

Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key⽀持大小⽐较。

map底层存储数据的内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。map底层是⽤红⿊树实 现，增删查改效率是 O(logN) ，迭代器遍历是⾛的中序，所以是按key有序顺序遍历的。

template < class Key,class T,class Compare = less<Key>,
           class Alloc = allocator<pair<const Key,T> >>

了解pair

map系列中并未像之前在实现二叉搜索树中在结构体中存储Key/Value，而是把它们封装在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)
    {}
};

构造及迭代器

增删查

可以看到，stl库设计尽量保持接口一致，如上插入接口中，返回类型依旧是pair<iterator,bool>。

在下面一段程序中，我们通过map一系列接口的设计完成了对arr数组中的字符串的计数。

int main()
{
	string arr[] = { "苹果","香蕉","菠萝","苹果","香蕉" ,"苹果" ,"菠萝","苹果" };
	map<string, int> countmap;
	for (auto& ch : arr)
	{
		auto it = countmap.find(ch);
		if (it == countmap.end())
		{
			countmap.insert({ ch,1 });
		}
		else
		{
			it->second++;
		}
	}
	for (auto& ch : countmap)
	{
		cout << ch.first << " " << ch.second << endl;
	}
}

数据修改

我们清楚无论在map还是set系列都是不允许修改Key值的，因此这里的数据修改指的是修改Value值。可以这样想，在现实生活中，一个英文单词可以对应多个中文意思。

mapped_type& operator[] (const key_type& k)

这里的mapped_type实际就是Value值。

map的 [ ] 看起来高大上，实际上底层就是一个套了insert的壳，是如何实现的呢？

小编这里简化了主要的代码实现。

V& operator[](const K& key)
{
	pair<iterator, bool> ret = insert({ key, V() });
	return ret.first->second;
    //  *(ret.first).second//*引用指针，再指向值
}

开始看return返回值时可能会一头雾水，ret是pair的对象，那么ret.first访问的应该是pair中的Key值，后面的second又是什么意思呢？

这里其实是有两层含义的，首先ret是一个对象，ret.first访问的是迭代器iterator,进而ret.first->second访问pair中的Value值，实际是ret.first.operator->()->second访问指针指向的second的值。

[ ]的用法

	//[]的插入
	ret["left"];

	//[]的插入+修改
	ret["right"] = "右边";

	//[]的修改
	ret["left"] = "左边";

	//[]的查找
	cout << ret["left"] << endl;

[ ] 统计次数

在上文中实现了一个对出现单词的频率的计数，那是否可以用map中的[]接口的设计进行完善呢？

map<string, int> countmap;

for (auto& ch : arr)
{
    countmap[ch]++;
}

是的你没看错，只需要使用[]就能完成单词的计数，那它是如何达到我们的目的的呢？

1. 开始，map中没有存储数据，此时[]插入会成功，更新迭代器位置，返回Value值并进行++，此时Value为1；
2. 下一个数据如果在map中出现过，会插入失败，不更新迭代器位置，但是依旧会返回Value并进行++；
3. 综上两种情况，每出现一个单词都会对对应单词进行计数。

multimap

multimap版本是支持冗余的，那么insert/find/count/erase都围绕着⽀持关键值key冗余有所差异。

需要注意的是multimap并不支持 [ ] 接口，因为Key是支持冗余的，[] 操作符的设计初衷是返回一个唯一值，若键存在，它会返回该键对应的值 。如果多个相同的Key可能存在不同的Value会导致 [ ] 接口语义模糊不清。

博主通过以下习题让大火感谢下map系列的用处。

随机链表的复制

之前在实现随机链表的复制时，我们需要将每个结点都进行拷贝，通过旧链表进行random的链接，最后还要断开新旧链表，实现的步骤是非常麻烦的。

但学了map容器后，此题可以通过map中的映射关系，完成对随机链表的复制。

1. 通过map存储新旧结点并实现映射关系，方便之后处理random。
2. 通过[]接口设计完成对拷贝随机链表中random的链接。

Node* copyRandomList(Node* head) {
        Node* cur=head;
        map<Node*,Node*> nodemap;//存在映射关系
        Node* phead=nullptr,*ptail=nullptr;
        while(cur)
        {
            if(ptail==nullptr)
            {
                phead=ptail=new Node(cur->val);
            }
            else
            {
                ptail->next=new Node(cur->val);
                ptail=ptail->next;
            }
            nodemap[cur]=ptail;
            cur=cur->next;
        }

        //完成主逻辑
        cur=head;
        Node* ret=phead;
        while(cur)
        {
            if(cur->random==nullptr)
            {
                ret->random=nullptr;
            }
            else
            {
                ret->random=nodemap[cur->random];
            }
            ret=ret->next;
            cur=cur->next;
        }
        return phead;
    }

前K个高频单词（重点）

按此题要求会有以下情况：

1. 如何对每个单词计数？
2. 需要返回k个出现次数最多的单词，需要进行排序？用什么排序？
3. 单词频率相同情况下，如何处理？

解决方法：

1. 有map[]的接口可以实现对每个单词进行计数；
2. 使用multimap实现；用稳定排序(归并排序)；使用快排；用堆排序，那应该建大根堆还是小根堆？
3. 在使用快排时会出现一些问题，需要自己实现仿函数控制，在下面小编会谈及。

对单词频率进行计数后，想再通过map来对前k个高频单词记录在vector中，但是会出现一个问题：可能不同单词出现的频率是一样的，由于map不支持冗余，会导致之后出现频率相同的单词不被记录。因此，在这里使用multimap，first存的是次数，second存字符串。

multimap实现

        //记录次数
        map<string,int> countmap;
        for(auto& ch:words)
            countmap[ch]++;

        //使用multimap来完成
        multimap<int,string,greater<int>> mtmap;//完成降序
        for(auto& ch:countmap)
        {
            mtmap.insert({ch.second,ch.first});
        }

        vector<string> v;
        auto it=mtmap.begin();
        while(k--)
        {
            v.push_back(it->second);
            it++;
        }
        return v;

此题对应TopK问题，我们一般采用排序来处理问题。

要求的是返回前k个频率高的单词，而频率count存在map中的second，因此在使用排序时需要自己手动实现仿函数比较second。

快排(错误示例)

        bool operator()(const pair<string,int>& v1,const pair<string,int>& v2)
        {
            return v1.second>v2.second;
        }

        //记录次数
        map<string,int> countmap;
        for(auto& ch:words)
            countmap[ch]++;

        vector<pair<string,int>> v(countmap.begin(),countmap.end());

        vector<string> ret;
        sort(v.begin(),v.end(),vcompare()); //需要手动实现仿函数

        for(int i=0;i<k;i++)
        {
            ret.push_back(v[i].first);
        }
        return ret;

但是提交后会报错，这是为什么？

原因在于快排是一个不稳定的排序,何为不稳定？

稳定性：在待排序的序列中经过排序后，若相对排序保持不变，则称这种算法是稳定的；反之，相对顺序改变是不稳定的。

在std库中提供了稳定的排序(底层是归并排序)

stable_sort(v.begin(),v.end(),vcompare());

如果非要使用快排呢？可以通过调整仿函数实现目的。

我们需要解决的问题便是当单词出现频率相同时，如何按字典序排序。那么在仿函数中控制字典序排序的逻辑就能达到目的。

bool operator()(const pair<string,int>& v1,const pair<string,int>& v2)
{
    return (v1.second>v2.second||(v1.second==v2.second&&v1.first<v2.first));
}

在TopK问题中，我们一般采用堆排序来解决问题。那何时使用大根堆，何时使用小根堆呢？

1. 在面临数据量较小情况下，如果是取前k个降序元素时，一般使用大根堆；
2. 在处理海量数据时，如果是取前k个降序元素，一般使用小根堆。

需要注意的是，stl模板库中priority_queue的默认传的是less仿函数，理应是升序，但这里比较特殊 --> 排的是降序（槽点），因此仿函数的逻辑得反着来。

        bool operator()(const pair<string,int>& v1,const pair<string,int>& v2)
        {
            //次数相等的，字典序在前面
            return (v1.second<v2.second||(v1.second==v2.second&&v1.first>v2.first));
        }

        map<string,int> countmap;
        for(auto& ch:words)
            countmap[ch]++;

        // 将map中的<单词，次数>放到priority_queue中，仿函数控制⼤堆，次数相同按照字典
        priority_queue<pair<string, int>, vector<pair<string, int>>, vcompare> 
            p(countmap.begin(), countmap.end());
        vector<string> strV;   
        for(int i = 0; i < k; ++i)
        {
            strV.push_back(p.top().first);
            p.pop();
        }
        return strV;