【C++】万字详解 set 与 map 的模拟实现

利刃大大

发布于 2025-02-21 08:42:39

8600

代码可运行

文章被收录于专栏：csdn文章搬运csdn文章搬运

运行总次数：0

代码可运行

Ⅰ. 前言

我们前面实现了红黑树的插入以及删除（删除有一点 bug ），因此我们就能用其来实现 map 以及 set，这里只涉及了之前红黑树的插入，因为我们的重点是 map 与 set 是如何同时使用红黑树实现的以及红黑树的迭代器是如何实现的！

Ⅱ. 对红黑树模板参数的改造

一起回忆一下，之前红黑树的参数模板我们是这样子实现的：

enum Color
{
	BLACK,
	RED
};

template <class K, class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K, V>& kv, Color col = RED)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _col(col)
	{}

	RBTreeNode<K, V>* _left;   // 节点的左孩子
	RBTreeNode<K, V>* _right;  // 节点的右孩子
	RBTreeNode<K, V>* _parent; // 节点的双亲（红黑树需要旋转，为了实现简单给出该字段）
	pair<K, V> _kv; // 节点的键值对
	Color _col;     // 节点的颜色
};
template <class K, class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
    //.....
    
private:
	Node* _root;
};

有没有发现，我们实现的时候默认用的就是 <K, V> 结构，也就是 map 的结构，但是 set 呢？重写一个红黑树把结构变成 <K, K>？这样子就造成了数据冗余了！因为其实我们是可以去复用的，我们去 STL 中看看是怎么实现的！

很妙是吧，STL 中的红黑树的 Value 其实接收的 map 和 set 里面分别传过来的数据类型，如果是 set 的 Value 就是 Key，而如果是 map 则 Value 就是 pair<const Key, T> ！这就达到了一棵红黑树就可以封装 map 和 set 啦！

但是很快新的问题就来了！

还记得我们实现红黑树的 Insert 吗，如下：

bool Insert(const T& data)
{
    // .......
    while (cur)
    {
        if (cur->_data > data) // 这里对比的时候如果是map，因为map的_data是pair类型，无法直接对比
        {
            parent = cur;
            cur = cur->_left;
        }
        else if (cur->_data < data)
        {
            parent = cur;
            cur = cur->_right;
        }
        else
        {
            return false;
        }
    }
    // .......
}

可以发现我们之前写的红黑树的插入好像走不通了，因为这里的 data 的类型是 T，但是编译器不知道什么时候传的是 set 的数据类型还是 map 的数据类型，这就导致了在比较的时候出错，那该咋办呀？

我们再去 STL 中瞅一瞅哈哈哈！

可以看出，STL 中是通过传递仿函数来实现 map 和 set 的不同数据类型的通用比较。

通俗的讲，就是如果是 set，就用 set 的比较器比较；如果是 map，就用 map 的比较器比较！

// set的比较器仿函数
struct SetKeyOfT
{
    const K& operator()(const K& key)
    {
        return key;
    }
};

// map的比较器仿函数
struct MapKeyOfT
{
    const K& operator()(const pair<const K, V>& kv)
    {
        return kv.first;
    }
};

然后接下来我们对红黑树的插入进行一些修改:

private:
	KeyOfT _kt; // 仿函数对象，这个也可以定义在函数里面
public:
    pair<iterator, bool> Insert(const T& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            _root->_col = BLACK;
            return make_pair(iterator(_root), true);
        }

        // 寻找要插入的位置
        Node* cur = _root;
        Node* parent = nullptr;
        while (cur)
        {
            if (_kt(cur->_data) > _kt(data)) // 将他们的key分别提取出来
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (_kt(cur->_data) < _kt(data)) // 将他们的key分别提取出来
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                return make_pair(iterator(cur), false);
            }
        }

        // 插入新节点并将新节点的颜色设为红色
        // ......
        if (_kt(parent->_data) > _kt(data)) // 将他们的key分别提取出来
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_right = cur;
            cur->_parent = parent;
        }

        // 控制平衡
        // ......

        return make_pair(iterator(newnode), true);
    }

But…好像还有一个问题，STL 库中实现的 insert 返回的值是 pair<iterator, bool>，但是我们红黑树还没有实现迭代器呀，所以我们下面就得好好来讲一下红黑树的迭代器！

一、红黑树的迭代器

迭代器的好处是可以方便遍历，是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代器，需要考虑以下问题：

begin() 与 end()

我们先来参考一下 STL 中是如何定义 begin 和 end 的：

STL 明确规定，begin() 与 end() 代表的是一段前闭后开的区间，而对红黑树进行中序遍历后，可以得到一个有序的序列，因此：begin() 可以放在红黑树中最小节点 ( 最左侧节点 ) 的位置，end() 放在最大节点 ( 最右侧节点 ) 的下一个位置，关键是最大节点的下一个位置在哪块？能否给成 nullptr 呢？答案是行不通的，因为 对 end() 位置的迭代器进行一一操作，必须要能找最后一个元素，此处就不行，因此最好的方式是将 end() 放在头结点的位置。 但是我们在模拟实现的时候做了简化，也就是让 end 指向 nullptr，但其实这是有缺陷的！

template <class K, class T, class KeyOfT>
class RBTree
{
public:
    typedef TreeIterator<T, T&, T*> iterator; // 为了通过复用实现const版本，这里传三个模板参数给迭代器
    typedef TreeIterator<T, const T&, const T*> const_iterator;
public:
    iterator begin()
    {
        Node* cur = _root;
        while (cur && cur->_left) // 找到最左节点
        {
            cur = cur->_left;
        }
        return iterator(cur);
    }

    iterator end()
    {
        return iterator(nullptr); // 以nullptr作为end
    }
}

🌵 除此之外，这里还有一个重点：回忆一下实现 list 的迭代器的时候，为了能够复用的去实现 const 版本的迭代器，我们这里传三个模板参数给迭代器，当我们需要 const 的迭代器的时候，只需要将模板参数改为 const 即可！详细的参考 list 中的实现！

operator++() 与 operator–() 有了 begin() 和 end() 之后我们就可以来构造我们的迭代器了，那么其实红黑树的迭代器最重要的就是两个：operator++ 和 operator--（注意由于我们自己实现的 end 是指向 nullptr 的，所以实现细节会有点不一样）

对于 operator++()：

如果目前节点存在右子树，则让 cur 移动到右子树的最左节点
如果目前节点不存在右子树，说明该节点已经访问完毕，则向上寻找节点不是祖先节点的右子树的那个节点（直到走到空或者找到该节点为止）

对于 operator--()：

如果目前节点存在左子树，则让 cur 移动到左子树的最右节点
如果目前节点不存在左子树，说明该节点已经访问完毕，则向上寻找节点不是祖先节点的左子树的那个节点（直到走到空或者找到该节点为止）

Self& operator++()
{
    // 若右子树不为空，则去访问右子树中序的那个，即右子树的最左节点
    if (_node->_right != nullptr)
    {
        Node* cur = _node->_right;
        while (cur->_left)
            cur = cur->_left;

        _node = cur;
    }
    else // 若右子树为空，说明_node节点已经访问完了，则向上查找为祖先的左的节点
    {
        Node* cur = _node;
        Node* parent = _node->_parent;
        while (parent && parent->_right == cur)
        {
            cur = parent;
            parent = parent->_parent;
        }

        _node = parent;
    }
    return *this;
}

Self operator++(int) // 后置++
{
    Self tmp = *this;
    this->operator++();  // 这里不能直接这样调用++_node
    return tmp;
}

Self& operator--()
{
    // 若左子树不为空，则去访问左子树中序的那个，即左子树的最右节点
    if (_node->_left != nullptr)
    {
        Node* cur = _node->_left;
        while (cur->_right)
            cur = cur->_right;

        _node = cur;
    }
    else // 若左子树为空，说明_node节点已经访问完了，则向上查找为祖先的右的节点
    {
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && parent->_left == cur)
        {
            cur = parent;
            parent = parent->_parent;
        }

        _node = parent;
    }
    return *this;
}

Self operator--(int) // 后置--
{
    Self tmp(*this);
    this->operator--();
    return tmp;
}

至此我们就将红黑树的迭代器最重要的部分讲完啦，我们将其他部分也实现出来，等会顺便适配一下反向迭代器！

🐛 迭代器的完整代码：

template <class T, class Ref, class Ptr>
struct TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef TreeIterator<T, Ref, Ptr> Self;

	// 给反向迭代器中用的
	typedef Ref Ref;
	typedef Ptr Ptr;

	TreeIterator(Node* node)
		:_node(node)
	{}

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

	Ptr operator->()
	{
		return &(_node->_data);
	}

	Self& operator++();
	Self operator++(int);
	Self& operator--();
	Self operator--(int);

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

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

	Node* _node;
};

🔺 注意： 这里大部分其实和实现 list 迭代器是一样的，所以详细的可以参考 list 的迭代器！

二、红黑树的反向迭代器

有了正向迭代器，我们就可以给红黑树适配出一个反向迭代器啦！

🏗 事实上，我们只要有了一个统一写法的反向迭代器，只要我们存在一个正向迭代器，那么它的反向迭代器就自然出来了！通俗的说，反向迭代器是适配器！

🚗 但是值得注意的是当我们 在反向迭代器中去取迭代器中的模板类型如 Ref 的时候，需要加 typename 声明一下该模板类型，代表它是存在的，因为如果不在 typename，此时正向迭代器其实还没实例化，所以我们没法从中取出其模板类型。（具体也可以参考 list 的反向迭代器中的讲解）

// 反向迭代器--迭代器适配器
// 放在"Iterator.h"
template <class Iterator>
struct ReverseIterator
{
	typedef ReverseIterator<Iterator> Self;
    
    // 要用typename去取iterator中的类型
	typedef typename Iterator::Ref Ref;
	typedef typename Iterator::Ptr Ptr;

	ReverseIterator(Iterator it)
		:_it(it)
	{}

	Ref operator*()
	{
		return *_it;
	}

	Ptr operator->()
	{
		return _it.operator->();
	}

	Self& operator++()
	{
		--_it;
		return *this;
	}

	Self operator++(int)
	{
		Self tmp(*this);
		--_it;
		return tmp;
	}

	Self& operator--()
	{
		++_it;
		return *this;
	}

	Self operator--(int)
	{
		Self tmp(_it);
		++_it;
		return tmp;
	}

	bool operator!=(const Self& s) const
	{
		return _it != s._it;
	}

	bool operator==(const Self& s) const
	{
		return _it == s._it;
	}

	Iterator _it;
};

三、改造完后的红黑树整体框架

#include "Iterator.h" // 反向迭代器的头文件
enum Color
{
	BLACK,
	RED
};

template <class T>
struct RBTreeNode
{
	RBTreeNode(const T& data)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _data(data)
		, _col(RED)
	{}

	RBTreeNode<T>* _left;   // 节点的左孩子
	RBTreeNode<T>* _right;  // 节点的右孩子
	RBTreeNode<T>* _parent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)
	T _data; 	// 节点的值域
	Color _col; // 节点的颜色
};

template <class T, class Ref, class Ptr>
struct TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef TreeIterator<T, Ref, Ptr> Self;

	// 给反向迭代器中用的
	typedef Ref Ref;
	typedef Ptr Ptr;

	TreeIterator(Node* node)
		:_node(node)
	{}

	Ref operator*();

	Ptr operator->();

	Self& operator++();

	Self operator++(int);

	Self& operator--();

	Self operator--(int);

	bool operator!=(const Self& s) const;

	bool operator==(const Self& s) const;

	Node* _node;
};

template <class K, class T, class KeyOfT>
class RBTree
{
public:
	typedef RBTreeNode<T> Node;
	typedef TreeIterator<T, T&, T*> iterator;
	typedef TreeIterator<T, const T&, const T*> const_iterator;
	typedef ReverseIterator<iterator> reverse_iterator;
	// typedef ReverseIterator<const_iterator> const_reverse_iterator; 可以有的，但是这里就不写了
public:
	RBTree()
		:_root(nullptr)
	{}

    // 拷贝构造
	RBTree(const RBTree<K, T, KeyOfT>& t)
	{
		_root = Copy(t._root);
	}

    // 赋值重载
	RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
	{
		swap(t._root, _root);
		return *this;
	}

	~RBTree()
	{
		Destory(_root);
		_root = nullptr;
	}

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

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

	reverse_iterator rbegin()
	{
		Node* cur = _root;
		while (cur && cur->_right)
		{
			cur = cur->_right;
		}
		return reverse_iterator(iterator(cur));
	}

	reverse_iterator rend()
	{
		return reverse_iterator(iterator(nullptr));
	}

	pair<iterator, bool> Insert(const T& data);
	Node* find(const K& key);
	void RotateL(Node* parent);
	void RotateR(Node* parent);
	bool _CheckBlance(Node* root, int blackNum, int count);
	bool CheckBlance();

	void Destory(Node* root)
	{
		if (root == nullptr)
			return;
		Destory(root->_left);
		Destory(root->_right);
		delete root;
	}

	Node* Copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;

		Node* copynode = new Node(root->_data);
		copynode->_col = root->_col;
		copynode->_left = Copy(root->_left);
		copynode->_right = Copy(root->_right);

		// 将孩子节点的_parent链接上
		if (copynode->_left)
			copynode->_left->_parent = copynode;
		if (copynode->_right)
			copynode->_right->_parent = copynode;

		return copynode;
	}
private:
	KeyOfT _kt;
	Node* _root;
};

Ⅲ. set的模拟实现

从上面的改造红黑树，我们其实也可以发现 set 和 map 就是包装的红黑树啦，很多操作其实就是依赖着红黑树，所以这里就不细讲了，无非就是一些迭代器等等的 typedef 以及插入的返回值等等，具体参考红黑树的笔记！

🐛 值得注意就是这里传给红黑树的 Key 和 Value 都是 Key，以及一个比较器！

#include "RBTree.h"

namespace liren
{
	template <class K>
	class set
	{
	public:
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator;
	public:
		iterator begin()
		{
			return _t.begin();
		}

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

		reverse_iterator rbegin()
		{
			return _t.rbegin();
		}

		reverse_iterator rend()
		{
			return _t.end();
		}

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

Ⅳ. map的模拟实现

🐛 与 set 不同的是，map 多了一个 operator[]，以及传给红黑树的 Key 是 Key，但是 Value 是 pair<const K, Value>，其他都基本一样！

#include "RBTree.h"

namespace liren
{
	template <class K, class V>
	class map
	{
	public:
		struct MapKeyOfT
		{
			const K& operator()(const pair<const K, V>& kv)
			{
				return kv.first;
			}
		};
	public:
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::reverse_iterator reverse_iterator;
	public:
		iterator begin()
		{
			return _t.begin();
		}

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

		reverse_iterator rbegin()
		{
			return _t.rbegin();
		}

		reverse_iterator rend()
		{
			return _t.end();
		}

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

		V& operator[](const K& key)
		{
			pair<iterator, bool> res = insert(make_pair(key, V()));
			return res.first->second;
		}
	private:
		RBTree<K, pair<const K, V>, MapKeyOfT> _t;
	};
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-20，如有侵权请联系 cloudcommunity@tencent.com 删除

iterator