文章目录
- 前言
- 一、预备知识
- 关联式容器
- 键值对
- 二、set
- 何为set?
- set的使用
- set的特点
- multiset
- 三、map
- 何为map?
- map中的operator[ ]
- multimap
- 总结
前言
刚学完二叉搜索树,我们马上来感受一下直接与它相关的两个容器吧!
一、预备知识
关联式容器
在以往的 STL 容器学习中,我们接触到的都是 序列式容器,比如 string、vector、list、deque 等,序列式容器的特点就是 底层为线性序列的数据结构,就比如 list,其中的节点是 线性存储 的,一个节点存储一个元素,其中存储的元素都可序,但未必有序
关联式容器 则比较特殊,其中存储的是 <key, value> 的 键值对,这就意味着可以按照 键值大小 key 以某种特定的规则放置于适当的位置,关联式容器 没有首尾的概念,因此没有头插尾插等相关操作,本文中学习的 set 和 map 就属于 关联式容器
键值对
键值对是 一种用来表示具有一一对应关系的结构,该结构中一般只包含两个成员变量:key 和 value,前者表示 键值,后者表示 实值
关联式容器的实现离不开键值对
//SGI 版 STL 中的实现
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 中的 first 表示 键值,second 则表示 实值,在给 关联式容器 中插入数据时,可以构建 pair 对象
比如下面就构建了一个 键值 key 为 string,实值 value 为 int 的匿名 键值对 pair 对象
pair<string, int>("hehe", 123);
可以将此匿名对象传入 关联式容器 中,当然这样写未免过于麻烦了,于是库中设计了一个函数模板 make_pair,可以根据传入的参数,去调用 pair 构建对象并返回
make_pair("hehe", 123); //构建出的匿名对象与上面的一致
二、set
何为set?
set 其实就是之前在 二叉搜索树 中的K模型
也就是用来解决“在不在”问题的模型
其中的 T 就是 set 的实值(键值),参数2 Compare 为存储依据,默认为升序,即符合 二叉搜索树 中序遍历的结果:升序,参数3 Alloc 是空间配置器,现在不必深究
作为 STL 中的容器,set 当然少不了迭代器,树型关联式容器迭代器的遍历结果为有序,所以迭代器遍历的本质是 中序遍历,同时 set 的迭代器还是一个 双向迭代器,支持 ++ 和 – 操作
set的使用
set 的构造函数如下图所示:
可以直接创建一个空 set 使用,也可以根据迭代器区间创建 set
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main()
{
vector<int> arr = { 8,5,6,7,3,1,1,3 };
set<int> s1; //创建一个空的 set
set<int> s2(arr.begin(), arr.end()); //创建包含数据的 set
cout << "s1: ";
for (const auto& e : s1)
cout << e << " ";
cout << endl;
cout << "s2: ";
for (const auto& e : s2)
cout << e << " ";
cout << endl;
return 0;
}
就像 二叉搜索树 一样,set 是不支持数据冗余的,如果出现冗余的数据插入时,会失败,如果想存储冗余的数据,可以使用 multiset
set 中的常用功能
功能 | 用途 |
---|---|
empty | 判断容器是否为空 |
size | 当前容器中的元素数 |
insert | 元素插入,根据特定条件插入至合适位置 |
erase | 删除指定元素 |
swap | 交换两个容器 |
clear | 清空容器中的所有元素 |
find | 查找实值是否存在并返回迭代器位置 |
count | 统计容器中指定键值的数量 |
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main()
{
vector<int> arr = { 7,3,6,9,3,1,6,2 };
set<int> s1(arr.begin(), arr.end());
//迭代器遍历
cout << "迭代器遍历结果: ";
set<int>::iterator it = s1.begin();
while (it != s1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//判空、求大小
cout << "===================" << endl;
cout << "empty(): " << s1.empty() << endl;
cout << "size(): " << s1.size() << endl;
//插入元素
cout << "===================" << endl;
cout << "insert(5): ";
s1.insert(5);
for (const auto& e : s1) cout << e << " ";
cout << endl;
//删除元素
cout << "===================" << endl;
cout << "erase(6): ";
s1.erase(6);
for (const auto& e : s1) cout << e << " ";
cout << endl;
//交换、查找、清理
cout << "===================" << endl;
set<int> s2(arr.begin() + 5, arr.end());
s1.swap(s2);
cout << "s1: ";
for (const auto& e : s1) cout << e << " ";
cout << endl;
cout << "s2: ";
for (const auto& e : s2) cout << e << " ";
cout << endl;
cout << "s1.find(9): ";
cout << (s1.find(9) != s1.end()) << endl;
cout << "s2.clear(): " << endl;
s2.clear();
cout << "s1: ";
for (const auto& e : s1) cout << e << " ";
cout << endl;
cout << "s2: ";
for (const auto& e : s2) cout << e << " ";
cout << endl;
// 查询数量
cout << "s1.count(2):" << " " << s1.count(2) << endl;
return 0;
}
其实因为set不允许键值重复,所以 count() 只会有 0 或者 1 两种可能,所以理论上来说你可以用它来判断数字是否在容器中
另外请注意,二叉搜索树中的键值key是不允许改变的,如果改变了,会破坏二叉搜索树的结构导致失效
因此即使是 set 中的普通迭代器,本质上也是 const 迭代器
set的特点
总得来说就是下图
multiset
multi前缀在英语中是为 “多” 的意思
其实对比set,也就是多了支持数据冗余的功能
另外当查询数字有多个的时候,返回的是 中序遍历中第一次出现的元素
#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main()
{
vector<int> arr = { 3,5,3,4,5,9,2,3 };
multiset<int> ms1(arr.begin(), arr.end());
auto it = ms1.begin();
while (it != ms1.end())
{
cout << *it << " | " << &*(it) << endl;
++it;
}
cout << "================" << endl;
cout << "ms1.find(3): " << &*(ms1.find(3)) << endl;
return 0;
}
multiset 才是真正的排序,set 则是去重 + 排序
三、map
何为map?
map 是 二叉搜索树 改造后的 key / value 模型,是一个真正意义上的 键值对
map其实就是一种映射关系
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main()
{
vector<pair<string, int>> arr = { make_pair("G", 71), make_pair("A", 65), make_pair("F", 70) };
map<string, int> m1; //创建一个空的 map
map<string, int> m2(arr.begin(), arr.end()); //创建包含数据的 map
cout << "m1: " << endl;
for (const auto& e : m1)
cout << e.first << " | " << e.second << endl;
cout << "========================" << endl;
cout << "m2: " << endl;
for (const auto& e : m2)
cout << e.first << " | " << e.second << endl;
return 0;
}
map 中的常用功能
功能 | 用途 |
---|---|
empty | 判断容器是否为空 |
size | 当前容器中的元素数 |
operator[ ] | 按照键值,访问实值,如果没有,则新插入 |
insert | 元素插入,根据特定条件插入至合适位置 |
erase | 删除指定元素 |
swap | 交换两个容器 |
clear | 清空容器中的所有元素 |
find | 查找实值是否存在并返回迭代器位置 |
count | 统计容器中指定键值的数量 |
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
int main()
{
vector<pair<string, int>> arr{ make_pair("z", 122), make_pair("a", 97), make_pair("K", 75), make_pair("h", 104), make_pair("B", 66) };
map<string, int> m1(arr.begin(), arr.end());
//迭代器遍历
cout << "迭代器遍历结果: ";
map<string, int>::iterator it = m1.begin();
while (it != m1.end())
{
cout << "<" << it->first << ":" << it->second << "> ";
++it;
}
cout << endl;
//判空、求大小、解引用
cout << "===================" << endl;
cout << "empty(): " << m1.empty() << endl;
cout << "size(): " << m1.size() << endl;
cout << "m1[""a""]: " << m1["a"] << endl;
//插入元素
cout << "===================" << endl;
cout << "insert(""a"", 5): ";
m1.insert(make_pair("a", 5));
for (const auto& e : m1) cout << "<" << e.first << ":" << e.second << "> ";
cout << endl;
//删除元素
cout << "===================" << endl;
cout << "erase(""a""): ";
m1.erase("a");
for (const auto& e : m1) cout << "<" << e.first << ":" << e.second << "> ";
cout << endl;
//交换、查找、清理
cout << "===================" << endl;
map<string, int> m2(arr.begin() + 2, arr.end());
m1.swap(m2);
cout << "m1.swap(m2)" << endl;
cout << "m1: ";
for (const auto& e : m1) cout << "<" << e.first << ":" << e.second << "> ";
cout << endl;
cout << "m2: ";
for (const auto& e : m2) cout << "<" << e.first << ":" << e.second << "> ";
cout << endl;
cout << "m1.find(""B""): ";
cout << (m1.find("B") != m1.end()) << endl;
cout << "m2.clear()" << endl;
m2.clear();
cout << "m1: ";
for (const auto& e : m1) cout << "<" << e.first << ":" << e.second << "> ";
cout << endl;
cout << "m2: " << endl;
for (const auto& e : m2) cout << "<" << e.first << ":" << e.second << "> ";
cout << endl;
return 0;
}
map 不允许数据冗余,如果想插入重复的数据,可以使用 multimap
map的插入函数比较有意思,因为既要返回插入是否成功,又要返回插入成功的迭代器,所以它的返回值其实是个pair
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
int main()
{
map<string, int> m1;
auto ret = m1.insert(make_pair("a", 97));
cout << "<" << ret.first->first << ":" << ret.first->second << ">" << " | " << ret.second << endl;
ret = m1.insert(make_pair("a", 100));
cout << "<" << ret.first->first << ":" << ret.first->second << ">" << " | " << ret.second << endl;
return 0;
}
至于 find 和 count 跟 set 中的一样,可以用来判断元素是否存在,不过 find 返回的是 迭代器,count 返回的则是 键值数
map 是支持修改 实值 value 的,因此 可以根据普通迭代器修改实值
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
int main()
{
map<string, int> m1;
m1.insert(make_pair("a", 97));
auto it = m1.find("a");
cout << "<" << it->first << ":" << it->second << ">" << endl;
it->second = 100;
cout << "<" << it->first << ":" << it->second << ">" << endl;
return 0;
}
map中的operator[ ]
operator[ ] 返回的是当前 键值 对应的 实值,如果当前 键值 不存在,则会插入新的 键值对
这很强大,值得我们单独介绍一下它
operator[ ] 的返回值为 mapped_type,即 实值 value 的引用,参数 key_type 是 键值 key
(*((this->insert(make_pair(k, mapped_type()))).first)).second
- 插入一个新的键值对 this->insert( make_pair(k, mapped_type()) )
- 获取 insert 返回值中的 键值 返回值.first 即迭代器 iterator
- 最后通过迭代器获取 实值 (*iterator).second
所以说,这个operator[ ]包含了插入、修改、插入+修改、查找等功能
multimap
既然允许冗余数据插入,自然也就没有了operator[ ]
总结
复杂链表的复制
前K个高频单词
两道很有意思的题目,大家可以尝试运用本篇文章的内容来尝试一下