基于红黑树封装实现set和map

先看一下STL源码3.0版本的实现

stl3.0–参考大佬的代码

set的封装

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class Key, class Compare = less<Key>, class Alloc = alloc>
#else
template <class Key, class Compare, class Alloc = alloc>
#endif
class set {
public:typedef Key key_type;//Keytypedef Key value_type;//Keytypedef Compare key_compare;typedef Compare value_compare;
private:typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;rep_type t;  // red-black tree representing set

map的封装

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
#else
template <class Key, class T, class Compare, class Alloc = alloc>
#endif
class map {
public:typedef Key key_type;//Keytypedef T data_type;typedef T mapped_type;typedef pair<const Key, T> value_type;//Valuetypedef Compare key_compare;private:typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;rep_type t;  // red-black tree representing map

可以看出map和set底层都是用红黑树结构，两者用的都是Key-Value结构，只不过map传的两个模板参数分别是Key和pair<const Key, T>，而set传的两个模板参数都是Key。

tree.h

template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{typedef __rb_tree_node<Value>* link_type;Value value_field;
};template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc>
class rb_tree {
protected:typedef void* void_pointer;typedef __rb_tree_node_base* base_ptr;typedef __rb_tree_node<Value> rb_tree_node;
public:typedef rb_tree_node* link_type;
protected:size_type node_count; // keeps track of size of treelink_type header;  Compare key_compare;
};

既然这样，第二个模板参数value_type传入的类型就可以区分K或KV结构，为什么还要传第一个模板参数Key呢？

因为Key在插入、查找、删除以及迭代器操作里，都要用到Key等，void erase(const Key* first, const Key* last); iterator find(const key_type& x); iterator lower_bound(const key_type& x); iterator upper_bound(const key_type& x);

迭代器++和–

分别要实现const版本和普通版本的迭代器，set是不允许修改的（因为只有Key），只需要const版本迭代器即可；map模板参数之一为std::pair<const K, V>不允许修改Key，但是可以修改Value，//(it->first)++; // 无法修改 (it->second)++;//可以修改

迭代器的++是找中序的下一个节点

typedef typename RBTree<K, std::pair<const K, V>, MapKeyOfT>::iterator iterator;

要加上typename这个关键字，因为RBTree<K, std::pair<const K, V>, MapKeyOfT>还没有实例化，凡是没有实例化的类模板，编译器无法分清楚iterator到底是一个静态变量还是一个类型，用关键字typename告诉编译器，RBTree<K, std::pair<const K, V>, MapKeyOfT>::iterator是一个类型。

//RBTree.h
Self& operator++()
{	// 如果当前节点的右孩子不为空，就找右子树的最左节点if (_node->_right){Node* minRight = _node->_right;while (minRight && minRight->_left){minRight = minRight->_left;}_node = minRight;}// 如果当前节点的右孩子为空，就找孩子是父亲节点左孩子的节点else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_right == cur){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;
}

迭代器的–是找中序的上一个节点

//RBTree.h
Self& operator--()
{// 如果当前节点的左孩子不为空，就找左子树的最右节点if (_node->_left){Node* minLeft = _node->_left;while (minLeft && minLeft->_right){minLeft = minLeft->_right;}_node = minLeft;}// 如果当前节点的左孩子为空，就找孩子是父亲节点右孩子的节点else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = cur->_parent;parent = parent->_parent;}_node = parent;}return *this;
}

map支持[]操作

//RBTree.h
std::pair<iterator, bool> Insert(const T& data) //最重要的是insert返回值类型的处理
//Map.hV& operator[](const K& Key)
{std::pair<iterator, bool> ret = Insert(std::make_pair(Key, V()));return ret.first->second;
}

const迭代器

整体的处理与list的const迭代器的底层实现相似。

//RBTree.h
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T, Ref, Ptr> Self;typedef __RBTreeIterator<T, T&, T*> iterator;Node* _node;
};

set，因为前面都是用const迭代器来定义普通迭代器和const迭代器的，所以在使用的时候，想用iterator（底层是const迭代器）来接收普通迭代器的返回值，要做如下处理

//RBTree.h
typedef __RBTreeIterator<T, T&, T*> iterator;//普通迭代器
//当s是普通迭代器时，是拷贝构造
//当s是const迭代器时，是构造，也支持用普通迭代器来构造一个const迭代器
__RBTreeIterator(const iterator& s): _node(s._node){}

insert

set的插入函数还需要进行类型转换处理，要转换为std::pair<iterator, bool>类型。

//Set.h
std::pair<iterator, bool> Insert(const K& key)
{std::pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret =  _t.Insert(key);return std::pair<iterator, bool>(ret.first, ret.second);
}
//Map.h
std::pair<iterator, bool> Insert(const std::pair<const K, V>& kv)
{return _t.Insert(kv);
}

详细代码可以参考我的gitee库–基于红黑树封装实现set和map
使用的是VS2019。