博客

红黑树封装 map/set 及其迭代器(C++)

  • Post author:
  • Post category:其他

目录

一、map/set 的封装

1.1 封装思路

1.2 红黑树节点调整

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 红黑树节点调整

上文我们实现的红黑树是按照键值对的方式进行存储的，而接下来我们要同时封装 map/set，故不能直接定死存储的结构，所以我们在此进行修改。

将原来的 kv 模型改为 data 模型，data 即是比较的数据内容。

注意，将 Kv模型改为 data后，插入与查找中比较的代码都要进行更新，稍后会讲解。

1.3 map 和 set 的定义

map 和 set 底层都使用的红黑树，所以我们 map/set的功能就是调用红黑树的成员函数即可。

template<class K, class V>
class Map
{
private:
	RBTree<K, pair<K, V>> _t;
};

template<class K>
class Set
{
private:
	RBTree<K,K> _t;
};

因为 Map 有两个模板参数，而 Set 只有一个模板参数。所以当我们使用的一个红黑树实现时，要进行匹配处理。即使 Set 是一个模板参数，在调用红黑树时也要传入两个模板参数。因为第一个模板参数是匹配 Map 满足红黑树的两个模板参数，而第二个模板参数是为了让底层红黑树拿到比较的数据。

为什么 Map 除了传入 pair 外，第一个参数直接传入 K，为什么不能省略？

因为 Find 的存在，map中 Find 函数是直接按 pair 中的 K 进行查找的，所以要额外设置该参数。

1.4 仿函数 KeyOfValue

接下来我们就要将数据取出供红黑树比较了，如果是 map，就按 pair 中的 K去比较，如果是 set，就按 Key 比较。

为此我们可以在 map 和 set 内部定义一个仿函数将其数据取出。

template<class K, class V>
class Map
{
    //Map-keyofvalue 仿函数
	struct MapKeyOfvalue
	{
		const K& operator()(const std::pair<K, V>& kv)
		{
			return kv.first;
		}
	};
private:
	RBTree<K, pair<K, V>> _t;
};

template<class K>
class Set
{
    //Set-keyofvalue 仿函数
    struct SetKeyOfvalue
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
private:
	RBTree<K,K> _t;
};

然后我们将其仿函数也作为模板，传入红黑树中，对应的，红黑树要添加一个模板参数来接收该仿函数。

改动代码如下：

 改动这些之后，我们便要将红黑树中比较数据大小的地方进行修改

用仿函数将数据取出，然后进行比较：

//根据模板参数创建仿函数
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;
	}
}
//创建新节点，使用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<K, V>& kv)
{
	return _t.Insert(kv);
}

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

接下来进行测试，看我们map/set能否正常的插入数据。

二、map/set 迭代器实现

2.1 迭代器的定义

//			 节点数据	引用/const引用  指针/const指针
template <class T,class Ref,class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __RBTreeIterator<T, Ref, Ptr> self;
	Node* _node;
public:
	__RBTreeIterator(Node* node)
		:_node(node)
	{}
}

首先，我们要明确，其实 map/set 只是一层套壳，其中的功能都是由红黑树实现后，再封装到map/set中供我们使用，迭代器也不例外。

2.2 解引用运算符重载

解引用即返回该节点的存储的数据，主要用于 set 中，返回该数据的引用。

Ref operator*()
{
	return _node->_data;
}

2.3 成员访问运算符重载

成员访问操作符即返回该节点的地址，主要用于 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()对应红黑树的最左节点，end()对应最后一个节点的下一个节点，即nullptr(为了简化，并未设置哨兵节点实现将其完美实现)


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 进行声明。
告诉编译器这是一个类型，并不是一个静态变量

//如果想取一个类模板中的一个类型，要使用 typedname 进行声明。
//告诉编译器这是一个类型，并不是一个静态变量
typedef typename RBTree<K, pair<K, V>, MapKeyOfvalue>::iterator iterator;

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

2.6 ++ 运算符重载

首先我们需要明确，迭代器++是让当前迭代器指向红黑树中序遍历的下一个节点。

以下图的35节点为例。

  • 当迭代器指向 35 时，进行 ++，指向右子树最左节点，即 40。
  • 当迭代器指向 40 时，进行 ++，右子树为空，指向父节点，即 45。
  • 当迭代器指向 45 时，进行 ++，指向右子树最左节点，即 48。
  • 当迭代器指向 48 时，进行 ++，指向未遍历的父节点，即 50。

分析上面的情况，发现迭代器 ++ 始终围绕着右子树是否存在进行。

现在我们将其抽象化，分析其规律。

  1. 右子树不为空，进行 ++ 则是指向右子树中序的第一个(最左节点)。
  2. 右子树为空，++ 找孩子不是父亲右节点的祖先。

代码实现：


self& operator++()
{
	//如果右子树存在
	if (_node->_right)
	{
		Node* left = _node->_right;
		//则寻找右子树的最左节点
		while (left->_left)
		{
			left = left->_left;
		}
		_node = left;
	}
	//如果右子树不存在
	else
	{
        //找孩子不是父亲右节点的节点
		Node* parent = _node->_parent;
		Node* cur = _node;=
		while (cur == parent->_right)
		{
			cur = cur->_parent;
			parent = parent->_parent;
			//防止最后一个节点寻找祖先导致程序崩溃
			if (parent == nullptr)
			{
				break;
			}
		}
		_node = parent;
	}
	return *this;
}

需要注意，当 ++ 到最后一个节点的时候。有可能在寻找非父亲右节点的祖先时，父节点一路走到 nullptr 的情况，如图：

 

所以在每次 parent 更新时都进行一次判断，即可。

测试：

这里顺序把后置 ++ 的代码实现一下，直接套用前置 ++ 即可。

//迭代器后置++
self operator++(int)
{
	self it_temp(_node);
	++(*this);
	return it_temp;
}

2.7 — 运算符重载

有了前面++的模拟实现，实现 –就是反着遍历即可。

  1. 左子树不为空，进行 — 则是指向左子树中序的最后一个(最右节点)。
  2. 左子树为空，– 找孩子不是父亲左节点的祖先。

代码如下:

self& operator--()
{
	//如果左子树存在
	if (_node->left)
	{
		//找左子树的最右节点
		Node* right = _node->_left;
		while (right->_right)
		{
			right = right->_right;
		}
		_node = rihgt;
	}
	//如果左子树不存在
	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;
}

2.8 [ ]下标访问运算符重载

我们来看 map 的 [ ] 下标访问操作符，其中 [ ]返回的是mapped_type(pair) 类型。

我们便要对 map 中 insert 的返回值做出修改：

 注意，set 中的 insert 也是返回 pair，虽然很反常，但是官方库中确实是这样书写的。

因为只有 set 没有 [ ] 运算符重载，所以我们 set 中不必提供该函数，只用在 map 中提供即可。

首先，我们向 map 中 insert 数据 pair；pair的第一个参数为用户传入的 key 值，第二个参数则是用户声明的第二个模板参数的默认构造函数(如果是 int，则调用 int的构造函数，如果是 string ，则默认构造 string)。

pair<iterator, bool> result = insert(make_pair(key, V()));

然后我们返回迭代器指向的 pair 数据中的second。

//result.first取出迭代器，使用->运算符重载取出data地址，访问second并返回
return result.first->second;

完整的函数书写如下：

V& operator[](const K& key)
{
	pair<iterator, bool> result = insert(make_pair(key, V()));
	//如果存在，则插入失败
	//如果不存在，则插入数据
	//无论是否存在,都返回 second;
	return result.first->second;
}

接下来我们要对红黑树的 Insert 的返回值处进行改动，进而契合 map 的 pair 数据类型。改动有三处，这里贴图大家观察即可。

测试：

三、源代码+测试用例

3.1 map/set 

namespace brant
{
	template<class K,class V>
	class Map
	{
	public:
		struct MapKeyOfvalue
		{
			const K& operator()(const std::pair<K, V>& kv)
			{
				return kv.first;
			}
		};
		//外层要想使用红黑树的iterator，
		typedef typename RBTree<K, pair<K, V>, MapKeyOfvalue>::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);
		}
		void InOrder()
		{
			_t.Inorder();
		}
		V& operator[](const K& key)
		{
			pair<iterator, bool> result = insert(make_pair(key, V()));
			return result.first->second;
		}
	private:
		RBTree<K, pair<K,V>, MapKeyOfvalue> _t;
	};

    template<class K>
	class Set
	{
		struct SetKeyOfvalue
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K, K, SetKeyOfvalue>::iterator iterator;
		iterator begin()
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();
		}
		
		pair<iterator, bool> insert(const K& key)
		{
			return _t.Insert(key);
		}

		void InOrder()
		{
			_t.Inorder();
		}
	private:
		RBTree<K, K, SetKeyOfvalue> _t;
	};
}

3.2 迭代器

enum Color { RED, BLACK };
template <class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;	
	RBTreeNode<T>* _right;	
	RBTreeNode<T>* _parent;	
	T _data;
	Color _col;					

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

//			 节点数据	引用/const引用  指针/const指针
template <class T,class Ref,class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __RBTreeIterator<T, Ref, Ptr> self;
	typedef __RBTreeIterator<T, Ref, Ptr> iterator;
	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;
			//则寻找右子树的最左节点
			while (left->_left)
			{
				left = left->_left;
			}
			_node = left;
		}
		//如果右子树不存在
		else
		{
			//找孩子不是父亲右的节点
			Node* parent = _node->_parent;
			Node* cur = _node;
			while (cur == parent->_right)
			{
				cur = cur->_parent;
				parent = parent->_parent;
				//防止最后一个节点寻找祖先导致程序崩溃
				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::Set<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(3);
	s.insert(4);
	s.insert(5);
	brant::Set<int>::iterator it_set = s.begin();
	cout << "set:" << endl;
	while (it_set != s.end())
	{
		cout << *it_set << " ";
		it_set++;
	}
	cout << endl;

	brant::Map<int, int> m;
	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<int, int>::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::Map<string, int> countMap;
	for (auto& str : arr)
	{
		countMap[str]++;
	}

	brant::Map<string, int>::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 红黑树

只截取了改动和增添的部分。原来的红黑树在这.


template <class K, class T,class KeyOfvalue>
class RBTree
{
	typedef RBTreeNode<T> Node;

public:
	typedef __RBTreeIterator<T, T&, T*> iterator;
	typedef __RBTreeIterator<T, const T&, const T*> const_iteraotr;
	
	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)
{
	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);
	//插入成功，返回新增节点 
	//注意：cur 可能会改变(情况1变色处理,cur指向可能会改变)
	//使用newnode记录新创建节点的地址
	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);
}
};

 

版权声明：本文为Brant_zero原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
Tags: