C++中map和set封裝實(shí)現(xiàn)示例
更新時(shí)間：2023年02月06日 10:09:31 作者：頭發(fā)沒(méi)有代碼多
我們知道,map與set所使用的都是紅黑樹(shù),下面這篇文章主要給大家介紹了關(guān)于C++中map和set封裝實(shí)現(xiàn)的相關(guān)資料,文中通過(guò)圖文以及實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
mao和set模擬實(shí)現(xiàn)
STL map和set只是包含了幾個(gè)頭文件
主要在選中的這個(gè)文件里，打開(kāi)之后我們可以看到紅黑樹(shù)
用紅黑樹(shù)實(shí)現(xiàn)map和set
set的主要實(shí)現(xiàn)
set里面的value type和key type都是KEY
map里面的value type是pair，key type是KEY
這里用一顆泛型結(jié)構(gòu)的RBTree，通過(guò)不同的實(shí)例化參數(shù)，實(shí)現(xiàn)出了map和set。
模擬實(shí)現(xiàn)
這里不用說(shuō)明紅黑樹(shù)是K還是KV，用T來(lái)決定紅黑樹(shù)，使用時(shí)T是什么，紅黑樹(shù)就是什么
如Map傳的是pair，T就是pair，Set傳的是K，T就是K
T傳給了節(jié)點(diǎn)里面的data，上面?zhèn)鲄鱇的原因是find函數(shù)要用到，find是通過(guò)K去進(jìn)行查找。
Insert插入數(shù)據(jù)的時(shí)候要比較數(shù)據(jù)的大小選擇合適的位置插入，但這里data是T類(lèi)型，對(duì)于set可直接比較，而map傳過(guò)來(lái)的是pair，如果比較pair就要比較first和second，這種不滿(mǎn)足我們的需求，因?yàn)楸容^的時(shí)候既要滿(mǎn)足set也要滿(mǎn)足Map.
我們用仿函數(shù)來(lái)滿(mǎn)足這種要求，這里仿函數(shù)是把T里面的k取出來(lái)，pair的K就是first
取K的仿函數(shù)
對(duì)于set而言，直接返回就行
對(duì)于map而言，就要取first
之后修改rbtree.h，創(chuàng)建一個(gè)仿函數(shù)對(duì)象，這個(gè)對(duì)象是什么類(lèi)型的就根據(jù)什么類(lèi)型取比較即可
Insert
對(duì)于Map而言，_t是RBTree類(lèi)型，Map的insert只需調(diào)用紅黑樹(shù)的Insert即可
set也一樣
迭代器
迭代器也依靠紅黑樹(shù)的迭代器實(shí)現(xiàn)，tyoename作用，告訴編譯器是要把類(lèi)型進(jìn)行重命名
以下是紅黑樹(shù)的迭代器
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)
{}
};
template<class T, class Ref, class Ptr>
struct __RBTreeIterator//迭代器
{
typedef RBTreeNode<T> Node;
typedef __RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
__RBTreeIterator(Node* node)//構(gòu)造
:_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;
}
}；
begin和end
template<class K, class T, class KeyOfT>
struct RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __RBTreeIterator<T, T&, T*> iterator;
iterator begin()
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
}；begin是找最左邊的節(jié)點(diǎn)，這里的_root是紅黑樹(shù)的根節(jié)點(diǎn)，end是最后一個(gè)節(jié)點(diǎn)的下一個(gè)位置就是空。
++和--
這里++和--是按照中序進(jìn)行的
這里訪問(wèn)順序是左根右
1.如果右子樹(shù)不為空，++就是找右子樹(shù)中序的第一個(gè)（最左節(jié)點(diǎn)）
2.右子樹(shù)是空，++找孩子不是父親右的那個(gè)父親
第二句話(huà)理解，這里7訪問(wèn)完，父親是6，7是6右子樹(shù)，更新cur，parent，8是parent，6是cur，cur不是parent右子樹(shù)。所以下一個(gè)節(jié)點(diǎn)是8
--是反向左子樹(shù)
右根左
1.如果左子樹(shù)不為空，我們就訪問(wèn)它的最右節(jié)點(diǎn)
2.如果為空，訪問(wèn)孩子不是父親的左的父親
Self& operator++()
{
if (_node->_right)
{
// 下一個(gè)就是右子樹(shù)的最左節(jié)點(diǎn)
Node* left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left;
}
else
{
// 找祖先里面孩子不是祖先的右的那個(gè)
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
if (_node->_left)
{
// 下一個(gè)是左子樹(shù)的最右節(jié)點(diǎn)
Node* right = _node->_left;
while (right->_right)
{
right = right->_right;
}
_node = right;
}
else
{
// 孩子不是父親的左的那個(gè)祖先
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_left)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}operator[]
[]的實(shí)現(xiàn)要改造一個(gè)迭代器
map和set的insert也做修改
只有map有[]，我們不需要在紅黑樹(shù)里面實(shí)現(xiàn)[]，單獨(dú)給map實(shí)現(xiàn)即可
ret.first是迭代器，->second是KV的value
Map中使用方括號(hào)訪問(wèn)鍵對(duì)應(yīng)的值map[key]時(shí)：
- 若該key存在，則訪問(wèn)取得value值；
- 若該key不存在，訪問(wèn)仍然成功，取得value對(duì)象默認(rèn)構(gòu)造的值。具體如下：
用 []訪問(wèn)，但key不存在時(shí)，C++會(huì)利用該key及默認(rèn)構(gòu)造的value，組成{key，value}對(duì)，插入到map中。
value為 string對(duì)象，則構(gòu)造空串；value為int對(duì)象，構(gòu)造為0。
范圍for也可以使用
完整代碼
set.h
#include"rbtree.h"
namespace myspace
{
template<class K>
class set
{
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
void test_set()
{
set<int> s;
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
s.insert(3);
s.insert(2);
s.insert(1);
s.insert(5);
s.insert(3);
s.insert(6);
s.insert(4);
s.insert(9);
s.insert(7);
it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
}map.h
#include"rbtree.h"
#pragma once
namespace myspace
{
template<class K, class V>
class map
{
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator;
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
pair<iterator, bool> insert(const pair<K, V>& kv)
{
return _t.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
return ret.first->second;
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
void test_map()
{
string arr[] = { "蘋(píng)果", "西瓜", "蘋(píng)果", "西瓜", "蘋(píng)果", "蘋(píng)果", "西瓜", "蘋(píng)果", "香蕉", "蘋(píng)果", "香蕉" };
map<string, int> countMap;
for (auto& str : arr)
{
// 1、str不在countMap中，插入pair(str, int()),然后在對(duì)返回次數(shù)++
// 2、str在countMap中，返回value(次數(shù))的引用，次數(shù)++;
countMap[str]++;
}
map<string, int>::iterator it = countMap.begin();
while (it != countMap.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
}
}rbtree.h
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)
{}
};
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) const
{
return _node != s._node;
}
bool operator==(const Self& s) const
{
return _node == s._node;
}
Self& operator++()
{
if (_node->_right)
{
// 下一個(gè)就是右子樹(shù)的最左節(jié)點(diǎn)
Node* left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left;
}
else
{
// 找祖先里面孩子不是祖先的右的那個(gè)
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_right)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self& operator--()
{
if (_node->_left)
{
// 下一個(gè)是左子樹(shù)的最右節(jié)點(diǎn)
Node* right = _node->_left;
while (right->_right)
{
right = right->_right;
}
_node = right;
}
else
{
// 孩子不是父親的左的那個(gè)祖先
Node* parent = _node->_parent;
Node* cur = _node;
while (parent && cur == parent->_left)
{
cur = cur->_parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
};
template<class K, class T, class KeyOfT>
struct RBTree
{
typedef RBTreeNode<T> Node;
public:
typedef __RBTreeIterator<T, T&, T*> iterator;
iterator begin()
{
Node* left = _root;
while (left && left->_left)
{
left = left->_left;
}
return iterator(left);
}
iterator end()
{
return iterator(nullptr);
}
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot;
if (_root == nullptr)
{
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}
Node* parent = nullptr;
Node* cur = _root;
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;
while (parent && parent->_col == RED)
{
Node* grandfater = parent->_parent;
assert(grandfater);
assert(grandfater->_col == BLACK);
// 關(guān)鍵看叔叔
if (parent == grandfater->_left)
{
Node* uncle = grandfater->_right;
// 情況一 : uncle存在且為紅，變色+繼續(xù)往上處理
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
// 繼續(xù)往上處理
cur = grandfater;
parent = cur->_parent;
}// 情況二+三：uncle不存在 + 存在且為黑
else
{
// 情況二：右單旋+變色
// g
// p u
// c
if (cur == parent->_left)
{
RotateR(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
else
{
// 情況三：左右單旋+變色
// g
// p u
// c
RotateL(parent);
RotateR(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
else // (parent == grandfater->_right)
{
Node* uncle = grandfater->_left;
// 情況一
if (uncle && uncle->_col == RED)
{
parent->_col = uncle->_col = BLACK;
grandfater->_col = RED;
// 繼續(xù)往上處理
cur = grandfater;
parent = cur->_parent;
}
else
{
// 情況二：左單旋+變色
// g
// u p
// c
if (cur == parent->_right)
{
RotateL(grandfater);
parent->_col = BLACK;
grandfater->_col = RED;
}
else
{
// 情況三：右左單旋+變色
// g
// u p
// c
RotateR(parent);
RotateL(grandfater);
cur->_col = BLACK;
grandfater->_col = RED;
}
break;
}
}
}
_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
bool IsBalance()
{
if (_root == nullptr)
{
return true;
}
if (_root->_col == RED)
{
cout << "根節(jié)點(diǎn)不是黑色" << endl;
return false;
}
// 黑色節(jié)點(diǎn)數(shù)量基準(zhǔn)值
int benchmark = 0;
/*Node* cur = _root;
while (cur)
{
if (cur->_col == BLACK)
++benchmark;
cur = cur->_left;
}*/
return PrevCheck(_root, 0, benchmark);
}
private:
bool PrevCheck(Node* root, int blackNum, int& benchmark)
{
if (root == nullptr)
{
//cout << blackNum << endl;
//return;
if (benchmark == 0)
{
benchmark = blackNum;
return true;
}
if (blackNum != benchmark)
{
cout << "某條黑色節(jié)點(diǎn)的數(shù)量不相等" << endl;
return false;
}
else
{
return true;
}
}
if (root->_col == BLACK)
{
++blackNum;
}
if (root->_col == RED && root->_parent->_col == RED)
{
cout << "存在連續(xù)的紅色節(jié)點(diǎn)" << endl;
return false;
}
return PrevCheck(root->_left, blackNum, benchmark)
&& PrevCheck(root->_right, blackNum, benchmark);
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subR;
}
else
{
ppNode->_right = subR;
}
subR->_parent = ppNode;
}
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
{
subLR->_parent = parent;
}
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (ppNode->_left == parent)
{
ppNode->_left = subL;
}
else
{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
private:
Node* _root = nullptr;
};總結(jié)
到此這篇關(guān)于C++中map和set封裝實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ map和set封裝內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
- C++用一棵紅黑樹(shù)同時(shí)封裝出set與map的實(shí)現(xiàn)代碼
- C++使用一棵紅黑樹(shù)同時(shí)封裝出map和set實(shí)例代碼
- C++ map與set封裝實(shí)現(xiàn)過(guò)程講解
- C++深入探究哈希表如何封裝出unordered_set和unordered_map
- c++容器list、vector、map、set區(qū)別與用法詳解
- C++ STL入門(mén)教程(7) multimap、multiset的使用
- C++中map和set的簡(jiǎn)介及使用詳解
- C++中set/multiset與map/multimap的使用詳解
- C++中map和set的使用詳細(xì)攻略
- C++中常見(jiàn)容器類(lèi)的使用方法詳解(vector/deque/map/set)
- C++實(shí)現(xiàn)map和set封裝詳解
相關(guān)文章
C語(yǔ)言中單鏈表(不帶頭結(jié)點(diǎn))基本操作的實(shí)現(xiàn)詳解
鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。本文主要和大家聊聊C語(yǔ)言中單鏈表(不帶頭結(jié)點(diǎn))的基本操作，感興趣的小伙伴可以了解一下2022-11-11
C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之單鏈表
單鏈表是一種鏈?zhǔn)酱嫒〉臄?shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。本文將為大家介紹C語(yǔ)言中單鏈表的基本概念與讀取數(shù)據(jù)元素，需要的可以參考一下2021-12-12
C++ 允許多個(gè)函數(shù)擁有相同的名字，只要它們的參數(shù)列表不同就可以，這就是函數(shù)的重載（Function Overloading），借助重載，一個(gè)函數(shù)名可以有多種用途2022-05-05
本文主要介紹 C語(yǔ)言指針變量運(yùn)算的知識(shí)，這里整理了詳細(xì)的知識(shí)點(diǎn)，并附示例代碼，有需要學(xué)習(xí)C語(yǔ)言指針的朋友可以參考下2016-08-08
C語(yǔ)言編程C++動(dòng)態(tài)內(nèi)存分配示例講解
這篇文章主要介紹了C語(yǔ)言編程C++動(dòng)態(tài)內(nèi)存分配示例講解，為什么存在動(dòng)態(tài)內(nèi)存分配？本文通過(guò)動(dòng)態(tài)內(nèi)存介紹及常見(jiàn)內(nèi)存錯(cuò)誤等示例來(lái)為大家講解2021-09-09
C語(yǔ)言實(shí)現(xiàn)倉(cāng)庫(kù)物資管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)倉(cāng)庫(kù)物資管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-12-12
這篇文章主要介紹了C++異步調(diào)用方法,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-05-05
C++指向類(lèi)成員函數(shù)的指針詳細(xì)解析
由于這幾天在開(kāi)發(fā)中要用到函數(shù)指針，所以就整理了一下關(guān)于函數(shù)指針的概念2013-08-08
這篇文章主要介紹了c++ 解析yaml文件的步驟，幫助大家更好的理解和使用c++，感興趣的朋友可以了解下2020-12-12
Qt C++實(shí)現(xiàn)錄屏錄音功能的示例詳解
實(shí)現(xiàn)一個(gè)錄屏+錄音的功能且需要快速開(kāi)發(fā)，Qt無(wú)疑是一個(gè)非常好的選擇。他有豐富的類(lèi)庫(kù)和接口可以很好的滿(mǎn)足開(kāi)發(fā)需求。本文就來(lái)和大家聊聊具體的實(shí)現(xiàn)方法吧2023-03-03