企业官网建设流程全解析

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

核心定义：STL 容器按逻辑结构可分为两类，区别在于元素之间有没有紧密的关联关系。

• 序列式容器：逻辑结构是线性序列，元素按存储位置顺序保存和访问，两个位置的值之间一般没有紧密关联，交换一下仍是序列式容器。
• 常见序列式容器：string、vector、list、deque、array、forward_list。
• 关联式容器：逻辑结构通常是非线性结构，两个位置之间有紧密关联关系，交换后存储结构就被破坏；元素按关键字保存和访问。
• 常见关联式容器：map/set 系列、unordered_map/unordered_set 系列。

易错点：判断容器类型看的是“元素之间有没有关联”，不是看“能不能排序”。

本章重点：map 和 set 底层都是红黑树，红黑树是一棵平衡二叉搜索树。

• set：key 搜索场景的结构。
• map：key/value 搜索场景的结构。

2. set系列的使用

2.1 set和multiset参考文档

参考文档：<set> - C++ Reference

2.2 set类的介绍

• 模板声明：template <class T, class Compare = less<T>, class Alloc = allocator<T>> class set;，其中T 就是 set 底层关键字的类型。
• 比较方式：set 默认要求 T 支持小于比较；若不支持或想按自己的需求走，可以自行实现仿函数传给第二个模板参数。
• 内存来源：底层数据内存从空间配置器申请，需要时可自己实现内存池传给第三个参数。
• 一般情况：都不需要传后两个模板参数。
• 底层与效率：底层是红黑树，增删查效率是O(logN)；迭代器遍历走的是搜索树的中序，所以结果有序。
• 学习方式：STL 容器接口设计高度相似，不再逐个接口介绍，而是直接看文档、挑重要接口讲解。

2.3 set的构造和迭代器

构造接口（关注这几种即可）：

• 无参默认构造：explicit set(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
• 迭代器区间构造：template <class InputIterator> set(InputIterator first, InputIterator last, ...);
• 拷贝构造：set(const set& x);
• initializer 列表构造：set(initializer_list<value_type> il, ...);

迭代器要点：

• 支持正向和反向迭代遍历，迭代器是双向迭代器。
• 遍历默认按升序，因为底层是二叉搜索树，迭代器走的是中序。
• 支持迭代器就意味着支持范围 for。
• 易错点：set 的 iterator 和 const_iterator都不支持修改数据，因为修改关键字会破坏底层搜索树的结构。

2.4 set的增删查

成员类型：key_type 和 value_type都是第一个模板参数 T。

• 单个插入：pair<iterator,bool> insert(const value_type& val);，如果已经存在则插入失败。
• 列表插入：void insert(initializer_list<value_type> il);，已存在的值不会插入。
• 区间插入：template <class InputIterator> void insert(InputIterator first, InputIterator last);，已存在的值不会插入。
• 查找：iterator find(const value_type& val);，找到返回该值所在迭代器，没找到返回 end()。
• 计数：size_type count(const value_type& val) const;，返回 val 的个数。
• 按位置删除：iterator erase(const_iterator position);
• 按值删除：size_type erase(const value_type& val);，不存在返回 0，存在返回 1。
• 区间删除：iterator erase(const_iterator first, const_iterator last);
• lower_bound：返回大于等于 val位置的迭代器。
• upper_bound：返回大于 val位置的迭代器。

2.5 insert和迭代器遍历使用样例

#include<iostream> #include<set> using namespace std; int main() { // 去重+升序排序 set<int> s; // 去重+降序排序（给一个大于的仿函数） //set<int, greater<int>> s; s.insert(5); s.insert(2); s.insert(7); s.insert(5); //set<int>::iterator it = s.begin(); auto it = s.begin(); while (it != s.end()) { // error C3892: “it”: 不能给常量赋值 // *it = 1; cout << *it << " "; ++it; } cout << endl; // 插入一段initializer_list列表值，已经存在的值插入失败 s.insert({ 2,8,3,9 }); for (auto e : s) { cout << e << " "; } cout << endl; set<string> strset = { "sort", "insert", "add" }; // 遍历string比较ascll码大小顺序遍历的 for (auto& e : strset) { cout << e << " "; } cout << endl; }

要点提炼：

• set 天然实现去重 + 升序；换成greater<int>仿函数即去重 + 降序。
• 重复插入 5 不会报错，只是插入失败。
• string 元素按ASCII 码大小顺序遍历。

2.6 find和erase使用样例

#include<iostream> #include<set> using namespace std; int main() { set<int> s = { 4,2,7,2,8,5,9 }; for (auto e : s) { cout << e << " "; } cout << endl; // 删除最小值 s.erase(s.begin()); for (auto e : s) { cout << e << " "; } cout << endl; // 直接删除x int x; cin >> x; int num = s.erase(x); if (num == 0) { cout << x << "不存在！" << endl; } for (auto e : s) { cout << e << " "; } cout << endl; // 直接查找在利用迭代器删除x cin >> x; auto pos = s.find(x); if (pos != s.end()) { s.erase(pos); } else { cout << x << "不存在！" << endl; } for (auto e : s) { cout << e << " "; } cout << endl; // 算法库的查找 O(N) auto pos1 = find(s.begin(), s.end(), x); // set自身实现的查找 O(logN) auto pos2 = s.find(x); // 利用count间接实现快速查找 cin >> x; if (s.count(x)) { cout << x << "在！" << endl; } else { cout << x << "不存在！" << endl; } return 0; }

#include<iostream> #include<set> using namespace std; int main() { std::set<int> myset; for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90 for (auto e : myset) { cout << e << " "; } cout << endl; // 实现查找到的[itlow,itup)包含[30, 60]区间 // 返回 >= 30 auto itlow = myset.lower_bound(30); // 返回 > 60 auto itup = myset.upper_bound(60); // 删除这段区间的值 myset.erase(itlow, itup); for (auto e : myset) { cout << e << " "; } cout << endl; return 0; }

易错点与对比：

• 算法库 find是O(N)；set 自身 find是O(logN)，优先用成员函数。
• count(x)在 set 中返回值只有 0 或 1，可间接实现快速查找。
• lower_bound 是“大于等于”，upper_bound 是“大于”，两者配合可得到左闭右开区间[itlow, itup)，从而删除[30, 60]这样的闭区间。

2.7 multiset和set的差异

核心区别：multiset 支持值冗余，insert/find/count/erase 都围绕这一点产生差异。

#include<iostream> #include<set> using namespace std; int main() { // 相比set不同的是，multiset是排序，但是不去重 multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 }; auto it = s.begin(); while (it != s.end()) { cout << *it << " "; ++it; } cout << endl; // 相比set不同的是，x可能会存在多个，find查找中序的第一个 int x; cin >> x; auto pos = s.find(x); while (pos != s.end() && *pos == x) { cout << *pos << " "; ++pos; } cout << endl; // 相比set不同的是，count会返回x的实际个数 cout << s.count(x) << endl; // 相比set不同的是，erase给值时会删除所有的x s.erase(x); for (auto e : s) { cout << e << " "; } cout << endl; return 0; }

• 排序但不去重。
• find：x 可能有多个，返回中序的第一个。
• count：返回 x 的实际个数。
• erase(值)：会删除所有的 x。

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

class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> s1(nums1.begin(), nums1.end()); set<int> s2(nums2.begin(), nums2.end()); // 因为set遍历是有序的，有序值，依次比较 // 小的++，相等的就是交集 vector<int> ret; auto it1 = s1.begin(); auto it2 = s2.begin(); while(it1 != s1.end() && it2 != s2.end()) { if(*it1 < *it2) { it1++; } else if(*it1 > *it2) { it2++; } else { ret.push_back(*it1); it1++; it2++; } } return ret; } };

思路要点：先用 set 构造两个有序去重序列，再用双指针依次比较：小的前进，相等即为交集。

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

数据结构初阶阶段，通过证明“一个指针从头开始走、一个指针从相遇点开始走，会在入口点相遇”，理解证明都很麻烦。这里使用set 查找记录解决，非常简单方便，体现了 set 在解决一些问题时的价值，完全是降维打击。

class Solution { public: ListNode *detectCycle(ListNode *head) { set<ListNode*> s; ListNode* cur = head; while(cur) { auto ret = s.insert(cur); if(ret.second == false) return cur; cur = cur->next; } return nullptr; } };

要点：利用insert返回的pair<iterator,bool>，second 为 false 说明该结点已出现过，即环的入口。

3. map系列的使用

3.1 map和multimap参考文档

参考文档：<map> - C++ Reference

3.2 map类的介绍

• 模板声明：template <class Key, class T, class Compare = less<Key>, class Alloc = allocator<pair<const Key,T>>> class map;
• Key是底层关键字的类型，T是底层value的类型。
• 默认要求 Key 支持小于比较；不支持或需要时可自行实现仿函数传给第二个模板参数。
• 底层数据内存从空间配置器申请，一般情况下不需要传后两个模板参数。
• 底层是红黑树，增删查改效率是O(logN)；迭代器遍历走中序，所以按 key 有序遍历。

3.3 pair类型介绍

定义：map 底层红黑树节点中的数据，使用pair<Key, T>存储键值对，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) ); }

• first存 key，second存 value。
• make_pair是构造 pair 的便捷函数。

3.4 map的构造

构造接口（关注这几种即可）：

• 无参默认构造：explicit map(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
• 迭代器区间构造：template <class InputIterator> map(InputIterator first, InputIterator last, ...);
• 拷贝构造：map(const map& x);
• initializer 列表构造：map(initializer_list<value_type> il, ...);

迭代器要点：

• 支持正向和反向迭代遍历，迭代器是双向迭代器。
• 遍历默认按 key 升序，因为底层是二叉搜索树，迭代器走中序。
• 支持迭代器就意味着支持范围 for。
• 易错点：map支持修改 value 数据，不支持修改 key 数据，修改关键字会破坏底层搜索树的结构。

3.5 map的增删查

成员类型：key_type 是 Key，mapped_type 是 T，value_type 是 pair<const key_type, mapped_type>。

• 插入：pair<iterator,bool> insert(const value_type& val);，如果 key 已存在则插入失败；key 存在但 value 不相等也会插入失败。
• 列表插入 / 区间插入：已存在的值不会插入。
• 查找：iterator find(const key_type& k);，没找到返回 end()。
• 计数：size_type count(const key_type& k) const;，返回 k 的个数。
• 删除：按位置、按 key、按区间三种方式，与 set 完全类似。
• lower_bound：返回大于等于 k位置的迭代器。

与 set 的异同：map 的插入接口不同（插入的是 pair 键值对），但查和删的接口只用关键字 key，与 set 完全类似；不过find 返回 iterator，不仅可以确认 key 在不在，还能找到 key 映射的 value，并通过迭代器修改 value。

3.6 map的数据修改

两种修改方式：

• 通过迭代器：迭代器遍历时，或 find 返回 key 所在 iterator 后修改。
• 通过 operator[]：非常重要的修改接口，不仅支持修改，还支持插入数据和查找数据，是一个多功能复合接口。

概念澄清：从内部实现角度，map 把传统说的 value 值给的是 T 类型，typedef 为mapped_type；而value_type 是红黑树结点中存储的 pair 键值对值。日常使用还是习惯把这里的 T 映射值叫做 value。

insert 返回值说明：

• 返回pair<iterator,bool>。
• key 已存在：插入失败，first 是key 所在结点的迭代器，second 是false。
• key 不存在：插入成功，first 是新插入 key 所在结点的迭代器，second 是true。
• 无论成功还是失败，first 都指向 key 所在的迭代器，所以insert 插入失败时充当了查找的功能，正是这一点让 insert 可以实现 operator[]。

易错点：这里有两个 pair，不要混淆——一个是 map 底层红黑树节点中存的pair<key, T>，另一个是 insert 返回值pair<iterator,bool>。

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[] 三种能力总结：

• 插入：key 不存在时插入{k, mapped_type()}。
• 查找：key 存在时返回对应 value 的引用。
• 修改：返回的是引用，可直接赋值修改。

3.7 构造遍历及增删查使用样例

#include<iostream> #include<map> using namespace std; int main() { // initializer_list构造及迭代遍历 map<string, string> dict = { {"left", "左边"}, {"right", "右边"}, {"insert", "插入"},{ "string", "字符串" } }; //map<string, string>::iterator it = dict.begin(); auto it = dict.begin(); while (it != dict.end()) { //cout << (*it).first <<":"<<(*it).second << endl; // map的迭代基本都使用operator->,这里省略了一个-> // 第一个->是迭代器运算符重载，返回pair*，第二个箭头是结构指针解引用取pair数据 //cout << it.operator->()->first << ":" << it.operator->()->second << endl; cout << it->first << ":" << it->second << endl; ++it; } cout << endl; // insert插入pair对象的4种方式，对比之下，最后一种最方便 pair<string, string> kv1("first", "第一个"); dict.insert(kv1); dict.insert(pair<string, string>("second", "第二个")); dict.insert(make_pair("sort", "排序")); dict.insert({ "auto", "自动的" }); // "left"已经存在，插入失败 dict.insert({ "left", "左边，剩余" }); // 范围for遍历 for (const auto& e : dict) { cout << e.first << ":" << e.second << endl; } cout << endl; string str; while (cin >> str) { auto ret = dict.find(str); if (ret != dict.end()) { cout << "->" << ret->second << endl; } else { cout << "无此单词，请重新输入" << endl; } } // erase等接口跟set完全类似，这里就不演示讲解了 return 0; }

要点提炼：

• insert 插入 pair 的 4 种方式：已有 pair 对象、pair<K,V>(...)、make_pair(...)、{...}，最后一种最方便。
• it->first等价于(*it).first；第一个->是迭代器运算符重载返回 pair*，第二个箭头是结构指针解引用取 pair 数据。
• key 已存在时插入失败，不会覆盖原 value。

3.8 map的迭代器和[]功能样例

样例一：利用 find 和 iterator 修改功能，统计水果出现的次数

#include<iostream> #include<map> #include<string> using namespace std; int main() { // 利用find和iterator修改功能，统计水果出现的次数 string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> countMap; for (const auto& str : arr) { // 先查找水果在不在map中 // 1、不在，说明水果第一次出现，则插入{水果, 1} // 2、在，则查找到的节点中水果对应的次数++ auto ret = countMap.find(str); 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; }

样例二：利用 [] 插入+修改功能，巧妙实现统计水果出现的次数

#include<iostream> #include<map> #include<string> using namespace std; int main() { // 利用[]插入+修改功能，巧妙实现统计水果出现的次数 string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> countMap; for (const auto& str : arr) { // []先查找水果在不在map中 // 1、不在，说明水果第一次出现，则插入{水果, 0}，同时返回次数的引用，++一下就变成1次了 // 2、在，则返回水果对应的次数++ countMap[str]++; } for (const auto& e : countMap) { cout << e.first << ":" << e.second << endl; } cout << endl; return 0; }

样例三：operator[] 的插入、修改、查找三种用法

#include<iostream> #include<map> #include<string> using namespace std; int main() { map<string, string> dict; dict.insert(make_pair("sort", "排序")); // key不存在->插入 {"insert", string()} dict["insert"]; // 插入+修改 dict["left"] = "左边"; // 修改 dict["left"] = "左边、剩余"; // key存在->查找 cout << dict["left"] << endl; return 0; }

易错点：dict["insert"];这一句虽然只是“读”，但因为 key 不存在，会悄悄插入一个默认值，这是 operator[] 最容易踩的坑。

3.9 multimap和map的差异

• 核心区别：multimap 支持关键值 key 冗余，insert/find/count/erase 都围绕这一点产生差异，与 set 和 multiset 的差异完全一样。
• find：有多个相同 key 时，返回中序第一个。
• 易错点：multimap不支持 operator[]，因为支持 key 冗余，[] 就只能支持插入，不能支持修改。

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

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

class Solution { public: Node* copyRandomList(Node* head) { map<Node*, Node*> nodeMap; Node* copyhead = nullptr,*copytail = 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; } // 原节点和拷贝节点map kv存储 nodeMap[cur] = copytail; cur = cur->next; } // 处理random 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; } };

思路要点：第一遍遍历拷贝结点并建立原结点到拷贝结点的映射；第二遍遍历用nodeMap[cur->random]直接定位拷贝结点的 random 指向。

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

题目要求：利用 map 统计出次数后，答案按单词出现频率由高到低排序；特殊要求是不同单词出现频率相同时，按字典顺序排序。

解决思路1：用排序找前 k 个单词

因为 map 中已经对 key 单词排序过，遍历 map 时，次数相同的单词字典序小的在前面、大的在后面。将数据放到 vector 中用一个稳定的排序即可满足特殊要求；但 sort 底层是快排、不稳定，所以要用stable_sort。

class Solution { public: struct Compare { bool operator()(const pair<string, int>& x, const pair<string, int>& y) const { return x.second > y.second; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> countMap; for(auto& e : words) { countMap[e]++; } vector<pair<string, int>> v(countMap.begin(), countMap.end()); // 仿函数控制降序 stable_sort(v.begin(), v.end(), Compare()); //sort(v.begin(), v.end(), Compare()); // 取前k个 vector<string> strV; for(int i = 0; i < k; ++i) { strV.push_back(v[i].first); } return strV; } };

解决思路2：放到 vector 排序，或放到 priority_queue 中选前 k 个

利用仿函数强行控制次数相等的，字典序小的在前面。

class Solution { public: struct Compare { bool operator()(const pair<string, int>& x, const pair<string, int>& y) const { return x.second > y.second || (x.second == y.second && x.first < y.first); } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> countMap; for(auto& e : words) { countMap[e]++; } vector<pair<string, int>> v(countMap.begin(), countMap.end()); // 仿函数控制降序,仿函数控制次数相等，字典序小的在前面 sort(v.begin(), v.end(), Compare()); // 取前k个 vector<string> strV; for(int i = 0; i < k; ++i) { strV.push_back(v[i].first); } return strV; } };

class Solution { public: struct Compare { bool operator()(const pair<string, int>& x, const pair<string, int>& y) const { // 要注意优先级队列底层是反的，大堆要实现小于比较，所以这里次数相等，想要字典 // 序小的在前面要比较字典序大的为真 return x.second < y.second || (x.second == y.second && x.first > y.first); } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> countMap; for(auto& e : words) { countMap[e]++; } // 将map中的<单词，次数>放到priority_queue中，仿函数控制大堆，次数相同按照字典序规则排序 priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> p(countMap.begin(), countMap.end()); vector<string> strV; for(int i = 0; i < k; ++i) { strV.push_back(p.top().first); p.pop(); } return strV; } };

易错点：优先级队列底层是反的，大堆要实现小于比较；所以次数相等时，想让字典序小的排在前面，仿函数里要写成比较字典序大的为真。