重庆专业做网站的公司北京债务优化公司

一、前言

$STL$ 中的关联式容器分为树型结构和哈希结构，树型结构主要有四种：$set$、$multiset$、$map$、$multimap$，都是用红黑树实现的

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

• 增删查改都是 $O(logn)$
• 支持遍历，遍历结果默认字典序升序

$set$ 和 $multiset$ 中只存 $value$，$map$ 和 $multimap$ 中存的是键值对 $<key,value>$

C++ 的键值对是用 $pair$ 实现的，所以 $map$ 和 $multimap$ 存的其实是 $pair$

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. 常见应用

$set$：排序 + 去重

$multiset$：排序

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

$map$ 的一个 $key$ 只能对应一个 $value$

$multimap$ 的一个 $key$ 可以对应多个 $value$

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");

$map::operator[]$

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';