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