map和set
一.序列式容器和关联式容器
-
前面我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
-
关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。关联式容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。
-
本章节讲解的map和set底层是红黑树，红黑树是一颗平衡⼆叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。而unordered_map和unordered_set的低层是哈希表。
二.set系列的使用
1.set和multiset参考文档
2.set类的介绍
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;
- set的声明如上，T就是set底层关键字key的类型。
- set默认要求T支持小于较，如果不支持或者想按自己的需求走可以自行实现仿函数传给第⼆个模版参数。例如：传入日期类的指针比较日期。
- set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。
- 一般情况下，我们都不需要传后两个模版参数。
- set底层是用红黑树实现，增删查效率是O(logN) ，迭代器遍历是走的搜索树的中序，由于二叉搜索树的性质，左子树小于根，根小于右子树，所以中序是有序的。
3.set的构造和迭代器
-
set的构造我们关注以下几个接口即可。
-
set的支持正向和反向迭代遍历（双向迭代器：支持++/–，但是不支持+/-），遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。
//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 (4) C++11支持: 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();
int main()
{
vector<int> v = { 1,5,4,2,3,6,7,8,9 };
set<int> s1; //无参默认构造
set<int> s2(v.begin(), v.end()); //迭代器区间构造
set<int> s3(s2); //拷贝构造
set<int> s4 = { 1,5,4,2,3,6,7,8,9 }; //列表初始化构造
//1.正向迭代器
auto it = s2.begin();
while (it != s2.end())
{
cout << *it << " "; //输出：1 2 3 4 5 6 7 8 9
++it;
}
cout << endl;
//2.set是双向迭代器迭代器支持++/--，但是不是随机迭代器不支持+/-
it = --s2.end(); auto end = --s2.begin();
while (it != end)
{
cout << *it << " "; //输出：9 8 7 6 5 4 3 2 1
--it;
}
cout << endl;
//3.反向迭代器
set<int>::reverse_iterator rit = s4.rbegin();
while (rit != s4.rend())
{
cout << *rit << " "; //输出 9 8 7 6 5 4 3 2 1
++rit;
}
cout << endl;
return 0;
}
4.set的增删查
set支持增删查，但是set不支持修改，因为修改之后就会可能失去红黑树的性质。
set的增删查关注以下几个接口即可：
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;
//1.单个数据插入，如果已经存在则插入失败
pair<iterator, bool> insert(const value_type& val);
//2.列表插入，已经在容器中存在的值不会插入
void insert(initializer_list<value_type> il);
//3.迭代器区间插入，已经在容器中存在的值不会插入
template <class InputIterator>
void insert(InputIterator first, InputIterator last);
//查找val，返回val所在的迭代器，没有找到返回end()
iterator find(const value_type& val);
//查找val，返回Val的个数
size_type count(const value_type& val) const;
//1.删除一个迭代器位置的值
iterator erase(const_iterator position);
//2.删除val，val不存在返回0，存在返回1
size_type erase(const value_type& val);
//3.删除一段迭代器区间的值
iterator erase(const_iterator first, const_iterator last);
//返回大于等于val位置的迭代器
iterator lower_bound(const value_type& val) const;
//返回大于val位置的迭代器
iterator upper_bound(const value_type& val) const;
Member types
key_type -> The first template parameter (T)
value_type -> The first template parameter (T)
注意：
- set是key结构, map才是key/value结构, 这里的key_type和value_type是为了保持与map一致，所以才有了value_type，在set中其实就是key，当然key_type也是key。
- set不支持插入相同的数据，multiset支持插入相同的数据。
5.insert和迭代器遍历使用
int main()
{
vector<int> v{ 8,7,9 };
set<int> s1;
s1.insert(1);
s1.insert(2);
s1.insert(2); //1.单个数据插入，如果已经存在则插入失败
s1.insert(3);
s1.insert({ 4,5,6,5 }); //2.插入列表，同理如果已经存在则该数据插入失败
s1.insert(v.begin(), v.end()); //3.插入迭代器区间
//排序+去重
//升序<：set<int, less<int>> s;
//降序>：set<int, greater<int>> s;
set<int> s; //默认传入了仿函数less<int>
s.insert(5);
s.insert(2);
s.insert(7);
s.insert(5);
s.insert(8);
s.insert(1);
set<int>::iterator it = s.begin();
while (it != s.end())
{
//*it = 10; 不支持修改
cout << *it << " "; //输出：1 2 5 7 8
++it;
}
//set(initializer_list<value_type> il);
//单参数支持隐式类型转换：构造tmp+用tmp拷贝构造strset1——>优化为直接构造strset1
set<string> strset1 = { "sort", "insert", "add" };
//调用默认构造
set<string> strset2({ "sort", "insert", "add" });
//遍历strset1比较ascll码大小顺序遍历的：set的范围for本质就是迭代器的中序遍历
for (auto& e : strset1)
{
cout << e << " "; //输出：add insert sort
}
cout << endl;
return 0;
}
6.find和erase的使用
- 算法库的遍历查找，适用于各种容器： O(N)
auto pos1 = find(s.begin(), s.end(), x); - set自身实现的查找，利用二叉搜索树进行查找： O(logN)
auto pos2 = s.find(x);
//1.删除一个迭代器位置的值
iterator erase (const_iterator position);
//2.删除val，val不存在返回0，存在返回1
size_type erase (const value_type& val);
//3.删除⼀段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);
//查找val，返回val所在的迭代器，没有找到返回end()
iterator find (const value_type& val);
//查找val，返回Val的个数
size_type count (const value_type& val) const;
注意：删除具体的值返回size_type而不是bool是为了与multiset保持一致，multiset含有重复数据（例如：multiset中有3个5，若要删除5，则返回值就是3）
int main()
{
set<int> s = { 4,6,5,8,9,7,2,3,1 };
//1.迭代器删除最小值
s.erase(s.begin());
//2.删除具体的值val：低层就是find+迭代器删除
int x;
cin >> x;
int num = s.erase(x);
if (num == 0)
cout << x << "不存在！" << endl;
else
cout << x << "删除成功！" << endl;
//3.删除一段迭代器区间的值
auto first = s.find(4);
auto last = s.find(6);
s.erase(first, last); //删除的值位于迭代器区间[first,last)中
for (auto e : s)
cout << e << " ";
//find+迭代器删除：与上面等价
int y;
cin >> y;
auto pos = s.find(y); //找到返回该值的迭代器，找不到返回s.end()
if (pos != s.end())
s.erase(pos);
else
cout << y << "不存在！" << endl;
//利用count间接实现快速查找
int z;
cin >> z;
if (s.count(z))
cout << z << "在！" << endl;
else
cout << z << "不存在！" << endl;
return 0;
}
7.erase迭代器失效问题
int main()
{
set<int> s = { 1,5,6,3,2,4 };
auto pos = s.find(3);
s.erase(pos); //pos位置的迭代器失效
cout << *pos << endl; //强行访问导致程序崩溃
pos = s.erase(pos); //解决办法
cout << *pos << endl; //输出：3的中序的下一个迭代器4
//但是若查找的是6的话，那么删除6后迭代器pos就变成了s.end()，此时访问程序崩溃
return 0;
}
8.lower_bound与upper_bound
//返回大于等于val位置的迭代器：按照搜索树的规则找
iterator lower_bound(const value_type& val) const;
//返回大于val位置的迭代器：按照搜索树的规则找
iterator upper_bound(const value_type& val) const;
int main()
{
set<int> s1;
for (int i = 1; i < 10; i++)
{
s1.insert(i * 10); //10 20 30 40 50 60 70 80 90
}
set<int> s2(s1);
cout << endl;
//要求：删除[30, 50]区间的值
//1.erase的迭代器区间删除左闭右开：[)
auto first = s1.find(30);
auto last = s1.find(70);
s1.erase(first, last);
for (auto e : s1)
{
cout << e << " "; //10 20 70 80 90
}
cout << endl;
//要求：删除[25, 55]区间的值：则上面的方法无效，因为find查找不到，返回的是s.end()迭代器
//此时需要用到lower_bound和upper_bound
auto itlow = s2.lower_bound(25); //返回 >= 25的迭代器：就是30位置的迭代器
auto itup = s2.upper_bound(55); //返回 > 55的迭代器：就是60位置的迭代器
s2.erase(itlow, itup);
for (auto e : s2)
{
cout << e << " "; //10 20 60 70 80 90
}
cout << endl;
return 0;
}
9.multiset和set的差异
multiset和set的使用基本完全类似，主要区别点在于multiset支持值冗余，那么insert/find/count/erase都围绕着支持值冗余有所差异，具体参看下面的样例代码理解：
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 << " "; //输出：2 2 4 4 4 4 5 7 8 9
++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;
}
注意：查找3时，返回的是中序的第一个3的迭代器。好处：若后面还有3，则迭代器不断++就可以找到后面的所有3。
10.set解决：leetcode例题
1.两个数组的交集
解法：set+双指针
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
//1.将nums1和nums2放入set中：去重+迭代器遍历时是有序的
set<int> s1(nums1.begin(), nums1.end());
set<int> s2(nums2.begin(), nums2.end());
vector<int> ret;
//2.双指针
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中
{
ret.push_back(*it1);
++it1;
++it2;
}
}
return ret;
}
};
已知：集合A = {1, 2, 3, 4, 5}，集合B = {4, 5, 6, 7, 8}，求A与B的差集和B与A的差集？
A - B = A - AB = {1, 2, 3}；
B - A = B - AB = {6, 7, 8}；
思考：如何找差集？
- 小的就是差集。
- 相等就同时++。
- 若其中一个走完了另一个没走完的值也是属于差集。
2.交集与差集的应用：数据同步
云相册是一种将照片和视频等多媒体内容存储在云端（即互联网上的服务器）的相册服务。具体来说，云相册具备以下几个核心特点和优势：
- 用户可以将手机、相机等设备中的照片和视频上传到云端，通过云相册提供的平台，随时随地查看、编辑和分享这些照片和视频。
- 支持多设备同步，用户可以在任何设备上查看和编辑自己的照片和视频，无需担心数据丢失或无法访问的问题。
- 解决存储问题：传统存储方式存在容量有限、携带不便等问题，云相册的出现极大地缓解了这些问题，用户可以无限量地存储照片和视频。
- 跨平台使用：无论是iOS、Android还是Windows等操作系统，用户都可以通过相应的应用程序或网页版云相册来访问和管理自己的照片和视频。
- 节省设备空间：存储在云端的照片和视频不会占用设备的存储空间，用户可以释放设备空间以存储更多其他类型的文件。
3.环型链表||
解法一：快慢指针
在C语言中：我们通过证明一个指针从头开始走一个指针从相遇点开始走，会在入口点相遇，理解证明都会很麻烦。
struct ListNode* detectCycle(struct ListNode* head)
{
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
//有环
ListNode* meet = slow;//相遇点
while (meet != head)
{
//一个指针从相遇点开始走，一个指针从起点开始走，最终一定在入环点相遇
head = head->next;
meet = meet->next;
}
return meet;//入环点
}
}
return NULL;//无环
}
解法二：set容器
而C++中的set查找记录解决非常简单方便，这里体现了set在解决一些问题时的价值，完全是降维打击。
class Solution {
public:
ListNode *detectCycle(ListNode *head)
{
set<ListNode*> s;
ListNode* cur = head;
while(cur) //遍历链表
{
if(s.count(cur)) return cur; //若set中有cur，那么链表带环并且cur就是入口点
else s.insert(cur); //若set中没有cur，那么cur插入到set中
cur = cur->next;
}
return nullptr; //此时遍历完链表后，说明链表不带环
}
};
三.map系列的使用
1.set和multiset参考文档
2.map类的介绍
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的声明如上，Key就是map底层关键字的类型，T是map底层value的类型。
- map默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第⼆个模版参数。
- map底层存储数据的内存是从空间配置器申请的。
- 一般情况下，我们都不需要传后两个模版参数。
- map底层是用红黑树实现，增删查改效率是O(logN) ，迭代器遍历是走的中序，所以是按key有序顺序遍历的。
3.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) //创建pair对象
{
return (pair<T1, T2>(x, y));
}
Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>
注意：map是key/value搜索场景的结构，key_type就是key，而mapped_type就是value，而value_type才是pair。
4.map的构造和迭代器
-
map的构造我们关注以下几个接口即可。
-
map的支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，map支持修改value数据，但是不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。
//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 (4) 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();
int main()
{
map<int, int> m1; //无参默认构造
map<int, int> m2(m1.begin(), m1.end()); //迭代器区间构造
map<int, int> m3(m2); //拷贝构造
map<int, int> m4 = { {1,1},{2,2} }; //列表初始化构造
//1.正向迭代器
auto it = m4.begin();
while (it != m4.end())
{
cout << it->first << " " << it->second << endl; //输出：1 2 1 2
++it;
}
cout << endl;
//2.反向迭代器
map<int, int>::reverse_iterator rit = m4.rbegin();
while (rit != m4.rend())
{
cout << rit->first << " " << rit->second << endl; //输出：1 2 1 2
++rit;
}
cout << endl;
return 0;
}
5.map的增删查
- map的增删查关注以下几个接口即可：
- map插入的是pair键值对数据，跟set所有不同，但是查和删的接口只用关键字key跟set是完全类似的，不过find返回iterator，不仅仅可以确认key在不在，还找到key映射的value，同时通过迭代还可以修改value。
Member types
key_type -> The first template parameter (Key) //key
mapped_type -> The second template parameter (T) //value
value_type -> pair<const key_type,mapped_type> //pair
//单个数据插入，如果已经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 upper_bound(const key_type& k) const;
6.map构造遍历及增删查的使用
int main()
{
map<string, string> dict;
pair<string, string> kv1("first", "第一个"); //插入有名对象
dict.insert(kv1);
dict.insert(pair<string, string>("second", "第二个")); //插入匿名对象
dict.insert(make_pair("sort", "排序")); //利用make_pair函数返回构造的pair对象，插入
dict.insert({ "auto", "自动的" }); //C++11支持多参数隐式类型转换成pair对象，插入
dict.insert({ "first", "首先" }); //"first"已经存在，插入失败
//map<string, string>::iterator it = dict.begin();
auto it = dict.begin();
while (it != dict.end())
{
//不能这样写，pair没有重载流插入和流提取，*it是pair
//cout << *it << endl;
//++it;
//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;
//it->first += 'x'; key不支持修改
//it->second += 'x'; value支持修改
}
cout << endl;
//范围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中的erase可以说一模一样，就不做演示了
return 0;
}
7.map的数据修改：重载operator[]
- 前面我提到map支持修改mapped_type数据，不支持修改key数据，修改关键字数据，破坏了底层搜索树的结构。
- map第一个支持修改的方式是通过迭代器，迭代器遍历时或者find返回key所在的iterator修改，map还有一个非常重要的修改接口operator[]，但是operator[]不仅仅支持修改，还支持插入数据和查找数据，所以他是一个多功能复合接口。
- 需要注意从内部实现角度，map这理把我们传统说的value值，给的是T类型，typedef为mapped_type。而value_type是红黑树结点中存储的pair键值对值。日常使用我们还是习惯将这里的T映射值叫做value。
Member types
key_type -> The first template parameter (Key)
mapped_type -> The second template parameter (T)
value_type -> pair<const key_type,mapped_type>
//查找k，返回k所在的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的mapped_type(value)值
iterator find(const key_type& k);
//insert插入一个pair<key, T>对象
//1.如果key已经在map中，插入失败，则返回一个pair<iterator,bool>对象，
//返回pair对象first是key所在结点的迭代器，second是false
//2.如果key不在map中，插入成功，则返回一个pair<iterator,bool>对象，
//返回pair对象first是新插入key所在结点的迭代器，second是true
//也就是说无论插入成功还是失败，返回pair<iterator,bool>对象的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.如果key不在map中，insert会插入key和mapped_type(value)的默认值，同时[]返回结点pair<iterator,bool>中存储
//中的迭代器中存储的mapped_type(value)值的引用，那么我们可以通过引用修改返映射值。所以[]具备了插入 + 修改功能
//2.如果k在map中，insert会插入失败，但是insert返回pair对象的first是指向与key值相同的结点的
//迭代器，同时[]返回结点中存储mapped_type(value)值的引用，所以[]具备了查找 + 修改的功能
pair<iterator, bool> ret = insert({ k, mapped_type() });
iterator it = ret.first;
return it->second;
}
int main()
{
map<string, string> dict;
dict.insert(make_pair("sort", "排序"));
//insert不存在：插入
dict["insert"]; //插入{"insert", string()}
//left不存在：插入+修改
dict["left"] = "左边"; //将""修改为"左边"
//left存在：修改
dict["left"] = "左边、剩余"; //将"左边"修改为"左边、剩余"
//left存在：查找（确认left在才能这么用，否则就是插入了）
cout << dict["left"] << endl; //输出：左边、剩余
//boy不存在：插入
cout << dict["boy"] << endl; //输出：什么都没有
return 0;
}
8.map的迭代器和[]功能样例
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;
}
在实践当中不太喜欢用上面的代码来统计次数，而喜欢用重载的[]来统计次数，如下：
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;
}
9.multimap和map的差异
multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如find时，有多个key，返回中序第一个。其次就是multimap不支持[]，因为支持key冗余，[]就只能支持插入了，不能支持修改。
int main()
{
multimap<string, string> dict;
//插入一定成功
dict.insert({ "sort", "排序" });
dict.insert({ "sort", "排序1" });
dict.insert({ "sort", "排序2" });
dict.insert({ "sort", "排序3" });
dict.insert({ "sort", "排序" });
dict.insert({ "string", "字符串" });
//将sort全部删除
dict.erase("sort");
return 0;
}
10.map解决：leetcode例题
1.随机链表的复制
解法一：不使用map容器
class Solution {
public:
Node* copyRandomList(Node* head)
{
//1.拷贝节点插入在原节点的后面
Node* cur = head;
while(cur)
{
Node* copy = new Node(cur->val); //创建新节点
copy->next = cur->next; //插入新节点
cur->next = copy;
cur = copy->next;
}
//2.修改拷贝节点的random指针的指向
cur = head;
while(cur)
{
Node* copy = cur->next;
if(cur->random == nullptr) copy->random = nullptr;
else copy->random = cur->random->next;
cur = copy->next;
}
//3.把拷贝节点取下来尾插形成新链表，然后恢复原链表
Node* copyHead = nullptr, *copyTail = nullptr;
cur = head;
while(cur)
{
Node* copy = cur->next;
Node* next = copy->next;
if(copyHead == nullptr)
{
copyHead = copyTail = copy;
}
else
{
copyTail->next = copy; //尾差
copyTail = copyTail->next;
}
cur->next = next;
cur = next;
}
return copyHead;
}
};
解法二：使用map容器
为了控制随机指针，我们将拷贝结点链接在原节点的后面解决，后面拷贝节点还得解下来链接，非常麻烦。这里我们直接让{原结点，拷贝结点}建立映射关系放到map中，控制随机指针会非常简单方便，这里体现了map在解决一些问题时的价值，完全是降维打击。
class Solution {
public:
Node* copyRandomList(Node* head)
{
//创建map：原节点映射拷贝节点
map<Node*, Node*> nodeMap;
//1.拷贝新链表
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;
}
//原节点映射拷贝节点
nodeMap[cur] = copyTail; //或者nodeMap.insert({cur, copyTail});
cur = cur->next;
}
//2.利用映射处理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;
}
};
2.前K个高频单词
本题目我们利用map统计出次数以后，返回的答案应该按单词出现频率由高到低排序，有一个特殊要求，如果不同的单词有相同出现频率，按字典顺序排序（string从小到大排序）。
解法一：map+排序
用排序找前k个单词，因为map中已经对key单词排序过，也就意味着遍历map时，次数相同的单词，字典序小的在前面，字典序大的在后面。那么我们将数据放到vector中用一个稳定的排序就可以实现上面特殊要求，但是sort底层是快排，是不稳定的，所以我们要用stable_sort，他是稳定的。
class Solution {
public:
struct kvCompare
{
bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
{
//要实现int的降序用的是>
//int相等: 要实现string的升序用的是<
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& e : words) countMap[e]++; //统计单词出现的次数
//利用数组进行排序：vector支持随机迭代器，map不支持随机迭代器
vector<pair<string, int>> v(countMap.begin(), countMap.end());
//需要用pair的第二个int数据排降序：自己实现仿函数（函数传的是仿函数对象：可以传一个匿名对象）
//v是由countMap用迭代器区间初始化的，满足字典序
//而题目要求次数出现多的排在前面，若次数出现相等的情况下，按照字典序排
//若用普通的sort(快排)是不稳定的，算法库中有稳定的排序stable_sort(大概是归并)可以满足题目要求
//stable_sort(v.begin(), v.end(), kvCompare());
//或者修改仿函数也可以完成目的：int排降序就是>; int相等的话: string排升序就是<
sort(v.begin(), v.end(), kvCompare());
vector<string> ret;
for(int i = 0; i < k; i++)
{
ret.push_back(v[i].first); //尾插前K个高频单词
}
return ret;
}
};
解法二：map+优先级队列
将map统计出的次数的数据放到priority_queue中来选出前k个。利用仿函数强行控制次数相等的，字典序小的在前面。
class Solution {
public:
struct kvCompare
{
bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
{
//注意：堆的逻辑是发过来的
//要实现int的大堆用的是<;
//int相等时：要实现string的小堆用的是>;
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& e : words) countMap[e]++; //统计单词出现的次数
//利用优先级队列：将int大的放在上面; 若int相等: 将字典序小的放上面
//模版传的是类型：直接传仿函数，仿函数就是一个类
priority_queue<pair<string, int>, vector<pair<string, int>>, kvCompare> p(countMap.begin(), countMap.end());
vector<string> ret;
for(int i = 0; i < k; i++)
{
ret.push_back(p.top().first);
p.pop();
}
return ret;
}
};
解法三：也是map+优先级队列
建立小堆，再不断出堆顶数据，实现堆中全是满足要求的数据。
class Solution {
public:
struct kvCompare
{
bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
{
//要实现int的小堆用的是>;
//int相等时：要实现string的大堆用的是<;
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& e : words) countMap[e]++;
priority_queue<pair<string, int>, vector<pair<string, int>>, kvCompare> p; //小堆
for(auto& e : countMap)
{
p.push(e); //入堆
if (p.size() > k) //若堆中的个数大于K
{
p.pop(); //删除堆顶：小的出堆
}
}
vector<string> ret(k);
for (int i = k - 1; i >= 0; i--)
{
ret[i] = p.top().first; //将小的放在后面，大的放在前面
p.pop(); //出堆
}
return ret;
}
};