CD72.【C++ Dev】map和set
讲解C++中set和map的使用方法。对于set，介绍了其底层红黑树实现导致的深拷贝问题，以及三种删除节点方法的对比，推荐直接使用erase(val)方法。对于map，详细说明了pair的结构和四种插入方法，推荐使用make_pair或C++11的多参构造。重点分析了operator[]的实现原理，它通过insert实现插入和修改功能，可能导致意外插入默认构造值。文章通过代码示例和反汇编验证了这些
目录
如果insert的元素的key相同但value不相同,insert函数如何处理?
1.知识回顾
之前在C++ Contest专栏的文章提到过,但讲得不深入
下面深入讲解map和set的使用
2.set
从https://legacy.cplusplus.com/reference/set/set/?kw=set网站来看,
有两个提供缺省参数的模版参数Compare和Alloc,Compare是仿函数,Alloc是空间配置器,空间配置器一般不用改
提几个其他要点
1.由于set的底层是红黑树实现的,那么调用拷贝构造函数或者operator=成员函数会深拷贝一整棵树,空间开销较大
2.其实set也可以存key/value,但要存结构体,还要写仿函数,非常麻烦,建议用map
3.set的迭代器其实是const_iterator,不可修改
typedef typename _Rep_type::const_iterator iterator;//SGI STL删除节点的几种方法对比
erase成员函数的说明:
假设set<int> st中有一个节点3,删除3的几种方法:
//方法1
st.erase(3);
//方法2
auto pos=st.find(3);
st.erase(pos);
//方法3
auto pos = find(st.begin(), st.end(), 3);//<algorithm>的find函数
st.erase(pos);方法1
是size_type erase (const value_type& val);写法
如果没找到3,不会抛异常;
如果找到3,直接删除,时间复杂度为
不容易出错,推荐这样写
方法2
是void erase (iterator position);写法
如果没找到3,那么find(3)会返回st.end(),当erase(st.end())时,会直接抛异常,如果没有捕获异常,会终止进程,因此不建议这样写
如果能找到3,直接删除,那么时间复杂度为
方法3
如果没找到3,那么find(3)会返回st.end(),当erase(st.end())时,也会直接抛异常
如果能找到3,直接删除,那么时间复杂度为,从头到尾遍历每一个迭代器,是暴力查找,非常不推荐这样写
3.map
从https://legacy.cplusplus.com/reference/map/map/?kw=map网站来看,
和set一样,有两个提供缺省参数的模版参数Compare和Alloc,Compare是仿函数,但比较的关键字默认是Key
map的每一个元素其实是pair<const Key,T>,说明Key不能修改,T可以修改
map的iterator迭代器并没有像set一样重定义为const_iterator,因为map要修改<K,V>的V
typedef typename _Rep_type::iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;pair
之前在U1.【UVA】块问题-The Blocks Problem(补充了pair的使用)文章简单提到过pair的使用:
头文件:<utility>
pair可以简单理解为C++里面的结构体,里面两个变量
struct pair { type first; type second; }first和second可以定义为自己想要的任意类型
其实上面说的不准确,pair其实是类,在SGI STL的stl_pair.h中是这样定义的:
pair有自己的构造函数
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) {}
#ifdef __STL_MEMBER_TEMPLATES
template <class _U1, class _U2>
pair(const pair<_U1, _U2>& __p) : first(__p.first), second(__p.second) {}
#endif
};但pair并没有重载operator<<和operator*,需要自行写,例如:
cout << (*it).first << ":" << (*it).second << endl;
//或者
cout << it->first << ":" << it->second << endl;insert成员函数的几种方法
在https://legacy.cplusplus.com/reference/map/map/insert/网站中,
方法1: 先定义pair后,再插入至map中
map<string,int> mp;
pair<string, int> pack("test", 1);
mp.insert(pack);方法2: 使用匿名对象
直接向map中插入匿名对象
map<string,int> mp;
mp.insert(pair<string, int>("test", 1));方法3: C++98的make_pair函数
使用make_pair前先包含<utility>头文件
map<string,int> mp;
mp.insert(make_pair("test", 1));方法4: C++11的多参数的构造函数隐式类型转换
C++98支持单参数的构造函数隐式类型转换,但不支持多参数的构造函数隐式类型转换
map<string,int> mp;
mp.insert({ "test", 1 });反汇编分析:
下面会产生临时对象,需要用const引用,防止权限变大
推荐方法3和方法4的写法
插入单个pair时insert的返回值
single element (1) pair<iterator,bool> insert (const value_type& val);
会发现返回值是pair<iterator,bool>,并不是返回bool
从英文解读可以得知:
1. 如果key已经在树里面,返回pair<树里面key所在节点的iterator, false>
2. 如果key不在树里面,返回pair<新插入key所在节点的iterator, true>
可以看出Insert有插入和查找的价值
查找元素是否存在可以从insert的返回的pair的第二个bool值看出
如果insert的元素的key相同但value不相同,insert函数如何处理?
map<string, int> mp;
mp.insert({ "test",1 });
mp.insert({ "word",2 });
mp.insert({ "test",2 });//前面已经插入了{ "test",1 }了问题:执行mp.insert({ "test",2 })后,原来"test"对应的1会被2覆盖吗?
调试验证:
只比较key,如果key已经有了,匿那么就不插入了,不存在覆盖这一说法
operator[]
定义
返回值是<K,V>的V的引用,没有用const修饰,可以修改
operator[]可以实现覆盖或者插入的功能
插入
示例代码1
template<class T>
class Myclass
{
public:
Myclass(const T& x = T())
:val(x)
{ }
private:
T val;
};
int main()
{
map<string, Myclass<int>> mp;
mp["test"];//等价为mp.insert({"test",Myclass<int>()});
return 0;
}mp["test"]会插入pair<string, Myclass<int>>,其中Myclass<int>会调用默认构造函数为value提供初始值
示例代码2
map<string, int> mp;
mp["word"]=1;mp["word"]=1会插入key为"word",value为1的元素
覆盖
map<string, int> mp;
mp["word"]=1;
mp["word"]=2;//将value改为2这样比用迭代器修改要方便
operator[]的等价写法
调用operator[]的等价写法
cplusplus网提供的写法:
mapped_type& operator[] (const key_type& k)
{
return (*((this->insert(make_pair(k,mapped_type()))).first)).second;
}
可以看到是通过insert来实现的
通过继承验证正确性
VS2022上验证,使用继承来添加自制的operator[]
#include <iostream>
#include <map>
#include <utility>
namespace mystl
{
//截取自的VS2022的STL中的参数
template <class _Kty, class _Ty, class _Pr = std::less<_Kty>, class _Alloc = std::allocator<std::pair<const _Kty, _Ty>>>
class map : public std::map<_Kty, _Ty, _Pr, _Alloc>
{
public:
_Ty& operator[](const _Kty& __k)
{
return (*((this->insert(std::make_pair(__k, _Ty()))).first)).second;
}
};
}
int main()
{
mystl::map<int, int> mp;
mp[1] = 10;
std::cout << mp[1] << std::endl;
return 0;
}运行结果:退出代码为0
函数隐藏: mp[1]只会调用mystl::map的operator[],不会调用std::map的operator[],就近原则
(有关函数隐藏的知识参见CD58.【C++ Dev】继承(2)文章)
分析
将长的式子分成几个部分:
构造pair:
再插入pair:
如果插入成功
insert返回pair<新插入key所在节点的iterator, true>
取出iterator,其指向pair元素
调用operator*,获取pair元素的引用
获取pair元素<K,V>中V的引用
如果插入失败
insert返回pair<新插入key所在节点的iterator, true>
之后的步骤和插入成功情况一样
这样就能理解为什么之前在CC42.【C++ Cont】STL库的红黑树set和map的使用文章说的"使用[]时可能会插入不想要的值!!!",因为会调用<K,V>中V的默认构造函数
例如以下代码:
map<string, string> dict;
dict.insert(make_pair("string", "字符串"));
dict.insert(make_pair("sort", "排序"));
dict.insert(make_pair("insert", "插入"));
cout << dict["sort"] << endl; // 查找和读
dict["map"]; // 插入
dict["map"] = "映射,地图"; // 修改
dict["insert"] = "xxx"; // 修改
dict["set"] = "集合"; // 插入+修改4.multimap
从https://legacy.cplusplus.com/reference/map/multimap/?kw=multimap网站来看:
注意:multimap没有operator[],一个key在multimap中可以对应多个value
multimap的insert不像map的insert那样返回pair<iterator,bool>,multimap的insert在任何情况下都插入成功,因此返回iterator或者void
multimap的其他成员函数使用方法和map一样,这里不再赘述
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
26
0- 0
已为社区贡献6条内容
所有评论(0)