阅读量:2
个人主页：仍有未知等待探索-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 // c if (cur == p->_left) { // 右单旋 RotateR(g); // 变色 g->_col = Red; p->_col = Black; } // g // p u // c else { // 左右双旋 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 // c if (cur == p->_right) { // 左单旋 RotateL(g); // 变色 g->_col = Red; p->_col = Black; } // g // u p // c else { // 左右双旋 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; } 