map和set（c++）

前言

在前面我们在介绍二叉搜索树时我们分别实现了一个key结构和key-val结构，如果我们再进一步完善这棵树，将二叉搜索树升级为红黑树去存储key和key-val那么我们就可以得到我们今天要介绍的主角map和set。当然了标准库的实现还是有很多需要注意的地方，下面我们就带着大家简单的认识一下map和set

序列式容器和关联式容器

前面我们介绍过的的容器如string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系

但我们也见过关联式容器，比如priority_queue(优先级队列)，它表现为该位置存储的值和其所在的位置强相关，如果随意交换就会破坏这种结构，这就是关联式容器，今天我们介绍的map和set也属于关联式容器

set

手册

我们可以参考手册对set的描述，<set> - C++ Reference (cplusplus.com)

分类

set可以分为set和multiset，两者本质上的不同在于是否允许键冗余，我们这里讲解set为主，multiset的设计和set是高度一致的

声明

我们先来看看set的声明

template < class T,                        // set::key_type/value_typeclass Compare = less<T>,        // set::key_compare/value_compareclass Alloc = allocator<T>      // set::allocator_type> class set;

第一个参数是存储数据的类型。第二个参数是比较大小的方式可以缺省，默认调用<号比较，基本类型天然支持比较，自定义类型需要实现<重载，也可以自己实现比较的仿函数传入。第三个参数我们还是暂时不关注，这是空间配置器，缺省即可

set底层是⽤红⿊树实现，增删查效率是logN

构造

右值引用的方式我们暂时不关心

前三种构造方式在前面的数据结构种也是非常常见的，不再展开

initializer 列表构造可能比较陌生，我们在这里用一个例子

这种方式初始化还是非常方便的

迭代器

迭代器遍历是⾛的搜索树的中序，遍历是有序的

首先set的迭代器是双向迭代器，++和--都是支持的

// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

重载了*操作符，*迭代器可以直接将值取出

增删查

前面我们介绍过，set是关联式容器，存储的值和其存储的位置具有强关联性，所以不支持对指定元素修改其值，因为这会破坏set的结构

增

// 单个数据插⼊，如果已经存在则插⼊失败
pair<iterator,bool> insert (const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊
void insert (initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert (InputIterator first, InputIterator last);

其中pair<iterator,bool>可以暂时理解为是一种结构体，它的第一个元素是迭代器，第二个元素是布尔值，前者表示指向插入元素位置的迭代器，如果插入失败（因为元素已经存在），它指向容器中与 val 值相等的元素，后者标识是否插入成功

查

/ 查找val，返回val所在的迭代器，没有找到返回end()
iterator find (const value_type& val);
// 查找val，返回Val的个数
size_type count (const value_type& val) const;

删

// 删除⼀个迭代器位置的值
iterator erase (const_iterator position);
// 删除val，val不存在返回0，存在返回1
size_type erase (const value_type& val);
// 删除⼀段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);

其中那两个返回迭代器的方法返回值都是一个指向被删除元素后面元素的迭代器

获得区间

有的时候我们希望可以获得值区间的迭代器区间，为此我们介绍两个函数

// 返回⼤于等val位置的迭代器
iterator lower_bound (const value_type& val) const;
// 返回⼤于val位置的迭代器
iterator upper_bound (const value_type& val) const;

如果我们传入的是大于的伪函数，此时这个set如果中序遍历表现为降序lower_bound 和 upper_bound 的行为依然和它们在升序情况下类似，但它们的“查找方向”会变化

表现为大于等转为小于等，大于转为小于

再谈multiset和set

multiset和set的使⽤基本完全类似，主要区别点在于multiset⽀持值冗余，那insert/find/count/erase都围绕着⽀持值冗余有所差异

相⽐set不同的是，multiset是排序，但是不去重

相⽐set不同的是，x可能会存在多个，find查找中序的第⼀个

相⽐set不同的是，count会返回x的实际个数 0和1=》0和几

相⽐set不同的是，erase给值时会删除所有的x

map

手册

我们可以参考手册对map的描述，<map> - C++ Reference (cplusplus.com)

分类

map还是可以按照是否允许键冗余分为map和multimap，两者本质上的不同在于是否允许键冗余，我们这里讲解map为主，multimap的设计和map是高度一致的

声明

我们还是先来看看声明

template < class Key, // map::key_type
class T, // map::mapped_type
class Compare = less<Key>, // map::key_compare
class Alloc = allocator<pair<const Key,T> > //map::allocator_type
> class map;

Key类型是键的类型，T是值的类型，Compare是比较的伪函数，Alloc是空间配置器，我们暂时不关注

遍历默认按key的升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中序

map⽀持修改value数据，不⽀持修改key数据，修改关键字数据，破坏了底层搜索树的结构

pair类型

前面我们在介绍set的时候我们见过pair类型，但我们只是简单的介绍了一下，现在我们详细的讲解一下

首先我们需要知道，map底层的红⿊树节点中的数据，使⽤pair<Key,T>存储键值对数据

pair - C++ Reference (cplusplus.com)，先来看看手册

template <class T1, class T2> struct pair;

它也是一个类模板，它会存储两个类型的值让他们称为一个整体，这是它本来的作用，我们可以简单的看下实现

template <class T1, class T2>
struct pair //struct可以修饰类，其内部所有的成员默认公开
{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) //带参构造{}template<class U, class V>pair (const pair<U,V>& pr): first(pr.first), second(pr.second)//拷贝构造{}
};
//创造一个pair的方法
template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y)
{return ( pair<T1,T2>(x,y) );
}

构造

迭代器

双向迭代器

// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

增删改查

这里比set多支持改是因为我们支持该值，键依然不被允许修改

增

value_type -> pair<const key_type,mapped_type>
// 单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败
pair<iterator,bool> insert (const value_type& val);
// 列表插⼊，已经在容器中存在的值不会插⼊
void insert (initializer_list<value_type> il);
// 迭代器区间插⼊，已经在容器中存在的值不会插⼊
template <class InputIterator>
void insert (InputIterator first, InputIterator last);

查

key_type -> The first template parameter (Key)// 查找k，返回k所在的迭代器，没有找到返回end()
iterator find (const key_type& k);
// 查找k，返回k的个数
size_type count (const key_type& k) const;

删

// 删除⼀个迭代器位置的值
iterator erase (const_iterator position);
// 删除k，k存在返回0，存在返回1
size_type erase (const key_type& k);
// 删除⼀段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);

改

我们可以通过iterator修改，也可以使用operator[]修改

operator[]不仅仅⽀持修改，还⽀持插⼊数据和查找数据

insert插⼊⼀个pair<key, T>对象时，会返回一个pair<迭代器, 布尔值>的pair

迭代器会指向键为key的位置，布尔值表示是否插入成功

⽆论插⼊成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器

insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以⽤来实现operator[]

看一下实现

mapped_type& operator[] (const key_type& k)
{
pair<iterator, bool> ret = insert({ k, mapped_type() });
iterator it = ret.first;
return it->second;
}

获得区间

// 返回⼤于等k位置的迭代器
iterator lower_bound (const key_type& k);
// 返回⼤于k位置的迭代器
const_iterator lower_bound (const key_type& k) const;

如果我们传入的是大于的伪函数，此时这个map如果中序遍历表现为降序lower_bound 和 upper_bound 的行为依然和它们在升序情况下类似，但它们的“查找方向”会变化

表现为大于等转为小于等，大于转为小于

operator->

map的迭代基本都使⽤operator->,这⾥省略了⼀个->

// 第⼀个->是迭代器运算符重载，返回pair*，第⼆个箭头是结构指针解引⽤取
pair数据
//cout << it.operator->()->first << ":" << it.operator->()->second << endl;
cout << it->first << ":" << it->second << endl;

再谈multimap和map

multimap和map的使⽤基本完全类似，主要区别点在于multimap⽀持关键值key冗余，那么
insert/find/count/erase都围绕着⽀持关键值key冗余有所差异，这⾥跟set和multiset完全⼀样，⽐如find时，有多个key，返回中序第⼀个。其次就是multimap不⽀持[]，因为⽀持key冗余，[]就只能⽀持插⼊了，不能⽀持修改。