# 用红黑树封装实现map和set

#### map和set的实现原理

enum Color {RED,BLACK};
template<class T>//节点存储对象类型，可能是键值对也有可能是key
class RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Color _col;
RBTreeNode(const T& data)
:_data(data)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _col(RED)
{}
};

set

template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
private:
RBTree<K, K, SetKeyOfT> _t;
};

map

template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
public:
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

rbtree

template<class K,class T,class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
private:
Node* _root = nullptr;
};

#### map和set的迭代器

rbtree迭代器实现

struct __RBTreeIterator
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T> Self;
Node* _node;
__RBTreeIterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_right)
{
Node* min = _node->_right;
while (min->_left)
{
min = min->_left;
}
_node = min;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
//右子树 根 左子树
if (_node->_left)
{
//找左子树的最右结点，其实就是次大的结点
_node = _node->_left;
while (_node->_right)
{
_node = _node->_right;
}
}
else
{
Node* cur = _node;
Node* parent = _node->_parent;
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
//如果cur是parent的右，则直接让_node指向到parent即可
_node = parent;
}
return *this;//返回迭代器对象
}
bool operator!=(const Self& it)const//const修饰表示在该成员函数内部，不能修改对象的任何成员变量
{
return this->_node != it._node;
}
bool operator==(const Self& it)const//const对象和非const对象都可以调用
{
return this->_node == it._node;
}
};

template <class K>
class set
{
public:
//set表层的普通迭代器底层用的依旧是const_iterator，就是不允许对set的迭代器指向内容进行修改
typedef typename RBTree<K, K, SetKeyOfT<K>>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT<K>>::const_iterator const_iterator;
iterator begin()  const   //为了防止权限的放大，我们直接使用const，如果对象是const，调用const的begin，不是const也调用const的begin和end
{
return _t.begin();
}
iterator end()  const
{
return _t.end();
}

map的迭代器是需要实现两个版本的，因为map容器中的数据是可以被修改的，如果你想修改map中的数据那就用iterator，如果你想修改map中的数据那就用const_iterator。

template <class K, class V>
class map
{
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K, V>>::const_iterator const_iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT<K, V>>::const_iterator const_iterator;
//map的迭代器需要提供两个版本
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
const_iterator begin()const
{
return _t.begin();
}
const_iterator end()const
{
return _t.end();
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT<K,V>> _t;
};

#### 红黑树插入的改造

pair<iterator, bool> Insert(const T& data)
//红黑树必须通过结点里面存储的key来进行比较才可以插入结点，所以出现了kot仿函数对象
{
KeyOfT kot;
Node* parent = nullptr;
Node* cur = _root;
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
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* curit = cur;//保存一下cur的位置否则下面旋转调色过程中，cur有可能被改了
if (kot(parent->_data) > kot(data))
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
while (parent && parent->_col == RED)
{
Node* grandparent = parent->_parent;
if (parent == grandparent->_left)
{
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
cur = grandparent;
parent = cur->_parent;
}
else if (cur == parent->_left)
{
RotateR(grandparent);
grandparent->_col = RED;
parent->_col = BLACK;
break;
}
else if (cur == parent->_right)
{
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
break;
}
else
{
assert(false);
}
}
else
{
Node* uncle = grandparent->_left;
if (uncle && uncle->_col == RED)
{
grandparent->_col = RED;
uncle->_col = parent->_col = BLACK;
cur = grandparent;
parent = cur->_parent;
}
else if (cur == parent->_right)
{
RotateL(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
break;
}
else if (cur == parent->_left)
{
RotateR(parent);
RotateL(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
break;
}
else
{
assert(false);
}
}
}
_root->_col = BLACK;

return make_pair(iterator(curit), true);
}

#### map的[]重载

[]直接返回插入节点的值，如果[]内的key值不在红黑树中，就直接插入，若在其中也有进行修改，最后返回iterator的first的second

template <class K, class V>
class map
{
public:
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}

V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return (ret.first)->second;
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT<K,V>> _t;
};

|
5天前
|
JavaScript 前端开发 Java
ES6 逐点突破系列 -- Set Map，工作感悟，完美收官
ES6 逐点突破系列 -- Set Map，工作感悟，完美收官
6 0
|
5天前
|

JavaScript中的Set和Map：理解与使用
JavaScript中的Set和Map：理解与使用
8 0
|
6天前
|

ES6+新特性-Symbol与Set/Map数据结构
ES6 引入了三种新的数据结构：Symbol、Set和Map。Symbol是唯一且不可变的值，常用于定义对象的独特属性；Set存储不重复值，适合数组去重；Map则是键值对集合，键可为任意类型，提供了更灵活的存储方式。这些新数据结构提供了更高效的操作手段，分别解决了属性命名冲突、数据去重和复杂键值对存储的问题。示例展示了如何使用Symbol、Set和Map进行基本操作。
16 6
|
6天前
|

C++：map&set 对红黑树的封装
C++：map&set 对红黑树的封装
11 1
|
6天前
|

Map与Set的经典OJ题
Map与Set的经典OJ题
13 3
|
6天前
|

js开发：请解释什么是ES6的Map和Set，以及它们与普通对象和数组的区别。
27 3
|
6天前
|

Set和Map的应用场景
Set和Map的应用场景
17 0
|
6天前
|

map和set的简单介绍
map和set的简单介绍
27 1
|
6天前
|

Map与Set
Map与Set
13 3
|
6天前
|

C++：STL - set & map
C++：STL - set & map
16 4