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

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

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)
    {}
};

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值。可以这样想，在现实生活中，一个英文单词可以对应多个中文意思。

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

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

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

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

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

map<string, int> countmap;

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

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;
    }

        //记录次数
        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;

        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;

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));
}

        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;