map和set的封装

一、红黑树的改造

1.1节点的定义

二、红黑树的迭代器

2.1用节点封装迭代器

2.2迭代器的实现

2.3map和set的迭代器

三、insert的返回值

3.1insert返回值的用处

3.2operator[ ]的实现

四、key不能修改的问题

封装map和set一般分为六步：

封装map和set
普通迭代器
const迭代器
insert的返回值
map operator[ ]
key不能修改问题

一、红黑树的改造

1.1节点的定义

map和set的底层都是用一棵红黑树来封装的，但是map和set节点里面存储的值不一样，map存储的是<key,pair<key,value>>，set存储的<key,key>，多存储一个key是因为查找节点的需要（查找节点一般是按照key去查找的），所以统一用data来表示map和set存储的数据，再在map和set内部定义一个仿函数，通过传参使用函数对象来获得data中具体的key值

RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED)
{}//set的keyoft
struct KeyOfT
{const K& operator()(const K& key){return key;}
};//map的keyofT
struct  KeyOfT
{const K& operator()(const pair<K, V>& kv){return kv.first;}
};

二、红黑树的迭代器

2.1用节点封装迭代器

用节点去封装迭代器，关键在于实现operator++和operator--。STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，那么下个位置是在哪里呢？实际上，end()是一个指向根节点的虚拟头结点。实现过程中，为了方便实现，定义end()的位置是nullptr；

template<class T, class Ptr, class Ref>
struct _Treeiterator
{typedef RBTreeNode<T> Node;Node* _node;typedef _Treeiterator<T, Ptr, Ref> Self;typedef _Treeiterator<T, T*, T&> iterator;_Treeiterator (Node* node):_node(node){}_Treeiterator(const iterator& it):_node(it._node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &(_node->_data);}Self& operator++(){//右树不为空-->找右树的最左节点if (_node->_right){Node* leftnode = _node->_right;while (leftnode->_left){leftnode = leftnode->_left;}_node = leftnode;}//右树为空else{Node* cur = _node;Node* parent = cur->_parent;while (parent){if (cur == parent->_left){break;}else{cur = cur->_parent;parent = parent->_parent;}}_node = parent;}return *this;}Self& operator--(){//左树不为空-->找左树的最右节点if (_node->_left){Node* rightnode = _node->_left;while (rightnode->_right){rightnode = rightnode->_right;}_node = rightnode;}//左树为空else{Node* cur = _node;Node* parent = cur->_parent;while (parent&& cur == parent->_left){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;}

实现operator++：红黑树是按照中序遍历的方式访问节点数据的，当前根节点访问完就要去访问当前根节点的右子树

因此++的重载分为两种情况：当右子树不为空，说明右子树的数据没有访问过，那就去访问右子树的最左节点；当右子树为空，说明该根节点形成的子树已经被访问完了，那么就要向上继续访问；
向上访问也分为两种情况：如果当前根节点是它父亲节点的左孩子，说明下一个访问的就是父亲节点，直接将_node更新为parent；如果当前根节点是它父亲节点的右孩子，说明以它的父亲节点为根节点的子树也访问完了，那么就向上继续访问，直到某个位置的节点是它父亲节点的左孩子，或者已经到达整棵树的根节点，再把_node更新为parent；

实现operator--：--实现的过程是++的逆过程，判断的时候判断左子树即可

2.2迭代器的实现

typedef _Treeiterator<T, T*,T&> iterator;
typedef _Treeiterator<T, const T*,const T&> const_iterator;iterator begin()
{Node* cur = _root;Node* leftmin = _root->_left;while (leftmin->_left){leftmin = leftmin->_left;}return iterator(leftmin);
}iterator end()
{return iterator(nullptr);
}const_iterator begin() const
{Node* cur = _root;Node* leftmin = _root->_left;while (leftmin->_left){leftmin = leftmin->_left;}return const_iterator(leftmin);
}const_iterator end() const
{return const_iterator(nullptr);
}

2.3map和set的迭代器

map的迭代器

set的迭代器

因为set中只有key，key永远是不可修改的，所以set的普通迭代器是用const迭代器去实现的，实现迭代器的时候也只需要实现const迭代器

三、insert的返回值

3.1insert返回值的用处

在map的operator[ ]中可以看到，operator[ ]的返回值是借助insert实现的，这就决定了insert的返回值必须是一个pair，并且是一个pair<iterator, bool>。要实现map的operator[ ]就要修改insert的返回值。
插入一个节点，如果key已经存在，就返回pair<该节点（存储该key）的迭代器, false>；如果key不存在，插入成功就返回pair<新插入节点的迭代器, true>。
插入节点的value默认给缺省值，外部没传值给value就默认使用缺省值。
以下是三种不同情况下，insert的返回值

初始化根节点

key已经存在

插入新节点且key不存在

3.2operator[ ]的实现

实际上，set中根本不需要实现operator[ ]，但是由于map和set都是用相同的一颗红黑树去封装的，红黑树insert的返回值改变也会影响set的插入，因为map有需求，而set就是一个陪跑。

map的operator[ ]

operator[ ]返回的是insert返回值中节点迭代器中的value值

set的insert

set的插入的返回值因为insert返回值的改变复杂了许多。原因是，在set内部，Insert返回的pair内的迭代器类型只能是一个const迭代器，但是在Insert内部调用树的insert返回的pair内的是一个普通迭代器，是完全不同的两个类型，所以必须用普通迭代器去构造const迭代器，才能保证Insert返回的pair内的是一个正确的const迭代器。

map内部Insert返回的pair内的迭代器类型可以是一个普通迭代器，因此不存在返回值类型不匹配的问题

那么如何才能用普通迭代器去构造const迭代器呢？这里有一个非常巧妙的思路。

这里的_Treeiterator(const iterator& it)包含两层意思：当需要创建的是一个const迭代器对象，这里的_Treeiterator(const iterator& it)就是一个构造函数；当需要创建的是一个普通迭代器，这里的_Treeiterator(const iterator& it)就是一个普通迭代器的拷贝构造函数。

为了实现这一点，我们多定义了一个模板显示实例化后一定为普通迭代器的iterator，目的就是为了保证_Treeiterator(const iterator& it)函数的实现。