24.map和set的使用
可以看到，operator[]内部调用insert，insert返回一个pair<iterator,bool>的结构，插入成功，pair.second为true，反之为false，pair.first为key位置所在的迭代器，operator[]返回该迭代器位置的value的引用。对于C++，简单很多，只需要将定义一个节点指针cur从头开始走，插入到set中，直到set插入失败，即回到环的开始节点
一、序列式容器和关联式容器
序列式容器：逻辑结构为线性序列的容器，两个位置所存放的数据一般没有紧密关系，例如两个位置交换一下，逻辑结构没有改变。
关联式容器：通常是非线性结构（堆例外），两个位置存放数据有紧密的关联关系，交换一下逻辑结构就改变了。
常见的序列式容器：string，vector，list，deque，array，forward_list
常见的关联式容器：map/set系列和unordered_map/unordered_set系列
map（key/value）和 set（key），底层是红黑树，红黑树是一颗平衡二叉搜索树。
易错点1：
map可以是升序，也可是降序，默认情况下是升序，如果需要降序，需要用户在实例化map时指定比较规则。
set中可以存储键值对，实例化set时，将set中元素类型设置为pair即可。
二、set的介绍
template < class T , // set::key_type/value_typeclass Compare = less<T>, // set::key_compare/value_compareclass Alloc = allocator<T> // set::allocator_type> class set;1.set默认T支持小于比较，若不支持或要改变比较逻辑要显式传仿函数。2.set增删查时间复杂度是O(logN)，迭代器遍历走的是搜索树的中序，即有序序列。
set的构造函数
empty (1) explicit set (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());range (2) template <class InputIterator> set (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());copy (3) 1）默认构造
2）迭代器区间构造
3）拷贝构造
set的迭代器是双向迭代器。
iterator a bidirectional iterator to value_type convertible to const_iterator const_iterator a bidirectional iterator to const value_type
Modifiers:
insert:
// 单个数据插⼊，如果已经存在则插⼊失败pair<iterator, bool > insert ( const value_type& val);// 列表插⼊，已经在容器中存在的值不会插⼊void insert (initializer_list<value_type> il);// 迭代器区间插⼊，已经在容器中存在的值不会插⼊template < class InputIterator >void insert (InputIterator first, InputIterator last);
erase:
1）删除迭代器位置，返回删除后中序遍历下一个位置的迭代器
(1) (2) (3)
2）删除val，删除了返回1，没有删除返回0
3）删除一段迭代器区间
注：erase()一个迭代器后，迭代器就失效了
原因：
1.如果该节点是叶子节点，或者左右子树有一为空的节点，会被直接删除，导致野指针的问题，迭代器失效了。
2.如果该节点的左右子树都不为空，会使用替换删除，虽然该节点没有被释放掉，但是意义变了，也认为迭代器失效了。
find和count
// 查找 val ，返回 val 所在的迭代器，没有找到返回 end()iterator find ( const value_type& val);// 查找 val ，返回 Val 的个数，通常用于查找size_type count ( const value_type& val) const ;
lower_bound和upper_bound
// 返回大于等val位置的迭代器
iterator lower_bound (const value_type& val) const;
// 返回大于val位置的迭代器
iterator upper_bound (const value_type& val) const;void test_set1() { set<int> s({ 10,20,30,40,50,60,70,80,90,100 }); //若要得到[20,55]区间的值 //lower_bound闭区间，upper_bound开区间 set<int>::iterator bit = s.lower_bound(20); set<int>::iterator eit = s.upper_bound(50); while(bit != eit) { cout << *bit << " "; ++bit; } cout << endl; }
lower_bound返回大于等于key的值，upper_bound返回大于key的值。
mutiset和set的区别：
find的示例，特别注意，++mit是按中序遍历走，有序序列的方式走，不会错过。
和set不同的是，count不只是返回0和1，而是可能有多个，erase删除key值也是删除所有key值。
set的使用场景（两个OJ题）：
349. 两个数组的交集 - 力扣（LeetCode）
思路：使用两个set达到排序和去重的效果，然后遍历两个set，输出有序序列，如果两个值相等，vector尾插这个值，两个迭代器都走；如果两个值不相等，值小的迭代器走，因为值大的后面没有比值小的更小了。拓展：若所求的是差集，那么遇到相等的跳过，两个迭代器都走；如果两个值不相等，值小的vector尾插这个值，值小的迭代器走，因为值大的后面没有比值小的更小了，值小的就是差集；如有一迭代器走完了，另一迭代器没走完的部分全是差集。
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> s1,s2; for(const auto& ch:nums1) { s1.insert(ch); } for(const auto& ch:nums2) { s2.insert(ch); } vector<int> v; set<int>::iterator it1 = s1.begin(); set<int>::iterator it2 = s2.begin(); while(it1!=s1.end() && it2!=s2.end()) { if(*it1==*it2) { v.push_back(*it1); ++it1; ++it2; } //小的走，因为大的后面没有比这小的了 else if(*it1>*it2) { ++it2; } else { ++it1; } } return v; } };给定一个链表的头节点
head，返回链表开始入环的第一个节点。 如果链表无环，则返回null。对于环形链表，用C语言解决的话有两种方式：
定义两个指针，慢指针一次走1步，快指针一次走2步或者3步，它们一定会相遇在环内部的一个节点，将这个节点记录为相遇节点。
1.在相遇节点处断开，然后就转化成了链表相交的问题，长链表从头走到和短链表一样长的位置，然后找到相交节点，由于题目本身不让破坏节点，最后相遇节点链接回去。
2.定义两个指针一个从头开始走，另一个从链表相交位置开始走，它们一定会在入口节点相遇，证明法。
对于C++，简单很多，只需要将定义一个节点指针cur从头开始走，插入到set中，直到set插入失败，即回到环的开始节点了，此时插入失败的节点指针就是入环的第一个节点。
class Solution { public: ListNode *detectCycle(ListNode *head) { set<ListNode*> s; ListNode* cur = head; while(cur) { pair<set<ListNode*>::iterator,bool> ret = s.insert(cur); if(ret.second==false) return cur; cur = cur->next; } return nullptr; } };
三、map系列的使用
map的声明
map底层也是红黑树，key-value模型，按key比较。
template < class Key, // map::key_type class T, // map::mapped_type class Compare = less<Key>, // map::key_compare class Alloc = allocator<pair<const Key,T> > // map::allocator_type > class map;map增删查改的效率是O(logN)。
pair结构
template <class T1, class T2> struct 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) ); }
member type definition notes key_type The first template parameter (Key) mapped_type The second template parameter (T) value_type pair<const key_type,mapped_type>
在map中，pair<const key_value,mapped_typed>被重命名为了value_type，第一个是const key，第二个是value，用了一个结构pair封装。
map的构造函数
// empty (1) ⽆参默认构造explicit map ( const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());// range (2) 迭代器区间构造template < class InputIterator >map (InputIterator first, InputIterator last,const key_compare& comp = key_compare (),const allocator_type& = allocator_type ());// copy (3) 拷⻉构造map ( const map& x);// initializer list (5) initializer 列表构造map (initializer_list<value_type> il,const key_compare& comp = key_compare (),const allocator_type& alloc = allocator_type ());// 迭代器是⼀个双向迭代器iterator -> a bidirectional iterator to const value_type// 正向迭代器iterator begin ();iterator end ();// 反向迭代器reverse_iterator rbegin ();reverse_iterator rend ();
map具体案例1：
void test_map1() { map<string, string> m({ {"sort","排序"},{"left","左边"} }); //多参数的隐式类型转换,C++11 // "right","右边"隐式类型转换成string //{string,string}隐式类型转换成pair<const string,string> m.insert({ "right","右边" }); //利用make_pair创建一个pair<const string,string>的匿名对象 m.insert(make_pair("right", "右边")); }map可以用初始化列表初始化，C++11支持多参数的隐式类型转换，用{}括起来。
map具体案例2：
void test_map2() { map<string, string> m({ {"sort","排序"},{"left","左边"} }); map<string, string>::iterator it = m.begin(); while (it != m.end()) { //注意it所指向的对象是一个pair结构的，不能直接解引用访问 cout << it->first << ":" << it->second << endl; ++it; } cout << endl; }注意map的迭代器指向的是一个pair结构，不能直接解引用访问。
map具体案例3：
void test_map3() { map<string, string> m({ {"sort","排序"},{"left","左边"} }); //insert一个已经存在的key，不会做任何修改 m.insert({ "left","剩余" }); for (const auto& ch : m) { cout << ch.first << ":" << ch.second << endl; } cout << endl; }
易错点：insert一个已经存在的key值，不会做任何修改。
map的增删查接口：
Member types key_type -> The first template parameter (Key) mapped_type -> The second template parameter (T) value_type -> pair<const key_type,mapped_type> // 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败 pair<iterator,bool> insert (const value_type& val); // 列表插⼊，已经在容器中存在的值不会插⼊ void insert (initializer_list<value_type> il); // 迭代器区间插⼊，已经在容器中存在的值不会插⼊ template <class InputIterator> void insert (InputIterator first, InputIterator last); // 查找k，返回k所在的迭代器，没有找到返回end() iterator find (const key_type& k); // 查找k，返回k的个数 size_type count (const key_type& k) const; // 删除⼀个迭代器位置的值 iterator erase (const_iterator position); // 删除k，k存在返回0，存在返回1 size_type erase (const key_type& k); // 删除⼀段迭代器区间的值 iterator erase (const_iterator first, const_iterator last); // 返回⼤于等k位置的迭代器 iterator lower_bound (const key_type& k); // 返回⼤于k位置的迭代器 const_iterator lower_bound (const key_type& k) const;
map具体案例4和5：
void test_map4() { // 利用find和iterator修改功能，统计水果出现的次数 string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> m; //插入数据 for (const string& s : arr) { m.insert({ s,0 }); } map<string, int>::iterator it; //再次遍历一遍arr // 用find查找对应key位置的迭代器，使value++ for (const string& s : arr) { it = m.find(s); it->second++; } for (const auto& ch : m) { cout << ch.first << ":" << ch.second << endl; } cout << endl; }这里利用find和iterator修改功能，统计水果出现的次数。但是这种写法太麻烦了，要遍历两便arr数组可改为以下写法：
void test_map5() { string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> m; //operator[]有插入，查找，修改三种功能 //key不存在，插入数据，返回value的引用，修改数据 //key存在，根据key查找，返回value的引用，修改数据 for (const string& s : arr) { m[s]++; } for (const auto& ch : m) { cout << ch.first << ":" << ch.second << endl; } cout << endl; }
operator[]的作用：插入，查找，修改。
1.key不存在，插入（期间会调用value的默认构造），返回value的引用。
2.key存在，查找，返回value的引用。
pair<iterator, bool > insert ( const value_type& val);mapped_type& operator [] ( const key_type& k);// operator 的内部实现mapped_type& operator [] ( const key_type& k){// 1、如果 k 不在 map 中， insert 会插⼊ k 和 mapped_type 默认值，同时 [] 返回结点中存储mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以 [] 具备了插⼊ + 修改功能// 2、如果 k 在 map 中， insert 会插⼊失败，但是 insert 返回 pair 对象的 first 是指向 key 结点的 迭代器，返回值同时 [] 返回结点中存储 mapped_type 值的引⽤，所以 [] 具备了查找 + 修改的功能pair<iterator, bool > ret = insert ({ k, mapped_type () });iterator it = ret.first;return it->second;}可以看到，operator[]内部调用insert，insert返回一个pair<iterator,bool>的结构，插入成功，pair.second为true，反之为false，pair.first为key位置所在的迭代器，operator[]返回该迭代器位置的value的引用。
mutimap和map的区别：
void test_mutimap1() { multimap<string, string> m({ {"sort","排序"},{"left","左边"} }); m.insert({ "left","剩余" }); for (const auto& s : m) { cout << s.first << ":" << s.second << endl; } cout << endl; m.erase("left"); for (const auto& s : m) { cout << s.first << ":" << s.second << endl; } cout << endl; }
multimap允许key值冗余，insert一定成功。
erase()删除所有key。
equal_range()
pair<const_iterator,const_iterator> equal_range (const key_type& k) const; pair<iterator,iterator> equal_range (const key_type& k);返回pair结构封装的迭代器区间，左闭右开。
两个OJ题：
若按C语言做，思路如下：
随机指针是原链表节点之间的关系，要使拷贝链表也具有这种关系，在每个原链表节点位置将拷贝节点插入到原链表节点的后面。
1）遍历一遍原链表，在每个原链表节点后复制一个节点插入到节点后面
2）再次遍历一遍链表，复制随机指针
3）再次遍历一遍链表，将复制链表取下来
按C++做，思路如下：
定义一个map<ListNode*,ListNode*>，key存原链表节点指针，value存现拷贝链表的指针。这样原链表节点的映射关系，拷贝链表也有了。
1）遍历一遍原链表，原链表指针作为key插入，new出来的拷贝链表指针的val和next赋值为原链表节点中对应的值
2）遍历两个链表，将节点指针插入进map
3）遍历一遍map，如果key->random为nullptr，value->random也为nullptr；如果key->random不为空，value->random = map[key->random]; 。
class Solution { public: Node* copyRandomList(Node* head) { map<Node*,Node*> m; Node* cur = head; Node *copyhead,*tail; copyhead = tail = nullptr; //1.复制链表的值和next指针 while(cur) { Node* newnode = new Node(cur->val); if(copyhead==nullptr) { tail = copyhead = newnode; } else { tail->next = newnode; tail = tail->next; } cur = cur->next; } //2.插入到map中 cur = head; Node* copycur = copyhead; while(cur && copycur) { m.insert({cur,copycur}); cur = cur->next; copycur = copycur->next; } //3.复制random指针 map<Node*,Node*>::iterator it = m.begin(); while(it!=m.end()) { if(it->first->random==nullptr) { it->second->random = nullptr; } else { it->second->random = m[it->first->random]; } ++it; } return copyhead; } };
思路1：将单词插入map中统计单词出现的次数，然后转入vector，对vector按次数排序，取出vector里的前k个高频单词。
注意点：map中默认是按单词string排了字典序，因此用vector排序时：
1）用稳定的排序。
2）使用sort，比较逻辑中特殊处理：对于出现次数相同的单词按字典序比较。
思路2：将单词插入map中统计单词出现的次数，然后转入priority_queue，比较逻辑特殊处理：对于出现次数相同的单词按字典序比较，取出priority_queue的前k个高频单词。
第一种：
class Solution { public: struct great { bool operator()(const pair<string,int>& p1,const pair<string,int>& p2) { return p1.second > p2.second; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string,int> m; for(const string& s:words) { //若不存在，插入，返回插入位置value的引用 //若存在，查找，返回key位置value的引用 m[s]++; } //转入vector中 vector<pair<string,int>> v(m.begin(),m.end()); //按降序排列 stable_sort(v.begin(),v.end(),great()); vector<string> ret; for(size_t i = 0;i<k;++i) { ret.push_back(v[i].first); } return ret; } };第二种：
class Solution { public: struct great { bool operator()(const pair<string,int>& p1,const pair<string,int>& p2) { return p1.second > p2.second || (p1.second==p2.second && p1.first < p2.first); } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string,int> m; for(const string& s:words) { //若不存在，插入，返回插入位置value的引用 //若存在，查找，返回key位置value的引用 m[s]++; } //转入vector中 vector<pair<string,int>> v(m.begin(),m.end()); //按降序排列 sort(v.begin(),v.end(),great()); vector<string> ret; for(size_t i = 0;i<k;++i) { ret.push_back(v[i].first); } return ret; } };第三种：
class Solution { public: struct less { bool operator()(const pair<string,int>& p1,const pair<string,int>& p2) { return p1.second < p2.second || (p1.second==p2.second && p1.first > p2.first); } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string,int> m; for(const string& s:words) { //若不存在，插入，返回插入位置value的引用 //若存在，查找，返回key位置value的引用 m[s]++; } //转入priority_queue中 priority_queue<pair<string,int>,vector<pair<string,int>>,less> q(m.begin(),m.end()); vector<string> ret; for(size_t i = 0;i<k;++i) { ret.push_back(q.top().first); q.pop(); } return ret; } };注意正常的大小堆的逻辑与大于小于相反，less排大堆，great排小堆。
这里也可转化成topK问题，建立一个大小为k的小堆，大堆每次插入时与小堆的堆顶比较，如果比小堆的堆顶大，就插入（如果满了就替换堆顶），然后调整。最后取出来的小堆的逆序就是topK。
欢迎加入DeepSeek 技术社区。在这里，你可以找到志同道合的朋友，共同探索AI技术的奥秘。
更多推荐
16
0- 0
已为社区贡献1条内容
所有评论(0)