欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++中map和set封裝實現(xiàn)示例

 更新時間：2023年02月06日 10:09:31   作者：頭發(fā)沒有代碼多  
我們知道,map與set所使用的都是紅黑樹,下面這篇文章主要給大家介紹了關于C++中map和set封裝實現(xiàn)的相關資料,文中通過圖文以及實例代碼介紹的非常詳細,需要的朋友可以參考下

mao和set模擬實現(xiàn) 

 STL map和set只是包含了幾個頭文件

 主要在選中的這個文件里，打開之后我們可以看到紅黑樹

用紅黑樹實現(xiàn)map和set

set的主要實現(xiàn)

set里面的value type和key type都是KEY

map里面的value type是pair，key type是KEY

這里用一顆泛型結構的RBTree，通過不同的實例化參數(shù)，實現(xiàn)出了map和set。

模擬實現(xiàn) 

這里不用說明紅黑樹是K還是KV，用T來決定紅黑樹，使用時T是什么，紅黑樹就是什么

如Map傳的是pair，T就是pair，Set傳的是K，T就是K

T傳給了節(jié)點里面的data，上面?zhèn)鲄鱇的原因是find函數(shù)要用到，find是通過K去進行查找。

Insert插入數(shù)據(jù)的時候要比較數(shù)據(jù)的大小選擇合適的位置插入，但這里data是T類型，對于set可直接比較，而map傳過來的是pair，如果比較pair就要比較first和second，這種不滿足我們的需求，因為比較的時候既要滿足set也要滿足Map.

我們用仿函數(shù)來滿足這種要求，這里仿函數(shù)是把T里面的k取出來，pair的K就是first

取K的仿函數(shù) 

對于set而言，直接返回就行 

對于map而言，就要取first

之后修改rbtree.h，創(chuàng)建一個仿函數(shù)對象，這個對象是什么類型的就根據(jù)什么類型取比較即可

Insert 

 對于Map而言，_t是RBTree類型，Map的insert只需調(diào)用紅黑樹的Insert即可

 set也一樣

迭代器 

 迭代器也依靠紅黑樹的迭代器實現(xiàn)，tyoename作用，告訴編譯器是要把類型進行重命名

 以下是紅黑樹的迭代器

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;
	}
}；

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é)點，這里的_root是紅黑樹的根節(jié)點，end是最后一個節(jié)點的下一個位置就是空。

 ++和-- 

 這里++和--是按照中序進行的

這里訪問順序是左根右

1.如果右子樹不為空，++就是找右子樹中序的第一個（最左節(jié)點）

2.右子樹是空，++找孩子不是父親右的那個父親

第二句話理解，這里7訪問完，父親是6，7是6右子樹，更新cur，parent，8是parent，6是cur，cur不是parent右子樹。所以下一個節(jié)點是8

--是反向左子樹

右根左

1.如果左子樹不為空，我們就訪問它的最右節(jié)點

2.如果為空，訪問孩子不是父親的左的父親

Self& operator++()
	{
		if (_node->_right)
		{
			// 下一個就是右子樹的最左節(jié)點
			Node* left = _node->_right;
			while (left->_left)
			{
				left = left->_left;
			}
 
			_node = left;
		}
		else
		{
			// 找祖先里面孩子不是祖先的右的那個
			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)
		{
			// 下一個是左子樹的最右節(jié)點
			Node* right = _node->_left;
			while (right->_right)
			{
				right = right->_right;
			}
 
			_node = right;
		}
		else
		{
			// 孩子不是父親的左的那個祖先
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (parent && cur == parent->_left)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
 
			_node = parent;
		}
 
		return *this;
	}

operator[]

 []的實現(xiàn)要改造一個迭代器

map和set的insert也做修改

只有map有[]，我們不需要在紅黑樹里面實現(xiàn)[]，單獨給map實現(xiàn)即可

ret.first是迭代器，->second是KV的value

Map中使用方括號訪問鍵對應的值map[key]時：

  1. 若該key存在，則訪問取得value值；
  2. 若該key不存在，訪問仍然成功，取得value對象默認構造的值。具體如下：
    用 []訪問，但key不存在時，C++會利用該key及默認構造的value，組成{key，value}對，插入到map中。
    value為 string對象，則構造空串；value為int對象，構造為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[] = { "蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };
 
		map<string, int> countMap;
		for (auto& str : arr)
		{
			// 1、str不在countMap中，插入pair(str, int()),然后在對返回次數(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)
		{
			// 下一個就是右子樹的最左節(jié)點
			Node* left = _node->_right;
			while (left->_left)
			{
				left = left->_left;
			}
 
			_node = left;
		}
		else
		{
			// 找祖先里面孩子不是祖先的右的那個
			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)
		{
			// 下一個是左子樹的最右節(jié)點
			Node* right = _node->_left;
			while (right->_right)
			{
				right = right->_right;
			}
 
			_node = right;
		}
		else
		{
			// 孩子不是父親的左的那個祖先
			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);
			// 關鍵看叔叔
			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é)點不是黑色" << endl;
			return false;
		}
 
		// 黑色節(jié)點數(shù)量基準值
		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é)點的數(shù)量不相等" << endl;
				return false;
			}
			else
			{
				return true;
			}
		}
 
		if (root->_col == BLACK)
		{
			++blackNum;
		}
 
		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "存在連續(xù)的紅色節(jié)點" << 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;
};

總結

到此這篇關于C++中map和set封裝實現(xiàn)的文章就介紹到這了,更多相關C++ map和set封裝內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

相關文章

  • 類成員函數(shù)的重載、覆蓋與隱藏之間的區(qū)別總結

    類成員函數(shù)的重載、覆蓋與隱藏之間的區(qū)別總結

    以下是對類成員函數(shù)的重載、覆蓋與隱藏之間的區(qū)別進行了詳細的總結分析，需要的朋友可以過來參考下。希望對大家有所幫助
    2013-10-10
  • 用C/C++代碼檢測ip能否ping通(配合awk和system可以做到批量檢測)

    用C/C++代碼檢測ip能否ping通(配合awk和system可以做到批量檢測)

    今天小編就為大家分享一篇關于用C/C++代碼檢測ip能否ping通(配合awk和system可以做到批量檢測)，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧
    2019-04-04
  • 深入解析C++中的auto自動類型推導

    深入解析C++中的auto自動類型推導

    C++標準委員會在C++11標準中改變了auto關鍵字的語義,使它變成一個類型占位符,允許在定義變量時不必明確寫出確切的類型,讓編譯器在編譯期間根據(jù)初始值自動推導出它的類型,下面我們就來看看auto自動類型推導的推導規(guī)則吧
    2024-04-04
  • c語言解析bmp圖片的實例

    c語言解析bmp圖片的實例

    下面小編就為大家?guī)硪黄猚語言解析bmp圖片的實例。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
    2017-08-08
  • C++實現(xiàn)Go的defer功能(示例代碼)

    C++實現(xiàn)Go的defer功能(示例代碼)

    defer和go一樣都是Go語言提供的關鍵字。defer用于資源的釋放，會在函數(shù)返回之前進行調(diào)用。接下來通過本文給大家介紹C++實現(xiàn)Go的defer功能，感興趣的朋友跟隨小編一起看看吧
    2021-07-07
  • C/C++中運算符的優(yōu)先級、運算符的結合性詳解

    C/C++中運算符的優(yōu)先級、運算符的結合性詳解

    這篇文章主要介紹了C/C++中運算符的優(yōu)先級、運算符的結合性詳解的相關資料,需要的朋友可以參考下
    2017-02-02
  • 基于C++中覆蓋，重載，隱藏的一點重要說明

    基于C++中覆蓋，重載，隱藏的一點重要說明

    下面小編就為大家?guī)硪黄贑++中覆蓋，重載，隱藏的一點重要說明。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
    2016-12-12
  • Java C++ 算法題解leetcode1608特殊數(shù)組特征值

    Java C++ 算法題解leetcode1608特殊數(shù)組特征值

    這篇文章主要為大家介紹了Java C++ 算法題解拓展leetcode1608特殊數(shù)組特征值實例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪
    2022-09-09
  • 封裝常用正則表達式的用法

    封裝常用正則表達式的用法

    這篇文章主要介紹了使用C++封裝常用正則表達式的用法，方便以后直接使用，最后還給出了測試代碼，大家可運行測試使用
    2014-03-03
  • C++實現(xiàn)旅館住宿管理系統(tǒng)

    C++實現(xiàn)旅館住宿管理系統(tǒng)

    這篇文章主要為大家詳細介紹了C++實現(xiàn)旅館住宿管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-05-05

最新評論