在STL源码当中,如何使用一颗红黑树同时实现map和set的?
直接去看stl源码
__rb_tree_node
的定义
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; }
这里是红黑树的定义。
然后看一下
stl_map.h
文件
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc> class map { public: // typedefs: typedef Key key_type; typedef T data_type; typedef T mapped_type; typedef pair<const Key, T> value_type; typedef Compare key_compare; class value_compare : public binary_function<value_type, value_type, bool> { friend class map<Key, T, Compare, Alloc>; protected : Compare comp; value_compare(Compare c) : comp(c) {} public: bool operator()(const value_type& x, const value_type& y) const { return comp(x.first, y.first); } };
然后再看
stl_set.h
文件
template <class Key, class Compare = less<Key>, class Alloc = alloc> class set { public: // typedefs: typedef Key key_type; typedef Key value_type; typedef 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 rep_type t; // red-black tree representing set }
可以看到在红黑树当中,是用第二个模板参数来确定到底是map还是set的
template <class Key, class Value, class KeyOfValue, class Compare, class Alloc = alloc> class rb_tree { protected: typedef __rb_tree_node<Value> rb_tree_node; }