C++STL系列之set和map系列

前言

set和map都是关联式容器，stl中树形结构的有四种，set，map，multiset,multimap.本次主要是讲他们的模拟实现和用法。

一、set、map、multiset、multimap

set

set的中文意思是集合，集合就说明不允许重复的元素
1…set是按照一定次序存储元素的容器
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
5. set在底层是用红黑树来实现的
6. 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。这个后面模拟实现会讲原因。
6. 使用set的迭代器遍历set中的元素，可以得到有序序列
7. set中的元素默认按照小于来比较
8.set中的元素不可以重复，所以可以用set来去重
9.set中的迭代器是双向迭代器
在这里插入图片描述
T是key，Compare是仿函数来控制比较规则，Alloc是空间配置器
构造函数没什么可说的，看一眼就懂了，这里的T有很大意义，后面模拟会提到。

重要函数

在这里插入图片描述
画横线的就是比较重要的，有几个注意事项：
1.关于insert，库里面的insert是提供迭代器位置插入的，这样做的目的有两个：
1.与其他stl的insert保持一致，比如vector，list都提供迭代器插入
2.看下面的emplace_hint，emplace版本的构造一般是直接在容器内部构造，而emplace_hint对应的版本就是迭代器位置插入，hint是提示，若pos指向的位置恰好是元素应插入的位置或邻近位置（如插入有序序列时，pos指向当前最后一个元素），红黑树可直接从pos开始验证，跳过大部分查找步骤，插入效率接近 O (1)；即使pos是错误提示，set 仍会按正常逻辑查找正确位置（退化至 O (log n)），但不会破坏元素的有序性
2.count就是计数，set里一定是一，这个接口是给multi版本使用的
3.lower_bound是大于等于元素的位置，upper_bound是大于元素的位置，这样是为了维护迭代器左闭右开的性质

map

1… map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:
typedef pair<const key, T> value_type;
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
6. map通常被实现为红黑树
在这里插入图片描述
第二个参数给的是T而不是Value，这里也有很大意义，后面模拟实现会提到，其他和set一样。

重要函数

map的重要接口和set类似，只多了比较重要的[] 和 at，都是通过key返回value的引用,他们的实现都得益于insert
在这里插入图片描述
[]功能很强大，支持修改，插入、插入 + 修改

int main()
{map<int, int> mp;mp.insert({ 0,1 });mp[0] = 2;mp[2];mp[3] = 3;return 0;
}

[]的实现实际上是这样,模拟实现还需要使用

V& operator[](const K& key)
{pair<K,V> pr = make_pair(key,V());iterator it = insert(pr).first;return *it.second;
}

multi系列

multi中文意思是多重，就意味着允许键值对冗余，也就是key可以重复。
count的作用是给他的，如果想使用可以重复的集合就用multiset
multimap中没有提供[],因为key是可以重复的，那我该返回哪个呢？所以就不提供

二、模拟实现

set和map的使用都比较简单，主要还是在模拟上。

框架

第一个问题就来了，一个是key模型，一个是key-value模型，难道要写成两份代码吗？之前list的迭代器提到了，其实库里面很杜绝这种相似代码写两份的，我们看看库里是怎么解决的，其实上面提供了一点消息就是T
在这里插入图片描述
都搞成了两个参数<K,T>,其中T对于set就是K，对于map就是pair< K,V> ,这样就可以通过一份代码来实现set和map，先搭一个框架，节点存放的就是T类型了

template<class T>
struct RBTreeNode {RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;Color color;	T _kv;RBTreeNode(const T& p):_left(nullptr),_right(nullptr),_parent(nullptr),color(Color::RED),_kv(p){}
};
template<class K,class T>
class RBTree {typedef RBTreeNode<T> Node;private: Node* _root;
}

set里面放的就是RBTree<K, K> _t;
map里面就是RBTree<K,pair<K, V> _t;
到了插入，又出现新问题了，现在insert能跑了吗？bool insert(const T& p)传的是T啊，对于set倒是能比大小，map呢？pair有一套自己的比较大小的规则，但是和实际插入的规则不同啊，所以还需要一个参数KofT，取出T中的K
map:

struct mapKOfT {const K& operator()(const pair<K, V>& kv){return kv.first;}
};
private:RBTree<K,pair<K, V>,mapKOfT> _t;

set:

struct SetKOfT {const K& operator()(const K& kv){return kv;}
};
RBTree<K, K, SetKOfT> _t;

insert就会变成KOfT koft;涉及到比大小都用koft套一层

到目前为止，基本的框架已经完事了。下一步，迭代器

迭代器

先看库里的迭代器怎么玩的
在这里插入图片描述
set为什么要这么搞呢？因为set本身就不支持任何的修改，所以set这两个都是const_iterator
但是对于map，map的value要支持修改，key不支持，所以不能搞成const，那他的key怎么防止修改呢？这个后面提，其实第一张图片已经看到了。

主要还是++ – begin end怎么实现：
迭代器架子很好搭建，因为有了list的基础

框架

template<class T,class Ref,class Ptr>
struct RBTree_Iterator
{typedef RBTreeNode<T> Node;typedef RBTree_Iterator<T, Ref, Ptr> Self;Node* _node;RBTree_Iterator(Node* node):_node(node){}Ref operator*(){return _node->_kv;}Ptr operator->(){return &_node->_kv;}Self& operator--(){}Self operator--(int){}Self operator++(int){}bool operator!=(const Self& ot)const{return _node != ot._node;}bool operator==(const Self& ot)const{return _node == ot._node;}
};

红黑树里面：

typedef RBTree_Iterator<T, T&, T*> iterator;
typedef RBTree_Iterator<T, const T&, const T*> const_iterator;

关于begin end ++ 和 - -

迭代器区间是左闭右开，begin就是最小元素，end呢，可以给空吗？不可以，因为要支持–end()走到上一个元素，库里的实现是搞了个类似哨兵位头节点的东西。
这个头节点，左孩子是最小节点也就是begin(),右孩子是最大节点，
头节点的父亲是根，根的父亲是头节点
在这里插入图片描述
但是这样维护起来比较麻烦，模拟实现只是为了了解底层，造不出更好的。所以这里不使用头节点方式，end就按空节点来存放（但实际上不是这样）

begin

begin其实就是找到最左节点返回就可以

iterator begin()
{Node* cur = _root;while (cur && cur->_left) cur = cur->_left;//考虑cur主要是考虑这是一颗空树的问题return iterator(cur);
}

++ 和 - -

在这里插入图片描述
上代码：

Self& operator--()
{Node* nodeleft = _node->_left;if (nodeleft){while (nodeleft->_right) nodeleft = nodeleft->_right;_node = nodeleft;return *this;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;return *this;}}
Self operator--(int)
{Node* tmp(_node);--(*this);return RBTree_Iterator(tmp);
}
Self& operator++()
{Node* noderight = _node->_right;if (noderight){while (noderight->_left) noderight = noderight->_left;_node = noderight;}else{Node* cur = _node;Node* parent = cur->_parent;//父亲有可能会为空，比如三角形结点的树while (parent && cur == parent->_right){cur = parent;parent = cur->_parent;}//如果父亲是空，说明这棵树已经遍历完全了//如果父亲不是空，正常父亲给Node_node = parent;}return *this;
}
Self operator++(int)
{Self tmp(_node);++(*this);return tmp;
}

此时基本上红黑树里面的迭代器基本完全了，实现map和set
注意：这里不加typename编译不通过，原因：
类模板没有被实例化，没有生成具体代码，编译器不敢去里面找iterator
都没有检查代码错误，取到的有可能是内部类或者静态成员变量或者类型，加上typename就是告诉他是类型

//set:
typedef typename RBTree<K, K, SetKOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKOfT>::const_iterator const_iterator;//map:
typedef typename RBTree<K, pair<K, V>, mapKOfT>::iterator iterator;
typedef typename RBTree<K, pair<K, V>, mapKOfT>::const_iterator const_iterator;

对于set的begin、end 和 cbegin、cend接口，const版本正常写，这里如果再写一个非const版本的会报错误，因为既然是非const，this指针会调用红黑树里非const版本的begin，返回非const迭代器，此时无法传给set里的const迭代器，所以只需要实现一个。

iterator begin()const
{return _t.begin();
}
iterator end()const
{return _t.end();
}

对于map的begin、end系列正常就可以了

iterator begin()
{return _t.begin();
}
iterator end()
{return _t.end();
}const_iterator begin()const
{return _t.begin();
}
const_iterator end()const
{return _t.end();
}

set、map防止修改

刚才已经讲了，set防止修改的方式就是迭代器都是const迭代器
那map呢？map不想让key修改，可以让value修改，来看库里的实现
在这里插入图片描述
他把那个T里面的key都换成了const key，我们也这么实现。
有的人会有疑问？那我map<const int ,int> mp;不是有两个const吗？不会报错吗？
不会，C++对重复的const编译器会进行优化成一个const。

typedef typename RBTree<K, pair<const K, V>, mapKOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, mapKOfT>::const_iterator const_iterator;
RBTree<K,pair<const K, V>,mapKOfT> _t;

这样map就做到了不能修改K但是可以修改V的效果。

map的【】实现

上面说了，第一件事就是改insert的返回值，主要就是改return的地方，搞成一个pair就可以了

pair<iterator,bool> insert(const T& p)
{KOfT koft;if (_root == nullptr){_root = new Node(p);_root->color = Color::BLACK;return make_pair(iterator(_root),true);}else{Node* cur = _root;Node* parent = nullptr;while (cur){//用T了之后还有点问题 set是K，map是pair<k,v>怎么比？//再传一个模板用来取出key即可if (koft(cur->_kv) < koft(p)){parent = cur;cur = cur->_right;}else if (koft(cur->_kv) > koft(p)){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}cur = new Node(p);Node* newnode = cur;if (koft(parent->_kv) < koft(p)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//这之前都是搜索树的逻辑//while (parent && parent->color == Color::RED){Node* grandf = parent->_parent;if (grandf->_left == parent){Node* uncle = grandf->_right;//叔叔存在且为红if (uncle && uncle->color == Color::RED){//判断uncle->color = parent->color = Color::BLACK;grandf->color = Color::RED;//继续判断cur = grandf;parent = cur->_parent;}//叔叔不存在或者为黑else{//开旋//if (parent->_left == cur){RotateRight(grandf);parent->color = Color::BLACK;grandf->color = Color::RED;}else{//parent->right  是cur，grandf的左边是parentRotateLeft(parent);RotateRight(grandf);cur->color = Color::BLACK;grandf->color = Color::RED;}}}//祖父的右边是父亲else{Node* uncle = grandf->_left;//uncle不存在 或者uncle为黑//uncle为红if (uncle && uncle->color == Color::RED){parent->color = uncle->color = Color::BLACK;grandf->color = Color::RED;cur = grandf;parent = cur->_parent;}//uncle为黑或者不存在else{//旋转//   grandf//uncle                parent//curif (cur == parent->_right){RotateLeft(grandf);parent->color = Color::BLACK;grandf->color = Color::RED;}else{RotateRight(parent);RotateLeft(grandf);cur->color = Color::BLACK;grandf->color = Color::RED;}}}}_root->color = Color::BLACK;return make_pair(iterator(newnode), true);}
}

改完之后就可以实现operator[]了，一句话看着不舒服可以分开

V& operator[](const K& key)
{return (*(insert(make_pair(key, V())).first)).second;
}

set的insert也需要跟着改。

改完之后跑了一段代码，发现set的跑不过，map的可以，为什么呢？
在这里插入图片描述
所以在迭代器里需要提供一个普通迭代器构造const迭代器，库里面实现的很牛。

typedef RBTree_Iterator<T, T&, T*> iterator;
RBTree_Iterator(const iterator& it)//可以拿普通迭代器构造const迭代器:_node(it._node)
{}

搞了一个迭代器参数永远是<T,T&,T*>无论外面传进来是const迭代器还是普通迭代器这里都是普通迭代器。
对于下面这个构造函数：
1.如果是普通迭代器，相当于普通迭代器的拷贝构造
2.如果是const迭代器，相当于普通迭代器来构造const迭代器。这样就能跑了。

另外，这一块其实也是库里一直都有的设计。任何的容器都支持const迭代器给非const迭代器

list<int> lt;
list<int>::const_iterator it = lt.begin();

三、完整代码

个人gitee

总结

map和set的东西不少，需要好好练习和掌握。