map源码成员变量
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
typedef Key key_type;
typedef T data_type;
typedef T mapped_type;
typedef pair<const Key, T> value_type;
typedef 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
set源码成员变量
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
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 t; // red-black tree representing set
红黑树主要成员变量
template <class Key, class Value, class KeyOfValue, class Compare,class Alloc = alloc>
class rb_tree {
typedef rb_tree_node* link_type;
protected:
typedef __rb_tree_node<Value> rb_tree_node;
link_type header;
map 和 set用的是用一棵红黑树,但是它们存储的类型不同,是怎么实现的呢?
两个传给红黑树的类型参数个数相同,只是真正的类型不同
typedef rb_tree<key_type, value_type,
identity<value_type>, key_compare, Alloc> rep_type;
map 传给红黑树的类型是:
typedef Key key_type;
typedef pair<const Key, T> value_type;
set 传给红黑树的类型是:
typedef Key key_type;
typedef Key value_type;
map传入的value_type是一个KV元组类型,set的是K类型,这就是模板的好处,但是红黑树里面有需要key来比较时候,这就需要上层(map、set)传入一个仿函数来获取到存储类型的key值用于比较。
class Key, class Value, class KeyOfValue, class Compare,class Alloc = alloc
红黑树模板参数类型解释:
Key
: key的类型,时候会用到,模板参数传入的类型不是值Value
: 存储值的类型,map是一个元组,set只有keyKeyOfValue
: 获取到存储类型的key值的仿函数,使得一颗红黑树实现两种不同的存储类型Compare
: 用于key值比较的仿函数Alloc
: 内存分配相关,暂时不用关心template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
typedef RBTreeIterator<T, Ref, Ptr> Self;
typedef RBTreeNode<T> Node;
Node* _node;
RBTreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& t)
{
return _node != t._node;
}
bool operator==(const Self& t)
{
return _node == t._node;
}
};
需要按中序遍历(有序)来实现迭代器的加减。
寻找下一个结点
即 ++ 迭代器
Self operator++()
{
if (_node->_right != nullptr)
{
// 找右子树最小结点
Node* minNode = _node->_right;
while (minNode->_left != nullptr)
{
minNode = minNode->_left;
}
_node = minNode;
}
else
{
// 找到 cur == parent->left
Node* parent = _node->_parent;
Node* cur = _node;
while (cur != parent->_left && parent != nullptr)
{
cur = parent;
parent = _node->_parent;
}
_node = parent;
}
return *this;
}
寻找前一个结点
即 – 迭代器
Self operator--()
{
if (_node->_left != nullptr)
{
// 找左子树最大结点
Node* maxNode = _node->_left;
while (maxNode->_right != nullptr)
{
maxNode = maxNode->_right;
}
_node = maxNode;
}
else
{
// 找到 cur == parent->_right
Node* parent = _node->_parent;
Node* cur = _node;
while (cur != parent->_right && parent != nullptr)
{
cur = parent;
parent = _node->_parent;
}
_node = parent;
}
return *this;
}
typedef RBTreeIterator<T, T&, T*> iterator;
typedef RBTreeIterator<T, const T&, const T*> const_iterator;
iterator begin()
{
Node* min = _root;
while (min && min->_left)
{
min = min->_left;
}
return iterator(min);
}
iterator end()
{
return iterator(nullptr);
}
// 拷贝构造函数
RBTree(const RBTree<K, T, KeyOfT>& t)
{
_root = Copy(t._root);
}
Node Copy(Node* node)
{
if (node == nullptr) return nullptr;
Node* newNode = new T(node->_data);
newNode->_col = node->_col;
// 链接左右孩子
newNode->_left = Copy(node->_left);
newNode->_right = Copy(node->_right);
// 链接父节点
if (newNode->_left)
newNode->_left->_parent = newNode;
if (newNode->_right)
newNode->_right->_parent = newNode;
return newNode;
}
// 赋值运算符重载
RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
{
std::swap(t._root, _root);
return *this;
}
// 析构函数
~RBTree()
{
Destroy(_root);
_root = nullptr;
}
void Destroy(Node* root)
{
if (root == nullptr)
return;
Destroy(root->_left);
Destroy(root->_right);
delete root; // 调用Node的析构函数
}
这下封装就很简单了直接调用红黑树的方法即可
#pragma once
namespace sqin
{
template<class K, class V>
class map
{
public:
// 获取类型的key值
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const pair<K,V>& kv)
{
return _t.Insert(kv);
}
iterator find(const K& k)
{
return _t.find(k);
}
// 利用插入返回值,实现[]功能
V& operator[](const K& k)
{
auto cur = _t.Insert(make_pair(k, V()));
return cur.first->second;
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
}
#pragma once
namespace sqin
{
template<class K>
class set
{
public:
// 获取类型的key值
struct SetKeyOfT
{
const K& operator()(const K& k)
{
return k;
}
};
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const K& k)
{
return _t.Insert(k);
}
iterator find(const K& k)
{
return _t.find(k);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}