【C++】STL：map/set，使用红黑树模拟实现

本篇博客让我们来了解一下STL库里面的map/set的使用，并尝试用自己写的红黑树封装一个类似的map/set出来

所用编译器：VS2019

1 set

set就是二叉搜索树中只有单个key的树，它有下面的函数可供使用

1.1 构造函数、迭代器

构造函数、迭代器什么的都很简单，在这里就提到了，和其他STL基本一致

1.2 节点计数 size

set自带节点计数，我们可以之间获取二叉树中节点的个数，或判断set是否为空

1.3 插入删除

插入删除等函数在这里不过多解释，使用方法和string、vector完全一致。如果大家的stl是从string一路学习过来，那么对于这些函数的使用肯定没有问题！

插入可以插入单个元素，其返回一个键值对包含这个元素的迭代器+一个bool标识是否插入成功。你还可以用相同类型set的迭代器区间进行插入操作

	set<int>t1;//定义 set 对象 t1

	for (int i = 0; i <= 3; ++i) 
	{ // 插入 1 2 3 4 5 6
		t1.insert(i);
	}
1
2
3
4
5
6

删除可以删除：

• 指定迭代器位置
• 指定元素
• 迭代器区间

不过对于二叉搜索树而言，删除一直都不是高频操作+效率较低。这也是为什么在实现二叉搜索树的时候，我没有去实现删除操作。

其实主要是删除操作比较难理解，特别是在平衡二叉树中

1.4 查找find

作为搜索二叉树，查找才是最重要的一个函数。该函数会返回一个迭代器，指向元素的位置。

如果没有找到这个元素，则返回end迭代器

所以我们只需要在使用这个函数的时候，加上对于end()迭代器的判断，只要不等于end说明找到了该元素，进行访问

	set<int> v1;
	v1.insert(1);
	v1.insert(3);
	v1.insert(6);
	set<int>::iterator it = v1.find(3);
	if (it != v1.end())
	{
		cout << "找到了 "<< *it << endl;
	}
1
2
3
4
5
6
7
8
9

因为set是只有key的搜素二叉树，在获取到迭代器之后，我们直接使用*it进行解引用即可得到节点的值

而当我们查找内部不存在的元素，也可以得知没有找到

---

1.5 count

这个函数的作用是查找二叉树中value值的个数。但由于默认的set不支持键值冗余，插入相同的键值会被忽略掉。所以这个count在这里只有0和1两个返回值，也只能用来判断该值是否存在。

但是因为count需要遍历所有元素，所以在set中，它的效率比find是更差的。

multiset支持键值冗余

这个函数真正起作用的地方是在multiset，人如其名，这是一个支持键值冗余的set，成员函数完全相同。

---

1.6 lower/upper_bound

iterator lower_bound (const value_type& val);   // 返回指向等于或大于指定键值元素的迭代器
iterator upper_bound (const value_type& val);   // 返回指向大于指定键值元素的迭代器
1
2

这两个函数的作用是返回一个和我们指定的元素相同/或者比指定元素更大（第一个更大的键值）的迭代器

如果更大的键值或者它本身不存在，就会返回一个end迭代器，这一点和find一样

set基本用得到的迭代器这里都提了一嘴，接下来康康map

2 map

map同样有一个支持键值冗余的multimap，后面就不说辣

前面关于构造函数都暂且不提，直接来看map和set最不一样的地方，插入

2.1 插入

map是一个kvl二叉搜索树，其所有元素都是一个键值对。这就要求我们插入的时候，需要先make_pair建立一个键值关系，再插入进map中。

也因为迭代器获取到的是一个键值对，所以访问的时候需要指定键值对的first和second。map是用first进行排序的，所以first是不能修改的，但是second可以

2.2 下标访问/at

map相比于set，最特殊的一点就是它可以用下标直接进行访问

map[key]=value;
1

所以我们可以使用这种方式非常方便的修改value

和重载了下标的vector一样，map也有一个at函数（C++11新增）在之前vector的函数中，我没有提到这两个的区别。在这里说一下

operator[]和at的主要区别在于operator[]不做边界检查，而at会做边界检查。

• 由于operator[]不做边界检查， 那怕越界了也会返回一个引用，当然这个引用是错误的引用，如何不小心调用了这个引用对象的方法，会直接导致应用退出。
• 而由于at会做边界检查，如果越界，会抛出异常，应用可以try/catch这个异常，进行异常管理，而应用还能继续运行。

at的使用和下标不太一样，和成员函数的使用方法一致。我们可以来试一试

在这里如果我们下标访问第11个元素，也不会出问题。因为下标访问会自动创建一个对应的key，而value会调用默认构造函数。int类型也是有默认构造的，返回一个0

但如果我们不用下标，直接用at访问第11个元素，就会报debug错误，这便是它们俩的区别所在

---

map和set有区别的地方主要就是上面两个函数，其余都是完全相同

我们直接快进到模式实现吧！

3.模拟实现

这里主要以KV键值对的map为例，set只需要修改keyofValue和它自己的模板参数即可

3.1 康康STL源码

利用红黑树实现map和set之前，我们需要先来思考一个问题：我们自己写的红黑树只有一个KV键值对，那么要怎么判断封装的是map还是只有key的set呢？

• 先来看看STL库的源码吧！【链接】

在map.h的第68行可以看到，实际上库函数里面的map和set都只是封装了红黑树

再去找红黑树的头文件，就能看到其与我们实现的不同。这里面的红黑树总共有5个模板参数，除去最后一个用来申请内存空间的alloc，其余4个都有其不同的用处

而其中的value是用来构造红黑树节点的参数

看起来好像差不多对吧？可再回头看看map，其传入的value是一个pair！

实际上，库中的红黑树，并不是一个简单的kvl，其k并不是真正用于比较的k，而是依靠第三个模板参数keyofvalue，以及我们传入的比较函数compore来进行比较的

说人话就是：RBtree不会判断你是map还是set，而是在map和set的封装端，根据数据的不同类型，传入对应的比较函数，以及键值。

• 比如set的keyofvalue就是它自己的key
• 而map的keyofvalue是pair.first

因为库函数里面pair的比较，是会比较first之后，再比较second的。

这和我们搜索二叉树的需求不太符合，所以STL库里面就需要写一个比较大小的仿函数，只针对pair的first进行严格比较，以保证稳定性

---

3.2 模拟实现的基础框架

如果我们自己模拟实现，则可以依据下面的模板进行操作

// 模板参数V决定红黑树存什么数据
// set: RBTree
// map: RBTree>
// KeyOfV: 取出V对象中key的仿函数
template<class K, class V, class KeyOfV>
1
2
3
4
5

而节点类也需要进行对应的修改，不再默认创建一个键值对。而是直接用V来创建一个基本的类型，这就和最基础的搜索二叉树相同。

template<class V>
struct RBTreeNode
{
	RBTreeNode<V>* _left;
	RBTreeNode<V>* _right;
	RBTreeNode<V>* _parent;
	V _data;

	//AVL树的平衡因子，在红黑树中为颜色
	Color _col;
	//插入节点的时候，默认为红色
	//因为这个满足性质3且不会破坏性质4
	RBTreeNode(const V& data)
		:_data(data),
		_left(nullptr),
		_right(nullptr),
		_parent(nullptr),
		_col(RED)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.3 修改插入的代码

因为新增了模板参数，所以这里我们也不能通过kv first进行键值的比较了。我们需要里利用模板参数中的KeyOfV仿函数来进行比较的操作。

在这里，先给出map和set两种KeyOfV仿函数的实现

struct MapKeyOfV
{
    const K& operator()(const pair<K, V>& kv)
    {
        return kv.first;//map是键值对，需要提供kv的first进行比较
    }
};
struct SetKeyOfV
{
    const K& operator()(const K& key)
    {
        return key;//set只有一个键值
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

有了这个仿函数，我们只需要实例化一个对象，然后将原有的比较替换成仿函数在进行比较即可！

pair<iterator,bool> Insert(const V& data)
{
    //判断root为空，即空树
    if (_root == nullptr)
    {
        _root = new Node(data);
        _root->_col = BLACK;//这里必须要手动给黑色
        return make_pair(iterator(_root),true);
    }
    //kv树的操作
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
        //利用key来判断，寻找待插入的位置
        if (kov(cur->_data)< kov(data))
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (kov(cur->_data) > kov(data))
        {
            parent = cur;
            cur = cur->_left;
        }
        else {
            return make_pair(iterator(cur), false);//构造一个迭代器返回
        }
    }
    //找到位置后插入节点
    cur = new Node(data);
    Node* newnode = cur;
    if (kov(parent->_data) < kov(data))
    {
        parent->_right = cur;
    }
    else
    {
        parent->_left = cur;
    }
    cur->_parent = parent;

    //插入之后需要向上更新颜色,只有出现连续红色之后才需要更新
    while (parent && parent->_col==RED)
    {
        Node* grandpa = parent->_parent;//祖父
        assert(grandpa);//祖父为空不需要进行操作

        //p是g的左
        if (parent == grandpa->_left)
        {
            Node* uncle = grandpa->_right;
            //情况1：插入后p是红，u存在且是红（不需要旋转）
            if (uncle && uncle->_col == RED)
            {
                uncle->_col = BLACK;
                parent->_col = BLACK;
                grandpa->_col = RED;//祖父变成红
                //继续向上调整
                //cur = cur->_parent;
                //parent = parent->_parent;
                cur = grandpa;
                parent = cur->_parent;
            }
            else//(uncle && uncle->_col == BLACK)
            {
                //情况2：插入后p为红，u存在且为黑（需要单旋）
                if (cur == parent->_left)
                {
                    RotateR(grandpa);//因为p在g的左边，所以右旋
                    parent->_col = BLACK;
                    grandpa->_col = RED;
                }
                else//cur == parent->_right
                {
                    //情况3：不是在同一侧，双旋
                    //   g
                    // p
                    //   c
                    RotateL(parent);
                    RotateR(grandpa);
                    grandpa->_col = RED;//祖父改成红色
                    cur->_col = BLACK;//自己成为了这里的根，需要改成黑的
                }
                break;
            }
        }
        else {
            Node* uncle = grandpa->_left;
            //情况1：插入后p是红，u存在且是红（不需要旋转）
            if (uncle && uncle->_col == RED)
            {
                uncle->_col = BLACK;
                parent->_col = BLACK;
                grandpa->_col = RED;//祖父变成红
                //继续向上调整
                cur = grandpa;
                parent = cur->_parent;
            }
            else//(uncle && uncle->_col == BLACK)
            {
                //情况2：插入后p为红，u存在且为黑（需要单旋）
                if (cur == parent->_right)
                {
                    RotateL(grandpa);//因为p在g的左边，所以右旋
                    parent->_col = BLACK;
                    grandpa->_col = RED;
                }
                else//cur == parent->_left
                {
                    //情况3：不是在同一侧，双旋
                    //   g
                    //		p
                    //   c
                    RotateR(parent);
                    RotateL(grandpa);
                    grandpa->_col = RED;//祖父改成红色
                    cur->_col = BLACK;//自己成为了这里的根，需要改成黑的
                }
                break;
            }
        }
    }

    //不管是什么情况，最后都把根改成黑，符合条件2
    _root->_col = BLACK;
    return make_pair(iterator(newnode), true);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

这里说明一下为何要把返回值替换成键值对。因为在实际操作的时候，我们需要获取道新插入元素的迭代器（迭代器的模拟实现会在后面提及），以方便在插入后进行修改value的操作。

比如我们默认插入的是一个空字符串，在进行一些判断之后，再重新给这个键值的value进行修改（仅限于map的情况）

如果不返回一个迭代器，那么想修改这个键值，就只能通过find函数查找后再进行修改，相对有些麻烦。

3.4 迭代器✨

这一部分是比较难理解的迭代器操作，主要就是在一个二叉树中应该如何进行迭代器的++/--操作。

3.4.1 加减操作

如果你看过我之前的stl博客，那么你应该还记得，我们的模拟实现迭代器其实就是用指针来进行的。迭代器的使用方法也和指针相差无几。

在此处我们选择使用中序遍历来进行迭代器的操作。中序遍历的基本情况就是左根右，只不过我们这里不再能使用递归进行操作了，而需要使用迭代的方法。

上图中cur遍历到了右子树，其左右子树都为空。这时候我们需要返回到的是根节点，准确来说是祖父节点——吗？要是cur的父亲prev不是g节点的左子树，我们就不能直接返回g进行打印！而需要返回g的左子树。

总结出来的规律如下，当我们执行++操作的时候：

• 如果右节点为空，当前节点是父亲的右侧，就需要继续往上找（我们需要找到父亲左侧的那个节点）
• 如果右子树不为空，找右子树的最左节点。

在上图中，prev就是g的左子树，所以我们只需要找到prev就行了。然后因为我们的prev的右子树已经遍历过，所以这时候就需要往上。因为g是根节点，所以就需要返回g的右子树的最左节点，也就是下图中的位置

而当我们做到最右侧的节点时，再次++的时候其实已经遍历完了。这时候右子树为空，开始往上找父亲是祖父左的哪一个。这时候会一直找到根，而根的父亲为空，停止遍历

转换为代码如下

	Self& operator++()
	{
		if (_node->_right == nullptr)
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			//只要当前节点是父亲的右侧，就需要继续往上找
			//我们需要找到是父亲左侧的那个节点。
			while (parent && parent->_right == cur)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			//如果不符合while的条件，就说明
			//1 父亲为空（根)
			//2 如果cur是父亲的左，那就直接将node设置为父亲
			_node = parent;
		}
		else
		{
			//右子树不为空，找右子树的最左节点
			Node* subLeft = _node->_right;
			while (subLeft->_left)
			{
				subLeft = subLeft->_left;
			}
			//最左节点
			_node = subLeft;
		}

		return *this;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

---

进行--操作的时候则是完全相反的情况。我们需要找到父亲是祖父节点右边的那一个。如果父亲是祖父的左，那就继续往上找。

Self& operator--()
{
    if (_node->_left == nullptr)
    {
        Node* cur = _node;
        Node* parent = cur->_parent;
        //依据中序的顺序，--就是和++反过来。需要找节点是父亲的右边的哪一个
        //如果是父亲的左就继续往上找
        while (parent && cur == parent->_left)
        {
            cur = cur->_parent;
            parent = parent->_parent;
        }
        //指向当前的父亲
        _node = parent;
    }
    else
    {
        // 左子树的最右节点
        Node* subRight = _node->_left;
        while (subRight->_right)
        {
            subRight = subRight->_right;
        }

        _node = subRight;
    }

    return *this;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

3.4.2 套上完整迭代器模板

完成了迭代器的加减操作后，我们只需要套上之前模拟实现的类似模板，再添加参数到红黑树的类中。即可配套好一个迭代器！

template<class V, class Ref, class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<V> Node;
	typedef __RBTreeIterator<V, 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;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

完整代码请参考我的Gitee仓库

3.4.3 添加参数到红黑树类中

我们需要把迭代器写入红黑树的类，并附上普通迭代器和const的两个版本，提供begin和end函数即可。

	//迭代器封装，const和普通版本
	typedef __RBTreeIterator<V, V&, V*> iterator;
	typedef __RBTreeIterator<V, const V&, const V*> const_iterator;
	iterator Begin()
	{
		Node* subLeft = _root;
		while (subLeft && subLeft->_left)
		{
			subLeft = subLeft->_left;
		}

		return iterator(subLeft);
	}

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

	const_iterator Begin() const
	{
		Node* subLeft = _root;
		while (subLeft && subLeft->_left)
		{
			subLeft = subLeft->_left;
		}

		return const_iterator(subLeft);
	}

	const_iterator End() const
	{
		return const_iterator(nullptr);
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

可以看到，迭代器已经可以正常使用了！

这里的测试环节最好把自己写的map套进一个命名空间中，不然就会用到stl库里面的map

迭代器写好之后，范围for也是可以用的

---

3.5 重载下标

map非常特殊的一点就是，可以直接用map[key]=value来修改value的内容。我们模拟实现的时候当然不能落下这个了！

其实操作起来非常简单。我们只需要直接调用插入，如果键值存在也会返回当前键值的迭代器。键值不存在就能直接插入，返回新插入元素的迭代器。这也是之前为啥insert函数没有直接用bool做插入的返回值的原因

//重载下标
V& operator[](const K& key)
{
    pair<iterator, bool> ret = insert(make_pair(key, V()));
    return ret.first->second;//返回的是一个引用，所以可以直接修改
}
1
2
3
4
5
6

因为我们返回的是V的引用，所以可以直接用=进行修改！

测试一下，咩有问题 OJBK👍

set的模拟实现更为简单，这里就不贴出来辣！大家可以去我的gitee看源码，有啥问题可以评论提出！

---

结语

最近感觉自己真的很忙，但又不知在忙什么。事情一个接着一个，虽然学校的课不算多，但事情真的没少多少。

有些事情自己又有拖延症，再加上作息不规律（指下午一睡睡3h），浪费了好多时间……