set&&map
- set/map简介
-
- set特性
- map特性
- 红黑树的接口
- set的封装
- map的封装
- 总结
set/map简介
我们所熟知的vector、list、deque被称为序列是容器；set和map是c++中的关联式容器，他们都是用来储存数据的。
只不过关联式容器里面存储的不是单个元素，而是一个<key, value>键值对，这种键值对在数据检索时，效率更高。
键值对：用来表示具有一一对应关系的一种结构，该结构中只包含变量key和value，key代表键值，value表示与key对应的信息。比如英汉互译的词典<apple， 苹果> 就是一个键值对。
set特性
- set是按照一定次序存储元素的容器。
- 在set中，存储的是<key, key>这样的键值对，并且每个key必须是唯一的。set中的元素不能在容器中修改。但是可以从容器中，插入或删除他们
- 在内部，set中的元素总是按照一定的顺序排列
- set插入时，只需要插入value即可，不需要构造键值对
- set底层使用红黑树实现
map特性
- map是按照特定顺序存储的容器
- map中存储的是<key, value>这样的键值对。并且每个key必须唯一。但是value值可以修改。也可以从容器中，插入或删除他们
- 在内部，map是按照key的顺序排列的
- map支持下标访问，且非常灵活。
- map插入时，需要插入一个<key, value>键值对
- map底层是用红黑树实现的
红黑树的接口
修改步骤：
- 将类模板修改为<K, T>， T为存入数据
- 增加一个仿函数的模板选项，用于获取数据的key
- 实现迭代器***
- 迭代器的单参构造（可以实现隐式转换）
- Insert函数，返回值的修改
- 迭代器++的逻辑
- 迭代器的typedef也要好好学学
enum class Color //结点颜色
{
RED,
BLACK
};
//1. 添加了T模板参数
template<class T>
struct RBTreeNode
{
//红黑树结点，默认红色
RBTreeNode(const T& data)
:_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_data(data)
,_color(Color::RED)
{}
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T _data;
Color _color;
};
//3. 迭代器实现(数据，数据的引用，数据的指针)
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)
{}
// *、typedef __RBTreeIterator<T, T&, T*> itertaor; 拷贝构造
// **、 typedef __RBTreeIterator<T, const T&, const T*> const_itertaor;
// 支持普通迭代器构造const迭代器的构造函数
RBTreeIterator(const RBTreeIterator<T, T&, T*>& it)
{
_node = it._node;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &(_node->_data);
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
//左根右
Self& operator++() //左根右
{
//1.右不为空，下一个就是右子树的最左结点
if (_node->_right)
{
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
else
{
//2.右为空，沿着到根的路径，找孩子是父亲左的那个祖先
Node* cur = _node;
Node* parent = cur->_parent;
while (parent && cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
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 && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
// 2. 注意添加了KeyOfT这个仿函数接口,用来把T里面的key给拿出来
template<class K, class T, class KeyOfT>
class RBTree
{
private:
typedef RBTreeNode<T> Node;
public:
//析构函数
~RBTree()
{
_Destroy(_root);
_root = nullptr;
}
public:
typedef RBTreeIterator<T, T&, T*> iterator;
typedef RBTreeIterator<T, const T&, const T*> const_iterator;
iterator begin()
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return iterator(cur);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin() const
{
Node* cur = _root;
while (cur && cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
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;
}
pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_color = Color::BLACK; //根结点就置为黑色
return make_pair(iterator(_root), true);
}
KeyOfT kot; //仿函数实例化
//1.找到插入位置
Node* cur = _root;
Node* parent = nullptr;
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);
}
}
//2.找到了直接插入
Node* newNode = new Node(data);
cur = newNode;
if (kot(parent->_data) > kot(data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent; //记得互联
//3.检查是否满足红黑树，若满足直接退出
//不满足，需要调整红黑树
while(parent && parent->_color == Color::RED)
{
//爷爷结点一定存在，因为parent为红，爷爷结点一定为黑！
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
//情况一： cur 为红，p为红，g为黑， u存在且为红
if (uncle && uncle->_color == Color::RED) // 只需要叔父爷变色即可
{
parent->_color = Color::BLACK;
grandfather->_color = Color::RED;
uncle->_color = Color::BLACK; //子树调整完成
//把爷爷当作新插入结点，继续调整
cur = grandfather;
parent = cur->_parent;
}
else //2.u存在且为黑 3.u不存在 旋转+变色
{
//2 g
// p u
// c
if (cur == parent->_left) //父亲爷爷变色
{
_RotateR(grandfather); //以g为轴点右单旋
parent->_color = Color::BLACK;
grandfather->_color = Color::RED;
}
else //cur是p的右孩子
{
// g
// p u
// c 叔父爷变色
_RotateL(parent);
_RotateR(grandfather);
grandfather->_color = Color::RED;
cur->_color = Color::BLACK;
}
break;
}
}
else //parent = grandfather->_right
{
// g
// u p
// c
Node* uncle = grandfather->_left;
if (uncle && uncle->_color == Color::RED) //情况1 u存在且为红
{
uncle->_color = Color::BLACK;
parent->_color = Color::BLACK;
grandfather->_color = Color::RED;
//继续往上调整
cur = grandfather;
parent = cur->_parent;
}
else //u存在为黑 u不存在
{
// g
// u p
// c
if (cur == parent->_right)
{
//左单旋
_RotateL(grandfather);
parent->_color = Color::BLACK;
grandfather->_color = Color::RED;
}
else
{
// g
// u p
// c
_RotateR(parent);
_RotateL(grandfather);
grandfather->_color = Color::RED;
cur->_color = Color::BLACK;
}
break;
}
}
}
_root->_color = Color::BLACK;
return make_pair(iterator(newNode), true);
}
private:
void _Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
void _RotateR(Node* parent)
{
//右单旋，儿子上位变父亲，父亲被挤到右边
Node* pParent = parent->_parent; //爷爷
Node* childL = parent->_left; //左孩子
parent->_left = childL->_right;
if (childL->_right)
{
childL->_right->_parent = parent; //子指向父
}
childL->_right = parent;
parent->_parent = childL; //子指向父
//最后将chldL指向pParent
childL->_parent = pParent;
if (pParent == nullptr) // childL 变成了根
{
_root = childL;
childL->_parent = nullptr;
}
else
{
if (pParent->_left == parent)
{
pParent->_left = childL;
}
else
{
pParent->_right = childL;
}
}
}
//左单旋
void _RotateL(Node* parent)
{
Node* childR = parent->_right; //存右孩子
parent->_right = childR->_left; //右孩子的左孩子互连父亲
if (childR->_left)
{
childR->_left->_parent = parent;
}
childR->_left = parent; //parent和childR互联
Node* pparent = parent->_parent; //暂存爷爷
parent->_parent = childR;
//爷爷和childR互联
childR->_parent = pparent;
if (pparent == nullptr) //爷爷为空，就是根
{
_root = childR;
childR->_parent = nullptr;
}
else
{
if (pparent->_left == parent)
{
pparent->_left = childR;
}
else
{
pparent->_right = childR;
}
}
}
private:
Node* _root=nullptr; //根
};
set的封装
注意问题：
- 要写一个仿函数，只有自己知道自己的数据类型
- 因为set不可更改value，所以要使用const迭代器，注意typedef的都是const命名的。
- 封装的成员变量直接是红黑树。
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()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
public:
pair<iterator, bool> Insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t; //定义为红黑树
};
map的封装
封装步骤：
- 模板参数不需要加仿函数！！
- 定义仿函数时，注意此参数设置应该具体
- 迭代器只需实现一份即可
- 注意[]的实现注意事项
//template<class K, class T, class KeyOfT> 自己写的，写的不好
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<const K, V>, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
return ret.first->second;
}
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
总结
map和set的封装，重点是封装的思想。多学学这里代码的套路。