set和map的模拟
目录
1.介绍
2.模拟实现
2.1节点的改造
2.2迭代器的实现
2.2.1
2.2.2
3.完整代码
1.介绍
STL中的set和map的底层都是用红黑树模拟实现的。但set每次只存储一个值，而map存储的是键值对，那是否要写两份红黑树的代码呢？
可写看下之前写的博客：可怕的红黑树_"派派"的博客-CSDN博客，实现是与map相似的。
2.模拟实现
2.1节点的改造
我们可用模板对红黑树进行改造，让map和set同时适用。
在红黑树的代码中，我们可把存储每个节点的结构代码体更改为：
enum Colour
{
RED,
BLACK,
};
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data; // 存储数据
Colour _col;
RBTreeNode(const T& data)
:_data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
};其中根据T中的类型进行存储，例如：T可以是set传来的int类型等，map传来的键值对。
但在插入时需要比较数据的大小，T可能为int类型或则键值对。所以需要再增加一个仿函数，用来提取第一个参数（map和set都是用第一个参数比较大小的）。
set中：
template<class K>
class Set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public：
bool insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};map中:
template<class K, class V>
class Map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)//提取第一个参数
{
return kv.first;
}
};
public:
bool insert(const pair<K,V>& kv)
{
_t.Insert(kv);
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
红黑树的代码部分：
template<class K, class T, class KeyOfT>//keyOfT用来接收仿函数
class RBTree
{
typedef RBTreeNode<T> Node;
public:
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
KeyOfT kot;
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (kot(cur->_data) < kot(data))
{
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(data);
Node* newnode = cur;
cur->_col = RED;
if (kot(parent->_data) < kot(data))
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
..................
..................
//旋转.....
}
}画图理解下：
我们可验证下结果是否准确，可在红黑树中定义一个中序遍历代码，然后在set，map中调用。
void test_set1()
{
Set<int> s;
s.insert(8);
s.insert(6);
s.insert(5);
s.insert(7);
s.insert(2);
s.insert(9);
Map<string, int>m;
m.insert(make_pair("香蕉", 1));
m.insert(make_pair("苹果", 1));
m.insert(make_pair("西瓜", 1));
m.insert(make_pair("草莓", 1));
s.Inorder();
cout << endl;
m.Inorder();
} 结果：
2.2迭代器的实现
红黑树也是可以像string，vector一样，通过迭代器像指针一样去遍历节点，不过它更像list的迭代器，不是一个原生指针，而是通过封装了节点的指针，对指针进行操作。
在红黑树中增加下面的代码：
typedef __RBTreeIterator<T, T&, T*> iterator;
typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
iterator Begin()//找其最左节点
{
Node* subLeft = _root;
while (subLeft && subLeft->_left)
{
subLeft = subLeft->_left;
}
return iterator(subLeft);
}
iterator End()
{
return iterator(nullptr);
}
const_iterator Begin() const
{
Node* subLeft = _root;
while (subLeft && subLeft->_left)
{
subLeft = subLeft->_left;
}
return const_iterator(subLeft);
}
const_iterator End() const
{
return const_iterator(nullptr);
}
iterator Find(const K& key)//查找
{
Node* cur = _root;
KeyOfT kot;
while (cur)
{
if (kot(cur->_data) < key)
{
cur = cur->_right;
}
else if (kot(cur->_data) > key)
{
cur = cur->_left;
}
else
{
return iterator(cur);
}
}
return End();
}迭代器的实现：
2.2.1
template<class T, class Ref, class Ptr>
struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
__RBTreeIterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
............
............
}
Self operator++(int)
{
Self tmp(*this);
++(*this);
return tmp;
}
Self& operator--()
{
..........
..........
}
Self operator--(int)
{
Self tmp(*this);
--(*this);
return tmp;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s->_node;
}
};
2.2.2
++的实现：
++的实现与中序遍历的规则类似，但每次只走一步。
思路：当一个节点有右子树时，对其节点++，之后指针是指向该右子树的最左节点。
当一个节点无右子树时，对其节点++，之后指针是指向（在其祖先里，孩子是属于祖先左 孩子的）。
如图：
Self& operator++()
{
if (_node->_right == nullptr)
{
// 找祖先里面，孩子是父亲左的那个
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && parent->_right == cur)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
else
{
// 右子树的最左节点
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
return *this;
}--的实现：
思路：当左子树不为空时，对其节点--，指向的是该左子树的最右节点。
当左子树为空时，对其节点--，之后指针是指向（在其祖先里，孩子是属于祖先右 孩子的）。
如图：
Self& operator--()
{
if (_node->_left == nullptr)
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_left)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
else
{
// 左子树的最右节点
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
return *this;
}当迭代器实现后，红黑树的插入代码要进行更改，insert函数返回值是pair，第一个参数是指向当前节点的迭代器，第二个参数是true/false;(插入成功返回true，否则返回false）。
3.完整代码
set:
template<class K>
class Set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin() const
{
return _t.Begin();
}
iterator end() const
{
return _t.End();
}
pair<iterator, bool> insert(const K& key)
{
//pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret =
// _t.Insert(key);
auto ret = _t.Insert(key);
return pair<iterator, bool>(iterator(ret.first._node), ret.second);
}
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};map代码：
template<class K, class V>
class Map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::const_iterator const_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& key)
{
return _t.Find(key);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};