【C++】快速上手map、multimap、set、multiset

本文主要是介绍【C++】快速上手map、multimap、set、multiset，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

一、前言
二、set / multiset
- 1. 常见应用
- 2. 核心操作
三、map / multimap
- 1. 常见应用
- 2. 核心操作

一、前言

$ST L$ 中的关联式容器分为树型结构和哈希结构，树型结构主要有四种： $se t$ 、 $m u lt i se t$ 、 $ma p$ 、 $m u lt ima p$ ，都是用红黑树实现的

与哈希结构不同，树型结构的这几个容器：

增删查改都是 $O (l o g n)$
支持遍历，遍历结果默认字典序升序

$se t$ 和 $m u lt i se t$ 中只存 $v a l u e$ ， $ma p$ 和 $m u lt ima p$ 中存的是键值对 $< k ey, v a l u e >$

C++ 的键值对是用 $p ai r$ 实现的，所以 $ma p$ 和 $m u lt ima p$ 存的其实是 $p ai r$

template <class T1, class T2>
struct pair
{T1 first;T2 second;pair() : first(T1()), second(T2()) {}pair(const T1& a, const T2& b) : first(a), second(b) {}
};

二、set / multiset

1. 常见应用

$se t$ ：排序 + 去重

$m u lt i se t$ ：排序

2. 核心操作

插入

set<int> s1;
multiset<int> s2;//set相同元素不会重复插入
s1.insert(1);
s1.insert(1);//multiset相同元素可以重复插入
s2.insert(1);
s2.insert(1);

删除

s.erase(1);//删除所有values.erase(s.find(1));//删除一个迭代器对应的value

查找

//返回一个value的个数
s.count(1) //返回一个value的第一个迭代器，不存在则返回 end()
s.find(1)

遍历

//for(auto it = s.begin(); it != s.end(); it++)//cout << *it << ' ';for(auto x : s)cout << x << ' ';

三、map / multimap

$ma p$ 的一个 $k ey$ 只能对应一个 $v a l u e$

$m u lt ima p$ 的一个 $k ey$ 可以对应多个 $v a l u e$

1. 常见应用

有序的字典

2. 核心操作

插入

map<string, int> m;m.insert(make_pair{"a", 1});
m.insert({"b", 2});//也可以这样写//multimap同理

删除

m.erase("a");//删除一个key对应的所有键值对m.erase(m.find("a"));//删除一个迭代器对应的键值对

查找

//返回一个key对应的键值对个数
m.count("a");//返回一个key对应的键值对的第一个迭代器，不存在则返回 end()
m.find("a");

$ma p :: o p er a t or []$

m["a"] = 1;//map::operator[]的原理
//用<key, T()>构造一个键值对插入
//若key已经存在则插入失败，若key不存在则插入成功
//最后返回value的引用

遍历

//for(auto it = m.begin(); it != m.end(); ++it)//cout << it->first << ' ' << it->second << '\n';//cout << (*it).first << ' ' << (*it).second << '\n';//cout << it.operator->()->first << ' ' << it.operator->()->second << '\n';for(auto& kv : m)cout << kv.first << ' ' << kv.second << '\n';