C++ map的簡(jiǎn)單使用實(shí)現(xiàn)
map和set的底層都是通過(guò)紅黑樹來(lái)實(shí)現(xiàn)的，但并不是原生態(tài)的紅黑樹，而是經(jīng)過(guò)改造后的紅黑樹。且容器都會(huì)在各自的類中添加一些獨(dú)特的函數(shù)來(lái)解決各自適配的問(wèn)題
map和set底層是改造后的紅黑樹，我們先來(lái)看看改造后的紅黑樹
和普通的紅黑樹不同的是，在根節(jié)點(diǎn)上再加了一個(gè)頭結(jié)點(diǎn)，該結(jié)點(diǎn)不是真實(shí)的結(jié)點(diǎn)，只是一個(gè)輔助結(jié)點(diǎn)，是為了后面實(shí)現(xiàn)紅黑樹的迭代器而出現(xiàn)的。該header結(jié)點(diǎn)的父節(jié)點(diǎn)就是真實(shí)的根節(jié)點(diǎn)，其左孩子是這棵樹的最左結(jié)點(diǎn)，其右孩子是這棵樹的最右節(jié)點(diǎn)。
我們現(xiàn)在通過(guò)STL源碼來(lái)簡(jiǎn)單剖析一下map和set中如何利用紅黑樹來(lái)實(shí)現(xiàn)各自不同的功能的
在map中有兩個(gè)泛型參數(shù)，一個(gè)是Key，一個(gè)是T，也就是value。其中Key的別名是key_type，然后再將Key和T作為pair對(duì)象的一個(gè)泛型參數(shù)，將其的別名改為value_type。成員只有一棵樹，該樹就是紅黑樹，紅黑樹有兩個(gè)泛型參數(shù)，一個(gè)是Key，一個(gè)是Value。Key就是紅黑樹中結(jié)點(diǎn)的值的類型，Value就是結(jié)點(diǎn)Key對(duì)應(yīng)的Value值。結(jié)點(diǎn)中繼承了一個(gè)結(jié)點(diǎn)類，其就相當(dāng)有5個(gè)成員，顏色、父類指針、左孩子指針、右孩子指針、結(jié)點(diǎn)的值。
在set中只有一個(gè)泛型參數(shù)Key。在該容器中，由于使用紅黑樹底層必須提供兩個(gè)泛型參數(shù)，set就將vkey當(dāng)做value。此時(shí)傳過(guò)去的紅黑樹的泛型參數(shù)就是相同的，都是Key。
所以兩個(gè)容器的不同，起最關(guān)鍵的就是value類型不同，map容器底層中的紅黑樹的value是一個(gè)pair對(duì)象；而set容器中的的紅黑樹的value就是set中本身的key。在紅黑樹中做特殊處理，就可以獲得他們的value。
以下代碼就是對(duì)紅黑樹的一種改進(jìn)，適配于map和set關(guān)聯(lián)容器
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
enum COLOR
{
BLACK,
RED
};
template <class V>
struct RBTreeNode
{
RBTreeNode<V>* _parent; //父節(jié)點(diǎn)
RBTreeNode<V>* _left; //左孩子
RBTreeNode<V>* _right; //右孩子
V _val;
COLOR _color; //顏色
RBTreeNode(const V& val = V())
:_parent(nullptr)
, _left(nullptr)
, _right(nullptr)
, _val(val)
, _color(RED)
{}
};
template <class K, class V, class KeyOfValue>
class RBTree
{
public:
typedef RBTreeNode<V> Node;
RBTree()
:_header(new Node)
{
//創(chuàng)建空樹
_header->_left = _header->_right = _header;
}
bool insert(const V& val)
{
if (_header->_parent == nullptr)
{
Node* root = new Node(val);
_header->_parent = root;
root->_parent = _header;
_header->_left = _header->_right = root;
//根節(jié)點(diǎn)為黑色
root->_color = BLACK;
return true;
}
Node* cur = _header->_parent;
Node* parent = nullptr;
KeyOfValue kov;
//1.尋找到要插入的結(jié)點(diǎn)的位置
while (cur)
{
parent = cur;
if (kov(cur->_val) == kov(val))
return false;
else if (kov(cur->_val) > kov(val))
cur = cur->_left;
else
cur = cur->_right;
}
//2.創(chuàng)建節(jié)點(diǎn)
cur = new Node(val);
if (kov(parent->_val) > kov(cur->_val))
parent->_left = cur;
else
parent->_right = cur;
cur->_parent = parent;
//3.顏色的修改或者結(jié)構(gòu)的調(diào)整
while (cur != _header->_parent && cur->_parent->_color == RED)//不為根且存在連續(xù)紅色，則需要調(diào)整
{
parent = cur->_parent;
Node* gfather = parent->_parent;
if (gfather->_left == parent)
{
Node* uncle = gfather->_right;
//情況1.uncle存在且為紅
if (uncle && uncle->_color == RED)
{
parent->_color = uncle->_color = BLACK;
gfather->_color = RED;
//向上追溯
cur = gfather;
}
else
{
if (parent->_right == cur)//情況3
{
RotateL(parent);
swap(cur, parent);
}
//情況2.uncle不存在或者uncle為黑
RotateR(gfather);
parent->_color = BLACK;
gfather->_color = RED;
break;
}
}
else
{
Node* uncle = gfather->_left;
if (uncle && uncle->_color == RED)
{
parent->_color = uncle->_color = BLACK;
gfather->_color = RED;
//向上追溯
cur = gfather;
}
else
{
if (parent->_left == cur)
{
RotateR(parent);
swap(cur, parent);
}
RotateL(gfather);
parent->_color = BLACK;
gfather->_color = RED;
break;
}
}
}
//根節(jié)點(diǎn)為黑色
_header->_parent->_color = BLACK;
//更新頭結(jié)點(diǎn)的左右指向
_header->_left = leftMost();
_header->_right = rightMost();
return true;
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
if (parent == _header->_parent)
{
_header->_parent = subR;
parent->_parent = _header;
}
else
{
Node* gfather = parent->_parent;
if (gfather->_left == parent)
gfather->_left = subR;
else
gfather->_right = subR;
subR->_parent = gfather;
}
subR->_left = parent;
parent->_parent = subR;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
if (parent == _header->_parent)
{
_header->_parent = subL;
subL->_parent = _header;
}
else
{
Node* gfather = parent->_parent;
if (gfather->_left == parent)
gfather->_left = subL;
else
gfather->_right = subL;
subL->_parent = gfather;
}
subL->_right = parent;
parent->_parent = subL;
}
Node* leftMost()
{
Node* cur = _header->_parent;
while (cur && cur->_left)
{
cur = cur->_left;
}
return cur;
}
Node* rightMost()
{
Node* cur = _header->_parent;
while (cur && cur->_right)
{
cur = cur->_right;
}
return cur;
}
private:
Node* _header;
};
template<class K, class T>
class Map
{
struct MapKeyOfValue
{
const K& operator()(const pair<K, T>& val)
{
return val.first;
}
};
public:
bool insert(const pair<K, T>& kv)
{
return _rbt.insert(kv);
}
T& operator[](const K& key)
{
bool ret = _rbt.insert(make_pair(key, T()));
}
private:
typedef RBTree<K, pair<K, T>, MapKeyOfValue> rbt;
rbt _rbt;
};
template <class K>
class Set
{
struct SetKeyOfValue
{
const K& operator()(const K& val)
{
return val;
}
};
public:
bool insert(const K& val)
{
return _rbt.insert(val);
}
private:
typedef RBTree<K, K, SetKeyOfValue> rbt;
rbt _rbt;
};
迭代器
我們?cè)腘ode結(jié)點(diǎn)迭代器是無(wú)法實(shí)現(xiàn)迭代器的普通操作的，所以我們必須要對(duì)結(jié)點(diǎn)進(jìn)行另一層的封裝，重載對(duì)應(yīng)的操作運(yùn)算符。在該類中只有一個(gè)成員變量，就是Node結(jié)點(diǎn)。
對(duì)迭代器的解引用，就是獲得迭代器的val值
V& operator*()
{
return _node->_val;
}
對(duì)迭代器的箭頭操作，就是獲得迭代器值的地址
V* operator->()
{
return &_node->_val;
}
兩個(gè)迭代器的判等操作就是結(jié)點(diǎn)的地址是否相同
bool operator!=(const Self& it)
{
return _node != it._node;
}
迭代器的++和- -是要符合中序遍歷的有序遍歷，下面我們來(lái)一起分析
迭代器的begin()位置應(yīng)該是樹中最小的結(jié)點(diǎn)，而樹中最小的結(jié)點(diǎn)就是樹的最左結(jié)點(diǎn)；迭代器的end()位置應(yīng)該是樹中最大的結(jié)點(diǎn)，而樹中最大的結(jié)點(diǎn)就是樹的最右結(jié)點(diǎn)
迭代器的++操作分為兩種情況，第一種是存在右子樹的情況，第二種是不存在右子樹的情況
當(dāng)存在右子樹時(shí)，我們需要遍歷到右子樹的最左結(jié)點(diǎn)，然后訪問(wèn)該結(jié)點(diǎn)。例如我們現(xiàn)在的迭代器在8的位置，根據(jù)中序遍歷的條件，我們應(yīng)該訪問(wèn)的是10號(hào)結(jié)點(diǎn)，所以我們先走到8結(jié)點(diǎn)的右子樹11號(hào)結(jié)點(diǎn)，然后遍歷11的最左結(jié)點(diǎn)，該結(jié)點(diǎn)為10，也正是我們要訪問(wèn)的結(jié)點(diǎn)
if (_node->_right)
{
//右子樹的最左結(jié)點(diǎn)
_node = _node->_right;
while (_node->_left)
{
_node = _node->_left;
}
}
第二種情況是不存在右子樹。當(dāng)不存在右子樹，我們需要向上回溯，中序遍歷的遍歷規(guī)則就是左孩子、根、右孩子。所以我們要判斷當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子還是右孩子，如果是左孩子則表示父節(jié)點(diǎn)還未訪問(wèn)，此時(shí)需要訪問(wèn)父節(jié)點(diǎn)；如果是右孩子則表示父節(jié)點(diǎn)也訪問(wèn)過(guò)了，需要向上回溯，直至該結(jié)點(diǎn)不為父節(jié)點(diǎn)的右孩子。例如我們節(jié)點(diǎn)在5號(hào)結(jié)點(diǎn)的位置，需要判斷該結(jié)點(diǎn)父節(jié)點(diǎn)6號(hào)結(jié)點(diǎn)的左邊還是右邊，此時(shí)5號(hào)結(jié)點(diǎn)再6號(hào)結(jié)點(diǎn)的左邊，可以表示6號(hào)結(jié)點(diǎn)也未訪問(wèn)，此時(shí)將迭代器更新的父節(jié)點(diǎn)的位置即可。
當(dāng)我們迭代器在7號(hào)結(jié)點(diǎn)時(shí)，7號(hào)結(jié)點(diǎn)時(shí)在6號(hào)結(jié)點(diǎn)的右邊，此時(shí)需要向上回溯，讓結(jié)點(diǎn)更新置父節(jié)點(diǎn)，然后父節(jié)再向上回溯至其父節(jié)點(diǎn)的位置，再判斷當(dāng)前節(jié)點(diǎn)的位置是否為父節(jié)點(diǎn)的右邊，此時(shí)6號(hào)結(jié)點(diǎn)是8號(hào)結(jié)點(diǎn)的左邊，表示8號(hào)結(jié)點(diǎn)還未訪問(wèn)，此時(shí)訪問(wèn)8號(hào)結(jié)點(diǎn)即可
但是我們需要考慮到一種特殊的情況，就是該樹的根節(jié)點(diǎn)沒有右孩子時(shí)
正常來(lái)說(shuō)，我們對(duì)迭代器的++操作應(yīng)該會(huì)移動(dòng)到空的頭結(jié)點(diǎn)的位置，但是我們?cè)倩厮莸倪^(guò)程中會(huì)出現(xiàn)問(wèn)題。此時(shí)因?yàn)閕t沒有右結(jié)點(diǎn)，需要判斷該結(jié)點(diǎn)是在父節(jié)點(diǎn)的左邊還是右邊，此時(shí)是在右邊，就會(huì)向上回溯
這樣子對(duì)迭代器的++是一個(gè)死操作，永遠(yuǎn)不會(huì)走到空的位置。所以我們需要再跟結(jié)點(diǎn)處做特殊的處理。當(dāng)node結(jié)點(diǎn)的右孩子為自己的父親時(shí)，就不用更新結(jié)點(diǎn)了，此時(shí)已經(jīng)走到end()的了，如果還更新置parent結(jié)點(diǎn)，則該++操作就沒有發(fā)生改變
我們現(xiàn)在進(jìn)行測(cè)試
迭代器部分代碼
template <class V>
struct RBTreeIterator
{
typedef RBTreeNode<V> Node;
typedef RBTreeIterator<V> Self;
Node* _node;
RBTreeIterator(Node* node)
:_node(node)
{}
//解引用
V& operator*()
{
return _node->_val;
}
V* operator->()
{
return &_node->_val;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
Self& operator++()
{
if (_node->_right) //存在右節(jié)點(diǎn)
{
//右子樹的最左結(jié)點(diǎn)
_node = _node->_right;
while (_node->_left)
{
_node = _node->_left;
}
}
else //不存在右節(jié)點(diǎn)
{
Node* parent = _node->_parent;
while (_node == parent->_right)//回溯
{
_node = parent;
parent = parent->_parent;
}
//特殊情況：根節(jié)點(diǎn)沒有右孩子，則不需要更新結(jié)點(diǎn)
if (_node->_right != parent)
_node = parent;
}
return *this;
}
};
紅黑樹添加迭代器代碼
typedef RBTreeIterator<V> iterator;
iterator begin()
{
return iterator(_header->_left);
}
iterator end()
{
return iterator(_header);
}
map中添加紅黑樹迭代器代碼
typedef typename RBTree<K, pair<K, T>, MapKeyOfValue>::iterator iterator;
iterator begin()
{
return _rbt.begin();
}
iterator end()
{
return _rbt.end();
}
測(cè)試結(jié)果：
這里直接給出迭代器- -的代碼，原理和++類似
在迭代器類中
Self& operator--()
{
if (_node->_left)
{
//右子樹的最左結(jié)點(diǎn)
_node = _node->_left;
while (_node->_right)
{
_node = _node->_right;
}
}
else
{
Node* parent = _node->_parent;
while (_node == parent->_left)
{
_node = parent;
parent = parent->_parent;
}
if (_node->_left != parent)
_node = parent;
}
return *this;
}
在紅黑樹類中添加反向迭代器用于測(cè)試
iterator rbegin()
{
return iterator(_header->_right);
}
map中也添加反向迭代器
iterator rbegin()
{
return _rbt.rbegin();
}
測(cè)試：
方括號(hào)[]
插入的返回值是返回一個(gè)pair對(duì)象，所以我們?cè)诓迦霑r(shí)的返回值都需要修改成一個(gè)pair對(duì)象，且pair對(duì)象的first為插入后的結(jié)點(diǎn)的迭代器，second為插入是否成功
pair<iterator, bool> insert(const V& val)
{
if (_header->_parent == nullptr)
{
Node* root = new Node(val);
_header->_parent = root;
root->_parent = _header;
_header->_left = _header->_right = root;
//根節(jié)點(diǎn)為黑色
root->_color = BLACK;
return make_pair(iterator(root), true);
}
Node* cur = _header->_parent;
Node* parent = nullptr;
KeyOfValue kov;
//1.尋找到要插入的結(jié)點(diǎn)的位置
while (cur)
{
parent = cur;
if (kov(cur->_val) == kov(val))
return make_pair(iterator(cur), false);
else if (kov(cur->_val) > kov(val))
cur = cur->_left;
else
cur = cur->_right;
}
//2.創(chuàng)建節(jié)點(diǎn)
cur = new Node(val);
Node* node = cur;
if (kov(parent->_val) > kov(cur->_val))
parent->_left = cur;
else
parent->_right = cur;
cur->_parent = parent;
//3.顏色的修改或者結(jié)構(gòu)的調(diào)整
while (cur != _header->_parent && cur->_parent->_color == RED)//不為根且存在連續(xù)紅色，則需要調(diào)整
{
parent = cur->_parent;
Node* gfather = parent->_parent;
if (gfather->_left == parent)
{
Node* uncle = gfather->_right;
//情況1.uncle存在且為紅
if (uncle && uncle->_color == RED)
{
parent->_color = uncle->_color = BLACK;
gfather->_color = RED;
//向上追溯
cur = gfather;
}
else
{
if (parent->_right == cur)//情況3
{
RotateL(parent);
swap(cur, parent);
}
//情況2.uncle不存在或者uncle為黑
RotateR(gfather);
parent->_color = BLACK;
gfather->_color = RED;
break;
}
}
else
{
Node* uncle = gfather->_left;
if (uncle && uncle->_color == RED)
{
parent->_color = uncle->_color = BLACK;
gfather->_color = RED;
//向上追溯
cur = gfather;
}
else
{
if (parent->_left == cur)
{
RotateR(parent);
swap(cur, parent);
}
RotateL(gfather);
parent->_color = BLACK;
gfather->_color = RED;
break;
}
}
}
//根節(jié)點(diǎn)為黑色
_header->_parent->_color = BLACK;
//更新頭結(jié)點(diǎn)的左右指向
_header->_left = leftMost();
_header->_right = rightMost();
//return true;
return make_pair(iterator(node), true);
}
在map中也要修改
pair<iterator, bool> insert(const pair<K, T>& kv)
{
return _rbt.insert(kv);
}
T& operator[](const K& key)
{
pair<iterator, bool> ret = _rbt.insert(make_pair(key, T()));
//ret.first 迭代器
//迭代器-> pair<k,v>對(duì)象
//pair<k,v>->second，獲得v
return ret.first->second;
}
測(cè)試：
到此這篇關(guān)于C++ map的簡(jiǎn)單使用實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ map 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++ 操作系統(tǒng)內(nèi)存分配算法的實(shí)現(xiàn)詳解
本文主要介紹了在動(dòng)態(tài)分區(qū)管理方式下采用不同的分配算法實(shí)現(xiàn)主存分配和實(shí)現(xiàn)主存回收，旨在幫助學(xué)生理解在動(dòng)態(tài)分區(qū)管理方式下應(yīng)怎樣實(shí)現(xiàn)主存空間的分配和回收。感興趣的可以了解一下2021-11-11
用C++實(shí)現(xiàn)一個(gè)命令行進(jìn)度條的示例代碼
這篇文章主要介紹了用C++實(shí)現(xiàn)一個(gè)命令行進(jìn)度條的示例代碼，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-04-04
這篇文章主要介紹了C++設(shè)計(jì)模式之單例模式,本文同時(shí)給出了數(shù)種單例模式的實(shí)現(xiàn)代碼,需要的朋友可以參考下，希望能夠給你帶來(lái)幫助2021-09-09
堆和棧都是一種數(shù)據(jù)項(xiàng)按序排列的數(shù)據(jù)結(jié)構(gòu)。在C語(yǔ)言中是非常重要的知識(shí)點(diǎn)，接下來(lái)通過(guò)本文給大家介紹C語(yǔ)言中堆和棧的區(qū)別，感興趣的朋友一起看下吧2016-06-06
c語(yǔ)言獲取當(dāng)前工作路徑的實(shí)現(xiàn)代碼(windows/linux)
這篇文章主要介紹了c語(yǔ)言獲取當(dāng)前工作路徑的實(shí)現(xiàn)代碼(windows/linux),需要的朋友可以參考下2017-09-09
Visual Studio Code (vscode) 配置C、C++環(huán)境/編寫運(yùn)行C、C++的教程詳解（Windows
這篇文章主要介紹了Visual Studio Code (vscode) 配置C、C++環(huán)境/編寫運(yùn)行C、C++的教程詳解（Windows）【真正的小白版】,圖文詳解介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-03-03
詳解C語(yǔ)言動(dòng)態(tài)內(nèi)存的分配
這篇文章主要為大家介紹了C語(yǔ)言動(dòng)態(tài)內(nèi)存的分配，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2021-12-12
今天小編就為大家分享一篇關(guān)于C++11并發(fā)編程:多線程std::thread，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2018-12-12
這篇文章主要介紹了淺談C++中virtual的三種用法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
算法中排序是十分重要的,而每一個(gè)學(xué)習(xí)計(jì)算機(jī)的都會(huì)在初期的時(shí)候接觸到這種排序,下面這篇文章主要給大家介紹了關(guān)于c語(yǔ)言冒泡排序的相關(guān)資料,需要的朋友可以參考下2023-01-01