首页 > 编程语言 >C++:map&set 对红黑树的封装

C++:map&set 对红黑树的封装

时间:2024-03-24 14:00:13浏览次数:31  
标签:黑树 map const cur parent 对红 key return iterator

C++:map&set 对红黑树的封装


C++的STL库中,把红黑树封装为了两个容器mapset,本博客将基于红黑树,来实现mapset的封装。如果不了解红黑树,可见博客[数据结构/C++:红黑树]

将红黑树封装为泛型

我们现有如下结构的红黑树:

enum Colour
{
    RED,
    BLACK
};

template<class K, class V>
struct RBTreeNode
{
    RBTreeNode* _left;
    RBTreeNode* _right;
    RBTreeNode* _parent;
    pair<K, V> _kv;
    Colour _col;

    RBTreeNode(const pair<K, V>& kv)
        : _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _kv(kv)
        , _col(RED)
    {}
};

template<class K, class V>
class RBTree
{
    typedef RBTreeNode<K, V> Node;
public:

private:
    Node* _root = nullptr;
};

基本结构:RBTreeNode是红黑树的节点,RBTree则是红黑树本体,RBTree内部的_root 是整颗红黑树的根。

这颗红黑树有一个问题,在于它的节点,存储的值是pair<K, V> _kv;,也就是键值对的形式来存储数据。但是在STL中,set是只存储key值的,只有map存储键值对。如果我们要使得红黑树可以同时作为mapset的底层,那么我们就要想办法让这个红黑树的节点可以存储多种类型的数据。也就是让节点RBTreeNode内部存储泛型:

template<class T>
struct RBTreeNode
{
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    Colour _col;
    T _data;

    RBTreeNode(const T& data)
        : _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _data(data)
        , _col(RED)
    {}
};

我们把原先的模板template<class K, class V>换成了template<class T>,并把pair<K, V> _kv;改为了T _data;,此时我们存储的数据就不一定是键值对的格式了。

当我们需要存储键值对,那么T就是pair<K, V>
当我们只存储key值,那么T就是K

相应的,我们的RBTree主体也要修改一下:

template<class T>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:

private:
    Node* _root = nullptr;
};

现在我们先尝试对红黑树进行封装,写出一个mapset的基本框架:
mySet.h

template<class K>
class set
{
public:
private:
    RBTree<K> _t;
};

myMap.h

template<class K, class V>
class map
{
public:
private:
    RBTree<pair<K, V>> _t;
};

经过这一层封装,我们的mapset的基本框架就有了,但是有一个小问题:mapset中的key值是不可以修改的,所以我们要给K的类型加上const修饰。不过要注意map中的value是可以修改的,所以不是给pair加上const修饰,而是只修饰K。

mySet.h

template<class K>
class set
{
public:
private:
    RBTree<const K> _t;
};

myMap.h

template<class K, class V>
class map
{
public:
private:
    RBTree<pair<const K, V>> _t;
};

Find接口

到此为止,我们仅完成了基本框架的搭建,接下来我们看看红黑树的Find接口:

Node* Find(const K& key)
{
    Node* cur = _root;

    while (cur)
    {
        if (cur->_kv.first < key)
            cur = cur->_right;
        else if (cur->_kv.first > key)
            cur = cur->_left;
        else
            return cur;
    }

    return nullptr;
}

以上Find接口,是在红黑树没有修改前的接口,我们看看它目前有什么问题:

  1. 我们已经把模板从template<class K, class V>换成了template<class T>,此时已经没有K这个类型了,我们在给Find传参的时候,不可以直接传const K& key

但是我们既然要在红黑树中查找,一定是要查key的,也就是说,我们不可以遗漏K这个类型,因此我们的模板参数要再加一个K,变成:template<class K, class T>。前面的K用于传入key的类型,后面的T用于传入红黑树存储的数据类型。

template<class K, class T>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:

private:
    Node* _root = nullptr;
};
  1. cur->_kv.first这个过程是有问题的,其意图通过找到key值,然后比较当前节点与查找节点的大小,来决定下一步去左子树还是右子树找节点。但是我们对RBTreeNode改造后,其内部存储的已经不是_kv了,而是_data,对于set而言,这个_data是没有first这个成员的,因此我们不能直接通过_kv.first这种方式来访问key

这个问题的关键在于,我们想要拿到红黑树节点中的key值,但是对于map而言,这个key_data中的成员变量first;而对于set而言,这个key就是_data也就是mapset取用key值的方式不同,我们无法统一处理

为了解决这个问题,我们就要想办法,用统一的方式从_data中获得mapsetkey。此时可以在红黑树的外部写仿函数,然后在仿函数的内部返回key值。对于红黑树而言,不论是什么类型,只需要向仿函数传入_data,然后接受返回值就可以拿到key

这里我们给红黑树传入第三个模板参数KeyOfT

template<class K, class T, class keyOfT>//keyOfT仿函数,取出T对象中的key
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
private:
    Node* _root = nullptr;
};

接着就是set的仿函数:

struct SetKeyOfT
{
    const K& operator()(const K& key)
    {
        return key;
    }
};

对于set而言,T就是K,也就是_data的类型为K,要从_data中得到key,直接返回_data即可。

map的仿函数:

struct MapKeyOfT
{
    const K& operator()(const pair<K, V>& kv)
    {
        return kv.first;
    }
};

对于map而言,Tpair<K, V>,也就是_data的类型为pair<K, V>,要从_data中得到key,需要返回_data的第一个成员first

然后我们再对Find接口进行改造,把所有需要取用key的地方都改用仿函数:

bool Find(const K& key)
{
    keyOfT kot;
    Node* cur = _root;

    while (cur)
    {
        if (kot(cur->_data) < key)
            cur = cur->_right;
        else if (kot(cur->_data) > key)
            cur = cur->_left;
        else
            return true;
    }

    return false;
}

其中kot就是仿函数keyOfT 实例化出的对象。

当前框架如下:
RBTree

template<class K, class T, class keyOfT>//keyOfT仿函数,取出T对象中的key
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
private:
    Node* _root = nullptr;
};

mySet.h

template<class K>
class set
{
    struct SetKeyOfT
    {
        const K& operator()(const K& key)
        {
            return key;
        }
    };
public:
    iterator find(const K& key)
    {
        return _t.Find(key);
    }
private:
    RBTree<K, const K, SetKeyOfT> _t;
};

myMap.h

template<class K, class V>
class map
{
    struct MapKeyOfT
    {
        const K& operator()(const pair<K, V>& kv)
        {
            return kv.first;
        }
    };
public:
    bool find(const K& key)
    {
        return _t.Find(key);
    }
private:
    RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

迭代器

先搭建出一个迭代器iterator的基本框架:

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

    Node* _node;

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

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

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

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

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

在此我不讲解这个框架是如何搭建的了,如果不明白,可见博客[C++:迭代器的封装思想]

现在的主要问题在于:迭代器应该如何行动,走到下一个节点?
通过迭代器遍历与直接中序遍历一颗红黑树不一样,中序遍历可以通过递归,自动按照左子树 - 根 - 右子树的顺序遍历。但是迭代器只知道当前节点,不知道前一步与后一步是谁。比如下图:

在这里插入图片描述
当前迭代器处于这个蓝色框中的节点,请问它下一步是往左子树走,右子树走,还是父节点走?

值得注意的是,当迭代器指向哪一个节点,说明当前就遍历到了哪一个节点,此时迭代器处于这个蓝色框中的节点,说明这个节点的左子树已经遍历完了,刚好遍历到这个蓝色框节点。因此下一步就是中序遍历右子树,即让迭代器走到当前节点的右子树位置,并且找到右子树的最左节点,该节点就是下一个节点。

但是如果右子树为空呢?

比如我们遍历到以下节点:
在这里插入图片描述

此时说明以蓝色框为根的整颗子树都遍历完毕了,那么我们就要向上移动,走到当前节点的父节点处:
在这里插入图片描述

但是对于这个父节点而言,其左子树遍历完了,刚刚右子树遍历完毕后,走到了当前节点,说明当前节点也遍历完毕了(中序遍历,根节点一定在右子树前遍历完),此时还要向上移动,以此类推,直到走到第一个当前节点是父节点的左子树的情况

在这里插入图片描述

至此,我们就大概清除迭代器移动的情况了:

如果迭代器当前节点的右子树不为空,遍历右子树(找到右子树的最左节点)
如果迭代器当前节点的右子树为空,向上找前一个节点是当前节点的左子树的节点

代码如下:

Self& operator++()
{
    if (_node->_right)//右不为空,找右子树最左节点
    {
        Node* subLeft = _node->_right;

        while (subLeft->_left)
        {
            subLeft = subLeft->_left;
        }

        _node = subLeft;
    }
    else//右为空
    {
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_right)
        {
            cur = parent;
            parent = cur->_parent;
        }

        _node = parent;//parent前一个节点cur是其左子树
    }

    return *this;
}

operator--同理,只是相反的:

如果迭代器当前节点的左子树不为空,遍历左子树(找到左子树的最右节点)
如果迭代器当前节点的左子树为空,向上找前一个节点是当前节点的右子树的节点

代码如下:

Self& operator--()
{
    if (_node->_left)//左不为空
    {
        Node* subRight = _node->_left;

        while (subRight->_right)
        {
            subRight = subRight->_right;
        }

        _node = subRight;
    }
    else//左为空
    {
        Node* cur = _node;
        Node* parent = cur->_parent;
        while (parent && cur == parent->_left)
        {
            cur = parent;
            parent = cur->_parent;
        }

        _node = parent;//第一个为cur右子树的祖先
    }

    return *this;
}

接下来我们要把迭代器的类封装进RBTree中,首先定义出iteratorconst_iterator

typedef RBTreeIterator<T, T*, T&> iterator;
typedef RBTreeIterator<T, const T*, const T&> const_iterator;

接着写出beginend的接口:

直接拿空指针构造end接口:

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

要注意的是,begin接口不是直接拿_root去构造iterator,中序遍历的第一个节点是整棵树的最左侧节点,所以要先找到最左侧节点,再构造:

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

    return iterator(subLeft);
}

const_iterator同理:

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

接着我们再封装出mapset的迭代器,直接复用RBTree的迭代器接口即可:
mySet.h

typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;
typedef typename RBTree<K, const K, SetKeyOfT>::const_iterator const_iterator;

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

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

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

const_iterator end() const
{
    return _t.end();
}

myMap.h

 typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
 typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;

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

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

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

 const_iterator end() const
 {
     return _t.end();
 }

这里有一个注意点,在typedef的时候,由于我们的RBTree是一个模板,我们到模板的域中访问了变量。编译器无法区分模板中const_iterator的是变量还是类型,所以编译器会默认把它视为一个变量。如果它是一个类型,那么我们要明确告诉编译器,即通过typename 关键词。不然const_iterator会被识别为一个变量,而不是一个类型。

由于STL中,find接口返回的是迭代器,现在我们已经实现了迭代器,所以我们还要把find的返回值改为迭代器,而不是布尔值,这里不做展示了,可以到文章末尾的代码块中查看。


insert接口

mapset中,insert的返回值比较特殊,其会返回pair<iterator, bool>

如果插入值data原先存在,此时iterator指向原先的data节点,bool值返回false表示插入失败
如果插入值data原先不存在,此时iterator指向新插入的data节点,bool值返回true表示插入成功

因此我们还要改一下Insert接口:

如果插入成功:

return  make_pair(iterator(newNode), true);

如果插入失败:

return make_pair(iterator(cur), false);

由于插入逻辑比较复杂,若需要看整段代码,可以在文章末尾查看。


map的operator[]接口

map还重载了[],这个重载比较复杂,但是非常有用,我们先看到声明:

V& operator[] (const K& key);

其接收一个K类型的参数,也就是接受一个key,然后返回一个V&,也就是一个value的引用。其功能为:接受一个key值,然后返回这个key对应的value的引用。

其等效于下面的代码:

(*((this->insert(make_pair(k,V()))).first)).second

现在我们来解读以上代码,我们将其拆解为四个部分:make_pair(k, V( )) + this->insert( ) + ( ).first + (*( )).second,我们一层层解析。

第一层:

make_pair(k, V( ))

可以看出,这是在利用参数k,通过make_pair构造一个pair,而这个pairvalue使用了V( )V就是value的类型)来调用默认构造。这样我们最后就得到了一个pair<key, value>

第二层:

this->insert( )

上一层我们构造了一个pair<key, value>,然后它被作为参数,传入到这个insert中,相当于把刚刚构造的节点插入进map中。map的插入后,不论成功与否,都会返回一个pair<iterator, bool>iterator用于指向key的迭代器,bool用于标识插入是否成功。所以这一层最后得到了一个pair,分别存储了指向key的迭代器和bool

第三层:

( ).first

上一层中我们得到了pair<iterator, bool>,这一层访问它的first,也就是访问了iterator,所以这一层得到了指向key值的迭代器

第四层:

(*( )).second

我们上一层拿到了指向key的迭代器,这一层先对迭代器解引用*( ),此时就得到了一个map的节点。而map的节点是pair<key, value>,所以我们解引用得到了一个pair,随后通过( ).second访问pair<key, value>second,也就是value。最后返回这个value的引用。

所以我们最后得到了key对应的value的引用。那么这有什么用呢?

假设我们有一个map<string, string>类型的字典dict,通过这个来展示operator[ ]的功能:

  1. 插入一个key值:
    dict["left"];
    以上语句在dict中插入了一个key = "left"但是没有value的节点

  1. 插入一对key - value
    dict["left"] = "左边";
    由于operator[ ]返回的是对应的引用,因此我们可以直接给返回值赋值,此时我们就插入了一个节点key = "left" - value = "左边"

  1. 修改key对应的value
    dict[“coffe”] = "咖啡";
    如果我们的dict原先就存在key = "coffe"的节点,以上代码可以修改这个keyvalue

  1. 得到key对应的value
    cout << dict["coffe"] << endl;
    由于我们拿到的是value的引用,我们也可以把它作为一个值赋值给别人或者输出

可以看到,operator[]的功能非常丰富,整体来说还是一个很好用的重载。

operator[]实现:
由于我们先前已经用insert铺垫好了,我们直接调用insert,然后返回value的引用即可:

V& operator[](const K& key)
{
    pair<K, V>& ret = insert(make_pair(key, V()));

    return ret.first->second;
}

总代码展示

RBTree.h

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

enum Colour
{
    RED,
    BLACK
};

template<class T>
struct RBTreeNode
{
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T>* _parent;
    Colour _col;
    T _data;

    RBTreeNode(const T& data)
        : _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _data(data)
        , _col(RED)
    {}
};

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

    Node* _node;

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

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

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

    Self& operator++()
    {
        if (_node->_right)//右不为空
        {
            Node* subLeft = _node->_right;

            while (subLeft->_left)
            {
                subLeft = subLeft->_left;
            }

            _node = subLeft;
        }
        else//右为空
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_right)
            {
                cur = parent;
                parent = cur->_parent;
            }

            _node = parent;//第一个为cur左子树的祖先
        }

        return *this;
    }

    Self& operator--()
    {
        if (_node->_left)//左不为空
        {
            Node* subRight = _node->_left;

            while (subRight->_right)
            {
                subRight = subRight->_right;
            }

            _node = subRight;
        }
        else//左为空
        {
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent && cur == parent->_left)
            {
                cur = parent;
                parent = cur->_parent;
            }

            _node = parent;//第一个为cur右子树的祖先
        }

        return *this;
    }

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

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

template<class K, class T, class keyOfT>//keyOfT仿函数,取出T对象中的key
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
    typedef RBTreeIterator<T, T*, T&> iterator;
    typedef RBTreeIterator<T, const T*, const T&> 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);
    }

    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;

        keyOfT kot;
        while (cur)
        {
            if (kot(cur->_data) < kot(data))
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (kot(cur->_data) > kot(data))
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return make_pair(iterator(cur), false);
            }
        }

        cur = new Node(data);

        if (kot(parent->_data) > kot(data))
            parent->_left = cur;
        else
            parent->_right = cur;

        cur->_parent = parent;
        Node* newNode = cur;

        while (parent && parent->_col == RED)//只有parent为红,才更新 (parent可能不存在)
        {
            Node* grandfather = parent->_parent;
            if (parent == grandfather->_left)
            {
                Node* uncle = grandfather->_right;

                //uncle存在且为红节点
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }
                else//uncle不存在或为黑节点 (旋转)
                {
                    if (cur == parent->_left)
                    {
                        RotateR(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        RotateL(parent);
                        RotateR(grandfather);

                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }

                    break;//旋转后一定平衡
                }
            }
            else
            {
                Node* uncle = grandfather->_left;

                //uncle存在且为红节点
                if (uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    cur = grandfather;
                    parent = cur->_parent;
                }
                else//uncle不存在或为黑节点 (旋转)
                {
                    if (cur == parent->_right)
                    {
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    else
                    {
                        RotateR(parent);
                        RotateL(grandfather);

                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }

                    break;//旋转后一定平衡
                }
            }
        }

        _root->_col = BLACK;//在循环内部不判断root情况,统一处理

        return  make_pair(iterator(newNode), true);
    }
    
    //左单旋
    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        if (subRL)
            subRL->_parent = parent;

        subR->_left = parent;
        Node* ppNode = parent->_parent;
        parent->_parent = subR;

        if (parent == _root)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {
            if (ppNode->_left == parent)
                ppNode->_left = subR;
            else
                ppNode->_right = subR;

            subR->_parent = ppNode;
        }
    }

    //右单旋
    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        parent->_left = subLR;
        if (subLR)
            subLR->_parent = parent;

        subL->_right = parent;
        Node* ppNode = parent->_parent;
        parent->_parent = subL;

        if (parent == _root)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        else
        {
            if (ppNode->_left == parent)
                ppNode->_left = subL;
            else
                ppNode->_right = subL;

            subL->_parent = ppNode;
        }
    }

    size_t Size()
    {
        return _Size(_root);
    }

    size_t _Size(Node* root)
    {
        if (root == nullptr)
            return 0;;

        return _Size(root->_left) + _Size(root->_right) + 1;
    }

    iterator Find(const K& key)
    {
        keyOfT kot;
        Node* cur = _root;

        while (cur)
        {
            if (kot(cur->_data) < key)
                cur = cur->_right;
            else if (kot(cur->_data) > key)
                cur = cur->_left;
            else
                return iterator(cur);
        }

        return end();
    }

    //--------------------------------------------------------------------------------------------------------------

    //中序
    void InOrder()
    {
        _InOrder(_root);
        cout << "end" << endl;
    }

private:
    //中序
    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;

        _InOrder(root->_left);
        cout << root->_kv.first << " - ";

        _InOrder(root->_right);
    }

    Node* _root = nullptr;
};

mySet.h

#pragma once
#include "RBTree.h"

namespace mySet
{
    template<class K>
    class set
    {
        struct SetKeyOfT
        {
            const K& operator()(const K& key)
            {
                return key;
            }
        };

    public:
        typedef typename RBTree<K, const K, SetKeyOfT>::iterator iterator;
        typedef typename RBTree<K, const K, SetKeyOfT>::const_iterator const_iterator;

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

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

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

        const_iterator end() const
        {
            return _t.end();
        }

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

        iterator find(const K& key)
        {
            return _t.Find(key);
        }

    private:
        RBTree<K, const K, SetKeyOfT> _t;
    };
}

myMap.h

#pragma once
#include "RBTree.h"

namespace myMap
{
    template<class K, class V>
    class map
    {
        struct MapKeyOfT
        {
            const K& operator()(const pair<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>::const_iterator const_iterator;

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

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

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

        const_iterator end() const
        {
            return _t.end();
        }

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

        V& operator[](const K& key)
        {
            pair<K, V>& ret = insert(make_pair(key, V()));

            return ret.first->second;
        }

        iterator find(const K& key)
        {
            return _t.Find(key);
        }

    private:
        RBTree<K, pair<const K, V>, MapKeyOfT> _t;
    };
}

标签:黑树,map,const,cur,parent,对红,key,return,iterator
From: https://blog.csdn.net/fsdfafsdsd/article/details/136767956

相关文章

  • Lecture 09 Shading 3 (Texture Mapping cont
    Lecture09Shading3(TextureMappingcont.)Shading3Barycentriccoordinates重心坐标为了在三角形内部任何一点内插值,我们引入重心坐标为什么需要插值?指定顶点属性在三角形内部保持平滑变化插值什么内容?纹理坐标、颜色、法向量,...怎么做插值?重心坐标......
  • Lecture 08 Shading 2 (Shading, Pipeline and Texture Mapping)
    Lecture08Shading2(Shading,PipelineandTextureMapping)ShadingfrequenciesP1每个面着色一次P2每个顶点着色一次,每个三角面内插值P3每个像素着色一次FlatShading(逐三角形)每个三角面是一个平面,只有一个法线在光滑表面效果不好Gouraudshading(逐顶点)每个......
  • HasMap底层分析
    一、散列表结构HashMap的存储结构为数组+链表+红黑树同时它的数组的默认初始容量是16、扩容因子为0.75,每次采用2倍的扩容。也就是说,每当我们数组中的存储容量达到75%的时候,就需要对数组容量进行2倍的扩容。初始容量和负载因子也可以通过构造方法指定: publicHashM......
  • c++ stl 之映射—— map 详解
     map是stl的一个关联容器,名叫“映射”,何为“映射”?其实就是一个数组,但有了数组何必还需映射,这是一个高深的问题。目录一、map简介         1.空间复杂度    2.时间复杂度     3.“键”的类型二、 map用法     1.声明  ......
  • 构建空间场景轻应用,Mapmost Alpha来啦【文末赠书(10本)--第二期】
    文章目录:一、MapmostAlpha介绍二、MapmostAlpha应对数字孪生业务痛点解决之道2.1MapmostAlpha提供海量城市底板2.2MapmostAlpha提供便捷的配置管理工具2.3MapmostAlpha提供一键式部署发布和分享三、沉浸式体验MapmostAlpha3.1创建应用3.2新手指导3.3场......
  • Golang: 探究sync.map的实现
    Golang:探究sync.map的实现背景探究下载并发模式下,sync.map的实现,以及该实现方式可能引入的问题链接Github基本使用packagemainimport"sync"funcmain(){ m:=sync.Map{} m.Load("key") m.Store("key","value") m.LoadOrStore("key",&q......
  • HashMap的数组最大容量为什么要设计为2的30次方?而不是2的31次方-1?数组容量为什么一定
    目录问题 数组容量为什么一定要设计为2的幂(2的n次方)?1、首先要清楚HashMap的底层基本原理2、再来看下怎么通过hash值决定存放在哪个桶中?首先看下hash值再看下怎么确定当前key存放在哪个数组下标下的为什么要做按位与而不用模运算符%?为什么要n-1呢?n是一个什么样的数......
  • 一文彻底搞懂HashMap
    文章目录1.数据结构2.扩容机制3.常问问题3.1HashMap为什么要树化3.2链表中转红黑树的阈值为什么设为81.数据结构JDK7中的HashMap使⽤的是数组+链表的实现⽅式,即拉链法。当发生哈希冲突时,即多个键映射到同一个数组索引位置时,HashMap会将这些键值对存储在......
  • P5266 【深基17.例6】学籍管理(Map)
    #include<bits/stdc++.h>usingnamespacestd;map<string,string>m;intmain(){ intn; cin>>n; while(n--) { inta; stringname,score; cin>>a; if(a==1) { cin>>name>>score; if(m.find(name)!=m.end())m[......
  • AXI Memory Mapped to PCI Express学习笔记(二)——PCIe中断
    AXIMemoryMappedtoPCIExpress IP核的中断包括Local中断,MSI中断和 Legacy中断。1Local中断   在配置AXI桥接器时,中断输出(interrupt_out)引脚可以根据中断掩码寄存器(InterruptMaskregister)的设置来发送中断。这个中断输出引脚会向连接到桥接器内存映射AXI4侧......