当前位置：首页 > news >正文

C++中map和set的封装

news 来源：原创 2025/5/14 5:39:56

一、关于封装过程中传入的模板参数的问题

通过源码中的封装方式进行理解：

1.1map和set中成员变量

set中：

template <class Key, class Compare = less<Key>, class Alloc = alloc>
class set
{
public:typedef Key key_type;typedef Key value_type;typedef Compare key_compare;
private:typedef rb_tree<key_type, value_type, identity<value_type>, key_compare, Alloc> rep_type;rep_type t;
}

map中：

template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map
{
public:typedef Key key_type;typedef pair<const Key, T> value_type;typedef Compare key_compare;
private:typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;rep_type t; 
}

观察可以发现，在定义成员变量的时候我们只用了一个t，它是rb_tree类型的，并且对于set来说，我们相当于传了两个相同的key到rb_tree的模板参数列表中

由此可以推断出，实际上的操作大都在类rb_tree中实现，而set与map中很可能只套上了一层外壳

1.2为什么要传入key_type与value_type两个呢？

观察rb_tree的源码来寻找答案

template <class Key, class Value, class KeyOfValue, class Compare,class Alloc = alloc>
class rb_tree {typedef __rb_tree_node_base* base_ptr;
typedef __rb_tree_node<Value> rb_tree_node;typedef __rb_tree_color_type color_type;
}

根据重定义，追溯到结点的定义

template <class Value>
struct __rb_tree_node : public __rb_tree_node_base
{typedef __rb_tree_node<Value>* link_type;Value value_field;
};

根据继承的基类，在此处定义三叉链表和颜色

struct __rb_tree_node_base
{typedef __rb_tree_color_type color_type;typedef __rb_tree_node_base* base_ptr;color_type color; base_ptr parent;base_ptr left;base_ptr right;
};

综合以上观察情况，我们可以得出：

map和set底层都是红黑树rb_tree，

此时他们会传入两个模板key_type与value_type，

对于set来说，传入的是<key，key>

而对于map来说，传入的是<key，pair<const Key, T>>

传入看似冗余的参数原因是：

①在map和set的实现过程中，rb_tree中节点进行typedef需要用到

value_type这一传过来对应Value的模板参数来申请节点，

如 rb_tree 中的

typedef __rb_tree_node<Value> rb_tree_node;

②除此之外，因为我们在find和erase的时候传入的是Key的类型，尤其是对于map来说，很明显不能够传入一个pair<K，V>来进行查找或者删除，所以只有Value很明显是不够的，为此我们要额外传入一个参数key_type对应传过来的参数Key。

1.3参数KeyOfValue的作用

在插入的过程当中，我们的一些操作需要直接对Value进行，但是比较的逻辑应该按照Key的来进行：

这一问题对于set来说还好，但是对于map来说我们却不能直接利用库函数重载的对于pair的比较

（库中pair的对比方式：例如对于<的重载，先看first的大小关系，first小就返回true，first大或者相等会再去比较second的大小关系）因为我们并不希望比较大小的过程涉及到second

为了解决这一问题，我们需要利用仿函数，具体的做法就是：

在rb_tree的模板类型中添加一个特殊的仿函数“KeyOfValue”，同时在map与set中分别实现不同逻辑的“MapKeyOfValue”和“SetKeyOfValue”在其中分别对operator()重载比较逻辑，返回pair中Key的值即可

之后在rb_tree的比较之前声明一个KeyOfValue类型的kot，实现比较逻辑的时候就可以

if(kot(cur->_data) < kot(data))

当然，如果对比较的方式还有要求，还可以再利用正常情况下的仿函数Compare

if(com(kot(cur->_data) , kot(data)))

1.3补:类模板中写本类的类型名，可以直接省略模板参数

如：

template<class K,class T>
class _ma
{//原写法：_ma(const _ma<K,T>& t){}//省略写法_ma(const _ma& t){}
}

这种设置在我们模板参数类型很多的时候可以起到很好的简化代码的作用

二、map与set的迭代器

2.1观察库中代码，理顺迭代器的实现逻辑

set中：

typedef typename rep_type::const_iterator iterator;
typedef typename rep_type::const_iterator const_iterator;

rep_type这一类型是之前对rb_tree类型的重定义，

typedef rb_tree<key_type, value_type, select1st<value_type>, key_compare, Alloc> rep_type;

同时我们发现map中也有完全相同的一句

typedef typename rep_type::iterator iterator;
typedef typename rep_type::const_iterator const_iterator;

由此可以推断map和set的迭代器都使用了rb_tree中的迭代器。

此时我们可以去rb_tree中寻找相应的迭代器来进行观察

在rb_tree中：

public:typedef __rb_tree_iterator<value_type, reference, pointer> iterator;

继续寻找__rb_tree_iterator的定义

template <class Value, class Ref, class Ptr>
struct __rb_tree_iterator : public __rb_tree_base_iterator
{typedef Value value_type;typedef Ref reference;typedef Ptr pointer;typedef __rb_tree_iterator<Value, Value&, Value*>             iterator;typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator;
}

从中可以发现Ref与Ptr这两个模板参数,与vector当中一样，他们也是为了const迭代器服务的；而除此之外，迭代器所需要的各种重载和接口也是在这一层实现的

再看基类：

struct __rb_tree_base_iterator
{typedef __rb_tree_node_base::base_ptr base_ptr;base_ptr node;
};

综合来看，迭代器中真正存的还是一个的__rb_tree_node_base*类型的节点指针

2.2根据库中逻辑进行总结

按照这一逻辑，我么可以选择在自行实现的RBTree中实现一个

template<class T,class Ref ,class Ptr>
struct RBTree_Iterator

其中存一个节点的指针Node* _node;

完成对它的构造，并在map和set中进行对应的typedef，迭代器的框架就搭好了

2.3迭代器类中的运算符重载与接口

2.3.1遍历需要的重载

要实现遍历，我们需要对三个运算符进行重载，它们分别是operator* ,operator++ ,operator!= ,operator->

其中*，->和!=逻辑与之前vector实现的过程类似，此处不再赘述

唯独++在重载过程中有这样一个问题：

红黑树的++需要我们走中序遍历，而不是简单的如链表一般的移动，该怎么做呢？

①首先明确中序遍历是：左子树根右子树

②既然是++，那么其针对的并不一定会是整棵树，也有可能是树中的节点，

因此要实现的话，我们需要以局部的视角来看这个问题

假设：

1>情况一：当传入节点为it(例子中为11)时，传入节点的右子树不为空，++对应的节点就应该是右子树的最左节点(例子中为12)，让_node对应的节点移到新对应节点上

2>情况二：当传入节点为it(例子中为7)时，右子树为空，代表当前子树走完了，根据中序遍历顺序，我们应该沿着到根节点的路径进行查找，直到找到“孩子是父亲的左孩子”此时对应的那一个祖先节点(例子中是8)就是下一个要访问的节点，此时为左子树走完

如果走到了根节点，那么就把_node置为nullptr，因为此时为右子树走完

2.3.2begin和end接口的实现

map和set中的begin和end可以直接调用rb_tree中的Begin和End来完成功能

①Begin

对应返回整颗子树的最左节点，只要循环查找即可找到对应位置的迭代器进行返回

②End

End的实现可以直接iterator(nullptr)，这样的实现虽然不同于常规，但也可以保证这两点

1>树为空时，Begin和End返回值相等

2>树不为空时，指向有效节点的下一个(本来就是空)

2.3.2补：实现思路与源码的区别

其实在源码中是实现了一个哨兵位的头节点作为End的载体

哨兵位也是一个节点，节点的三叉链指向：

_parent:指向根节点，且根节点的_parent也指向哨兵位

_left:直接指向整颗子树的最左节点

_right:直接指向整颗子树的最右节点

这种实现的好处：

若是遇到这段代码

it=end();
--it;

可以让it对应的迭代器位置直接指向最后一个元素，也就是树的最右节点，符合了它双向迭代器的要求，

只是这一部分还算不得优点，毕竟在重载--也是要进行特殊情况特殊处理，

我们使用nullptr直接构造End也可以在重载--时处理一下

最重要的是有了哨兵位就可以更容易地拿到_root根节点地迭代器了，这一点是直接nullptr构造比不上的

2.3.3--运算符的重载与特殊

参考++时候地逻辑，--正好反向：右子树根左子树

实现看左子树是否为空：①为空，则为左子树地最右节点

②不为空，则说明右子树走完了，想上找cur是parent右孩子这种情况对应的parent，就是要的祖先节点

特殊处理：

在--对应的节点为nullptr的时候，我们直接查找整颗子树地最右节点，只是此时要拿到树的根节点，最直接地办法就是让迭代器类中多存一个结点指针的成员变量，这种情况下把_root传过来就是最好的解决办法了

用库中对应地结构可以避开这一额外传参的问题，但本质上各有利弊，在其他地方会有麻烦出现

2.4const迭代器

一如之前vector中控制const迭代器的方式，利用两个新的模板参数Ref与Ptr来做*与->的返回值，

之后在map和set以及RBTree中补充对应模板参数的const_iterator的重定义

特殊：

通常意义上const迭代器与普通迭代器的区别就是例如遍历过程中

*it之后不可以进行值的修改

但是，对于map和set以及RBTree而言不止const迭代器，普通迭代器也不能随意修改，否则会造成树结构的直接混乱，因此我们进行了如下措施：

set中定义成员变量

RBTree<K, const K, SetKeyOfT> _t;

map中定义成员变量

RBTree<K, pair<const K,V>, MapKeyOfT> _t;

都是通过const直接修饰来阻止对值进行修改

（在源码中，直接把set与map中的普通迭代器利用rb_tree中的const迭代器进行了typedef）

2.4补：如何保证const迭代器对应接口与原接口构成重载

如果直接

iterator begin() 
{return _t.Begin();
}const_iterator begin()
{return _t.Begin();
}

只有返回值类型不同是无法构成函数重载的，因此我们需要利用const修饰成员函数来让重载顺利构成，即

const_iterator begin() const
{return _t.Begin();
}

2.补：迭代器的加深理解

迭代器可以说是一种实用性很高的封装的体现，

他把各种各样的容器如数组，链表，树，哈希，双端队列等等不同的容器统一typedef

使得使用者只需要容器::iterator即可轻松进行遍历

迭代器屏蔽了底层的细节，提供了统一的访问方式

三、map和set需要的其余接口

3.1查找

find接口返回的是迭代器类型，实现思路可以是rb_tree中走搜索二叉树的查找，map和set中套壳

3.2插入

insert接口返回的是pair<iterator,bool>，实现思路可以是rb_tree中走红黑树的插入，成功/失败插入返回一个make_pair()，map和set中套壳

3.3map中对于[]的重载

依托于insert进行，传入key的值，直接用一个pair<iterator,bool>类型的值接收insert(key)的返回值，再return一下iterator->second即可