由于博主的能力有限,所以为了方便大家对于map和set的学习,我放一个官方的map和set的链接供大家参考: https://cplusplus.com/
在初阶阶段,我们已经接触过STL中的部分容器,比如:vector、list、deque,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。那什么是关联式容器?它与序列式容器有什么区别?
关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是<key, value>结构的键值对,在数据检索时比序列式容器效率更高。
在二叉搜索树的应用中我们就了解到了kv,他们可以用于单词的翻译等,其实这里的k就是我们所说的键,而v就是值,他们是以键值对的形式存入容器的,而我们今天所学习的map就是kv结构
用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代表键值,value表示与key对应的信息。比如:现在要建立一个英汉互译的字典,那该字典中必然有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应该单词,在词典中就可以找到与其对应的中文含义。
为了方便大家的理解,我们在stl的源码中提取了对于键值对的定义:
我们从map的官方解释中可以看到,键值对的类型是 pair<const key,T> 源码中就是定义了pair的结构体 在结构体pair中两个成员,一个为 first,另一个为second,first就是我们所说的键key,second就是值value
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)
{}
};
根据应用场景的不桶,STL总共实现了两种不同结构的管理式容器:树型结构与哈希结构。树型结构的关联式容器主要有四种:map、set、multimap、multiset。这四种容器的共同点是:使用平衡搜索树(即红黑树)作为其底层结果,容器中的元素是一个有序的序列。
typedef pair<const key, T> value_type;
map的模板参数
key: 键值对中key的类型 T: 键值对中value的类型 Compare: 比较器的类型,map中的元素是按照key来比较的,缺省情况下按照小于来比较,一般情况下(内置类型元素)该参数不需要传递,如果无法比较时(自定义类型),需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递) Alloc:通过空间配置器来申请底层空间,不需要用户传递,除非用户不想使用标准库提供的空间配置器
注意:在使用map时,需要包含头文件,set也一样
map的构造:
map的迭代器:
关于迭代器的使用我们依旧用代码来了解,更容易理解
map<string, string> mp;
mp["插入"] = "insert";
for (map<string, string>::iterator i = mp.begin(); i!=mp.end();i++)
{
cout << i->first << ":" << i->second << endl;
}
return 0;
map<string, string> mp;
mp["插入"] = "insert";
mp["删除"] = "pop";
mp["字符串"] = "string";
for (map<string, string>::reverse_iterator i = mp.rbegin(); i!=mp.rend();i++)
{
cout << i->first << ":" << i->second << endl;
}
我们可以看到map的一个很有实用价值的点: 下标访问符号[]
它可以修改键值对,新增键值对,查找键值对
在元素访问时,有一个与operator[]类似的操作at()(该函数不常用)函数,都是通过key找到与key对应的value然后返回其引用,不同的是:当key不存在时,operator[]用默认value与key构造键值对然后插入,返回该默认value,at()函数直接抛异常。
insert函数:
map<string, string> mp;
mp["插入"] = "insert";
mp["删除"] = "pop";
mp["字符串"] = "string";
mp.insert(pair <string, string>("结束", "end"));
for (map<string, string>::iterator i = mp.begin(); i!=mp.end();i++)
{
cout << i->first << ":" << i->second << endl;
}
return 0;
很多同学会有疑惑,为什么插入的键值对到第二个去了呢,不是 在最后一个吗,其实是因为插入后map根据key进行了自动的排序
erase函数: erase函数可以根据key来删除指定的键值对
map<string, string> mp;
mp["插入"] = "insert";
mp["删除"] = "pop";
mp["字符串"] = "string";
mp.insert(pair <string, string>("结束", "end"));
mp.erase("结束");
for (map<string, string>::iterator i = mp.begin(); i!=mp.end();i++)
{
cout << i->first << ":" << i->second << endl;
}
return 0;
find函数: find函数可以根据key返回这个节点,如果找不到就返回cend
map<string, string> mp;
mp["插入"] = "insert";
mp["删除"] = "pop";
mp["字符串"] = "string";
mp.insert(pair <string, string>("结束", "end"));
mp.erase("结束");
for (map<string, string>::iterator i = mp.begin(); i!=mp.end();i++)
{
cout << i->first << ":" << i->second << endl;
}
auto x=mp.find("删除");
cout << x->first << ":" << x->second << endl;
return 0;
count函数: count函数能够根据key计算这个容器中的key的个数,要么是0,要么是1,就算是你后面插入也插入不进去
map<string, string> mp;
mp["插入"] = "insert";
mp["删除"] = "pop";
mp["字符串"] = "string";
mp.insert(pair <string, string>("结束", "end"));
mp.insert(pair<string, string>("字符串", "end"));
mp.erase("结束");
for (map<string, string>::iterator i = mp.begin(); i!=mp.end();i++)
{
cout << i->first << ":" << i->second << endl;
}
cout << mp.count("字符串");
return 0;
总结:
注意:multimap和map的唯一不同就是:map中的key是唯一的,而multimap中key是可以重复的。
并且map和mutimap的头文件都是一样的,但是multimap没有重载[]符号
set的简单介绍:
这里还有几个需要注意的点:
set的使用
其实set的使用和map的区别不大,这里不做过多的讲解:
set<int> st;
st.insert(1);
st.insert(2);
st.insert(3);
st.insert(3);
st.insert(4);
for (set<int>::iterator i = st.begin(); i != st.end(); i++)
{
cout << *i << endl;
}
return 0;
从本段代码的输出结果来看就知道set的去重效果了
我们可以用迭代器来排出一个有序的序列:
set<int> st;
st.insert(5);
st.insert(2);
st.insert(3);
st.insert(3);
st.insert(4);
for (set<int>::iterator i = st.begin(); i != st.end(); i++)
{
cout << *i << endl;
}
return 0;
注意:
其实set和multiset的区别就在于multiset可以有相同的元素,并且他的底层实现是存储<value, value>的键值对,而set是<key, value>的键值对
multiset<int> st;
st.insert(5);
st.insert(2);
st.insert(3);
st.insert(3);
st.insert(4);
for (multiset<int>::iterator i = st.begin(); i != st.end(); i++)
{
cout << *i << endl;
}
return 0;
好了,今天的分享到这里就结束了,感谢大家的支持!