set和map(二)详解

map

map和set大部分都相似，只有insert插入键值对不同，insert要插入pair,pair中有key和value。erase和find只与key有关，其实insert也只与key有关，只是插入时要插入pair


删除一个pos位置，用find去找然后删除
删除一个数k,有就删除，没有也不报错
删除一段迭代器区间

operator[ ]的底层

mapped_type - > value
key_type->key
value_type->pair

• operator[ ]支持 插入，修改，查找
• 插入：没有的key就插入，不会报错
• 查找：insert插入成功返回新插入值所在的迭代器
  pair<新插入值所在的迭代器，true>
  insert插入失败返回已经存在跟key相等值的迭代器
  pair<已经存在跟key相等值的迭代器，false>
• 那么也就意味着insert插入失败时充当了查找的功能，正是因为这一点，insert可以用来实现operator[ ]
• 需要注意的是这里有两个pair，不要混淆了，一个是map底层红黑树节点中存的pair<key, T>，另一个是insert返回值pair<iterator,bool>

int main()
{
	// 利⽤find和iterator修改功能，统计⽔果出现的次数
	string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
	"苹果", "香蕉", "苹果", "香蕉" };
	map<string, int> countMap;
	for (const auto& str : arr)
	{
		countMap[str]++;

		// 先查找⽔果在不在map中
		// 1、不在，说明⽔果第⼀次出现，则插⼊{⽔果, 1}
		// 2、在，则查找到的节点中⽔果对应的次数++
		//auto ret = countMap.find(str);
		 找到返回对应的位置
		 没找到返回end()
		//if (ret == countMap.end())
		//{
		//	countMap.insert({ str, 1 });
		//}
		//else
		//{
		//	ret->second++;
		//}
	}

	for (const auto& e : countMap)
	{
		cout << e.first << ":" << e.second << endl;
	}
	cout << endl;

	return 0;
}

// operator的内部实现
mapped_type& operator[] (const key_type& k)
{
// 1、如果k不在map中，插入+修改
// 2、如果k在map中，查找+修改
pair<iterator, bool> ret = insert({ k, mapped_type() });
iterator it = ret.first;
return it->second;
}

ret是返回值的迭代器，通过这个迭代器去修改底层红黑树的value,达到修改的效果

operator[ ]使用的实例

int main()
{
	map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	// key不存在插入{"insert",string()}
	
	// 如果value是内置类型并且不给值,默认它的值是0
	// key不存在插入
	dict["string"];

	// key不存在->插入+修改
	dict["left"] = "左边";

	// key存在修改
	dict["left"] = "右边";

	// key存在查找,只有存在才能这么用,否则就是插入了
	cout << dict["left"] << endl;

	// 插入,因为right不存在
	cout << dict["right"] << endl;

	return 0;
}

multimap

允许插入相同的key,find查找的是中序的第一个，erase从中序的第一个开始删除（一直++），multimap不支持operator[ ]，因为有多个相同的key,不知道用哪个

int main()
{
	multimap<string, string> dict;
	dict.insert({ "string","字符串1" });
	dict.insert({ "string", "字符串2" });
	dict.insert({"string", "字符串3"});
	dict.insert({ "string", "字符串4" });
	dict.insert({ "string", "字符串" });
	dict.insert({ "sort", "排序" });

	dict.erase("string");

	return 0;
}

equal_range

找一段相等值的迭代器区间

[ )左闭右开的区间去找

两道题目

题目解析

题目链接

算法原理

• 建立这整个节点和拷贝出来的节点的映射关系，cur-copytail
  思路：先将原链表拷贝一份放入新的链表中，在这其中也建立cur节点和拷贝链表的映射关系（nodeMap[cur] = copytail）
  然后开一个新的指针遍历链表，将random指针进行链接，copy->random = nodeMap[cur->random]

代码

class Solution 
{
public:
    Node* copyRandomList(Node* head) 
    {
        // val和next,random这个节点是key,copytail是value
        // 构建key-value的映射关系
        map<Node*,Node*> nodeMap;
        Node* copytail = nullptr;
        Node* copyhead = nullptr;
        Node* cur = head;    
        while(cur)
        {
            if(copytail == nullptr)
            {
                copyhead = copytail = new Node(cur->val);
            }
            else
            {
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            // 建立映射关系 k-value
            nodeMap[cur] = copytail;
            cur = cur->next;
        }

        cur = head;
        Node* copy = copyhead;
        while(cur)
        {
            if(cur->random == nullptr)
            {
                copy->random = nullptr;
            }
            else
            {
                copy->random = nodeMap[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};

题目解析

题目链接

算法原理

pair比较的是first,second,其中一个小就小，先比较的是first,相等是两个相等才相等
map比较的是string的字典序，sort比较的是出现次数

代码

class Solution 
{
public:
    struct Compare
    {
        bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2)
        {
            return kv1.second > kv2.second;
        }

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

    };
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        map<string,int> countMap;
        // 字典序排序 + 统计次数
        for(auto& s : words)
        {
            countMap[s]++;
        }
        
        vector<pair<string,int>> v(countMap.begin(),countMap.end());
        // 仿函数比较实现次数的降序
        // sort排序是不稳定的
         stable_sort(v.begin(),v.end(),Compare());
       //  sort(v.begin(),v.end(),Compare());

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