企业官网建设流程全解析

目录

一. 序列式容器和关联式容器

二. set 容器

2.1 了解 set 类

2.2 set的构造和迭代器

2.3 set 的增删查

2.3.1 set 的增

2.3.2 set 的查

2.3.3 set 的删

2.3.3.1 count

2.3.3.2 lower_bound 和 upper_bound

2.4 multiset

2.4.1 multiset 和 set 的差异

代码实现

2.4.1.1 查找

2.4.1.2 删除

2.5 实战演练

349. 两个数组的交集 - 力扣（LeetCode）

142. 环形链表 II - 力扣（LeetCode）

三.map 容器

3.1 了解 map 类

3.2 pair 类型

3.3 map 的增删查

3.3.1 map 的增

3.3.1.1 map 的 key 的唯一性

3.3.2 遍历

3.3.3 equal_range

3.3.4 map 的查

3.3.5 map 的删

3.4 operator[ ]

3.4.1 统计次数

查找 + 插入

利用operator[ ]搞定dict查找

3.5 mutimap

3.5.1 插入

3.5.2 equal_range

3.6 实战演练

138. 随机链表的复制 - 力扣（LeetCode）

692. 前K个高频单词 - 力扣（LeetCode）

写法一：

写法二：

写法三：

一. 序列式容器和关联式容器

前面我们已经接触过STL中的部分容器比如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。

这部分要介绍的map和set底层是红黑树，红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构，map是key / value搜索场景的结构。

二. set 容器

2.1 了解 set 类

1、set的声明如下，T就是set底层关键字的类型；

2、set对T要求比较大小，默认要求T支持小于比较的就可以了，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数；

3、set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参
数——这一点不需要管；

4、一般情况下，我们都不需要传后两个模版参数；

5、set底层是用红黑树实现的，红黑树我们已经知道是平衡二叉树，增删查效率是O(logN) ，迭代器遍历是走的搜索树的中序，左根右，所以是有序的；

6、前面部分我们已经介绍了vector / list等容器的使用，因为STL容器接口设计高度相似，所以这里我们就不再一个接口一个接口的介绍，而是直接带大家看文档，挑比较重要的接口进行介绍。

template < class T, // set::key_type/value_type class Compare = less<T>, // set::key_compare/value_compare class Alloc = allocator<T> // set::allocator_type > class set;

2.2 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 & = allocator_type()); // copy (3) 拷贝构造 set(const set& x); // initializer list (5) initializer 列表构造 set(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();

#include<iostream> #include<set> using namespace std; int main() { //默认构造 set<int> a1; //迭代器构造 int arr[] = { 1,2,3,4,5 }; set<int> a2(arr, arr + sizeof(arr)/sizeof(int)); //拷贝构造 set<int> a3(a1); //赋值运算符重载 a2 = a1; return 0; }

2.3 set 的增删查

2.3.1 set 的增

#include<set> int main() { //去重+升序排序(换成greater<int>变降序) set<int,greater<int>> s1; //不支持插入相同的值 s1.insert(5); s1.insert(2); s1.insert(7); s1.insert(5); set<int, greater<int>>::iterator it = s1.begin(); while (it != s1.end()) { //不支持*it++; cout << *it << ' '; it++; } cout << endl; return 0; }

2.3.2 set 的查

#include<set> int main() { //去重+升序排序(换成greater<int>变降序) set<int,greater<int>> s1; //不支持插入相同的值 s1.insert(5); s1.insert(2); s1.insert(7); s1.insert(5); set<int, greater<int>>::iterator pos = s1.find(2); if (pos != s1.end()) { cout << *pos << endl; } return 0; }

2.3.3 set 的删

#include<set> int main() { //去重+升序排序(换成greater<int>变降序) set<int,greater<int>> s1; //不支持插入相同的值 s1.insert(5); s1.insert(2); s1.insert(7); s1.insert(5); int x; cin >> x; int num = s1.erase(x); if (num == 0) { cout << x << "不存在" << endl; } else { cout << x << "删除成功" << endl; } return 0; }

2.3.3.1 count

#include<set> int main() { //去重+升序排序(换成greater<int>变降序) set<int,greater<int>> s1; //不支持插入相同的值 s1.insert(5); s1.insert(2); s1.insert(7); s1.insert(5); if (s1.count(2)) { cout << "存在" << endl; } else { cout << "不存在" << endl; } return 0; }

2.3.3.2 lower_bound 和 upper_bound

#include<set> #include<iostream> using namespace std; int main() { set<int> myset; for (int i = 1; i < 10; i++) { myset.insert(i * 10); } for (auto e : myset) { cout << e << ' '; } cout << endl; //删除[30,50] set<int>::iterator itlow = myset.lower_bound(30); set<int>::iterator itup = myset.upper_bound(50); myset.erase(itlow, itup); for (auto e : myset) { cout << e << ' '; } cout << endl; return 0; }

2.4 multiset

2.4.1 multiset 和 set 的差异

multiset和set的使用基本完全类似，主要区别点在于multiset支持值冗余。

代码实现

#include<set> #include<iostream> using namespace std; int main() { multiset<int,greater<int>> s = { 4,2,3,1,4,5,2,3,1,6,8,6,3,9 }; multiset<int>::iterator it = s.begin(); while (it != s.end()) { cout << *it << ' '; it++; } cout << endl; return 0; }

2.4.1.1 查找

比如查找3这个节点，如果有多个3节点，会查找中序遍历的第一个3节点——

#include<set> #include<iostream> using namespace std; int main() { int x; cin >> x; multiset<int,greater<int>> s = { 4,2,3,1,4,5,2,3,1,6,8,6,3,9 }; multiset<int>::iterator pos = s.find(x); while (pos != s.end() && *pos == x) { cout << *pos << ' '; pos++; } cout << endl; return 0; }

2.4.1.2 删除

#include<iostream> #include<set> using namespace std; int main() } multiset<int,greater<int>> s = { 4,2,3,1,4,5,2,3,1,6,8,6,3,9 }; multiset<int>::iterator it = s.begin(); while (it != s.end()) { cout << *it << ' '; it++; } cout << endl; //删除全部的3 s.erase(3); multiset<int>::iterator _it = s.begin(); while (_it != s.end()) { cout << *_it << ' '; _it++; } cout << endl; return 0; }

2.5 实战演练

349. 两个数组的交集 - 力扣（LeetCode）

使用set直接实现排序j＋去重

class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> set1(nums2.begin(),nums2.end()); set<int> set2(nums1.begin(),nums1.end()); vector<int> ans; set<int>::iterator it=set1.begin(); while(it!=set1.end()) { auto pos=set2.find(*it); if(pos!=set2.end()) { ans.push_back(*it); } it++; } return ans; } };

142. 环形链表 II - 力扣（LeetCode）

set存指针，用count函数判断是否重复

class Solution { public: ListNode *detectCycle(ListNode *head) { multiset<ListNode*> st; ListNode* cur=head; while(cur) { st.insert(cur); if(st.count(cur)==2) { return cur; } cur=cur->next; } return nullptr; } };

三.map 容器

3.1 了解 map 类

map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数，map底层存储数据的内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模版参数。map底层是用红黑树实现，增删查改效率是O（logN），迭代器遍历是走的中序，所以是按key有序顺序遍历的。

3.2 pair 类型

3.3 map 的增删查

3.3.1 map 的增

#include<iostream> #include<map> using namespace std; int main() { map<string, string> dict; dict.insert(pair<string, string>("first", "第一个")); dict.insert(pair<string, string>("second", "第二个")); //更简洁一点的话，就用make_piar dict.insert(make_pair("sort", "排序")); //隐式类型转换,构造pair再插入 dict.insert({ "auto","自动的" }); return 0; }

3.3.1.1 map 的 key 的唯一性

想插入相同的 key 值， value 并不会更新，也不会插入成功。

#include<iostream> #include<map> using namespace std; int main() { map<string, string> dict; dict.insert(pair<string, string>("first", "第一个")); dict.insert(pair<string, string>("second", "第二个")); //更简洁一点的话，就用make_piar dict.insert(make_pair("sort", "排序")); //隐式类型转换,构造pair再插入 dict.insert({ "auto","自动的" }); dict.insert({ "auto","自动的xxxxxx" }); map<string, string>::iterator it = dict.begin(); while (it != dict.end()) { cout << it.operator->()->first << ":" << it.operator->()->second << endl; ++it; } return 0; }

3.3.2 遍历

map 的迭代器遍历稍微有点不同，因为 pia r本身没有重载流插入和流提取，所以不能直接打印。

#include<iostream> #include<map> using namespace std; int main() { map<string, string> dict; dict.insert(pair<string, string>("first", "第一个")); dict.insert(pair<string, string>("second", "第二个")); //更简洁一点的话，就用make_piar dict.insert(make_pair("sort", "排序")); //隐式类型转换,构造pair再插入 dict.insert({ "auto","自动的" }); map<string, string>::iterator it = dict.begin(); while (it != dict.end()) { cout << it.operator->()->first << ":" << it.operator->()->second << endl; ++it; } return 0; }

3.3.3 equal_range

3.3.4 map 的查

#include<iostream> #include<map> using namespace std; int main() { map<string, string> dict; dict.insert(pair<string, string>("first", "第一个")); dict.insert(pair<string, string>("second", "第二个")); //更简洁一点的话，就用make_piar dict.insert(make_pair("sort", "排序")); //隐式类型转换,构造pair再插入 dict.insert({ "auto","自动的" }); string x; cin >> x; auto it = dict.find(x); if (it != dict.end()) { cout<<"找到了"<< it->first << ":" << it->second << endl; } else { cout << "没有找到" << endl; } return 0; }

3.3.5 map 的删

#include<map> using namespace std; int main() { map<string, string> dict; dict.insert(pair<string, string>("first", "第一个")); dict.insert(pair<string, string>("second", "第二个")); //更简洁一点的话，就用make_piar dict.insert(make_pair("sort", "排序")); //隐式类型转换,构造pair再插入 dict.insert({ "auto","自动的" }); dict.erase("first"); map<string, string>::iterator it = dict.begin(); while (it != dict.end()) { cout << it.operator->()->first << ":" << it.operator->()->second << endl; ++it; } return 0; }

3.4 operator[ ]

简单点说就是：我给你一个 key，你帮我找到对应的 value，然后返回这个 value。operator[ ]有三种功能：插入、查找、修改

map<string, string> dict; dict.insert(make_pair("sort", "搜索")); //key不存在->插入 dict["insert"]; //插入+修改 dict["left"] = "左边"; //修改 dict["left"] = "剩余"; map<string, string>::iterator it = dict.begin(); while (it != dict.end()) { cout << it.operator->()->first << ":" << it.operator->()->second << endl; ++it; } return 0;

这些功能的实现也离不开insert的返回类型

3.4.1 统计次数

查找 + 插入

// 查找 + 插入组合 map<string, int> countMap; for (auto& e : arr) { auto it = countMap.find(e); if (it != countMap.end()) { it->second++; // 存在则递增 } else { countMap.insert({ e,1 }); // 不存在则插入 } }

利用operator[ ]搞定dict查找

// 利用 operator[] 的特性 for (auto e : arr) { countMap[e]++; }

3.5 mutimap

multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么insert / find / count / erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如find时，有多个key，返回中序第一个。其次就是multimap不支持[]，因为支持key冗余，[ ]就只能支持插入了，不能支持修改。

3.5.1 插入

无论 key 值是否相同，都会插入

#include<iostream> #include<map> using namespace std; int main() { multimap<string, string>dict; dict.insert(make_pair("sort", "排序")); dict.insert(make_pair("sort", "排序1")); dict.insert(make_pair("sort", "排序2")); dict.insert(make_pair("sort", "排序3")); dict.insert(make_pair("sort", "排序4")); dict.insert(make_pair("sort", "排序5")); multimap<string, string>::iterator it = dict.begin(); while (it != dict.end()) { cout << it.operator->()->first << ":" << it.operator->()->second << endl; ++it; } return 0; }

3.5.2 equal_range

equal_range 在 multimap上可以用于找出一段相同值

#include<iostream> #include<map> using namespace std; int main() { multimap<string, string>dict; dict.insert(make_pair("sort", "排序")); dict.insert(make_pair("ort", "排序1")); dict.insert(make_pair("ort", "排序2")); dict.insert(make_pair("sort", "排序3")); dict.insert(make_pair("ort", "排序4")); dict.insert(make_pair("sort", "排序5")); auto _pair = dict.equal_range("sort"); auto it = _pair.first; while (it != _pair.second) { cout << it->first << ":" << it->second << endl; it++; } return 0; }

3.6 实战演练

138. 随机链表的复制 - 力扣（LeetCode）

数据结构初阶阶段，为了控制随机指针，我们将拷贝结点链接在原节点的后面解决，后面拷贝节点还得解下来链接，非常麻烦。这里我们直接让{原结点，拷贝结点}建立映射关系放到map中，控制随机指针会非常简单方便，这里体现了map在解决一些问题时的价值，完全是降维打击。

/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val = _val; next = NULL; random = NULL; } }; */ class Solution { public: Node* copyRandomList(Node* head) { map<Node*,Node*> nodeMap; Node* copyhead =nullptr,*copytail = nullptr; Node* cur= head; while(cur) { Node* copy=new Node(cur->val); // 尾随 if(copytail == nullptr) { copyhead = copytail=copy; } else { copytail->next=copy; copytail=copy; } nodeMap.insert({cur,copy}); 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; } };

692. 前K个高频单词 - 力扣（LeetCode）

本题目我们利用map统计出次数以后，返回的答案应该按单词出现频率由高到低排序，有一个特殊要求，如果不同的单词有相同出现频率，按字典顺序排序。

写法一：

用排序找前k个单词，因为map中已经对key单词排序过，也就意味着遍历map时，次数相同的单词，字典序小的在前面，字典序大的在后面。那么我们将数据放到vector中用一个稳定的排序就可以实现上面特殊要求，但是sort底层是快排，是不稳定的，所以我们要用stable_sort，他是稳定的。

// 方法1 class Solution { public: struct kv_pair { bool operator()(const pair<string, int>& kv1,const pair<string, int> kv2) { return kv1.second > kv2.second; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> countMap; for(auto& str : words) { countMap[str]++; } // multimap<int,string> sortMap; // 降序 vector<pair<string, int>> v(countMap.begin(), countMap.end()); // sort(v.begin(),v.end(),kv_pair()); // 稳定的排序 stable_sort(v.begin(), v.end(), kv_pair()); for (auto& [k, v] : v) { cout << k << ":" << v << endl; } cout << endl; vector<string> ret; for (size_t i = 0; i < k; ++i) { ret.push_back(v[i].first); } return ret; } };

写法二：

将map统计出的次数的数据放到vector中排序，或者放到priority_queue中来选出前k个。利用仿函数强行控制次数相等的，字典序小的在前面。

// 方法2 class Solution { public: // 自己实现一个仿函数，控制比较逻辑 struct kv_pair { // 次数大的在前面，次数相等的、字典序小的在前面 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) { for(auto& str : words) { countMap[str]++; } // multimap<int,string> sortMap; // 降序 vector<pair<string,int>> v(countMap.begin(),countMap.end()); sort(v.begin(),v.end(),kv_pair); for(auto& [k,v] : v) { cout<< k << ":" << v << endl; } cout << endl; vector<string> ret; for(size_t i = 0;i < k;++i) { ret.push_back(v[i].first); } return ret; } };

写法三：

使用优先级队列，大堆提供的小于的比较逻辑。

次数大的在前面，次数相等的，字典序小的在前面——

// 方法3 class Solution { public: struct kv_pair{ // 次数大的在前面，次数相等的，字典序小的在前面 // 优先级队列，大堆提供的小于的比较逻辑 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& str : words) { countMap[str]++; } // 大堆 priority_queue<pair<string,int>,vector<pair<string,int>>, kv_pair> pq(countMap.begin(),countMap.end()); vector<string> ret; for(size_t i = 0;i < k;++i) { ret.push_back(pq.top().first); pq.pop(); } return ret; } };