C++进阶——set和map
目录
前言
set和map呢，底层是红黑树（后面我的博客也会重点讲解），红黑树是一种平衡二叉搜索树，set和map本身是不支持插入重复元素的，不过也有实现的支持插入重复元素的版本multiset和multimap。
set和map的区别呢，主要在于其应用场景，set用于key场景，map用于key/value场景（我上一篇博客有提到过，不知道的可以移步我上篇博客了解C++进阶——二叉搜索树-CSDN博客）。
这篇博客会着重讲解set和map的使用，模拟实现我会放到后续的博客来讲解。
一、set
文档资料：set - C++ Reference (cplusplus.com)
1.set的基本介绍
1.set的模板声明中，T就是key的类型，后面的Compare是仿函数，用于底层搜索树的比较逻辑，一般情况下不用我们自己传，缺省值给的就够用，当默认的仿函数不符合我们需求时，我们需要自己实现一个仿函数然后传递，第三个模板参数时空间配置器，这个我们暂时先不用管。
2.set的底层是红黑树，是一种与完全二叉树形态很相似的二叉搜索树，高度是logN，所以增删查的效率是O(logN)。
3.迭代器是双向迭代器（bidirectional iterator），走的中序遍历，也就是说迭代器遍历出的序列是有序的。
2.set的使用
2.1构造与迭代器
1.set支持默认构造、拷贝构造、初始化列表构造和迭代器区间构造等，跟之前的容器很类似，就不再一一演示。
2.迭代器是中序遍历，所以遍历出来的序列一定是有序的。
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<string> s{ "banana","apple","pear","orange" };
set<string>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
return 0;
}2.2插入
1.支持指定key插入，如果存在key则插入失败，不存在则插入成功
pair<iterator, bool> insert(const value_type& val);
pair<iterator, bool>是啥？
我们可以借由这个返回值来判断插入成功还是失败，以及获取插入后该结点对应的迭代器（插入失败则会返回原来存在的与key值相等的结点的迭代器）
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<string> s{ "banana","apple","pear","orange" };
set<string>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
auto iit = s.find("apple");
auto ret = s.insert("apple");
auto iit1 = ret.first;
if (iit1 == s.end()) cout << "插入失败1" << endl;
if (iit1 == iit) cout << "插入失败2" << endl;
// 所以插入失败了返回的迭代器是原相同key值对应的迭代器，一定不是end()
return 0;
}2.支持初始化列表插入，没有返回值，列表中搜索树中不存在的就插入，存在的就跳过。
void insert(initializer_list<value_type> il);
3.支持迭代器区间插入，已经存在的值将不会再插入，无返回值
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
2.3删除
1.删除指定迭代器对应结点
iterator erase(const_iterator position);
返回的迭代器是删除结点位置的下一个结点（中序），如果没有下一个就是返回end()。
2.删除指定值为key的结点
size_type erase(const value_type& val);
删除成功则返回1，不存在删除失败则返回0，为什么不是返回bool值？也是因为需要跟multiset的接口对其，multiset返回的是删除key值为val的结点的个数。
3.删除一段迭代器区间（也就是中序遍历的一段序列）
iterator erase(const_iterator first, const_iterator last);
返回的迭代器是删除最后一个结点位置的下一个结点（中序），如果没有下一个就是返回end()。
2.4查找
1.find，返回找到位置的迭代器，找不到就返回end()
iterator find(const value_type& val);
2.count，返回key值为val的结点的个数
size_type count(const value_type& val) const;
为什么返回个数而不是bool值？同样是为了跟multiset的接口对齐
2.5获取需要的区间
需要两个接口来打配合：
1.lower_bound 返回大于等于val位置的迭代器
iterator lower_bound(const value_type& val) const;
2.upper_bound 返回大于val位置的迭代器
iterator upper_bound(const value_type& val) const;
怎么打配合呢？
两者可以配合着来找我们需要找的迭代器区间，看名字也很容易记住，lower就是区间下限，upper就是区间下限嘛，然后返回的两个迭代器组成的区间（左闭右开）中就包含了所有搜索树中具有我们传递的[val1,val2]中的所有数据。（我们传递数据图方便和思维习惯肯定是左闭右闭了~）
#include <iostream>
#include <set>
#include <vector>
using namespace std;
void test2()
{
set<int> s{ 5, 4, 7, 5, 2, 1, 9, 4, 3, 5, 2, 6, 8 };
// 1 2 3 4 5 6 7 8 9
for (auto e : s)
cout << e << " ";
cout << endl;
// 两个接口的配合，可以找到我们需要获取的迭代器区间
auto lower_it = s.lower_bound(4); // 大于等于4 4
auto upper_it = s.upper_bound(7); // 大于7 8
// [4, 8) 迭代器都是左闭右开
vector<int> v(lower_it, upper_it);
// 4 5 6 7
for (auto e : v)
cout << e << " ";
// 如果4 和 7 不在里面呢？会找到[5,8) 5，6，7也符合我们的需求（在[4, 7]区间内的所有数据组成的区间）
// 总而言之，两个配合可以找到所有在[4, 7]区间内的所有数据构成的迭代器区间
}
int main()
{
test2();
return 0;
}2.6一些使用示例
下面是上面一些接口的使用示例，大家可以看看：
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
// 构造、迭代器、insert
void show1()
{
// 去重+升序排序
set<int> s;
// 去重+降序排序（降序要自己传仿函数）（默认是升序Less<T>）
//set<int, greater<int>> s;
s.insert(5);
s.insert(2);
s.insert(7);
s.insert(5);
auto it = s.begin();
while (it != s.end())
{
// error C3892: “it”: 不能给常量赋值
// key是肯定不能修改的，不管是不是const迭代器，修改了就可能会破坏掉搜索树的结构
// *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 = { "banana","apple","pear","orange" };
// 遍历string，比较的方法跟字符串一样，ascll比较
for (auto& e : strset)
{
cout << e << " ";
}
cout << endl;
}
// find、erase
void show2()
{
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);
// 包是自身的查找好的呀，算法库里面的查找是双向迭代器的容器通用的，都没利用set的特性
// 利⽤count间接实现快速查找
cin >> x;
if (s.count(x))
{
cout << x << "在！" << endl;
}
else
{
cout << x << "不存在！" << endl;
}
}
// lower_bound和upper_bound
void show3()
{
set<int> s{ 5, 4, 7, 5, 2, 1, 9, 4, 3, 5, 2, 6, 8 };
// 1 2 3 4 5 6 7 8 9
for (auto e : s)
cout << e << " ";
cout << endl;
// 两个接口的配合，可以找到我们需要获取的迭代器区间
auto lower_it = s.lower_bound(4); // 大于等于4 4
auto upper_it = s.upper_bound(7); // 大于7 8
// [4, 8) 迭代器都是左闭右开
vector<int> v(lower_it, upper_it);
// 4 5 6 7
for (auto e : v)
cout << e << " ";
// 如果4 和 7 不在里面呢？会找到[5,8) 5，6，7也符合我们的需求（在[4, 7]区间内的所有数据组成的区间）
// 总而言之，两个配合可以找到所有在[4, 7]区间内的所有数据构成的迭代器区间
}
int main()
{
show2();
return 0;
}3.set和multiset的区别
首先注意：set和multiset都是在同一个头文件<set>里面的。
最主要的区别还是set不支持重复元素，multiset支持重复元素插入（废话）。
不过它们使用的时候的区别也是从这句废话中产生的：
multiset的增删查由于支持相同数据的插入所以会相对set有所变动。
1.构造：都会排序，但是multiset不去重
2.insert：multiset不去重插入，给什么插入什么
3.erase：multiset会删除所有的值为x的结点
4.find：查找中序遍历的第一个值为x的结点
5.count：返回值为x的结点的个数，结果不再是0或1
4.set相关oj题目
相关思路及细节我都会写在代码的注释中~
// 这里两个数组的交集是不用考虑重复元素的问题的，也就是说，我们可以利用set去重之后再进行找交集的操作
// set天然的结构使迭代器的遍历（中序）是有序的，且数据是去重过的，那么我们小小地使用一下双指针就可以解决~~
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());
vector<int> ret;
// 利用双指针（迭代器）来遍历s1和s2
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，只需要遍历链表，把遍历到的每一个数据都插入到set，插入之前count或者find一下
// 如果有这个数据了之前，那么就一定是环形链表
class Solution
{
public:
ListNode *detectCycle(ListNode *head)
{
// 注意这里的模板类型和后面的插入类型相匹配，*是必须的
set<ListNode*> s;
ListNode* cur = head;
while(cur)
{
if(s.count(cur) == 1)
return cur;
else
s.insert(cur);
cur = cur->next;
}
return nullptr;
}
};二、map
文档资料：map - C++ Reference (cplusplus.com)
1.map的基本介绍
map与set极为类似，不同的是多了一个模板参数类型T，这个T本质上就是key/value类型的value。
Key用作比较，T是跟Key相关的数据。
但是这里有个设计比较搓的地方，key_type是K（key）没问题，mapped_type按理来说设计成V（value）会更好理解，不过它设计成了T那也就按这么来吧。
再下面的value_type是一个pair类型的类类型，这个类里面存了两个类型（K和T）的参数分别一个，这个pair正是map底层红黑树存储的结点数据。
2.map的使用
由于map和set的使用真的很相似很相似，我只列举比较重要且核心的
2.1构造与迭代器
只需要了解一点与set不同的：
1.由于map的底层红黑树的结点数据是pair<K, T>类型的，所以我们需要在构造的时候传pair<K, T>类型的参数而不是让K和T分开传
2.迭代器用->访问key或者value
#include <iostream>
#include <map>
using namespace std;
void map_test1()
{
map<string, string> m{ {"apple", "苹果"}, {"pear", "梨"}};
// 匿名对象
m.insert(pair<string, string>("orange", "橙子"));
// 调用函数返回pair
m.insert(make_pair("banana", "香蕉"));
// 隐式类型转换
//map<string, string> m{ {"apple", "苹果"}, {"pear", "梨"} };
auto it = m.begin();
while (it != m.end())
{
//cout << (*it).first << " : " << (*it).second << endl;
// operator->()是特殊处理过的，这里是省略一个箭头的写法
// operator->()返回的是pair的指针
//cout << it.operator->()->first;
cout << it->first << " : " << it->second << endl;
++it;
}
// map这边operator->()很常用
}
int main()
{
map_test1();
return 0;
}2.2增删查以及获取区间
皆与set相类似，就不再赘述
2.3数据修改
与set不同，set不能修改key主要是因为修改key会造成结构损坏，而map虽不能修改key，但是可以修改与key连带在一起的value，这样不会破坏底层红黑树的结构。
#include <iostream>
#include <map>
using namespace std;
void map_test2()
{
// 利用[]插⼊+修改功能，巧妙实现统计水果出现的次数
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;
}
void map_show1()
{
map<string, string> m{ {"apple", "苹果"}, {"pear", "梨"}, {"banana", "香蕉"}, {"orange", "橙子"} };
// iterator find (const key_type& k);
auto ret = m.find("apple");
// ret是迭代器
ret->second = "_苹果";
for (auto e : m)
{
cout << e.first << " " << e.second << endl;
}
// pair<iterator,bool> insert (const value_type& val);
auto iit = m.insert({"pineapple", "菠萝"});
// insert 的返回值:
// 插入成功就是返回当前结点的迭代器+true
// 插入失败就是返回与插入key值相同的原有结点的迭代器+false
// 也就是说无论插入成功与否都能返回值为key的结点
// 所以我们也可以利用insert来充当查找的功能
iit.first->second = "_菠萝";
for (auto e : m)
{
cout << e.first << " " << e.second << endl;
}
// mapped_type& operator[] (const key_type& k);
// 传key
// [] 返回的是value的引用，所以就可以利用这个来统计出现次数
// []的内部实现原理：
//mapped_type& operator[] (const key_type& k)
//{
//// 传key进来，利用value的缺省值构造出一个pair
//// 插入这个pair，如果有就插入，没有就算了，不过还是都返回了key值的结点迭代器
//// 实现了查找功能
//pair<iterator, bool> ret = insert({ k, mapped_type() });
//iterator it = ret.first;
//return it->second;
//}
map_test2();
}
int main()
{
map_show1();
return 0;
}3.map和multimap的区别
两者主要区别在于是否允许key值冗余，所以增删查会有所区别，与set和multiset的区别几乎完全一样，还有就是multimap不支持[]，因为multimap的key是可以冗余的，所以就算实现[]也是插入，不过我们已经有insert了。
4.map相关oj题目
法1（利用插入结点建立映射关系）：
// 解决这道题需要：结点的深拷贝、结点的映射关系
// 如果不用map，这个映射关系需要深拷贝一个个结点插入原链表中，完成映射
// 也就是说7，13，11，10，1变成了7，7，13，13，11，11，10，10，1，1
// 然后再给新结点通过结点之间的映射关系来进行链接
// 最后还得再解除两个链表的链接，让两个链表再次独立
class Solution
{
public:
Node* copyRandomList(Node* head)
{
if (!head) return nullptr; // 处理空链表
Node* cur = head;
// 结点深拷贝，插入原链表，建立映射关系
while(cur)
{
Node* copycur = new Node(cur->val); // 创建新的节点
copycur->next = cur->next; // 将新节点的 next 指向原链表的下一个节点
cur->next = copycur; // 将原节点的 next 指向新节点
cur = copycur->next; // 移动到下一原节点
}
// 搞定新链表各节点的random指针
cur = head;
while(cur)
{
if(cur->random) // 检查是否有随机指针
cur->next->random = cur->random->next; // 新节点的随机指向
// random初始值就是nullptr所以不需要再else
cur = cur->next->next; // 移动到下一个原节点
}
// 分离两个链表
cur = head;
Node* newHead = head->next; // 新链表的头节点
Node* copyCur = newHead; // 复制链表的当前指针
while(cur)
{
cur->next = cur->next->next; // 恢复原链表
if (copyCur->next)
copyCur->next = copyCur->next->next; // 移动复制链表
cur = cur->next; // 继续移动原链表
copyCur = copyCur->next; // 继续移动复制链表
}
return newHead; // 返回新链表的头节点
}
};
法2（利用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)
{
if (!head) return nullptr; // 处理空链表
map<Node*, Node*> nodeMap; // 创建一个映射，原节点 -> 新节点
Node* cur = head;
// 第一遍历：复制节点并建立映射关系
while (cur)
{
nodeMap[cur] = new Node(cur->val); // 创建新节点并存入映射
cur = cur->next; // 移动到下一个原节点
}
// 第二遍历：设置新节点的 next 和 random 指针
cur = head;
while (cur)
{
nodeMap[cur]->next = nodeMap[cur->next]; // 设置 next 指针
nodeMap[cur]->random = nodeMap[cur->random]; // 设置 random 指针
cur = cur->next; // 移动到下一个原节点
}
return nodeMap[head]; // 返回新链表的头节点
}
};class Solution
{
public:
struct myCmp
{
bool operator()(const pair<string, int>& p1, const pair<string, int>& p2)
{
// 由于出现次数相同的单词需要用字典序排序，所以加上后面的这个判断条件（sort本身是不稳定排序）
return p1.second > p2.second || (p1.second == p2.second && p1.first < p2.first);
// 次数不同次数大的在前面，次数相同字典序小的在前面
// 如果没有字典序后面的判断也可以，但是需要用stable_sort
}
};
vector<string> topKFrequent(vector<string>& words, int k)
{
// 给的单词列表需要排序，又因为需要统计次数，那么自然需要map
map<string, int> m;
for(auto& e : words)
m[e]++;
vector<pair<string, int>> vs(m.begin(), m.end());
// 其实插入后m和vs已经是字典序了
// 不过sort排序不是一个稳定排序，并且sort默认的仿函数不能解决我们pair比较的需求
sort(vs.begin(), vs.end(), myCmp());
vector<string> ret;
auto vsit = vs.begin();
while(k--)
{
ret.push_back((*vsit).first);
++vsit;
}
return ret;
}
};完结撒花~~~~~~~~~~~
耶╰(✿´⌣`✿)╯♡
原文地址：https://blog.csdn.net/2301_79830926/article/details/143020746
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！