您现在的位置是：首页 >其他 >【C++】模拟实现map和set网站首页其他
【C++】模拟实现map和set
简介【C++】模拟实现map和set
1.关联式容器
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的 键值对，在数据检索时比序列式容器效率更高。
2 .键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代 表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然 有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应 该单词，在词典中就可以找到与其对应的中文含义。 SGI-STL中关于键值对的定义：
template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair() : first(T1()), second(T2())
{}
pair(const T1& a, const T2& b) : first(a), second(b)
{}
};
3.树形结构的关联式容器
根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结 构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使 用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一 个容器。
3.1 set
3.1.1 set介绍
set是按照一定次序存储元素的容器
在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。 set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行 排序。
set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对 子集进行直接迭代。 5. set在底层是用二叉搜索树(红黑树)实现的。
注意：
与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对。
set中插入元素时，只需要插入value即可，不需要构造键值对。
set中的元素不可以重复(因此可以使用set进行去重)。
使用set的迭代器遍历set中的元素，可以得到有序序列
set中的元素默认按照小于来比较
set中查找某个元素，时间复杂度为： l o g 2 n log_2 n log2n
set中的元素不允许修改(仔细想想为什么?)
set中的底层使用二叉搜索树(红黑树)来实现。
3.1.2 set的使用
-
set的模板参数列表
T: set中存放元素的类型，实际在底层存储的键值对。 Compare：set中元素默认按照小于来比较 Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理
- set构造和赋值
功能描述：创建set容器以及赋值
构造：
set<T> st;//默认构造函数：set(const set &st);//拷贝构造函数
赋值：
set& operator=(const set &st);//重载等号操作符
示例：
#include <set>
void printSet(set<int> & s)
{
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
//构造和赋值
void test01()
{
set<int> s1;
s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(40);
printSet(s1);
//拷贝构造
set<int>s2(s1);
printSet(s2);
//赋值
set<int>s3;
s3 = s2;
printSet(s3);
}
int main()
{
test01();
return 0;
}
总结：
- set容器插入数据时用insert
- set容器插入数据的数据会自动排序
- set大小和交换
功能描述：
- 统计set容器大小以及交换set容器
函数原型：
size();//返回容器中元素的数目empty();//判断容器是否为空swap(st);//交换两个集合容器
示例：
#include <set>
void printSet(set<int> & s)
{
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
//大小
void test01()
{
set<int> s1;
s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(40);
if (s1.empty())
{
cout << "s1为空" << endl;
}
else
{
cout << "s1不为空" << endl;
cout << "s1的大小为： " << s1.size() << endl;
}
}
//交换
void test02()
{
set<int> s1;
s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(40);
set<int> s2;
s2.insert(100);
s2.insert(300);
s2.insert(200);
s2.insert(400);
cout << "交换前" << endl;
printSet(s1);
printSet(s2);
cout << endl;
cout << "交换后" << endl;
s1.swap(s2);
printSet(s1);
printSet(s2);
}
int main()
{
test01();
test02();
return 0;
}
总结：
- 统计大小 — size
- 判断是否为空 — empty
- 交换容器 — swap
- set插入和删除
功能描述：
- set容器进行插入数据和删除数据
函数原型：
insert(elem);//在容器中插入元素。clear();//清除所有元素erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。erase(elem);//删除容器中值为elem的元素。
示例：
#include <set>
void printSet(set<int> & s)
{
for (set<int>::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
//插入和删除
void test01()
{
set<int> s1;
//插入
s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(40);
printSet(s1);
//删除
s1.erase(s1.begin());
printSet(s1);
s1.erase(30);
printSet(s1);
//清空
//s1.erase(s1.begin(), s1.end());
s1.clear();
printSet(s1);
}
int main()
{
test01();
return 0;
}
-
总结：
- 插入 — insert
- 删除 — erase
- 清空 — clear
-
set查找和统计
功能描述：
- 对set容器进行查找数据以及统计数据
函数原型：
find(key);//查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();count(key);//统计key的元素个数
示例：
#include <set>
//查找和统计
void test01()
{
set<int> s1;
//插入
s1.insert(10);
s1.insert(30);
s1.insert(20);
s1.insert(40);
//查找
set<int>::iterator pos = s1.find(30);
if (pos != s1.end())
{
cout << "找到了元素 ： " << *pos << endl;
}
else
{
cout << "未找到元素" << endl;
}
//统计
int num = s1.count(30);
cout << "num = " << num << endl;
}
int main()
{
test01();
return 0;
}
总结：
- 查找 — find （返回的是迭代器）
- 统计 — count （对于set，结果为0或者1）
3.2 multiset
3.2.1 multiset的介绍
multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
multiset底层结构为二叉搜索树(红黑树)。
注意：
multiset中再底层中存储的是<value, value>的键值对
mtltiset的插入接口中只需要插入即可
与set的区别是，multiset中的元素可以重复，set是中value是唯一的
使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
multiset中的元素不能修改
在multiset中找某个元素，时间复杂度为 O ( l o g 2 N ) O(log_2 N) O(log2N)
multiset的作用：可以对元素进行排序
注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。
3.2.2 multimap的使用
multimap中的接口可以参考map，功能都是类似的。
注意：
-
multimap中的key是可以重复的。
-
multimap中的元素默认将key按照小于来比较
-
multimap中没有重载operator[]操作(思考下为什么?)。
-
使用时与map包含的头文件相同：
示例：
#include <set>
//set和multiset区别
void test01()
{
set<int> s;
pair<set<int>::iterator, bool> ret = s.insert(10);
if (ret.second)
{
cout << "第一次插入成功!" << endl;
}
else
{
cout << "第一次插入失败!" << endl;
}
ret = s.insert(10);
if (ret.second)
{
cout << "第二次插入成功!" << endl;
}
else
{
cout << "第二次插入失败!" << endl;
}
//multiset
multiset<int> ms;
ms.insert(10);
ms.insert(10);
for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++)
{
cout << *it << " ";
}
cout << endl;
}
int main()
{
test01();
return 0;
}
总结：
- 如果不允许插入重复数据可以利用set
- 如果需要插入重复数据利用multiset
3.3 map
3.3.1 map的介绍
map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair<const key, T> value_type;
在内部，map中的元素总是按照键值key进行比较排序的。
map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。
3.3.2 map的使用
map的模板参数说明
- key: 键值对中key的类型
- T： 键值对中value的类型
- Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
- Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器
- 注意：在使用map时，需要包含头文件。
- map构造和赋值
函数原型：
构造：
map<T1, T2> mp;//map默认构造函数:map(const map &mp);//拷贝构造函数
赋值：
map& operator=(const map &mp);//重载等号操作符
#include <map>
void printMap(map<int,int>&m)
{
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
{
cout << "key = " << it->first << " value = " << it->second << endl;
}
cout << endl;
}
void test01()
{
map<int,int>m; //默认构造
m.insert(pair<int, int>(1, 10));
m.insert(pair<int, int>(2, 20));
m.insert(pair<int, int>(3, 30));
printMap(m);
map<int, int>m2(m); //拷贝构造
printMap(m2);
map<int, int>m3;
m3 = m2; //赋值
printMap(m3);
}
int main()
{
test01();
return 0;
}
总结：map中所有元素都是成对出现，插入数据时候要使用对组
- map大小和交换
- 统计map容器大小以及交换map容器
函数原型：
size();//返回容器中元素的数目empty();//判断容器是否为空swap(st);//交换两个集合容器
示例：
#include <map>
void printMap(map<int,int>&m)
{
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
{
cout << "key = " << it->first << " value = " << it->second << endl;
}
cout << endl;
}
void test01()
{
map<int, int>m;
m.insert(pair<int, int>(1, 10));
m.insert(pair<int, int>(2, 20));
m.insert(pair<int, int>(3, 30));
if (m.empty())
{
cout << "m为空" << endl;
}
else
{
cout << "m不为空" << endl;
cout << "m的大小为： " << m.size() << endl;
}
}
//交换
void test02()
{
map<int, int>m;
m.insert(pair<int, int>(1, 10));
m.insert(pair<int, int>(2, 20));
m.insert(pair<int, int>(3, 30));
map<int, int>m2;
m2.insert(pair<int, int>(4, 100));
m2.insert(pair<int, int>(5, 200));
m2.insert(pair<int, int>(6, 300));
cout << "交换前" << endl;
printMap(m);
printMap(m2);
cout << "交换后" << endl;
m.swap(m2);
printMap(m);
printMap(m2);
}
int main()
{
test01()
test02();
return 0;
}
总结：
- 统计大小 — size
- 判断是否为空 — empty
- 交换容器 — swap
-
map插入和删除
- map容器进行插入数据和删除数据
函数原型：
insert(elem);//在容器中插入元素。clear();//清除所有元素erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。erase(key);//删除容器中值为key的元素。
示例：
#include <map>
void printMap(map<int,int>&m)
{
for (map<int, int>::iterator it = m.begin(); it != m.end(); it++)
{
cout << "key = " << it->first << " value = " << it->second << endl;
}
cout << endl;
}
void test01()
{
//插入
map<int, int> m;
//第一种插入方式
m.insert(pair<int, int>(1, 10));
//第二种插入方式
m.insert(make_pair(2, 20));
//第三种插入方式
m.insert(map<int, int>::value_type(3, 30));
//第四种插入方式
m[4] = 40;
printMap(m);
//删除
m.erase(m.begin());
printMap(m);
m.erase(3);
printMap(m);
//清空
m.erase(m.begin(),m.end());
m.clear();
printMap(m);
}
int main()
{
test01();
return 0;
}
总结：
- map插入方式很多，make_pair()和[]比较常用
- 插入 — insert
- 删除 — erase
- 清空 — clear
-
map查找和统计
- 对map容器进行查找数据以及统计数据
函数原型：
find(key);//查找key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();count(key);//统计key的元素个数
示例：
#include <map>
//查找和统计
void test01()
{
map<int, int>m;
m.insert(pair<int, int>(1, 10));
m.insert(pair<int, int>(2, 20));
m.insert(pair<int, int>(3, 30));
//查找
map<int, int>::iterator pos = m.find(3);
if (pos != m.end())
{
cout << "找到了元素 key = " << (*pos).first << " value = " << (*pos).second << endl;
}
else
{
cout << "未找到元素" << endl;
}
//统计
int num = m.count(3);
cout << "num = " << num << endl;
}
int main()
{
test01();
return 0;
}
总结：
- 查找 — find （返回的是迭代器）
- 统计 — count （对于map，结果为0或者1）
-
map容器排序
-
map容器默认排序规则为 按照key值进行 从小到大排序，掌握如何改变排序规则
-
利用仿函数，可以改变排序规则
-
示例：
#include <map>
class MyCompare
{
public:
bool operator()(int v1, int v2)
{
return v1 > v2;
}
};
void test01()
{
//默认从小到大排序
//利用仿函数实现从大到小排序
map<int, int, MyCompare> m;
m.insert(make_pair(1, 10));
m.insert(make_pair(2, 20));
m.insert(make_pair(3, 30));
m.insert(make_pair(4, 40));
m.insert(make_pair(5, 50));
for (map<int, int, MyCompare>::iterator it = m.begin(); it != m.end(); it++)
{
cout << "key:" << it->first << " value:" << it->second << endl;
}
}
int main()
{
test01();
return 0;
}
总结：
- 利用仿函数可以指定map容器的排序规则
- 对于自定义数据类型，map必须要指定排序规则,同set容器
3.4 multimap
3.4.1 multimap的介绍
Multimaps是关联式容器，它按照特定的顺序，存储由key和value映射成的键值对<key,value>，其中多个键值对之间的key是可以重复的。
在multimap中，通常按照key排序和惟一地标识元素，而映射的value存储与key关联的内容。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对:typedef pair<const Key, T> value_type;
在内部，multimap中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序的。
multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。
multimap在底层用二叉搜索树(红黑树)来实现。
注意：multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的。
3.4.2 multimap的使用
multimap中的接口可以参考map，功能都是类似的。
注意：
multimap中的key是可以重复的。
multimap中的元素默认将key按照小于来比较
multimap中没有重载operator[]操作(思考下为什么?)。
使用时与map包含的头文件相同
4. 红黑树模拟实现STL中的map与set
传送门:快速过一遍红黑树
4.1 实现红黑树的迭代器
迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器，需要考虑以前问题
- begin()与end()
STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？
能否给成nullptr呢？答案是行不通的，因为对end()位置的迭代器进行–操作，必须要能找最后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置：
- operator++()与operator–()
Self operator++()
{
Node* cur = _node;
if (cur->_right)//如果存在右子树，则找右子树最左节点(本质就是右子树的最小节点)
{
cur = cur->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else//没有右子树，就找孩子是父亲左孩子的节点
{
Node* parent = cur->_parent;
while (parent != _header && parent->_left != cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self operator--()
{
if (_node == _header)//如果迭代器的位置是end,那么--之后就是最大值
{
Node* cur = _header->_parent;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else//正常节点的情况
{
Node* cur = _node;
if (cur->_left)//如果存在左子树，就找左子树的最右节点(本质就是左子树的最大节点)
{
cur = cur->_left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else//找孩子是父亲的右孩子节点
{
Node* parent = cur->_parent;
while (parent != _header && parent->_right != cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
}
return *this;
}
4.2 改造红黑树
在上一文章快速过一遍红黑树中,我们实现的黑红树并非是关联式,因为要实现map这样的容器,我们需要进行改造
大体框架如下:
// 因为关联式容器中存储的是<key, value>的键值对，因此
// k为key的类型，
// ValueType: 如果是map，则为pair<K, V>; 如果是set，则为k
// KeyOfValue: 通过value来获取key的一个仿函数类
template<class K, class ValueType, class KeyOfValue>
class RBTree
{
typedef RBTreeNode<ValueType> Node;
typedef Node* PNode;
public:
typedef RBTreeIterator<ValueType, ValueType*, ValueType&> iterator;
public:
RBTree();
~RBTree()
/
// Iterator
iterator Begin() { return iterator(_pHead->_pLeft); }
iterator End() { return iterator(_pHead); }
//
// Modify
pair<iterator, bool> Insert(const ValueType& data)
{
// 插入节点并进行调整
// 参考下面代码...
return make_pair(Iterator(pNewNode), true);
}
// 将红黑树中的节点清空
void Clear();
iterator Find(const K& key);
//
// capacity
size_t Size()const;
bool Empty()const;
// ……
private:
PNode _pHead;
size_t _size; // 红黑树中有效节点的个数
};
具体代码如下
#pragma once
#include <iostream>
#include <time.h>
#include <assert.h>
namespace hdm
{
enum Color
{
BLACK, //黑色
RED, //红色
};
template<class T>
struct RBTreeNode
{
T _data;
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Color _col;
RBTreeNode(const T& data=T())
:_data(data),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED)//默认给节点红色
{}
};
template<class T,class Ptr,class Ref>
class _RBTreeIterator
{
public:
typedef _RBTreeIterator<T, Ptr, Ref> Self;
typedef _RBTreeIterator<T, T*, T&> iterator;
typedef RBTreeNode<T> Node;
_RBTreeIterator(Node* node,Node* header):_node(node),_header(header){}
_RBTreeIterator(const iterator& it)
:_node(it._node),_header(it._header)
{}
Self operator++()
{
Node* cur = _node;
if (cur->_right)//如果存在右子树，则找右子树最左节点(本质就是右子树的最小节点)
{
cur = cur->_right;
while (cur->_left)
{
cur = cur->_left;
}
_node = cur;
}
else//没有右子树，就找孩子是父亲左孩子的节点
{
Node* parent = cur->_parent;
while (parent!=_header&&parent->_left != cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
return *this;
}
Self operator--()
{
if (_node == _header)//如果迭代器的位置是end,那么--之后就是最大值
{
Node* cur = _header->_parent;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else//正常节点的情况
{
Node* cur = _node;
if (cur->_left)//如果存在左子树，就找左子树的最右节点(本质就是左子树的最大节点)
{
cur = cur->_left;
while (cur->_right)
{
cur = cur->_right;
}
_node = cur;
}
else//找孩子是父亲的右孩子节点
{
Node* parent = cur->_parent;
while (parent != _header && parent->_right != cur)
{
cur = parent;
parent = cur->_parent;
}
_node = parent;
}
}
return *this;
}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator==(const Self& it) const
{
return _node == it._node;
}
bool operator!=(const Self& it)const
{
return _node != it._node;
}
//private:
Node* _node;
Node* _header;
};
template<class K,class T,class KeyOfT>
class RBTree
{
public:
typedef RBTreeNode<T> Node;
typedef _RBTreeIterator<T, T*, T&> iterator;
typedef _RBTreeIterator<T, const T*, const T&> const_iterator;
iterator begin()
{
Node* cur = _header->_parent;
while (cur->_left)
{
cur = cur->_left;
}
return iterator(cur, _header);
}
iterator end()
{
return iterator(_header, _header);
}
const_iterator begin()const
{
Node* cur = _header->_parent;
while (cur->_left)
{
cur = cur->_left;
}
return const_iterator(cur, _header);
}
const_iterator end()const
{
return const_iterator(_header, _header);
}
std::pair<iterator,bool> Insert(const T& data)
{
if (_header == nullptr)
{
_header = new Node();
Node* root = new Node(data);
root->_parent = _header;
_header->_parent = root;
_header->_left = _header->_right = root;
_header->_col = BLACK;
++_size;
return std::make_pair(iterator(_header->_parent, _header), true);
}
Node* cur = _header->_parent;
Node* parent = cur;//记录cur的父亲
while (cur)
{
if (KeyOfT()(cur->_data) > KeyOfT()(data))
{
parent = cur;
cur = cur->_left;
}
else if (KeyOfT()(cur->_data) < KeyOfT()(data))
{
parent = cur;
cur = cur->_right;
}
else
{
return std::make_pair(iterator(cur, _header),false);//不允许插入重复节点
}
}
//判断kv和parent的关系，确定kv的位置
cur = new Node(data);
Node* newnode = cur;
if (KeyOfT()(parent->_data) > KeyOfT()(data))
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
cur->_parent = parent;
//判断是否符合黑红树规则
while (parent!=_header && parent->_col == RED)
{
//三种情况
//1.叔叔节点存在而且为空
//2.叔叔节点不存在或者存在且为黑，插入节点与parent同侧
//3.叔叔节点不存在或者存在且为黑，插入节点与parent不同侧
//注意分左右侧，细分一共6种
Node* grandparent = parent->_parent;
if (grandparent->_left == parent)//在左子树处理
{
//叔叔节点位置在parent另一侧
Node* uncle = grandparent->_right;
if (uncle && uncle->_col == RED)//情况一：叔叔节点存在而且为红
{
//直接变色处理:parent和uncle变黑，grandparent变红
parent->_col = uncle->_col = BLACK;
grandparent->_col = RED;
//这种改grandparent的情况要继续往上处理
cur = grandparent;
parent = cur->_parent;
}
else//这种情况就是uncle不是红色或者不存在
{
//分两种情况：
//1.parent和cur同侧
//2.parent和cur不同侧
if (parent->_left == cur)//同侧的情况
{
//对grandparent右单旋+变色
RotateR(grandparent);
parent->_col = BLACK;
grandparent->_col = RED;
}
else//不同侧的情况
{
//左右旋+变色
//对parent左单旋，再对grandparent右单旋
RotateL(parent);
RotateR(grandparent);
cur->_col = BLACK;
grandparent->_col = RED;
}
break;//这种情况替换了grandparent但是原来黑的位置不变，不会影响其他
}
}
else//在右子树处理--跟上面相反
{
Node* uncle = grandparent->_left;
if (uncle&& uncle->_col == RED)
{
//变色处理
grandparent->_col = RED;
parent->_col = uncle->_col = BLACK;
//向上处理
cur = grandparent;
parent = cur->_parent;
}
else
{
if (parent->_right == cur)//同侧
{
//左单旋+变色
RotateL(grandparent);
grandparent->_col = RED;
parent->_col = BLACK;
}
else//不同侧
{
//右左旋+变色
//对parent右单旋+对grandparent左单旋+变色
RotateR(parent);
RotateL(grandparent);
grandparent->_col = RED;
cur->_col = BLACK;
}
break;
}
}
}//while end
_header->_parent->_col = BLACK;//保证根节点是黑色
update_header();//更新虚拟头节点的孩子指向
++_size;
return std::make_pair(iterator(newnode, _header),true);
}//Insert end
size_t size()const
{
return _size;
}
iterator Find(const K& x)
{
Node* cur = _header->_parent;
while (cur)
{
if (KeyOfT()(cur->_data) > KeyOfT()(x))
{
cur = cur->_left;
}
else if (KeyOfT()(cur->_data) < KeyOfT()(x))
{
cur = cur->_right;
}
else
{
return iterator(cur,_header);
}
}
return iterator(cur, _header);
}
void InorderTree()
{
InorderTree(_header->_parent);
}
bool IsValidRBTree()
{
if (_header->_parent == nullptr)//空树也是红黑树
return true;
if (_header->_parent->_col != BLACK)
{
std::cout << "违反了红黑树性质二：根节点必须为黑色" << std::endl;
return false;
}
//获取任意一个节点的黑色节点
size_t blackCount = 0;
Node* cur = _header->_parent;
while (cur)
{
if (cur->_col == BLACK)
blackCount++;
cur = cur->_left;
}
// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数
size_t k = 0;
return IsValidRBTree(_header->_parent, blackCount, k);
}
void clear()
{
Node* cur = _header->_parent;
clear(cur);
_size = 0;
delete _header;
}
bool empty()
{
return _size == 0;
}
private:
void clear(Node* root)
{
if (root == nullptr)
return;
clear(root->_left);
clear(root->_right);
//--_size;
delete root;
}
void update_header()//创建虚拟头节点与_root连接or更新虚拟头节点的指向
{
Node* root = _header->_parent;
//找最小节点
Node* left_min = root;
while (left_min->_left)
{
left_min = left_min->_left;
}
//找最大节点
Node* right_max = root;
while (right_max->_right)
{
right_max = right_max->_right;
}
//hander的左孩子连接最小节点,右孩子连最大节点
_header->_left = left_min;
_header->_right = right_max;
}
void InorderTree(Node* root)
{
if (root == nullptr)
return;
InorderTree(root->_left);
std::cout << root->_kv.first<<":"<<root->_kv.second << " ";
InorderTree(root->_right);
}
void RotateL(Node* parent)//左单旋
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* pparent = parent->_parent;
//连接
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
subR->_parent = pparent;
if (pparent == _header)
{
//那么subR就是新的根节点
_header->_parent = subR;
}
else
{
//判断subR在pparent的那一侧
if (KeyOfT()(pparent->_data) > KeyOfT()(subR->_data) )
{
pparent->_left = subR;
}
else
{
pparent->_right = subR;
}
}
}
void RotateR(Node* parent)//右单旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* pparent = parent->_parent;
//连接
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
parent->_parent = subL;
subL->_right = parent;
subL->_parent = pparent;
if (pparent == _header)
{
_header->_parent = subL;
}
else
{
//判断位于那一侧
if (KeyOfT()(pparent->_data) > KeyOfT()(subL->_data))
{
pparent->_left = subL;
}
else
{
pparent->_right = subL;
}
}
}
bool IsValidRBTree(Node* root, size_t blackCount, size_t k)
{
//走到null之后，判断k和black是否相等
if (root == nullptr)
{
if (k != blackCount)
{
std::cout << "违反性质四：每条路径中黑色节点的个数必须相同" << std::endl;
return false;
}
return true;
}
// 统计黑色节点的个数
if (root->_col == BLACK)
k++;
// 检测当前节点与其双亲是否都为红色
Node* parent = root->_parent;
if (parent && parent->_col == RED && root->_col == RED)
{
std::cout << "违反性质三：不能存在连在一起的红色节点" << std::endl;
return false;
}
return IsValidRBTree(root->_left, blackCount, k) &&
IsValidRBTree(root->_right, blackCount, k);
}
private:
Node* _header = nullptr;//哨兵位头节点
size_t _size = 0;// 红黑树中有效节点的个数
};
}
4.3 set的模拟实现
set的底层为红黑树，因此只需在set内部封装一棵红黑树，即可将该容器实现出来
#pragma once
#include "RBTree.h"
#include <iostream>
using namespace std;
namespace hdm
{
template<class K>
class KeyofK
{
public:
const K& operator()(const K& key)
{
return key;
}
};
template<class K>
class set
{
public:
typedef typename hdm::RBTree<K,K,KeyofK<K>>::const_iterator iterator;
typedef typename hdm::RBTree<K, K, KeyofK<K>>::const_iterator const_iterator;
std::pair<iterator,bool> insert(const K& key)
{
return _t.Insert(key);
}
iterator begin()const
{
return _t.begin();
}
iterator end()const
{
return _t.end();
}
bool empty()
{
return _t.empty();
}
size_t size()
{
return _t.size();
}
private:
hdm::RBTree<K, K, KeyofK<K>> _t;
};
void test_set()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
set<int> s;
for (auto e : a)
{
s.insert(e);
}
set<int>::iterator it = s.begin();
while (it != s.end())
{
//(*it)++;
//++(*it);
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
}
}
4.4 map的模拟实现
map的底层结构就是红黑树，因此也是在map中直接封装一棵红黑树，然后将其接口包装下即可
#pragma once
#include "RBTree.h"
namespace hdm
{
template<class K,class V>
class keyofV
{
public:
const K& operator()(const std::pair<K, V>& kv)
{
return kv.first;
}
};
template<class K,class V>
class map
{
public:
typedef typename hdm::RBTree<K,std::pair<const K, V>, keyofV<K, V>>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
std::pair<iterator, bool> insert(const std::pair<K, V>& kv)
{
return _t.Insert(kv);
}
V& operator[](const K& key)
{
std::pair<iterator, bool> ret = _t.Insert(std::make_pair(key, V()));
return ret.first->second;
}
size_t size()
{
return _t.size();
}
void clear()
{
_t.clear();
}
bool empty()
{
return _t.empty();
}
private:
hdm::RBTree<K,std::pair<const K, V>, keyofV<K,V>> _t;
};
//测试代码
void test_map()
{
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
map<int, int> m;
for (auto e : a)
{
if(e == 14)
int i = 14;
m.insert(std::make_pair(e, e));
}
//for (auto& e : m)
//{
// cout << e.first << ":" << e.second << endl;
//}
auto it = m.begin();
while (it != m.end())
{
std::cout << it->first << ":" << it->second << std::endl;
++it;
}
it = m.end();
while (it != m.begin())
{
--it;
std::cout << it->first << ":" << it->second << std::endl;
}
cout << "总数" << m.size() << endl;
cout << "empty:" << m.empty() << endl;
m.clear();
cout << "clear().." << endl;
cout << "empty:" << m.empty() << endl;
cout << "总数" << m.size() << endl;
}
void TestMap()
{
//统计水果出现的次数
std::string arr[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };
map<string, int> mapcount;
for (auto& e : arr)
{
mapcount[e]++;
}
for (auto& e : mapcount)
{
cout << e.first << ":" << e.second << endl;
}
}
}//namespace end
风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。
站长推荐
- SpringSecurity实现前后端分离认证授权
SpringSecurity实现前后端分离认证授权 - stm32使用HAL库配置串口中断收发数据（保姆级教程）
stm32使用HAL库配置串口中断收发数据（保姆级教程） - U8W/U8W-Mini使用与常见问题解决
U8W/U8W-Mini使用与常见问题解决 - 【社区图书馆】伴我前行的一本书《The C Programming Language》
【社区图书馆】伴我前行的一本书《The C Programming Language》 - Unity创建文本时自动修改默认字体
Unity创建文本时自动修改默认字体