基于红黑树封装实现set和map
基于红黑树封装实现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。