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

所用编译器：VS2019

[TOC]

1 set

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

1.1 构造函数、迭代器

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

image-20220914183344425

image-20220914183432951

1.2 节点计数 size

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

image-20220914183452192

1.3 插入删除

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

image-20220914183820052

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

image-20220914190146549

1
2
3
4
5
6
set<int>t1;//定义 set 对象 t1

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

删除可以删除：

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

image-20220914190132193

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

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

1.4 查找find

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

image-20220914183937192

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

image-20220914184006728

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

1
2
3
4
5
6
7
8
9
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;
}

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

image-20220914184552582

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

image-20220914184727241

1.5 count

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

image-20220914184906876

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

multiset支持键值冗余

这个函数真正起作用的地方是在multiset，人如其名，这是一个支持键值冗余的set，成员函数完全相同。第一个模板变量是set的参数类型，第二个是比较函数，第三个是一个空间配置器

1
2
3
4
template < class T,                        // multiset::key_type/value_type
           class Compare = less<T>,        // multiset::key_compare/value_compare
           class Alloc = allocator<T> >    // multiset::allocator_type
           > class multiset;

image-20220914185118689

1.6 lower/upper_bound

image-20220914185452204

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

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

image-20220914185703890

image-20220914185857749

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

image-20220914185832199

image-20220914190026131

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

2 map

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

image-20220914190819875

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

2.1 插入

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

image-20220914191601632

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

2.2 下标访问/at

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

1
map[key]=value;

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

image-20220914192353480

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

image-20220914192938536

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

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

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

image-20220914193216317

image-20220914193524468

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

image-20220914193723870

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

image-20220914193811435

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

2.3 下标访问自定义类型必须要有默认构造函数

如题，如果你想在map里面插入一个自定义类型，使用emplace和insert的时候不会出现问题，但是使用[]重载就会有编译错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class mytestint
{
public:
    mytestint(uint16_t id, uint16_t pr) : _id(id), _pr(pr) {}

    uint16_t get_id() const
    {
        return _id;
    }

private:
    uint16_t _id;
    uint16_t _pr;
};

这里我有一个自定义类型，内部只实现了一个有参构造函数，没有无参构造。

此时调用下标重载，就会出现问题

1
2
3
4
5
6
7
8
9
10
map<uint16_t, mytestint> _test_map;

void test_emplace(uint16_t id, uint16_t pr, const std::string &info)
{
    mytestint temp = {id, pr};
    auto t = _test_map.emplace(id, temp); // good
    auto s = _test_map.insert({pr, temp});// good
    _test_map[id] = temp; // error
    auto h = _test_map[pr]; // error
}

编译这个代码，会出现如下报错（如果去掉最后两个下标的访问，只用insert和emplace是不会有报错的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/usr/include/c++/11/tuple:1820:9: error: no matching function for call to ‘mytestint::mytestint()’
 1820 |         second(std::forward<_Args2>(std::get<_Indexes2>(__tuple2))...)
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from test.cpp:1:
src/main.hpp:51:5: note: candidate: ‘mytestint::mytestint(uint16_t, uint16_t)’
   51 |     mytestint(uint16_t id, uint16_t pr) : _id(id), _pr(pr) {}
      |     ^~~~~~~~~
src/main.hpp:51:5: note:   candidate expects 2 arguments, 0 provided
src/main.hpp:47:7: note: candidate: ‘constexpr mytestint::mytestint(const mytestint&)’
   47 | class mytestint
      |       ^~~~~~~~~
src/main.hpp:47:7: note:   candidate expects 1 argument, 0 provided
src/main.hpp:47:7: note: candidate: ‘constexpr mytestint::mytestint(mytestint&&)’
src/main.hpp:47:7: note:   candidate expects 1 argument, 0 provided
make: *** [makefile:2: test] Error 1

如果给mytestint类添加一个默认构造，则不会有编译错误

1
mytestint() = default;

2.4 迭代器失效问题

https://zh.cppreference.com/w/cpp/container/map/erase

在cppreference网站上有记录，对于map/set而言，erase会让指向被删除元素的迭代器失效，其他元素的迭代器不受影响。因为map/set本质是个二叉树（红黑树），每一个节点都是独立的，删除一个节点可能会影响其他节点之间的关联关系，但不会让其他节点的迭代器直接失效。

image.png

所以在循环的时候，如果你想删除某个元素，应该如下操作

1
2
// 先itr++，然后返回itr++之前的值给erase函数
testMap.erase(itr++);

下面给个测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
   // 测试map迭代器失效的情况
   map<string, int> testMap;
   testMap["a"] = 10;
   testMap["b"] = 20;
   testMap["c"] = 30;
   testMap["d"] = 40;
   testMap["e"] = 50;
// 尝试在for中删除一个元素
   for (auto itr = testMap.begin();itr!=testMap.end();itr++)
   {
       if(itr->first == "c"){
           testMap.erase(itr);
       }
       cout << itr->first << "-" << itr->second << "\n";
   }

这种情况下，因为我们没有进行itr++还访问了c的迭代器，直接段错误了（也不一定每次都会段错误）

1
2
3
4
5
❯ g++  test.cpp -o test1 && ./test1
a-10
b-20
c-30
[1]    13583 segmentation fault  ./test1

如果加上，就不会出现问题，能正常跳过c元素，往后遍历

1
2
3
4
5
6
7
for (auto itr = testMap.begin();itr!=testMap.end();itr++)
{
    if(itr->first == "c"){
        testMap.erase(itr++);
    }
    cout << itr->first << "-" << itr->second << "\n";
}

输出如下

1
2
3
4
5
❯ g++  test.cpp -o test1 && ./test1
a-10
b-20
d-40
e-50

3.模拟实现

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

3.1 康康STL源码

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

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

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

image-20220906105003709

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

image-20220906105224111

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

image-20220906105415100

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

image-20220906105611300

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

image-20220906110313780

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

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

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

image-20220906110712498

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

3.2 模拟实现的基础框架

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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)
	{}
};

3.3 修改插入的代码

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
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
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);
}

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

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

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

3.4 迭代器✨

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

3.4.1 加减操作

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

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

image-20220909091851584

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

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

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

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

image-20220909094915704

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

image-20220909110332143

转换为代码如下

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

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

image-20220909141007124

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

3.4.2 套上完整迭代器模板

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

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

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

3.4.3 添加参数到红黑树类中

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

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
//迭代器封装，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);
}

image-20220909103832130

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

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

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

3.5 重载下标

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

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

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

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

测试一下，咩有问题 OJBK👍

image-20220909104329256

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

4.更多操作

4.1 用set得出两组数据的重合处

假设有两个文件，我们现需要找到这两个文件的重合处

  • 设置两个set，分别插入两个文件的内容
  • 同时遍历两个set（从小到大）
    • 如果两个set的key相同，则取出这个相同值，两个set一起++
    • 如果不相同，则++那个小的key
  • 其中一个set结束遍历，即代表重合处查找完毕！

结语

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

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

image-20220909141114564