当前位置：首页 > news >正文

C/C++ 进阶（7）模拟实现map/set

news 来源：原创 2024/9/20 5:05:38

个人主页：仍有未知等待探索-CSDN博客

专题分栏：C++

一、简介

map和set都是关联性容器，底层都是用红黑树写的。

特点：存的Key值都是唯一的，不重复。

map存的是键值对（Key—Value）。

set存的是键值（Key）。

二、map/set的模拟实现

map.h

#pragma once#include <iostream>
#include "RBTree.h"
using namespace std;template<class Key, class Value>
class map
{struct MapKeyOfT{const Key& operator()(const pair<Key, Value>& e){return e.first;}};public:typedef pair<Key, Value> PKV;typedef _RBTree_iterator<PKV, PKV*, PKV&> iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const pair<Key, Value>& e){return _t.insert(e);}void inorder(){_t.inorder();}
private:RBTree<Key, pair<Key, Value>, MapKeyOfT> _t;
};

set.h

#pragma once#include "RBTree.h"template<class Key>
class set
{struct SetKeyOfT{const Key& operator()(const Key& e){return e;}};
public :typedef _RBTree_iterator<Key, Key*, Key&> iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const Key& e){return _t.insert(e);}void inorder(){_t.inorder();}
private:RBTree<Key, Key, SetKeyOfT> _t;
};

RBTree.h

#pragma once#include<iostream>
using namespace std;enum color
{Red,Black
};
template <class ValueTpye>
struct RBTreeNode
{RBTreeNode(const ValueTpye& e = ValueTpye()):_left(nullptr),_right(nullptr),_parent(nullptr),_col(Red),_val(e){}struct RBTreeNode<ValueTpye>* _left;struct RBTreeNode<ValueTpye>* _right;struct RBTreeNode<ValueTpye>* _parent;int _col;ValueTpye _val;
};template<class ValueType, class Ptr, class Ref>
class _RBTree_iterator
{typedef RBTreeNode<ValueType> node;typedef _RBTree_iterator<ValueType, Ptr, Ref> iterator;
public:_RBTree_iterator(node* e):_node(e){}Ptr operator->(){return &_node->_val;}Ref operator*(){return _node->_val;}bool operator!=(iterator it){return _node != it._node;}iterator& operator++(){if (_node->_right){node* left = _node->_right;while (left->_left){left = left->_left;}_node = left;}else{node* cur = _node;node* p = cur->_parent;while (p && cur == p->_right){cur = p;p = p->_parent;}_node = p;}return *this;}
private:node* _node;
};template <class Key, class ValueType, class KeyOfT>
class RBTree
{
public:typedef RBTreeNode<ValueType> node;typedef _RBTree_iterator<ValueType, ValueType*, ValueType&> iterator;KeyOfT kot;RBTree():_root(nullptr){}iterator begin(){node* cur = _root;while (cur && cur->_left){cur = cur->_left;}return iterator(cur);}iterator end(){return iterator(nullptr);}node* find(const Key& e){node* cur = _root;while (cur){if (kot(cur->_val).first > e){cur = cur->_left;}else if (kot(cur->_val).first < e){cur = cur->_right;}else{return cur;}}return nullptr;}bool insert(const ValueType& e){// 根据二叉搜索树插入的方式进行插入node* cur = _root;node* parent = cur;while (cur){parent = cur;if (kot(cur->_val) > kot(e)){cur = cur->_left;}else if (kot(cur->_val) < kot(e)){cur = cur->_right;}else{return false;}}cur = new node(e);if (parent == nullptr){_root = cur;}else{if (kot(parent->_val) > kot(cur->_val)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;}// 更新，对于不同的情况，进行不同的调整// parent 为黑、不存在，结束node* p = parent;while (p && p->_col == Red){node* g = p->_parent;if (g->_left == p){node* u = g->_right;// 叔叔存在且为红if (u && u->_col == Red){p->_col = u->_col = Black;g->_col = Red;// 继续往上处理cur = g;p = cur->_parent;}// 叔叔不存在且为黑else {//    g//  p   u// cif (cur == p->_left){// 右单旋RotateR(g);// 变色g->_col = Red;p->_col = Black;}//    g//  p   u//    celse {// 左右双旋RotateL(p);RotateR(g);// 变色cur->_col = Black;g->_col = Red;}// 叔叔不存在或者存在且为黑调整完，就不需要继续进行调整了break;}}else{node* u = g->_left;if (u && u->_col == Red){p->_col = u->_col = Black;g->_col = Red;// 继续往上处理cur = g;p = cur->_parent;}else {//    g//  u   p//        cif (cur == p->_right){// 左单旋RotateL(g);// 变色g->_col = Red;p->_col = Black;}//    g//  u   p//    celse {// 左右双旋RotateR(p);RotateL(g);// 变色cur->_col = Black;g->_col = Red;}// 叔叔不存在或者存在且为黑调整完，就不需要继续进行调整了break;}}}_root->_col = Black;return true;}void inorder(){_inorder(_root);}
private:void _inorder(node* root){if (root == nullptr) return;_inorder(root->_left);cout << kot(root->_val) << " ";_inorder(root->_right);}void RotateR(node* parent){node* subl = parent->_left;node* sublr = subl->_right;node* grandfather = parent->_parent;parent->_left = sublr;if (sublr){sublr->_parent = parent;}subl->_right = parent;parent->_parent = subl;subl ->_parent = grandfather;if (_root == parent){if (grandfather->_left == parent){grandfather->_left = subl;}else{grandfather->_right = subl;}}else{_root = subl;}}void RotateL(node* parent){node* subr = parent->_right;node* subrl = subr->_left;node* grandfather = parent->_parent;parent->_right = subrl;if (subrl){subrl->_parent = parent;}subr->_left = parent;parent->_parent = subr;subr ->_parent = grandfather;if (_root != parent){if (grandfather->_left == parent){grandfather->_left = subr;}else{grandfather->_right = subr;}}else{_root = subr;}}private:node* _root;
};

main.cpp（测试）

#define _CRT_SECURE_NO_WARNINGS 1#include "map.h"
#include "set.h"
//#include <map>
//#include <set>
#include <iostream>
using namespace std;void test1()
{int a[] = {5, 3, 7, 3, 7, 8, 4, 2, 9, 10};map<int, int> m;for (int e : a){m.insert(make_pair(e, e));}m.inorder();
}void test2()
{int a[] = {5, 3, 7, 3, 7, 8, 4, 2, 9, 10};set<int> s;for (int e : a){s.insert(e);}s.inorder();
}void test3()
{int a[] = {5, 3, 7, 3, 7, 8, 4, 2, 9, 10};set<int> s;for (int e : a){s.insert(e);}auto it = s.begin();while (it != s.end()){cout << *it << endl;++ it;}
}void test4()
{pair<int, int> a[] = {{5, 5}, {3, 3}, {7, 7}, {3, 3}, {7, 7}, {8, 8}, {4, 4}, {2, 2}, {9, 9}, {10, 10}};set<pair<int, int>> s;for (auto e : a){s.insert(e);}auto it = s.begin();while (it != s.end()){cout << (*it).first << " " << (*it).second << endl;++ it;}
}
int main()
{test1();return 0;
}