C++中map_set的封装实现整体代码
<div id="navCategory"><h5 class="catalogue">目录</h5><ul class="first_class_ul"><li>前言</li><li>一. 源码剖析</li><li>二. 逐步实现</li><ul class="second_class_ul"><li>1. 框架</li><li>2. 仿函数取 Key</li><li>3. 迭代器</li><li>4. const 迭代器</li><li>5. map 的 operator[ ]</li><ul class="third_class_ul"><li>RBTree.h</li><li>MySet.h</li><li>MyMap.h</li></ul></ul><li>三. 整体代码</li><ul class="second_class_ul"></ul><li>总结</li><ul class="second_class_ul"></ul></ul></div><p class="maodian"></p><h2>前言</h2><p>以前理解的 set 是 key；map 是 key_value，似乎是 2 棵树，但其实他俩用同一个类模板</p>
<p class="maodian"></p><h2>一. 源码剖析</h2>
<p><strong>set</strong></p>
<div class="jb51code"><pre class="brush:cpp;">#include <stl_tree.h>
#include <stl_set.h>
#include <stl_multiset.h></pre></div>
<p>set 和 map 是一层浅浅的封装，核心都在树里实现</p>
<p><strong>stl_set.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
typedef Key key_type;
typedef Key value_type;
private:
typedef rb_tree<key_type, value_type, // <K, K>
identity<value_type>, key_compare, Alloc> rep_type;
rep_type t;// red-black tree representing set
}</pre></div>
<p><strong>stl_map.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
typedef Key key_type;
typedef pair<const Key, T> value_type;
private:
typedef rb_tree<key_type, value_type,// <K, pair<K, V>>
select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t;// red-black tree representing map
}</pre></div>
<p><strong>stl_tree.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">struct __rb_tree_node_base
{
typedef __rb_tree_color_type color_type;
typedef __rb_tree_node_base* base_ptr;
color_type color;
base_ptr parent;
base_ptr left;
base_ptr right;
};
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 __rb_tree_node<Value> rb_tree_node;
public:
typedef Key key_type;
typedef Value value_type;
typedef rb_tree_node* link_type;
protected:
size_type node_count; // keeps track of size of tree
link_type header;
Compare key_compare;
}</pre></div>
<p>link_type 是节点的指针</p>
<blockquote><p>树的节点里存第二个模板参数 Value ，这个不是真 value<br />对 map 而言，value_type 传给 Value 的是 pair<K, V>（树的节点存的是 pair<K, V>）<br />对 set 而言，value_type 传给 Value 的是 K（树的节点存的是 K）</p></blockquote>
<p>用 <span><strong>Value</strong></span> 做 __rb_tree_node 的模板参数，<span><strong>决定了树节点 node 里面存什么</strong></span></p>
<p class="maodian"></p><h2>二. 逐步实现</h2>
<p class="maodian"></p><h3>1. 框架</h3>
<p><strong>MySet.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">#include "RBTree.h"
namespace qtw
{
template <class K>
class set
{
private:
RBTree<K, K> _t;
};
}</pre></div>
<p><strong>MyMap.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">#include "RBTree.h"
namespace qtw
{
template <class K, class V>
class map
{
private:
RBTree<K, pair<K, V>> _t;
};
}</pre></div>
<p><strong>RBTree.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">enum Colour { RED, BLACK };
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
T _data;
RBTreeNode(const T& data)
:_data(data)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{ }
};
template<class K, class T>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_data < data)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_data > data)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
// ......
}</pre></div>
<p>39 44 行不能用 data 直接比较。set 可以；map 不期望用 pair<>，期望用 pair.first 比较<br />库里重载了 pair 的比较：first 小或 second 小，但不符合我们的需求</p>
<p class="maodian"></p><h3>2. 仿函数取 Key</h3>
<p>用<span><strong>仿函数</strong></span>可以解决，再认识仿函数</p>
<p>在一. 源码剖析可以看到 stl_tree.h 多了个模板参数 KeyOfValue，取出 Value 中的 Key</p>
<p><strong>MySet.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">#include "RBTree.h"
namespace qtw
{
template <class K>
class set
{
struct SetKeyOfT // 定义成内部类，可以直接用模板参数 K,V
{
const K& operator()(const K& key)
{
return key;
}
};
public:
bool insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}</pre></div>
<p><strong>MyMap.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">#include "RBTree.h"
namespace qtw
{
template <class K, class V>
class map
{
struct MapKeyOfT // 定义成内部类，可以直接用模板参数 K,V
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
bool insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
}</pre></div>
<p><strong>RBTree.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
Node* 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 cur;
}
}
return nullptr;
}
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
KeyOfT kot;
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);
//cur->_col = RED;
if (kot(parent->_data) < kot(data))
parent->_right = cur;
else
parent->_left = cur;
cur->_parent = parent;
//......
}</pre></div>
<p>仿函数对象调 operator() 取出 T 中的 key<br />比较交给树里实现，可以用仿函数控制，在一. 源码剖析可以看到 stl_tree.h 第四个模板参数 Compare</p>
<p class="maodian"></p><h3>3. 迭代器</h3>
<p>库里增加了哨兵位的头结点</p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121509001951.png" /></p>
<blockquote><p>root == header->parent<br />header == root->parent</p></blockquote>
<p><strong>stl_tree.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">iterator begin() { return leftmost(); }
link_type& leftmost() const { return (link_type&) header->left; }
iterator end() { return header; }</pre></div>
<p><strong>我们用空代表 end</strong></p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121509001926.png" /></p>
<p>迭代器要实现这个：</p>
<div class="jb51code"><pre class="brush:cpp;">it = s.begin()
while (it != s.end())
{
cout << *it << " ";
++it;
}</pre></div>
<p>搜索树的迭代器要中序遍历</p>
<p><span><strong>++：左 根 右</strong><br /><strong>1. 右不为空，访问右子树的最左节点（最小节点）</strong><br /><strong>2. 右为空，下一个访问的是 孩子是父亲左的父亲（是该节点的祖先）</strong></span></p>
<p><strong>--：右 根 左</strong><br /><strong>1. 左不为空，访问左子树的最右节点（最大节点）</strong><br /><strong>2. 左为空，下一个访问的是 孩子是父亲右的父亲（是该节点的祖先）</strong></p>
<p><strong>RBTree.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">template<class T>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T> Self;
Node* _node;
__TreeIterator(Node* node)
:_node(node)
{ }
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
Self& operator--()
{
if (_node->_left)
{
// 访问左子树的最右节点
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//while (parent)
//{
// if (cur == parent->_right)
// {
// break; // 我是父亲的右，下一个访问父亲(右 根 左)
// }
// else // 我是父亲的左，找孩子是父亲右的那一个
// {
// cur = parent;
// parent = parent->_parent;
// }
//}
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator++()
{
if (_node->_right)
{
// 访问右子树的最左节点
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//while (parent)
//{
// if (cur == parent->_left)
// {
// break; // 我是父亲的左，下一个访问父亲(左 根 右)
// }
// else // 我是父亲的右，找孩子是父亲左的那一个
// {
// cur = parent;
// parent = parent->_parent;
// }
//}
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __TreeIterator<T> iterator;
iterator begin()
{
Node* leftMin = _root;
while (leftMin && leftMin->_left) // 有可能空树
{
leftMin = leftMin->_left;
}
return iterator(leftMin);
}
iterator end()
{
return iterator(nullptr);
}
Node* Find(const K& key)
// ...
}</pre></div>
<p><strong>MySet.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">#include "RBTree.h"
namespace qtw
{
template <class K>
class set
{
struct SetKeyOfT // 定义成内部类，可以直接用模板参数 K,V
{
const K& operator()(const K& key)
{
return key;
}
};
public:
//typedef RBTree<K, K, SetKeyOfT>::iterator iterator; 错
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
bool insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}</pre></div>
<p>第 16 行错：RBTree<K, K, SetKeyOfT> 是类模板，没被实例化时不生成具体代码，设计没有实例化的具体参数，编译器不敢从类模板里找 iterator；而且内嵌类型、静态也可以用这个语法</p>
<p>加上 typename 是告诉编译器这里是类型，等实例化以后再找 iterator</p>
<p><strong>MyMap.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">#include "RBTree.h"
namespace qtw
{
template <class K, class V>
class map
{
struct MapKeyOfT // 定义成内部类，可以直接用模板参数 K,V
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
//typedef RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; 错
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
bool insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
}</pre></div>
<p><strong>Test.cpp</strong></p>
<div class="jb51code"><pre class="brush:cpp;">#include"MyMap.h"
#include"MySet.h"
int main()
{
qtw::map<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(3, 3));
m.insert(make_pair(2, 2));
qtw::map<int, int>::iterator mit = m.begin();
while (mit != m.end())
{
//cout << *mit << " "; 错
//调operator*,返回T类型的_data,是pair,pair不支持流插入
//迭代器模拟自定义类型指针，用operator->
cout << mit->first << ":" << mit->second << endl;
++mit;
}
cout << endl;
for (const auto& kv : m)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
qtw::set<int> s;
s.insert(5);
s.insert(2);
s.insert(2);
s.insert(12);
s.insert(22);
s.insert(332);
s.insert(7);
qtw::set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (const auto& e : s)
{
cout << e << " ";
}
cout << endl;
return 0;
}</pre></div>
<p>还有问题：set 本不允许修改；map 仅允许 V 修改；重载 operator[ ] 要改 insert 的返回值</p>
<p class="maodian"></p><h3>4. const 迭代器</h3>
<p>先把树的 const 迭代器搞好，才能搞 set_map 的 const 迭代器</p>
<p><strong>RBTree.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">template<class T, class Ptr, class Ref>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T, Ptr, Ref> Self;
Node* _node;
__TreeIterator(Node* node)
:_node(node)
{ }
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
Self& operator--()
{
if (_node->_left)
{
// 访问左子树的最右节点
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//while (parent)
//{
// if (cur == parent->_right)
// {
// break; // 我是父亲的右，下一个访问父亲(右 根 左)
// }
// else // 我是父亲的左，找孩子是父亲右的那一个
// {
// cur = parent;
// parent = parent->_parent;
// }
//}
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator++()
{
if (_node->_right)
{
// 访问右子树的最左节点
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//while (parent)
//{
// if (cur == parent->_left)
// {
// break; // 我是父亲的左，下一个访问父亲(左 根 右)
// }
// else // 我是父亲的右，找孩子是父亲左的那一个
// {
// cur = parent;
// parent = parent->_parent;
// }
//}
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __TreeIterator<T, T*, T&> iterator;
typedef __TreeIterator<T, const T*, const T&> const_iterator;
iterator begin()
{
Node* leftMin = _root;
while (leftMin && leftMin->_left) // 有可能空树
{
leftMin = leftMin->_left;
}
return iterator(leftMin);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin() const
{
Node* leftMin = _root;
while (leftMin && leftMin->_left) // 有可能空树
{
leftMin = leftMin->_left;
}
return const_iterator(leftMin);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
Node* Find(const K& key)
// ......
}</pre></div>
<p><strong>MySet.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">#include "RBTree.h"
namespace qtw
{
template <class K>
class set
{
struct SetKeyOfT // 定义成内部类，可以直接用模板参数 K,V
{
const K& operator()(const K& key)
{
return key;
}
};
public:
//typedef RBTree<K, K, SetKeyOfT>::iterator iterator; 错
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();
}
bool insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}</pre></div>
<p><strong>MyMap.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">#include "RBTree.h"
namespace qtw
{
template <class K, class V>
class map
{
struct MapKeyOfT // 定义成内部类，可以直接用模板参数 K,V
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
//typedef RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; 错
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin() const
{
return _t.begin();
}
const_iterator end() const
{
return _t.end();
}
bool insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}</pre></div>
<p class="maodian"></p><h3>5. map 的 operator[ ]</h3>
<p><strong>RBTree.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __TreeIterator<T, T*, T&> iterator;
typedef __TreeIterator<T, const T*, const T&> const_iterator;
// ......
pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
Node* cur = _root;
Node* parent = nullptr;
KeyOfT kot;
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 make_pair(iterator(cur), 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;
// 如果cur是根、cur父亲是黑：直接完事
// cur父亲是红：进来
while (parent && parent->_col == RED)
{
// cur一定有爷，且爷为黑
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
// uncle存在，且为红：变色，继续更新
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else // uncle不存在，或存在且为黑
{
if (parent->_left == cur)
{
// g
// p
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
}
}
else // grandfather->_right == parent
{
Node* uncle = grandfather->_left;
// uncle存在，且为红：变色，继续更新
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else // uncle不存在，或存在且为黑
{
if (parent->_right == cur)
{
// g
// p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
}
}
}
_root->_col = BLACK; // 暴力处理
return make_pair(iterator(newnode), true);
}
};</pre></div>
<p><strong>MyMap.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">V& operator[](const K& key) { }
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}</pre></div>
<p><strong>MySet.h</strong></p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121509001969.png" /></p>
<p>报错：“return”: 无法从“std::pair<__TreeIterator<T,T *,T &>,bool>”转换为“std::pair<__TreeIterator<T,const T *,const T &>,bool>”</p>
<p>_t 是普通对象，调 Insert 返回普通迭代器；但红色的 iterator 是 const_iterator</p>
<p>看看库里是怎么搞的</p>
<p><strong>stl_set.h</strong></p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121509001983.png" /></p>
<p>第 2 行黄色的是普通迭代器，第 3 行绿色的是 const 迭代器</p>
<p>照猫画虎</p>
<p><strong>MySet.h</strong></p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121509001930.png" /></p>
<p>_t 是树的普通对象，调 Insert 返回树的<span>普通迭代器</span>；但 set 是 <span>const 迭代器</span>，过不不去</p>
<p>单独用普通的树的迭代器对象接收，再<strong>用</strong>这个<strong><span>普通迭代器</span></strong><strong>对象构造 </strong><strong><span>const 迭代器</span></strong><strong>对象</strong></p>
<p>因为 const 迭代器支持了一个构造：18 行</p>
<p><strong>stl_tree.h</strong></p>
<p style="text-align:center"><img alt="" src="https://img.jbzj.com/file_images/article/202512/2025121509001933.png" /></p>
<p>第 11 行的 iterator：不管是普通/const 迭代器，这个 iterator 都是普通迭代器</p>
<p>当这个类被实例化成 const 迭代器时，第 18 行的函数是一个构造，支持普通迭代器构造 const 迭代器<br />__rb_tree_iterator 是 const 迭代器，参数是 iterator 普通迭代器</p>
<p>当这个类被实例化成普通迭代器时，第 18 行的函数是一个拷贝构造</p>
<p><strong>RBTree.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">template<class T, class Ptr, class Ref>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T, Ptr, Ref> Self;
typedef __TreeIterator<T, T*, T&> Iterator; // 一直是普通迭代器
Node* _node;
__TreeIterator(const Iterator& it)
:_node(it._node)
{ }
// ......
}</pre></div>
<p><strong>MyMap.h</strong></p>
<div class="jb51code"><pre class="brush:cpp;">V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}</pre></div>
<p class="maodian"></p><h2>三. 整体代码</h2>
<p class="maodian"></p><h4>RBTree.h</h4>
<div class="jb51code"><pre class="brush:cpp;">enum Colour { RED, BLACK };
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
T _data;
RBTreeNode(const T& data)
:_data(data)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{ }
};
template<class T, class Ptr, class Ref>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T, Ptr, Ref> Self;
typedef __TreeIterator<T, T*, T&> Iterator; // 一直是普通迭代器
Node* _node;
__TreeIterator(const Iterator& it)
:_node(it._node)
{ }
__TreeIterator(Node* node)
:_node(node)
{ }
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
Self& operator--()
{
if (_node->_left)
{
// 访问左子树的最右节点
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//while (parent)
//{
// if (cur == parent->_right)
// {
// break; // 我是父亲的右，下一个访问父亲(右 根 左)
// }
// else // 我是父亲的左，找孩子是父亲右的那一个
// {
// cur = parent;
// parent = parent->_parent;
// }
//}
while (parent && cur == parent->_left)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator++()
{
if (_node->_right)
{
// 访问右子树的最左节点
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//while (parent)
//{
// if (cur == parent->_left)
// {
// break; // 我是父亲的左，下一个访问父亲(左 根 右)
// }
// else // 我是父亲的右，找孩子是父亲左的那一个
// {
// cur = parent;
// parent = parent->_parent;
// }
//}
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __TreeIterator<T, T*, T&> iterator;
typedef __TreeIterator<T, const T*, const T&> const_iterator;
iterator begin()
{
Node* leftMin = _root;
while (leftMin && leftMin->_left) // 有可能空树
{
leftMin = leftMin->_left;
}
return iterator(leftMin);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin() const
{
Node* leftMin = _root;
while (leftMin && leftMin->_left) // 有可能空树
{
leftMin = leftMin->_left;
}
return const_iterator(leftMin);
}
const_iterator end() const
{
return const_iterator(nullptr); // 我们用空代表end
}
Node* 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 cur;
}
}
return nullptr;
}
pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
Node* cur = _root;
Node* parent = nullptr;
KeyOfT kot;
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 make_pair(iterator(cur), 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;
// 如果cur是根、cur父亲是黑：直接完事
// cur父亲是红：进来
while (parent && parent->_col == RED)
{
// cur一定有爷，且爷为黑
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
// uncle存在，且为红：变色，继续更新
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else // uncle不存在，或存在且为黑
{
if (parent->_left == cur)
{
// g
// p
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
}
}
else // grandfather->_right == parent
{
Node* uncle = grandfather->_left;
// uncle存在，且为红：变色，继续更新
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else // uncle不存在，或存在且为黑
{
if (parent->_right == cur)
{
// g
// p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
}
}
}
_root->_col = BLACK; // 暴力处理
return make_pair(iterator(newnode), true);
}
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
Node* ppnode = parent->_parent;
// 2个核心步骤
parent->_right = curleft;
cur->_left = parent;
if (curleft) // 调整curleft父亲节点的指向
{
curleft->_parent = parent;
}
parent->_parent = cur; //调整parent父亲节点的指向
//cur->_parent = ppnode; 错
//调整cur父亲节点的指向
if (_root == parent)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
ppnode->_left = cur;
else
ppnode->_right = cur;
cur->_parent = ppnode;
}
}
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
Node* ppnode = parent->_parent;
// 2个核心步骤
parent->_left = curright;
cur->_right = parent;
parent->_parent = cur; // 调整parent父亲节点的指向
if (curright) // 调整curright父亲节点的指向
{
curright->_parent = parent;
}
//cur->_parent = ppnode; 错
// 调整cur父亲节点的指向
if (_root == parent)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_right == parent)
ppnode->_right = cur;
else
ppnode->_left = cur;
cur->_parent = ppnode;
}
}
bool CheckColor(Node* root, int blacknum, int benchnark)
{
if (root == nullptr)
{
if (benchnark != blacknum)
return false;
return true;
}
if (root->_col == BLACK)
blacknum++;
if (root->_col == RED && root->_parent && root->_parent->_col == RED)
{
cout << root->_kv.first << "出现连续红色节点" << endl;
return false;
}
return CheckColor(root->_left, blacknum, benchnark)
&& CheckColor(root->_right, blacknum, benchnark);
}
bool IsBalance()
{
return IsBalance(_root);
}
bool IsBalance(Node* root)
{
if (root == nullptr)
return true;
if (root->_col != BLACK)
return false;
// 基准值
int benchnark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
++benchnark;
cur = cur->_left;
}
return CheckColor(root, 0, benchnark);
}
private:
Node* _root = nullptr;
};</pre></div>
<p class="maodian"></p><h4>MySet.h</h4>
<div class="jb51code"><pre class="brush:cpp;">#include "RBTree.h"
namespace qtw
{
template <class K>
class set
{
struct SetKeyOfT // 定义成内部类，可以直接用模板参数 K,V
{
const K& operator()(const K& key)
{
return key;
}
};
public:
//typedef RBTree<K, K, SetKeyOfT>::iterator iterator; 错
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();
}
// iterator RBTree::const_iterator
pair<iterator, bool> insert(const K& key)
{
// pair<RBTree::iterator, bool>
pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
return pair<iterator, bool>(ret.first, ret.second);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}</pre></div>
<p class="maodian"></p><h4>MyMap.h</h4>
<div class="jb51code"><pre class="brush:cpp;">#include "RBTree.h"
namespace qtw
{
template <class K, class V>
class map
{
struct MapKeyOfT // 定义成内部类，可以直接用模板参数 K,V
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
//typedef RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; 错
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin() const
{
return _t.begin();
}
const_iterator end() const
{
return _t.end();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}</pre></div>
<p class="maodian"></p><h2>总结</h2>
<p>到此这篇关于C++中map_set封装实现的文章就介绍到这了,更多相关C++中map_set封装内容请搜索琼殿技术社区以前的文章或继续浏览下面的相关文章希望大家以后多多支持琼殿技术社区！</p>
<div class="art_xg">
<b>您可能感兴趣的文章:</b><ul><li>C++实现map和set封装详解</li><li>C++ map与set封装实现过程讲解</li><li>C++使用一棵红黑树同时封装出map和set实例代码</li><li>C++中map和set封装实现示例</li></ul>
</div>
</div>
<!--endmain-->
頁:
[1]