真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

成都創(chuàng)新互聯(lián)網站制作重慶分公司

紅黑樹封裝map/set及其迭代器(C++)-創(chuàng)新互聯(lián)

目錄

為府谷等地區(qū)用戶提供了全套網頁設計制作服務，及府谷網站建設行業(yè)解決方案。主營業(yè)務為成都網站建設、成都網站設計、府谷網站設計，以傳統(tǒng)方式定制建設網站，并提供域名空間備案等一條龍服務，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務。我們深信只要達到每一位用戶的要求，就會得到認可，從而選擇與我們長期合作。這樣，我們也可以走得更遠！

一、map/set 的封裝

1.1 封裝思路

1.2 紅黑樹節(jié)點調整

1.3 map 和 set 的定義

1.4 仿函數 KeyOfValue

1.5 map/set 的插入

二、map/set 迭代器實現

2.1 迭代器的定義

2.2?解引用運算符重載

2.3?成員訪問運算符重載

2.4?(不)等于運算符重載

2.5?begin() 與 end()

2.6?++ 運算符重載

2.7?-- 運算符重載

2.8 [ ]下標訪問運算符重載

三、源代碼+測試用例

3.1 map/set?

3.2 迭代器

3.3 測試用例

3.4?紅黑樹

一、map/set 的封裝

在實現了紅黑樹的部分功能后，我們可以便可以將紅黑樹作為底層結構來封裝map 和 set ，其中map是 K-Value 模型 ，而 set 是 Key 模型。

我們接下來將使用模板、仿函數用一棵紅黑樹實現 map和set。

1.1 封裝思路

因為 map 存儲的是 pair ，而 set 存儲的是 Key ，所以其解決的根本方向就是：

如果是 map，紅黑樹中就按照 pair 的 K 進行比較，從而插入；

如果是 set，紅黑樹中就按照 Key 值進行比較，進而插入。

讓 map / set 主動傳出待比較的數據，紅黑樹只用根據數據間關系進行插入即可，不用在乎待比較的數據是何種結構。

1.2 紅黑樹節(jié)點調整

上文我們實現的紅黑樹是按照鍵值對的方式進行存儲的，而接下來我們要同時封裝 map/set，故不能直接定死存儲的結構，所以我們在此進行修改。

將原來的 kv 模型改為 data 模型，data 即是比較的數據內容。

注意，將 Kv模型改為 data后，插入與查找中比較的代碼都要進行更新，稍后會講解。

1.3 map 和 set 的定義

map 和 set 底層都使用的紅黑樹，所以我們?map/set的功能就是調用紅黑樹的成員函數即可。

templateclass Map
{
private:
	RBTree>_t;
};

templateclass Set
{
private:
	RBTree_t;
};

因為 Map 有兩個模板參數，而 Set 只有一個模板參數。所以當我們使用的一個紅黑樹實現時，要進行匹配處理。即使 Set 是一個模板參數，在調用紅黑樹時也要傳入兩個模板參數。因為第一個模板參數是匹配 Map 滿足紅黑樹的兩個模板參數，而第二個模板參數是為了讓底層紅黑樹拿到比較的數據。

為什么 Map 除了傳入 pair 外，第一個參數直接傳入 K，為什么不能省略？

因為 Find 的存在，map中 Find 函數是直接按 pair 中的 K 進行查找的，所以要額外設置該參數。

1.4 仿函數 KeyOfValue

接下來我們就要將數據取出供紅黑樹比較了，如果是 map，就按 pair 中的 K去比較，如果是 set，就按 Key 比較。

為此我們可以在 map 和 set 內部定義一個仿函數將其數據取出。

templateclass Map
{
    //Map-keyofvalue 仿函數
	struct MapKeyOfvalue
	{
		const K& operator()(const std::pair& kv)
		{
			return kv.first;
		}
	};
private:
	RBTree>_t;
};

templateclass Set
{
    //Set-keyofvalue 仿函數
    struct SetKeyOfvalue
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
private:
	RBTree_t;
};

然后我們將其仿函數也作為模板，傳入紅黑樹中，對應的，紅黑樹要添加一個模板參數來接收該仿函數。

改動代碼如下：

改動這些之后，我們便要將紅黑樹中比較數據大小的地方進行修改

用仿函數將數據取出，然后進行比較：

//根據模板參數創(chuàng)建仿函數
KeyOfvalue kovalue;
if (!_root)
{
	_root = new Node(data);
	_root->_col = BLACK;
	return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
    //比較處————進行改動
	if (kovalue(cur->_data) >kovalue(data))
	{
		parent = cur;
		cur = cur->_left;
	}
    //比較處————進行改動
	else if (kovalue(cur->_data)< kovalue(data))
	{
		parent = cur;
		cur = cur->_right;
	}
	else
	{
		return false;
	}
}
//創(chuàng)建新節(jié)點，使用data進行構造
cur = new Node(data);
//比較處————進行改動
if (kovalue(parent->_data) >kovalue(data))
{
	parent->_left = cur;
}
else
{
	parent->_right = cur;
}
cur->_parent = parent;

這樣，紅黑樹便可以適配 map/set 的插入了。

1.5 map/set 的插入

接下來 map/set 的插入直接套用紅黑樹的即可。

代碼如下：

//map的插入，插入pair
bool insert(const pair& kv)
{
	return _t.Insert(kv);
}

//set的插入，插入key
bool insert(const K& key)
{
	return _t.Insert(key);
}

接下來進行測試，看我們map/set能否正常的插入數據。

二、map/set 迭代器實現 2.1 迭代器的定義
//			 節(jié)點數據	引用/const引用  指針/const指針
templatestruct __RBTreeIterator
{
	typedef RBTreeNodeNode;
	typedef __RBTreeIteratorself;
	Node* _node;
public:
	__RBTreeIterator(Node* node)
		:_node(node)
	{}
}

首先，我們要明確，其實 map/set 只是一層套殼，其中的功能都是由紅黑樹實現后，再封裝到map/set中供我們使用，迭代器也不例外。

2.2?解引用運算符重載

解引用即返回該節(jié)點的存儲的數據，主要用于 set 中，返回該數據的引用。

Ref operator*()
{
	return _node->_data;
}
2.3?成員訪問運算符重載

成員訪問操作符即返回該節(jié)點的地址，主要用于 map 中，方便訪問 pair 中的first以及second。

Ptr operator->()
{
	return &(_node->_data);
}
2.4?(不)等于運算符重載
bool operator==(const self& s) 
{
	return _node == s._node;
}


bool operator!=(const self& s) 
{
	return _node != s._node;
}
2.5?begin() 與 end()

迭代器常用成員函數begin()與end()，其中begin()對應紅黑樹的最左節(jié)點，end()對應最后一個節(jié)點的下一個節(jié)點，即nullptr(為了簡化，并未設置哨兵節(jié)點實現將其完美實現)

iterator begin()
{
	Node* left = _root;
	while (left && left->_left)
	{
		left = left->_left;
	}
	return iterator(left);
}

iterator end()
{
	return iterator(nullptr);
}

如果 map/set 中想使用紅黑樹中的迭代器，我們需要在 map/set 中進行聲明。

聲明如下：

如果想取一個類模板中的一個類型，要使用 typedname 進行聲明。
告訴編譯器這是一個類型，并不是一個靜態(tài)變量

//如果想取一個類模板中的一個類型，要使用 typedname 進行聲明。
//告訴編譯器這是一個類型，并不是一個靜態(tài)變量
typedef typename RBTree, MapKeyOfvalue>::iterator iterator;

注意：typename受限定符限制，盡量放在public下

2.6?++ 運算符重載

首先我們需要明確，迭代器++是讓當前迭代器指向紅黑樹中序遍歷的下一個節(jié)點。

以下圖的35節(jié)點為例。

  • 當迭代器指向 35?時，進行 ++，指向右子樹最左節(jié)點，即?40。
  • 當迭代器指向 40 時，進行 ++，右子樹為空，指向父節(jié)點，即 45。
  • 當迭代器指向 45?時，進行 ++，指向右子樹最左節(jié)點，即 48。
  • 當迭代器指向 48 時，進行 ++，指向未遍歷的父節(jié)點，即 50。

分析上面的情況，發(fā)現迭代器 ++ 始終圍繞著右子樹是否存在進行。

現在我們將其抽象化，分析其規(guī)律。

  1. 右子樹不為空，進行 ++ 則是指向右子樹中序的第一個(最左節(jié)點)。
  2. 右子樹為空，++ 找孩子不是父親右節(jié)點的祖先。

代碼實現：

self& operator++()
{
	//如果右子樹存在
	if (_node->_right)
	{
		Node* left = _node->_right;
		//則尋找右子樹的最左節(jié)點
		while (left->_left)
		{
			left = left->_left;
		}
		_node = left;
	}
	//如果右子樹不存在
	else
	{
        //找孩子不是父親右節(jié)點的節(jié)點
		Node* parent = _node->_parent;
		Node* cur = _node;=
		while (cur == parent->_right)
		{
			cur = cur->_parent;
			parent = parent->_parent;
			//防止最后一個節(jié)點尋找祖先導致程序崩潰
			if (parent == nullptr)
			{
				break;
			}
		}
		_node = parent;
	}
	return *this;
}

需要注意，當 ++ 到最后一個節(jié)點的時候。有可能在尋找非父親右節(jié)點的祖先時，父節(jié)點一路走到 nullptr 的情況，如圖：

所以在每次 parent 更新時都進行一次判斷，即可。

測試：

這里順序把后置 ++ 的代碼實現一下，直接套用前置 ++ 即可。

//迭代器后置++
self operator++(int)
{
	self it_temp(_node);
	++(*this);
	return it_temp;
}
2.7?-- 運算符重載

有了前面++的模擬實現，實現 --就是反著遍歷即可。

  1. 左子樹不為空，進行 -- 則是指向左子樹中序的最后一個(最右節(jié)點)。
  2. 左子樹為空，-- 找孩子不是父親左節(jié)點的祖先。

代碼如下:

self& operator--()
{
	//如果左子樹存在
	if (_node->left)
	{
		//找左子樹的最右節(jié)點
		Node* right = _node->_left;
		while (right->_right)
		{
			right = right->_right;
		}
		_node = rihgt;
	}
	//如果左子樹不存在
	else
	{
		//找孩子不是父親左節(jié)點的節(jié)點
		Node* parent = _node->parent;
		Node* cur = _node;
		while (parent->_left == cur)
		{
			cur = cur->_parent;
			parent = parent->_parent;
			if (parent == nullptr)
			{
				break;
			}
		}
		_node = parent;
	}
	return *this;
}
2.8 [ ]下標訪問運算符重載

我們來看 map 的 [ ] 下標訪問操作符，其中 [ ]返回的是mapped_type(pair)?類型。

我們便要對 map 中 insert 的返回值做出修改：

注意，set 中的 insert 也是返回 pair，雖然很反常，但是官方庫中確實是這樣書寫的。

因為只有 set 沒有 [ ] 運算符重載，所以我們 set 中不必提供該函數，只用在 map 中提供即可。

首先，我們向 map?中 insert 數據 pair；pair的第一個參數為用戶傳入的 key 值，第二個參數則是用戶聲明的第二個模板參數的默認構造函數(如果是 int，則調用 int的構造函數，如果是 string ，則默認構造 string)。

pairresult = insert(make_pair(key, V()));

然后我們返回迭代器指向的 pair 數據中的second。

//result.first取出迭代器，使用->運算符重載取出data地址，訪問second并返回
return result.first->second;

完整的函數書寫如下：

V& operator[](const K& key)
{
	pairresult = insert(make_pair(key, V()));
	//如果存在，則插入失敗
	//如果不存在，則插入數據
	//無論是否存在,都返回 second;
	return result.first->second;
}

接下來我們要對紅黑樹的 Insert 的返回值處進行改動，進而契合 map 的 pair 數據類型。改動有三處，這里貼圖大家觀察即可。

測試：

三、源代碼+測試用例 3.1 map/set?
namespace brant
{
	templateclass Map
	{
	public:
		struct MapKeyOfvalue
		{
			const K& operator()(const std::pair& kv)
			{
				return kv.first;
			}
		};
		//外層要想使用紅黑樹的iterator，
		typedef typename RBTree, MapKeyOfvalue>::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}

		pairinsert(const pair& kv)
		{
			return _t.Insert(kv);
		}
		void InOrder()
		{
			_t.Inorder();
		}
		V& operator[](const K& key)
		{
			pairresult = insert(make_pair(key, V()));
			return result.first->second;
		}
	private:
		RBTree, MapKeyOfvalue>_t;
	};

    templateclass Set
	{
		struct SetKeyOfvalue
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}
		
		pairinsert(const K& key)
		{
			return _t.Insert(key);
		}

		void InOrder()
		{
			_t.Inorder();
		}
	private:
		RBTree_t;
	};
}
3.2 迭代器
enum Color { RED, BLACK };
templatestruct RBTreeNode
{
	RBTreeNode* _left;	
	RBTreeNode* _right;	
	RBTreeNode* _parent;	
	T _data;
	Color _col;					

	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)              
	{}
};

//			 節(jié)點數據	引用/const引用  指針/const指針
templatestruct __RBTreeIterator
{
	typedef RBTreeNodeNode;
	typedef __RBTreeIteratorself;
	typedef __RBTreeIteratoriterator;
	Node* _node;
	__RBTreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_data;
	}
	//map常使用operator ->返回地址，然后通過——>訪問
	Ptr operator->()
	{
		return &(_node->_data);
	}

	bool operator==(const self& s)  
	{
		return _node == s._node;
	}

	bool operator!=(const self& s) 
	{
		return _node != s._node;
	}

	iterator begin()
	{
		Node* left = _node;
		while (left && left->_left)
		{
			left = left->_left;
		}
		return iterator(left);
	}

	iterator end()
	{
		return iterator(nullptr);
	}

	self& operator++()
	{
		//如果右子樹存在
		if (_node->_right)
		{
			Node* left = _node->_right;
			//則尋找右子樹的最左節(jié)點
			while (left->_left)
			{
				left = left->_left;
			}
			_node = left;
		}
		//如果右子樹不存在
		else
		{
			//找孩子不是父親右的節(jié)點
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (cur == parent->_right)
			{
				cur = cur->_parent;
				parent = parent->_parent;
				//防止最后一個節(jié)點尋找祖先導致程序崩潰
				if (parent == nullptr)
				{
					break;
				}
			}
			_node = parent;
		}
		return *this;
	}
	self operator++(int)
	{
		self it_temp(_node);
		++(*this);
		return it_temp;
	}

	self& operator--()
	{
		if (_node->left)
		{
			Node* right = _node->_left;
			while (right->_right)
			{
				right = right->_right;
			}
			_node = right;
		}
		else
		{
			Node* parent = _node->parent;
			Node* cur = _node;
			while (parent->_left == cur)
			{
				cur = cur->_parent;
				parent = parent->_parent;
				if (parent == nullptr)
				{
					break;
				}
			}
			_node = parent;
		}
		return *this;
	}
};
3.3 測試用例
void test_iterator()
{
	brant::Sets;
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(5);
	brant::Set::iterator it_set = s.begin();
	cout<< "set:"<< endl;
	while (it_set != s.end())
	{
		cout<< *it_set<< " ";
		it_set++;
	}
	cout<< endl;

	brant::Mapm;
	m.insert(make_pair(1, 100));
	m.insert(make_pair(2, 200));
	m.insert(make_pair(3, 300));
	m.insert(make_pair(4, 400));
	m.insert(make_pair(5, 500));
	brant::Map::iterator it_map = m.begin();
	cout<< "map:"<< endl;

	while (it_map != m.end())
	{
		cout<< (*it_map).first 
			<< "："<< (*it_map).second<< endl;
		++it_map;
	}
}

void test_map_()
{
	string arr[] = { "蘋果", "西瓜", "蘋果", "西瓜",
		"蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };

	brant::MapcountMap;
	for (auto& str : arr)
	{
		countMap[str]++;
	}

	brant::Map::iterator it = countMap.begin();
	while (it != countMap.end())
	{
		cout<< it->first<< ":"<< it->second<< endl;
		++it;
	}
	cout<< endl; 
	for (auto& kv : countMap)
	{
		cout<< kv.first<< ":"<< kv.second<< endl;
	}
}
3.4?紅黑樹

只截取了改動和增添的部分。原來的紅黑樹在這.

templateclass RBTree
{
	typedef RBTreeNodeNode;

public:
	typedef __RBTreeIteratoriterator;
	typedef __RBTreeIteratorconst_iteraotr;
	
	iterator begin()
	{
		//找最左節(jié)點
		Node* left = _root;
		while (left && left->_left)
		{
			left = left->_left;
		}
		//用一個節(jié)點構造迭代器
		return iterator(left);
	}

	iterator end()
	{
		//因為沒有哨兵節(jié)點，直接使用空進行返回
		return iterator(nullptr);
	}
pairInsert(const T& data)
{
	KeyOfvalue kovalue;
	if (!_root)
	{
		_root = new Node(data);
		_root->_col = BLACK;
		return make_pair(iterator(_root),true);
	}
	Node* parent = nullptr;
	Node* cur = _root;
	//找插入的位置
	while (cur)
	{
		if (kovalue(cur->_data) >kovalue(data))
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (kovalue(cur->_data)< kovalue(data))
		{
			parent = cur;
			cur = cur->_right;
		}
		else
		{
			return make_pair(iterator(cur),false);
		}
	}
	cur = new Node(data);
	//插入成功，返回新增節(jié)點 
	//注意：cur 可能會改變(情況1變色處理,cur指向可能會改變)
	//使用newnode記錄新創(chuàng)建節(jié)點的地址
	Node* newnode = cur;

	if (kovalue(parent->_data) >kovalue(data))
	{
		parent->_left = cur;
	}
	else
	{
		parent->_right = cur;
	}
	cur->_parent = parent;
	while (parent && parent->_col == RED)
	{
		Node* grandfater = parent->_parent;
		assert(grandfater);
		assert(grandfater->_col == BLACK);
		if (grandfater->_left == parent)
		{
			Node* uncle = grandfater->_right;
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfater->_col = RED;
				cur = grandfater;
				parent = cur->_parent;
			}
			else
			{
				if (cur == parent->_left)
				{
					RotateR(grandfater);
					parent->_col = BLACK;
					grandfater->_col = RED;
				}
				else
				{
					RotateL(parent);
					RotateR(grandfater);
					cur->_col = BLACK;
					grandfater->_col = RED;
				}
				break;
			}
		}
		else
		{
			Node* uncle = grandfater->_left;
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfater->_col = RED;
				cur = grandfater;
				parent = cur->_parent;
			}
			else
			{
				if (cur == parent->_right)
				{
					RotateL(grandfater);
					parent->_col = BLACK;
					grandfater->_col = RED;
				}
				else
				{
					RotateR(parent);
					RotateL(grandfater);
					cur->_col = BLACK;
					grandfater->_col = RED;
				}
				break;
			}
		}
	}
	_root->_col = BLACK;
	return make_pair(iterator(newnode), true);
}
};

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧


文章標題：紅黑樹封裝map/set及其迭代器(C++)-創(chuàng)新互聯(lián)
本文路徑：http://weahome.cn/article/pijhh.html

其他資訊

在線咨詢

微信咨詢

電話咨詢

028-86922220（工作日）

18980820575（7×24）

提交需求

返回頂部