🌈个人主页：秦jh_-CSDN博客

🔥 系列专栏：https://blog.csdn.net/qinjh_/category_12575764.html?spm=1001.2014.3001.5482

​ 

目录

 key和pair

 迭代器

const迭代器

 完整代码

RBTree.h

Set.h

Map.h

前言

💬 hello! 各位铁子们大家好哇。

             今日更新了map和set封装的相关内容

🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

 key和pair

上图是源码中的主要部分代码，可以看到，map里面存的是key和pair，而set里面存的是key和key。 

上图是底层大概思路。根据传入的类型不同（key或者pair），变成相应的搜索模型。

我们插入的时候要进行比较，但是我们不知道插入的是K还是pair，所以不能直接用data。虽然pair支持比较，但是它的比较不符合我们的需要，所以不能用。

上图是解决思路，底层的RBTree不知道传入的是k还是pair，但是上层的map和set知道。所以在RBTree多传入一个模板参数KeyOfT，这样再在map和set中分别实现取出key的逻辑即可。

 迭代器

STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后， 可以得到一个有序的序列，因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位 置，end()放在最大节点(最右侧节点)的下一个位置。

底层实现好后，就可以封装到set和map上了，如下图 ：

set的迭代器不能修改，map的first不能修改，second可以修改。所以还需要改进，如下图：

const迭代器

上图是底层RBTree实现。 

上图是封装到set中。 

上图是封装到map中。

 完整代码

set和map的底层都是红黑树

RBTree.h

<code>#pragma once

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)

:_left(nullptr)

, _right(nullptr)

, _parent(nullptr)

, _data(data)

, _col(RED)

{}

};

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;

}

bool operator!=(const Self& s)

{

return _node != s._node;

}

Self& operator++()

{

if (_node->_right)//当右不为空

{

//下一个，右树的最左节点

Node* leftMin = _node->_right;

while (leftMin->_left)

{

leftMin = leftMin->_left;

}

_node = leftMin;

}

else

{

//下一个，孩子等于父亲左的那个祖先

Node* cur = _node;

Node* parent = cur->_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 __RBTreeIterator<T, T&, T*> Iterator;

typedef __RBTreeIterator<T, const T&, const T*> ConstIterator;

RBTree() = default; //强制生成构造函数

RBTree(const RBTree<K, T, KeyOfT>& t) //拷贝构造，防止浅拷贝

{

_root = Copy(t._root);

}

//t2=t1

RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)

{

swap(_root, t._root);

return *this;

}

~RBTree()

{

Destroy(_root);

_root = nullptr;

}

Iterator Begin()

{

Node* leftMin = _root;

while (leftMin && leftMin->_left)//如果树是空，就直接返回空&&找到最左节点

{

leftMin = leftMin->_left;

}

return Iterator(leftMin);

}

Iterator End()

{

return Iterator(nullptr);

}

ConstIterator Begin() const

{

Node* leftMin = _root;

while (leftMin && leftMin->_left)//如果树是空，就直接返回空&&找到最左节点

{

leftMin = leftMin->_left;

}

return ConstIterator(leftMin);

}

ConstIterator End() const

{

return ConstIterator(nullptr);

}

Iterator Find(const K& key)

{

KeyOfT kot;

Node* cur = _root;

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();

}

pair<Iterator,bool> Insert(const T& data)

{

if (_root == nullptr)

{

_root = new Node(data);

_root->_col = BLACK; //根节点默认黑色

return make_pair(Iterator(_root), true);

}

KeyOfT kot;

Node* cur = _root;

Node* parent = nullptr;

while (cur)

{

//K

//pair<K,V>

//kot对象，是用来取T类型的data对象中的key

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;

// 检测新节点插入后，红黑树的性质是否造到破坏

//父亲的颜色是黑色也结束

while (parent && parent->_col == RED)

{

//关键看叔叔

Node* grandfather = parent->_parent;

if (parent == grandfather->_left)

{

Node* uncle = grandfather->_right;

//如果叔叔存在也为红->变色即可

if (uncle && uncle->_col == RED)

{

parent->_col = uncle->_col = BLACK;

grandfather->_col = RED;

//继续往上处理

cur = grandfather;

parent = cur->_parent;

}

else //叔叔不存在，或者存在且为黑

{

if (cur == parent->_left)

{

// g

// p u

// c

//单旋

RotateR(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else

{

// g

// p u

// c

//双旋

RotateL(parent);

RotateR(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;

}

}

else

{

Node* uncle = grandfather->_left;

//如果叔叔存在也为红->变色即可

if (uncle && uncle->_col == RED)

{

parent->_col = uncle->_col = BLACK;

grandfather->_col = RED;

//继续往上处理

cur = grandfather;

parent = cur->_parent;

}

else //叔叔不存在，或者存在且为黑

{

// g

// u p

// c

if (cur == parent->_right)

{

RotateL(grandfather);

parent->_col = BLACK;

grandfather->_col = RED;

}

else

{

// g

// u p

// c

RotateR(parent);

RotateL(grandfather);

cur->_col = BLACK;

grandfather->_col = RED;

}

break;

}

}

}

//始终保持根为黑

_root->_col = BLACK;

return make_pair(Iterator(newnode), true);

}

void RotateR(Node* parent)

{

Node* subL = parent->_left;

Node* subLR = subL->_right;

parent->_left = subLR;

if (subLR) //节点可能为空

subLR->_parent = parent;

subL->_right = parent; //旧父节点变成subL的右节点

Node* ppNode = parent->_parent; //该不平衡节点可能不是根节点，所以要找到它的父节点

parent->_parent = subL;

if (parent == _root) //如果该节点是根节点

{

_root = subL;

_root->_parent = nullptr;

}

else //不平衡节点只是一棵子树

{

if (ppNode->_left == parent) //如果旧父节点等于爷爷节点的左节点，新父节点为爷爷节点的左节点

{

ppNode->_left = subL;

}

else

{

ppNode->_right = subL;

}

subL->_parent = ppNode;//新父节点指向爷爷节点。

}

}

void RotateL(Node* parent)

{

Node* subR = parent->_right;

Node* subRL = subR->_left;

parent->_right = subRL;

if (subRL)

subRL->_parent = parent;

subR->_left = parent;

Node* ppNode = parent->_parent;

parent->_parent = subR;

if (parent == _root)

{

_root = subR;

_root->_parent = nullptr;

}

else

{

if (ppNode->_right == parent)

{

ppNode->_right = subR;

}

else

{

ppNode->_left = subR;

}

subR->_parent = ppNode;

}

}

void InOrder()

{

_InOrder(_root);

cout << endl;

}

bool IsBalance()

{

if (_root->_col == RED)

{

return false;

}

int refNum = 0; //取其中一条路径作为参考值

Node* cur = _root;

while (cur)

{

if (cur->_col == BLACK)

{

++refNum;

}

cur = cur->_left;

}

return Check(_root,0,refNum);

}

private:

Node* Copy(Node* root)

{

if (root == nullptr)

return nullptr;

Node* newroot = new Node(root->_data);

newroot->_col = root->_col;

newroot->_left = Copy(root->_left);

if (newroot->_left)

newroot->_left->_parent = newroot;

newroot->_right = Copy(root->_right);

if (newroot->_right)

newroot->_right->_parent = newroot;

return newroot;

}

void Destroy(Node* root)

{

if (root == nullptr)

return;

Destroy(root->_left);

Destroy(root->_right);

delete root;

root = nullptr;

}

bool Check(Node* root,int blackNum,const int refNum)

{

if (root == nullptr)

{

//cout << blackNum << endl;

if (refNum != blackNum)

{

cout << "存在黑色节点数量不相等的路径" << endl;

returnfalse;

}

return true;

}

if (root->_col == RED && root->_parent->_col == RED)

{

cout << root->_kv.first << "存在连续的红色节点" << endl;

return false;

}

if (root->_col == BLACK)

{

blackNum++;

}

return Check(root->_left,blackNum,refNum)

&& Check(root->_right,blackNum, refNum);

}

void _InOrder(Node* root)

{

if (root == nullptr)

return;

_InOrder(root->_left);

cout << root->_kv.first << ":" << root->_kv.second << endl;

_InOrder(root->_right);

}

private:

Node* _root = nullptr;

size_t _size = 0;

};

Set.h

#pragma once

namespace qjh

{

template<class K>

class set

{

struct SetKeyOfT

{

const K& operator()(const K& key)

{

return key;

}

};

public:

//没有实例化的类模板typedef时要加typename，这样编译器就会在实例化后再找这个东西

typedef typename RBTree<K, const K, SetKeyOfT>::Iterator iterator;

typedef typename RBTree<K, const K, SetKeyOfT>::ConstIterator 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();

}

iterator find(const K& key)

{

return _t.Find(key);

}

pair<iterator,bool> insert(const K& key)

{

return_t.Insert(key);

}

private:

RBTree<K, const K, SetKeyOfT> _t; //set迭代器不能修改

};

void PrintSet(const set<int>& s)

{

for (auto e : s)

{

cout << e << endl;

}

}

void test_set()

{

set<int> s;

s.insert(4);

s.insert(2);

s.insert(5);

s.insert(15);

s.insert(7);

s.insert(1);

s.insert(5);

s.insert(7);

PrintSet(s);

set<int>::iterator it = s.begin();

while (it != s.end())

{

//*it += 5;

cout << *it << " ";

++it;

}

cout << endl;

for (auto e : s)

{

cout << e << " ";

}

cout << endl;

set<int> copy = s;

for (auto e : copy)

{

cout << e << " ";

}

cout << endl;

}

}

Map.h

#pragma once

namespace qjh

{

template<class K,class V>

class map

{

struct MapKeyOfT

{

const K& operator()(const pair<K, V>& kv)

{

return kv.first;

}

};

public:

//first不能修改，second可以修改

typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::Iterator iterator;

typedef typename RBTree<K, const pair<const K, V>, MapKeyOfT>::ConstIterator const_iterator;

const_iterator begin() const

{

return _t.Begin();

}

const_iterator end() const

{

return _t.End();

}

iterator begin()

{

return _t.Begin();

}

iterator end()

{

return _t.End();

}

iterator find(const K& key)

{

return _t.Find(key);

}

pair<iterator, bool> insert(const pair<K, V>& kv)

{

return_t.Insert(kv);

}

V& operator[](const K& key)

{

pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));

return ret.first->second;

}

private:

RBTree<K, pair<const K,V>, MapKeyOfT> _t; //first不能修改，second可以修改

};

void test_map1()

{

map<string,int> m;

m.insert({"苹果",1});

m.insert({ "香蕉",1 });

m.insert({ "梨",1 });

m.insert({ "苹果",3 });

map<string, int>::iterator it = m.begin();

while (it != m.end())

{

//it->first += 'x';

it->second += 1;

//cout << it.operator->()->first << ":" << it->second << endl;

cout << it->first << ":" << it->second << endl;

++it;

}

cout << endl;

}

void test_map2()

{

string arr[] = { "苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜",

"苹果","香蕉","苹果","香蕉","苹果","草莓","苹果","草莓" };

map<string, int> countmap;

for (auto& e : arr)

{

countmap[e]++;

}

for (auto& kv : countmap)

{

cout << kv.first << ":" << kv.second << endl;

}

cout << endl;

}

}