【C++高阶二】STL的map和set

1.初识map和set

set是一个无序集合，存储唯一的元素

map是一个键值对的集合，其中的键是唯一的

2.pair

pair结构是一个键值对，结构包含两个成员变量key和value，key代表键值，value表示与key对应的信息

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){}
};

pair类有两个模板参数T1和T2，分别表示两个值的类型。
pair类有两个成员变量first和second，分别表示两个值
pair类的构造函数有多个重载形式，可以根据需要来创建pair对象

• pair()：默认构造函数，创建一个pair对象，默认初始化first和second
• pair(const T1& x, const T2& y)：构造函数，初始化first为x，second为y
• 拷贝构造函数、移动构造函数、赋值运算符重载和比较运算符重载

map中存储的就是pair结构，所以map也叫存储的KV模型，因为first和second对应key和value

3.set

1. set是一种集合容器，它是基于红黑树实现的，它可以存储不重复的元素，并且会自动按照元素的大小进行排序
2. set提供了迭代器，可以用于遍历集合中的元素
3. 在set中，元素的值是不可修改的。如果需要修改元素的值，需要先删除旧的元素，然后插入新的元素

3.1模板参数

template < class T, class Compare = less<T>> class set;

T：value值的类型
Compare：比较规则的仿函数

set默认情况下遍历出来是升序,但是如果定义对象时显示传参greater就是降序
在定义set的时候，也可以在模板参数中传入仿函数，用于制定规则：

template <class T>
struct compare
{bool operator()(const T& t1, const T& t2) const{return T1 > T2;}
};int main()
{set<int, compare<int>> s;return 0;
}

s1通过仿函数comp完成了逆序排列

3.2typedef的类型

key_type：第一个模板参数T的类型，即value的类型
value_type：第一个模板参数T的类型，即value的类型
key_compare：第二个模板参数的类型，即用于比较的仿函数的类型
value_compare：第二个模板参数的类型，即用于比较的仿函数的类型
key_compare与value_compare的缺省值是less<key_type>即升序排序的仿函数

3.3 insert

pair<iterator,bool> insert (const value_type& val);

最常用的插入，其用于直接插入一个val值的节点
返回值比较特别：pair<iterator,bool>

如果原先val存在，此时iterator指向原先的val节点，bool值返回false表示插入失败
如果原先val不存在，此时iterator指向新插入的val节点，bool值返回true表示插入成功

函数不能一次性返回两个值，于是把iterator和bool两个值封装进pair中返回
这样既可以得到了迭代器，又可以检测插入是否成功

int main()
{set<int> s;s.insert(1);s.insert(2);s.insert(3);s.insert(4);s.insert(5);for (auto e : s){cout << e << " ";}return 0;
}

3.4 erase

1. 用于删除迭代器指向的节点，迭代器必须有效

void erase (iterator position);

2. 用于删除整个迭代器区间[first, last)，迭代器必须有效

void erase (iterator first, iterator last);

3.用于删除val值的节点，val值可以不存在，删除后返回删除节点的个数。在set中，由于不存在重复节点，所以返回值只可能是0或1

size_type erase (const value_type& val);

3.5 lower_bound与upper_bound

iterator lower_bound (const value_type& val) const;
iterator upper_bound (const value_type& val) const;

lower_bound ：返回第一个 >=val 节点的迭代器
upper_bound ：返回第一个 >val 节点的迭代器
在STL设计中，都是利用左闭右开的区间特性，而迭代器也利用了此特性

例：现在我们想遍历一个set中[5, 15]的闭区间，该如何查找迭代器？

auto it1 = s1.find(5);
auto it2 = s2.find(15);while(it1 != it2)
{cout << *it1 << endl;++it1;
}

以上代码存在两个问题：

1. 在s1中可能不存在值为5或者15的节点，find有可能是失败的，此时我们就无法遍历到[5， 15]了
2. 迭代器遵循左闭右开的特性，所以我们找了一个比20大的迭代器21来遍历，但如果我们的set存储的是float类型的数据，20与21之间可能还会存在其它节点，此时我们可能就会多遍历到其它节点

因此我们可以利用lower_bound 与upper_bound配合来得到迭代器：

auto it1 = s1.lower_bound(5);
auto it2 = s2.upper_bound(15);while(it1 != it2)
{cout << *it1 << endl;++it1;
}

以上代码中lower_bound(5)可以得到第一个>=5节点的迭代器，如果5节点存在，此函数得到5，如果不存在，就得到大于5的下一个节点
而upper_bound(15)则是得到第一个>15节点的迭代器，如果我们存储了float类型的数据，刚好存储了一个15.0001的数据，那么此时upper_bound(21)就返回这个比15大的最近的节点
通过两者配合，我们就可以得到一个等效的左闭右开迭代器区间，后续方便操作

4. multiset

multiset是一个允许存在重复元素的set，其它的效果与set完全一致

值得注意的只有几个接口：

1. find：对multiset使用find时，由于一个val可能有多个节点，此时返回中序遍历的第一个节点
2. count：对于multiset才有用，可以检测val的个数（对于set而言，count用于返回某个val值的个数，由于set不能重复，所以这个count接口没有多大意义）

5.map

map是一种关联容器，用于存储键-值对（key-value）
其将key和value封装进了pair中，所以每一个节点都是一个pair<key, value>，每个元素都由一个键和一个与之关联的值组成，键和值可以是任意类型

5.1模板参数

template < class Key,  class T, class Compare = less<Key> >class map

Key：代表key值的类型
T：代表value值的类型
Compare：代表了比较规则的仿函数

5.2 typedef的类型

key_type：第一个模板参数Key的类型，即key的类型
mapped_type：第二个模板参数T的类型，即value的类型
value_type：将key与value封装后 pair<const key_type,mapped_type>的类型
key_compare：第二个模板参数的类型，即用于比较的仿函数的类型

5.3普通接口

map的很多接口和set一致，只有部分需要注意

1. begin , end等，遍历map 走中序遍历，得到有序数据
2. void erase (iterator position) 删除迭代器指向的节点 迭代器必须有效
3. size_type erase (const key_type& k) 删除key值的节点 key值可以不存在
4. iterator find (const key_type& k) 得到key位置的迭代器 如果没有找到，返回end()等效的迭代器

5.4 insert

对于map而言，insert的功能其实和set是一致的，但不一样的是需要插入pair<key, value>

pair<iterator,bool> insert (const value_type& val);

val的类型是value_type
value_type就是一个pair<key, value>的类型
所以要构造出一个pair插入进去

1. 利用匿名对象插入

map<string, int> m;
m.insert(pair<string, int>("hello", 100));

2. 利用多参数默认构造的类型转化

map<string, int> m;
m.insert({ "hello", 100 });

pair具有一个多参数的默认构造，具有类型转化的功能，所以我们可以利用隐式类型转化进行传参。而我们有多个参数，所以要把这些参数用{}括起来

3. 利用make_pair进行插入

map<string, int> m;
m.insert(make_pair("hello", 100));

利用make_pair函数，让其自动推导类型构造pair

5.5 operator[ ]

mapped_type& operator[] (const key_type& k);

接收一个key_type类型的参数（key值），返回一个mapped_type&类型的参数（value的引用）
等价于下面的代码：

(*((this->insert(make_pair(k,mapped_type()))).first)).second

我们一层层解析

1. 第一层：

make_pair(k, mapped_type( ))

用参数k，通过make_pair构造一个pair，这个pair的value使用了mapped_type( )默认构造（mapped_type是value的类型）
最后就得到了一个pair<key, value>

2. 第二层：

this->insert( )

第一层构造出了一个pair<key, value>，作为参数传入到这个insert中（相当于把刚刚构造的节点插入进map中）
插入后，不论成功与否，都会返回一个pair<iterator, bool>
iterator用于指向key的迭代器，bool用于标识插入是否成功
最后得到了一个pair（分别存储了指向key的迭代器和bool的值）

3. 第三层：

( ).first

第二层得到了pair<iterator, bool>，第三层访问它的first，也就是访问iterator
最后得到了指向key值的迭代器

4. 第四层：

(*( )).second

第三层层拿到了指向key的迭代器，第四层先对迭代器解引用*( )，此时就得到了一个map的节点，而map的节点是pair<key, value>，所以实际上我们解引用得到了一个pair
随后通过( ).second访问pair<key, value>的second，也就是value。最后返回这个value的引用
最后得到了key对应的value的引用

经过解析，用一个map<string, string>类型的字典dict展示operator[]的作用：

1. 插入一个key值

dict["left"];

在dict中插入了一个key = "left"但是没有value的节点

2. 插入一对key - value

dict["left"] = "左边";

（由于operator[ ]返回的是对应的引用，因此我们可以直接给返回值赋值），此时我们就插入了一个节点，key = “left”，value = “左边”

3. 修改key对应的value

dict[“coffe”] = "咖啡";

如果dict原先就存在key = "coffe"的节点且没有value，可以直接给value赋值

4. 得到key对应的value

cout << dict["coffe"] << endl;

由于我们拿到的是value的引用，我们也可以把它作为一个值赋值给别人或者输出

6.multimap

原本的map同一个key只能存在一个value，而multimap则可以存在多个key相同的节点