-
set和map的学习
0.底层实现
二叉平衡搜索树[具体见后期文章]
1.set的原型
template < class T, //set::key_type class Compare = less<T>, //set::key_compare class Alloc = allocator<T> //set::allocator_type > class set;- 1
- 2
- 3
- 4
- 5
- 6
2.set的成员函数
1.构造函数
//全缺省构造 explicit set(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); //迭代器区间构造 template <class InputIterator> set(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); //拷贝构造 set(const set& x);- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.代码演示
//插入、迭代器、范围for void test_set1() { //初始化1.0 set<int> s; s.insert(3); s.insert(1); s.insert(4); s.insert(2); s.insert(1); s.insert(2); //初始化2.0 //sets = { 1,2,1 }; //sets(a, a + sizeof(a) / sizeof(int)); set<int>::iterator it = s.begin(); while (it != s.end()) { // 二叉搜索树不允许修改key--破坏二叉搜索树的原则 cout << *it << " "; ++it; } cout << endl; // 范围for for (auto e : s) { cout << e << " "; } cout << endl; //set遍历后数据变成有序的 -- 搜索二叉树中序遍历 -- 有序数据 } //erase 查找是否存在:find/count 删除某个范围的值 void test_set2() { set<int> s; s.insert(3); s.insert(1); s.insert(4); s.insert(2); s.insert(1); s.insert(2); s.erase(30); //erase的底层 auto pos = s.find(30); if (pos != s.end()) { s.erase(pos); } int x; while (cin >> x) { /* auto ret = s.find(x); if (ret != s.end()) { cout << "yes" << endl; } else { cout << "no" << endl; } */ //count在set里的取值: 1 0 if (s.count(x)) { cout << "yes" << endl; } else { cout << "no" << endl; } } set<int> s1; set<int>::iterator itlow, itup; for (int i = 1; i < 10; i++) s1.insert(i * 10); //10 20 30 40 50 60 70 80 90 itlow = s1.lower_bound(25); //记录25或25后一个元素 itup = s1.upper_bound(60); //记录55后一个元素的位置 s1.erase(itlow, itup); //[ , ) cout << "s1 contains:"; for (auto it = s1.begin(); it != s1.end(); ++it) cout << ' ' << *it; cout << '\n'; } //多重set：multiset 允许键值冗余[重复] void test_set3() { multiset<int> ms; ms.insert(3); ms.insert(1); ms.insert(4); ms.insert(2); ms.insert(1); ms.insert(1); ms.insert(1); ms.insert(2); multiset<int>::iterator mit = ms.begin(); while (mit != ms.end()) { cout << *mit << " "; ++mit; } cout << endl; //中序遍历的第一个x auto pos = ms.find(1); while (pos != ms.end() && *pos == 1) { cout << *pos << " "; ++pos; } cout << endl; cout << "1的个数" << ms.count(1) << endl; ms.erase(1); //删除所有的1 cout << "1的个数" << ms.count(1) << endl; cout << "2的个数" << ms.count(2) << endl; //删除第1个3 auto pos = ms.find(3); if (pos != ms.end()) { ms.erase(pos); } //删除第2个3 ++pos; if (pos != ms.end()) { ms.erase(pos); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
3.map的原型
template < class Key, // key_type class T, // mapped_type class Compare = less<Key>, //key_compare class Alloc = allocator<pair<const Key,T> > // allocator_type > class map;- 1
- 2
- 3
- 4
- 5
- 6
- 7
4.map的成员函数
1.构造函数
//全缺省默认构造 explicit map(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); //迭代器区间构造 template <class InputIterator> map(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); //拷贝构造 map(const map& x);- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.代码演示
/* templatestruct pair { T1 _key; T2 _value; pair() : _key(T1()) , _value(T2()) { } pair(const T1& a, const T2& b) : _key(a) , _value(b) { } }; */ /* templateinline pair //插入、迭代器、make_pair void test_map1() { map<string, string> m; //创建pair -- 传参 pair<string, string> p("Kevin", "凯文"); m.insert(p); //匿名对象 m.insert(pair<string, string>("Kevin", "凯文")); //make_pair m.insert(make_pair("Eddie", "彭于晏")); m.insert(make_pair("Tom", "汤姆")); m.insert(make_pair("Jerry", "杰瑞")); //mapclass map { K _key; V _value; }; template //key不在count 插入pair( key, int() ) iterator指向key bool-true //key在count iterator指向原有key bool-false count[key]++; } for (auto& toy : count) { cout << toy.first << ":" << toy.second << endl; } }struct pair { T1 first; T2 second; pair() : first(T1()) , second(T2()) { } pair(const T1& a, const T2& b) : first(a) , second(b) { } }; insert函数调用 pair void insert(InputIterator first, InputIterator last); //迭代器区间构造 返回值为void V& operator[](const K& key) { pair - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
5.OJ练习
1.前K个高频单词
法一:map+vector+stable_sort
class Solution { typedef pair<string, int> p; public: struct cmp { bool operator()(const p& a, const p& b) { return a.second > b.second; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> m; //记录次数[按ascii码 此处已经按字典顺序存储] for (auto& str : words) m[str]++; //迭代器区间构造 vector<p> v(m.begin(), m.end()); //降序排序 //sort的参数迭代器是随机迭代器 但是map的迭代器是双向迭代器 //vector的构造函数可以接收任意类型的迭代器 stable_sort(v.begin(), v.end(), cmp()); //存储数据 vector<string> ret; for (size_t i = 0; i < k; ++i) ret.push_back(v[i].first); return ret; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
法二:map+vector+sort[控制逻辑]
class Solution { typedef pair<string, int> p; public: struct cmp { bool operator()(const p& a, const p& b) { if (a.second > b.second) return true; else if (a.second == b.second && a.first < b.first) return true; else return false; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> m; //记录次数 for (auto& str : words) m[str]++; //迭代器区间构造 vector<p> v(m.begin(), m.end()); //降序排序 sort(v.begin(), v.end(), cmp()); //存储数据 vector<string> ret; for (size_t i = 0; i < k; ++i) ret.push_back(v[i].first); return ret; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
法三:map+multimap+vector[leetcode巧合]
class Solution { typedef pair<string, int> p; public: vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> m; //记录次数--同时排序 //[二叉搜索树:ascii码小的在左 大的在右] for (auto& str : words) m[str]++; //创建多重map //多重map[greater]的底层巧合: // 大key在左 小key在右 相等key在右 // m中的string是按照ascii码排的 // M去遍历m时 string的顺序不变 // 当遇到相等key即int时 插在了右边 //使得中序遍历结果正确 multimap<int, string, greater<int>> M; for (auto& e : m) M.insert(make_pair(e.second, e.first)); vector<string> v; auto it = M.begin(); while (k--) { v.push_back(it->second); ++it; } return v; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
法四:map+multiset+vector
class Solution { typedef pair<string, int> p; public: struct cmp { bool operator()(const p& a, const p& b) const { if (a.second > b.second) return true; else if (a.second == b.second && a.first < b.first) return true; else return false; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> m; for (auto& e : words) m[e]++; multiset<p, cmp> s(m.begin(), m.end()); vector<string> v; auto it = s.begin(); while (k--) { v.push_back(it->first); ++it; } return v; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
法五:优先级队列
class Solution { typedef pair<string, int> p; public: struct Cmp { bool operator()(const p& a, const p& b) const { //second是int--即单词的次数 a比b小 返回true后 底层if语句为真 把小的放到堆下面 大的放到堆顶 if (a.second < b.second) return true; if (a.second == b.second && a.first > b.first) return true; return false; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> m; for (auto& e : words) m[e]++; priority_queue<p, vector<p>, Cmp> heap(m.begin(), m.end()); vector<string> v; while (k--) { v.push_back(heap.top().first); heap.pop(); } return v; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
2.两个数组的交集
交集
1、不相等 小的++
2、相等 同时++
3.一个集合走完就结束
差集
1、相等 同时++
2.不相等 小的就是差集 小的++
3.一个走完，另一个没有走完的集合的值也是差集
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { //排序+去重 // 法一: sort + unique // sort(nums1. begin(), nums1. end()); // unique( nums1. begin(), nums1.end()); // 法二: set set<int> s1(nums1.begin(), nums1.end()); set<int> s2(nums2.begin(), nums2.end()); auto it1 = s1.begin(); auto it2 = s2.begin(); vector<int> v; while (it1 != s1.end() && it2 != s2.end()) { if (*it1 < *it2) ++it1; else if (*it2 < *it1) ++it2; else { v.push_back(*it1); ++it1; ++it2; } } return v; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
拓展:给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { sort(nums1.begin(), nums1.end()); sort(nums2.begin(), nums2.end()); int len1 = nums1.size(), len2 = nums2.size(); vector<int> v; int i = 0, j = 0; while (i < len1 && j < len2) { if (nums1[i] < nums2[j]) i++; else if (nums1[i] > nums2[j]) j++; else { v.push_back(nums1[i]); i++; j++; } } return v; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
3.随机链表的复制
1.法一:基础法
链表oj中有相同题目解析
#define _CRT_SECURE_NO_WARNINGS #include#include #include struct Node { int val; struct Node* next; struct Node* random; }; struct Node* copyRandomList(struct Node* head) { // 1、拷贝连接 struct Node* cp = head; while (cp) { struct Node* tmp = (struct Node*)malloc(sizeof(struct Node)); //拷贝val tmp->val = cp->val; //拷贝next 即：原结点next指向谁 拷贝结点的next就指向谁 tmp->next = cp->next; //cp和tmp连接 cp->next = tmp; //cp后移 cp = tmp->next; } //2、匹配random cp = head; while (cp) { struct Node* tmp = cp->next; if (cp->random == NULL) tmp->random = NULL; else tmp->random = cp->random->next; cp = tmp->next; } //3、旧连旧--新连新 cp = head; struct Node* Head = NULL, * Tail = NULL; while (cp) { struct Node* tmp = cp->next; struct Node* next = tmp->next; if (Tail == NULL) { Head = Tail = tmp; } else { Tail->next = tmp; Tail = Tail->next; } cp->next = next; cp = next; } return Head; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
2.法二:map键值对法
struct Node { int val; struct Node* next; struct Node* random; }; class Solution { public: Node* copyRandomList(Node* head) { map<Node*, Node*> m; Node* cp = head; Node* Head = nullptr; Node* Tail = nullptr; Node* tmp = nullptr; while (cp) { tmp = new Node(cp->val); m[cp] = tmp; //存储键值对[cp , tmp] if (Tail == nullptr) Tail = Head = tmp; else { Tail->next = tmp; Tail = Tail->next; } cp = cp->next; } cp = head; tmp = Head; while (cp) { if (cp->random == nullptr) tmp->random = nullptr; else tmp->random = m[cp->random]; //键值对形式访问tmp自己的random cp = cp->next; tmp = tmp->next; } return Head; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
-
相关阅读:
【期中复习】深度学习
第2-3-5章 删除附件的接口开发-文件存储服务系统-nginx/fastDFS/minio/阿里云oss/七牛云oss
c/c++指针从浅入深介绍——基于数据内存分配的理解（上）
基于单片机的数字电压表设计
H5点击复制功能 兼容安卓、IOS
Elasticsearch(一)-基本概念与环境搭建
[vue3.x]实战问题--vue2.x升级vue3.x遇到的问题
金字塔型自动化的利弊
《Python 快速入门》C站最全Python标准库总结
Performing Inference In INT8 Precision
- 原文地址：https://blog.csdn.net/LHRan_ran_/article/details/133209164
