C++中map_set的封裝實(shí)現(xiàn)整體代碼
更新時間：2025年12月15日 09:12:43 作者：祁同偉.
這篇文章主要介紹了C++中map_set封裝實(shí)現(xiàn)的相關(guān)資料,包括源碼解析、仿函數(shù)的使用、迭代器的設(shè)計以及const迭代器的實(shí)現(xiàn),文中通過代碼介紹的非常詳細(xì),需要的朋友可以參考下
前言
以前理解的 set 是 key；map 是 key_value，似乎是 2 棵樹，但其實(shí)他倆用同一個類模板
一. 源碼剖析
set
#include <stl_tree.h> #include <stl_set.h> #include <stl_multiset.h>
set 和 map 是一層淺淺的封裝，核心都在樹里實(shí)現(xiàn)
stl_set.h
template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set {
public:
typedef Key key_type;
typedef Key value_type;
private:
typedef rb_tree<key_type, value_type, // <K, K>
identity<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing set
}stl_map.h
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
public:
typedef Key key_type;
typedef pair<const Key, T> value_type;
private:
typedef rb_tree<key_type, value_type, // <K, pair<K, V>>
select1st<value_type>, key_compare, Alloc> rep_type;
rep_type t; // red-black tree representing map
}stl_tree.h
struct __rb_tree_node_base
{
typedef __rb_tree_color_type color_type;
typedef __rb_tree_node_base* base_ptr;
color_type color;
base_ptr parent;
base_ptr left;
base_ptr right;
};
template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
typedef __rb_tree_node<Value>* link_type;
Value value_field;
};
template <class Key, class Value, class KeyOfValue, class Compare,
class Alloc = alloc>
class rb_tree {
protected:
typedef __rb_tree_node<Value> rb_tree_node;
public:
typedef Key key_type;
typedef Value value_type;
typedef rb_tree_node* link_type;
protected:
size_type node_count; // keeps track of size of tree
link_type header;
Compare key_compare;
}link_type 是節(jié)點(diǎn)的指針
樹的節(jié)點(diǎn)里存第二個模板參數(shù) Value ，這個不是真 value
對 map 而言，value_type 傳給 Value 的是 pair<K, V>（樹的節(jié)點(diǎn)存的是 pair<K, V>）
對 set 而言，value_type 傳給 Value 的是 K（樹的節(jié)點(diǎn)存的是 K）
用 Value 做 __rb_tree_node 的模板參數(shù)，決定了樹節(jié)點(diǎn) node 里面存什么
二. 逐步實(shí)現(xiàn)
1. 框架
MySet.h
#include "RBTree.h"
namespace qtw
{
template <class K>
class set
{
private:
RBTree<K, K> _t;
};
}MyMap.h
#include "RBTree.h"
namespace qtw
{
template <class K, class V>
class map
{
private:
RBTree<K, pair<K, V>> _t;
};
}RBTree.h
enum Colour { RED, BLACK };
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
T _data;
RBTreeNode(const T& data)
:_data(data)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{ }
};
template<class K, class T>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_data < data)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_data > data)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
// ......
}39 44 行不能用 data 直接比較。set 可以；map 不期望用 pair<>，期望用 pair.first 比較
庫里重載了 pair 的比較：first 小或 second 小，但不符合我們的需求
2. 仿函數(shù)取 Key
用仿函數(shù)可以解決，再認(rèn)識仿函數(shù)
在一. 源碼剖析可以看到 stl_tree.h 多了個模板參數(shù) KeyOfValue，取出 Value 中的 Key
MySet.h
#include "RBTree.h"
namespace qtw
{
template <class K>
class set
{
struct SetKeyOfT // 定義成內(nèi)部類，可以直接用模板參數(shù) K,V
{
const K& operator()(const K& key)
{
return key;
}
};
public:
bool insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}MyMap.h
#include "RBTree.h"
namespace qtw
{
template <class K, class V>
class map
{
struct MapKeyOfT // 定義成內(nèi)部類，可以直接用模板參數(shù) K,V
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
bool insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
}RBTree.h
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
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;
}
bool Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return true;
}
Node* cur = _root;
Node* parent = nullptr;
KeyOfT kot;
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 false;
}
}
cur = new Node(data);
//cur->_col = RED;
if (kot(parent->_data) < kot(data))
parent->_right = cur;
else
parent->_left = cur;
cur->_parent = parent;
//......
}仿函數(shù)對象調(diào) operator() 取出 T 中的 key
比較交給樹里實(shí)現(xiàn)，可以用仿函數(shù)控制，在一. 源碼剖析可以看到 stl_tree.h 第四個模板參數(shù) Compare
3. 迭代器
庫里增加了哨兵位的頭結(jié)點(diǎn)
root == header->parent
header == root->parent
stl_tree.h
iterator begin() { return leftmost(); }
link_type& leftmost() const { return (link_type&) header->left; }
iterator end() { return header; }我們用空代表 end
迭代器要實(shí)現(xiàn)這個：
it = s.begin()
while (it != s.end())
{
cout << *it << " ";
++it;
}搜索樹的迭代器要中序遍歷
++：左 根 右
1. 右不為空，訪問右子樹的最左節(jié)點(diǎn)（最小節(jié)點(diǎn)）
2. 右為空，下一個訪問的是 孩子是父親左的父親（是該節(jié)點(diǎn)的祖先）
--：右 根 左
1. 左不為空，訪問左子樹的最右節(jié)點(diǎn)（最大節(jié)點(diǎn)）
2. 左為空，下一個訪問的是 孩子是父親右的父親（是該節(jié)點(diǎn)的祖先）
RBTree.h
template<class T>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T> Self;
Node* _node;
__TreeIterator(Node* node)
:_node(node)
{ }
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
Self& operator--()
{
if (_node->_left)
{
// 訪問左子樹的最右節(jié)點(diǎn)
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//while (parent)
//{
// if (cur == parent->_right)
// {
// break; // 我是父親的右，下一個訪問父親(右 根 左)
// }
// else // 我是父親的左，找孩子是父親右的那一個
// {
// cur = parent;
// parent = parent->_parent;
// }
//}
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator++()
{
if (_node->_right)
{
// 訪問右子樹的最左節(jié)點(diǎn)
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//while (parent)
//{
// if (cur == parent->_left)
// {
// break; // 我是父親的左，下一個訪問父親(左 根 右)
// }
// else // 我是父親的右，找孩子是父親左的那一個
// {
// cur = parent;
// parent = parent->_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 __TreeIterator<T> iterator;
iterator begin()
{
Node* leftMin = _root;
while (leftMin && leftMin->_left) // 有可能空樹
{
leftMin = leftMin->_left;
}
return iterator(leftMin);
}
iterator end()
{
return iterator(nullptr);
}
Node* Find(const K& key)
// ...
}MySet.h
#include "RBTree.h"
namespace qtw
{
template <class K>
class set
{
struct SetKeyOfT // 定義成內(nèi)部類，可以直接用模板參數(shù) K,V
{
const K& operator()(const K& key)
{
return key;
}
};
public:
//typedef RBTree<K, K, SetKeyOfT>::iterator iterator; 錯
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
bool insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}第 16 行錯：RBTree<K, K, SetKeyOfT> 是類模板，沒被實(shí)例化時不生成具體代碼，設(shè)計沒有實(shí)例化的具體參數(shù)，編譯器不敢從類模板里找 iterator；而且內(nèi)嵌類型、靜態(tài)也可以用這個語法
加上 typename 是告訴編譯器這里是類型，等實(shí)例化以后再找 iterator
MyMap.h
#include "RBTree.h"
namespace qtw
{
template <class K, class V>
class map
{
struct MapKeyOfT // 定義成內(nèi)部類，可以直接用模板參數(shù) K,V
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
//typedef RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; 錯
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
bool insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
}Test.cpp
#include"MyMap.h"
#include"MySet.h"
int main()
{
qtw::map<int, int> m;
m.insert(make_pair(1, 1));
m.insert(make_pair(3, 3));
m.insert(make_pair(2, 2));
qtw::map<int, int>::iterator mit = m.begin();
while (mit != m.end())
{
//cout << *mit << " "; 錯
//調(diào)operator*,返回T類型的_data,是pair,pair不支持流插入
//迭代器模擬自定義類型指針，用operator->
cout << mit->first << ":" << mit->second << endl;
++mit;
}
cout << endl;
for (const auto& kv : m)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
qtw::set<int> s;
s.insert(5);
s.insert(2);
s.insert(2);
s.insert(12);
s.insert(22);
s.insert(332);
s.insert(7);
qtw::set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
for (const auto& e : s)
{
cout << e << " ";
}
cout << endl;
return 0;
}還有問題：set 本不允許修改；map 僅允許 V 修改；重載 operator[ ] 要改 insert 的返回值
4. const 迭代器
先把樹的 const 迭代器搞好，才能搞 set_map 的 const 迭代器
RBTree.h
template<class T, class Ptr, class Ref>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T, Ptr, Ref> Self;
Node* _node;
__TreeIterator(Node* node)
:_node(node)
{ }
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
Self& operator--()
{
if (_node->_left)
{
// 訪問左子樹的最右節(jié)點(diǎn)
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//while (parent)
//{
// if (cur == parent->_right)
// {
// break; // 我是父親的右，下一個訪問父親(右 根 左)
// }
// else // 我是父親的左，找孩子是父親右的那一個
// {
// cur = parent;
// parent = parent->_parent;
// }
//}
while (parent && cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator++()
{
if (_node->_right)
{
// 訪問右子樹的最左節(jié)點(diǎn)
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//while (parent)
//{
// if (cur == parent->_left)
// {
// break; // 我是父親的左，下一個訪問父親(左 根 右)
// }
// else // 我是父親的右，找孩子是父親左的那一個
// {
// cur = parent;
// parent = parent->_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 __TreeIterator<T, T*, T&> iterator;
typedef __TreeIterator<T, const T*, const T&> const_iterator;
iterator begin()
{
Node* leftMin = _root;
while (leftMin && leftMin->_left) // 有可能空樹
{
leftMin = leftMin->_left;
}
return iterator(leftMin);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin() const
{
Node* leftMin = _root;
while (leftMin && leftMin->_left) // 有可能空樹
{
leftMin = leftMin->_left;
}
return const_iterator(leftMin);
}
const_iterator end() const
{
return const_iterator(nullptr);
}
Node* Find(const K& key)
// ......
}MySet.h
#include "RBTree.h"
namespace qtw
{
template <class K>
class set
{
struct SetKeyOfT // 定義成內(nèi)部類，可以直接用模板參數(shù) K,V
{
const K& operator()(const K& key)
{
return key;
}
};
public:
//typedef RBTree<K, K, SetKeyOfT>::iterator iterator; 錯
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin() const
{
return _t.begin();
}
iterator end() const
{
return _t.end();
}
bool insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}MyMap.h
#include "RBTree.h"
namespace qtw
{
template <class K, class V>
class map
{
struct MapKeyOfT // 定義成內(nèi)部類，可以直接用模板參數(shù) K,V
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
//typedef RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; 錯
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator 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();
}
bool insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}5. map 的 operator[ ]
RBTree.h
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __TreeIterator<T, T*, T&> iterator;
typedef __TreeIterator<T, const T*, const T&> const_iterator;
// ......
pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
Node* cur = _root;
Node* parent = nullptr;
KeyOfT kot;
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);
}
}
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;
// 如果cur是根、cur父親是黑：直接完事
// cur父親是紅：進(jìn)來
while (parent && parent->_col == RED)
{
// cur一定有爺，且爺為黑
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
// uncle存在，且為紅：變色，繼續(xù)更新
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else // uncle不存在，或存在且為黑
{
if (parent->_left == cur)
{
// g
// p
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
}
}
else // grandfather->_right == parent
{
Node* uncle = grandfather->_left;
// uncle存在，且為紅：變色，繼續(xù)更新
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else // uncle不存在，或存在且為黑
{
if (parent->_right == cur)
{
// g
// p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
}
}
}
_root->_col = BLACK; // 暴力處理
return make_pair(iterator(newnode), true);
}
};MyMap.h
V& operator[](const K& key) { }
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}MySet.h
報錯：“return”: 無法從“std::pair<__TreeIterator<T,T *,T &>,bool>”轉(zhuǎn)換為“std::pair<__TreeIterator<T,const T *,const T &>,bool>”
_t 是普通對象，調(diào) Insert 返回普通迭代器；但紅色的 iterator 是 const_iterator
看看庫里是怎么搞的
stl_set.h
第 2 行黃色的是普通迭代器，第 3 行綠色的是 const 迭代器
照貓畫虎
MySet.h
_t 是樹的普通對象，調(diào) Insert 返回樹的普通迭代器；但 set 是 const 迭代器，過不不去
單獨(dú)用普通的樹的迭代器對象接收，再用這個普通迭代器對象構(gòu)造 const 迭代器對象
因?yàn)?const 迭代器支持了一個構(gòu)造：18 行
stl_tree.h
第 11 行的 iterator：不管是普通/const 迭代器，這個 iterator 都是普通迭代器
當(dāng)這個類被實(shí)例化成 const 迭代器時，第 18 行的函數(shù)是一個構(gòu)造，支持普通迭代器構(gòu)造 const 迭代器
__rb_tree_iterator 是 const 迭代器，參數(shù)是 iterator 普通迭代器
當(dāng)這個類被實(shí)例化成普通迭代器時，第 18 行的函數(shù)是一個拷貝構(gòu)造
RBTree.h
template<class T, class Ptr, class Ref>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T, Ptr, Ref> Self;
typedef __TreeIterator<T, T*, T&> Iterator; // 一直是普通迭代器
Node* _node;
__TreeIterator(const Iterator& it)
:_node(it._node)
{ }
// ......
}MyMap.h
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}三. 整體代碼
RBTree.h
enum Colour { RED, BLACK };
template<class T>
struct RBTreeNode
{
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
Colour _col;
T _data;
RBTreeNode(const T& data)
:_data(data)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_col(RED)
{ }
};
template<class T, class Ptr, class Ref>
struct __TreeIterator
{
typedef RBTreeNode<T> Node;
typedef __TreeIterator<T, Ptr, Ref> Self;
typedef __TreeIterator<T, T*, T&> Iterator; // 一直是普通迭代器
Node* _node;
__TreeIterator(const Iterator& it)
:_node(it._node)
{ }
__TreeIterator(Node* node)
:_node(node)
{ }
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const Self& s) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
Self& operator--()
{
if (_node->_left)
{
// 訪問左子樹的最右節(jié)點(diǎn)
Node* subRight = _node->_left;
while (subRight->_right)
{
subRight = subRight->_right;
}
_node = subRight;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//while (parent)
//{
// if (cur == parent->_right)
// {
// break; // 我是父親的右，下一個訪問父親(右 根 左)
// }
// else // 我是父親的左，找孩子是父親右的那一個
// {
// cur = parent;
// parent = parent->_parent;
// }
//}
while (parent && cur == parent->_left)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator++()
{
if (_node->_right)
{
// 訪問右子樹的最左節(jié)點(diǎn)
Node* subLeft = _node->_right;
while (subLeft->_left)
{
subLeft = subLeft->_left;
}
_node = subLeft;
}
else
{
Node* cur = _node;
Node* parent = cur->_parent;
//while (parent)
//{
// if (cur == parent->_left)
// {
// break; // 我是父親的左，下一個訪問父親(左 根 右)
// }
// else // 我是父親的右，找孩子是父親左的那一個
// {
// cur = parent;
// parent = parent->_parent;
// }
//}
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __TreeIterator<T, T*, T&> iterator;
typedef __TreeIterator<T, const T*, const T&> const_iterator;
iterator begin()
{
Node* leftMin = _root;
while (leftMin && leftMin->_left) // 有可能空樹
{
leftMin = leftMin->_left;
}
return iterator(leftMin);
}
iterator end()
{
return iterator(nullptr);
}
const_iterator begin() const
{
Node* leftMin = _root;
while (leftMin && leftMin->_left) // 有可能空樹
{
leftMin = leftMin->_left;
}
return const_iterator(leftMin);
}
const_iterator end() const
{
return const_iterator(nullptr); // 我們用空代表end
}
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->_col = BLACK;
return make_pair(iterator(_root), true);
}
Node* cur = _root;
Node* parent = nullptr;
KeyOfT kot;
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);
}
}
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;
// 如果cur是根、cur父親是黑：直接完事
// cur父親是紅：進(jìn)來
while (parent && parent->_col == RED)
{
// cur一定有爺，且爺為黑
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{
Node* uncle = grandfather->_right;
// uncle存在，且為紅：變色，繼續(xù)更新
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else // uncle不存在，或存在且為黑
{
if (parent->_left == cur)
{
// g
// p
// c
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p
// c
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
}
}
else // grandfather->_right == parent
{
Node* uncle = grandfather->_left;
// uncle存在，且為紅：變色，繼續(xù)更新
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else // uncle不存在，或存在且為黑
{
if (parent->_right == cur)
{
// g
// p
// c
RotateL(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{
// g
// p
// c
RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}
}
}
}
_root->_col = BLACK; // 暴力處理
return make_pair(iterator(newnode), true);
}
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
Node* ppnode = parent->_parent;
// 2個核心步驟
parent->_right = curleft;
cur->_left = parent;
if (curleft) // 調(diào)整curleft父親節(jié)點(diǎn)的指向
{
curleft->_parent = parent;
}
parent->_parent = cur; //調(diào)整parent父親節(jié)點(diǎn)的指向
//cur->_parent = ppnode; 錯
//調(diào)整cur父親節(jié)點(diǎn)的指向
if (_root == parent)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
ppnode->_left = cur;
else
ppnode->_right = cur;
cur->_parent = ppnode;
}
}
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
Node* ppnode = parent->_parent;
// 2個核心步驟
parent->_left = curright;
cur->_right = parent;
parent->_parent = cur; // 調(diào)整parent父親節(jié)點(diǎn)的指向
if (curright) // 調(diào)整curright父親節(jié)點(diǎn)的指向
{
curright->_parent = parent;
}
//cur->_parent = ppnode; 錯
// 調(diào)整cur父親節(jié)點(diǎn)的指向
if (_root == parent)
{
_root = cur;
cur->_parent = nullptr;
}
else
{
if (ppnode->_right == parent)
ppnode->_right = cur;
else
ppnode->_left = cur;
cur->_parent = ppnode;
}
}
bool CheckColor(Node* root, int blacknum, int benchnark)
{
if (root == nullptr)
{
if (benchnark != blacknum)
return false;
return true;
}
if (root->_col == BLACK)
blacknum++;
if (root->_col == RED && root->_parent && root->_parent->_col == RED)
{
cout << root->_kv.first << "出現(xiàn)連續(xù)紅色節(jié)點(diǎn)" << endl;
return false;
}
return CheckColor(root->_left, blacknum, benchnark)
&& CheckColor(root->_right, blacknum, benchnark);
}
bool IsBalance()
{
return IsBalance(_root);
}
bool IsBalance(Node* root)
{
if (root == nullptr)
return true;
if (root->_col != BLACK)
return false;
// 基準(zhǔn)值
int benchnark = 0;
Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
++benchnark;
cur = cur->_left;
}
return CheckColor(root, 0, benchnark);
}
private:
Node* _root = nullptr;
};MySet.h
#include "RBTree.h"
namespace qtw
{
template <class K>
class set
{
struct SetKeyOfT // 定義成內(nèi)部類，可以直接用模板參數(shù) K,V
{
const K& operator()(const K& key)
{
return key;
}
};
public:
//typedef RBTree<K, K, SetKeyOfT>::iterator iterator; 錯
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
iterator begin() const
{
return _t.begin();
}
iterator end() const
{
return _t.end();
}
// iterator RBTree::const_iterator
pair<iterator, bool> insert(const K& key)
{
// pair<RBTree::iterator, bool>
pair<typename RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
return pair<iterator, bool>(ret.first, ret.second);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}MyMap.h
#include "RBTree.h"
namespace qtw
{
template <class K, class V>
class map
{
struct MapKeyOfT // 定義成內(nèi)部類，可以直接用模板參數(shù) K,V
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
//typedef RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; 錯
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator 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();
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
private:
RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};
}總結(jié)
到此這篇關(guān)于C++中map_set封裝實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++中map_set封裝內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
goto 語句是一種跳轉(zhuǎn)語句,它允許程序控制流程在代碼中跳轉(zhuǎn)到帶有標(biāo)簽的語句處,本文就來詳細(xì)的介紹一下C語言中g(shù)oto語句的方法使用,感興趣的可以了解一下2025-12-12
這篇文章主要介紹如何實(shí)現(xiàn)C++中的日期類相關(guān)資料,需要的朋友可以參考下面文章的具體內(nèi)容2021-09-09
本篇文章是對linux下遍歷目錄樹的方法進(jìn)行了詳細(xì)的總結(jié)與分析，需要的朋友參考下2013-05-05
這篇文章主要介紹了深入解析C++中派生類的構(gòu)造函數(shù),是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
這篇文章主要為大家詳細(xì)介紹了如何基于MFC實(shí)現(xiàn)多線程進(jìn)度條效果,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2025-01-01
這篇文章主要介紹了詳解如何將c語言文件打包成exe可執(zhí)行程序，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
QT中在QLabel顯示圖片并且利用鼠標(biāo)點(diǎn)擊畫線問題
這篇文章主要介紹了QT中在QLabel顯示圖片并且利用鼠標(biāo)點(diǎn)擊畫線問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
C/C++之字面量詳解(代碼中的固定值,用于表示各種數(shù)據(jù)類型的常量)
C++字面量是直接表示常量的固定值,涵蓋整型、浮點(diǎn)、字符、字符串、布爾、指針等類型,支持多進(jìn)制、后綴及轉(zhuǎn)義,用戶定義字面量（C++11+）提供自定義解析方式,類型推導(dǎo)自動確定類型以避免隱式轉(zhuǎn)換和溢出問題2025-09-09
本篇文章是對WTL中使用雙緩沖避免閃爍的解決方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要為大家詳細(xì)介紹了C++中動態(tài)內(nèi)存管理和泛型編程的相關(guān)資料，文中示例代碼講解詳細(xì)，對我們學(xué)習(xí)C++具有一定幫助，感興趣的小伙伴快跟隨小編一起學(xué)習(xí)一2022-10-10