本来我们需要两个红黑树去分别封装map和set#xff0c;但是代码会有重复、冗…前言

我们已经学过了如何去实现一棵完整的红黑树而我们所知道的map和set容器的底层都是由红黑树实现的因此我们今天来学习如何用红黑树来实现封装map和set。

本来我们需要两个红黑树去分别封装map和set但是代码会有重复、冗余因此我们采用泛型编程的思想同一颗红黑树通过传不同的模板参数来分别实现map和set。

就是为了复用同一个类模板的红黑树让代码变的简洁体现了泛型编程的思想。

比如这里的模板参数T如果传的是K类型的代表使用的是set如果参数传的是pair类型的就代表是map。

问题为什么要用两个模板参数前面的K有什么用我们不是只需要后面的T就可以区分这两个容器了吗

当我们使用find这个函数的时候传的参数必须是K类型的因为如果我们只传后面的T模板参数那么使用map查找值的时候find函数的查找值的类型不可能是pair类型的因此这里我们需要多添加一个模板参数让find()的时候保持一致。

在insert函数里面我们需要通过比较T类型的值大小但是如果是pair类型的值如何比较呢

这与我们的比较理念有偏差我们只希望比较first内容的值不让second内容的值参与进来那我们该如何解决呢

我们之前只知道仿函数可以用来比较大小但其实仿函数可以做很多事情。

比如这里我们定义了一个仿函数之后呢你给仿函数一个值仿函数就会返回一个其他的值

KeyOfT仿函数

但是在红黑树中不清楚T类型到底是K还是key-value但是map和set知道因此我们可以将这个仿函数定义在我们的map和set里面进行一个传参。

templateclass

_t.Insert(kv);}private:RBTreeK,

pairconst

_t.Insert(key);}private:RBTreeK,

const

it指向结点右不为空下一个就是右子树的最左结点it指向结点右为空意味这个结点的子树中序访问完了下一个结点找祖先里面孩子

templateclass