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

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

stl3.0–参考大佬的代码

set的封装

#ifndef __STL_LIMITED_DEFAULT_TEMPLATES
template , class Alloc = alloc>
#else
template 
#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_compare, Alloc> rep_type;rep_type t;  // red-black tree representing set

map的封装

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

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

tree.h

template 
struct __rb_tree_node : public __rb_tree_node_base
{typedef __rb_tree_node* link_type;Value value_field;
};template 
class rb_tree {
protected:typedef void* void_pointer;typedef __rb_tree_node_base* base_ptr;typedef __rb_tree_node 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不允许修改Key，但是可以修改Value，//(it->first)++; // 无法修改 (it->second)++;//可以修改

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

typedef typename RBTree, MapKeyOfT>::iterator iterator;

要加上typename这个关键字，因为RBTree, MapKeyOfT>还没有实例化，凡是没有实例化的类模板，编译器无法分清楚iterator到底是一个静态变量还是一个类型，用关键字typename告诉编译器，RBTree, 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 Insert(const T& data) //最重要的是insert返回值类型的处理
//Map.hV& operator[](const K& Key)
{std::pair ret = Insert(std::make_pair(Key, V()));return ret.first->second;
}

const迭代器

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

//RBTree.h
template
struct __RBTreeIterator
{typedef RBTreeNode Node;typedef __RBTreeIterator Self;typedef __RBTreeIterator iterator;Node* _node;
};

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

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

insert

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

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

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