C++之STLmap和set的模拟实现

转x33g5p2x  于2022-03-21 转载在 其他  
字(12.6k)|赞(0)|评价(0)|浏览(219)

模拟实现map和set

我们首先来看一下源码当中的set和map的结构：

template <class Key,class Compare = less<Key>, class Alloc = alloc>
class set {
public:
    typedef Key key_type;
    typedef Key value_type;
    typedef rb_tree<key_type,value_type,identity<value_type>,key_compare,Alloc> rep_type;
    rep_type t; //red-black tree representing set
};
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 rb_tree<key_type,value_type,
                    select1st<value_type>,key_compare,Alloc> rep_type;
	rep_type t; //red-black tree representing mapI
};
typedef Key value_type;
typedef rb_tree<key_type,value_type,identity<value_type>,key_compare,Alloc> rep_type
//set的红黑树模板参数
    
typedef pair<const Key,T> value_type;
typedef rb_tree<key_type,value_type,select1st<value_type>,key_compare,Alloc> rep_type;
//map的红黑树模板参数

可以看到set当中的红黑树key_type,value_type这两个模板参数，key_type是Key，而且value_type也被typedef成Key，两个Key是什么意思呢？而map当中的红黑树key_type,value_type这两个模板参数，key_type是Key，而且value_type被typedef成pair<const Key,T>

源码中红黑树的结构

template <class Key,class Value, class KeyOfValue,class Compare,class Alloc = allpc>
class rb_tree 
{
protected:
	typedef _rb_tree_node<Value> rb_tree_node;
	typedef rb_tree_node* link_type;
protected:
	link_type header;
};
template <class Value>
struct _rb_tree_node : public _rb_tree_node_base
{
	typedef _rb_tree_node<Value>* link_type;
	Value value_field;
};

可以看到红黑树的模板参数中的第二个参数是Value，通过这个参数就可以实现上层set给红黑树传Key，Value就是Key，上层map给红黑树pair<const K,V>，Value就是pair<const K,V>，红黑树中的数据值Value value_field就能够灵活变换。

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

我们发现set底层的红黑树模板参数第一个和第二个一样，那么能不能不要第一个模板参数呢？

不能，对于set省略掉没有问题，因为set传入红黑树的参数一和二是相同的，但是map就不行，因为map如果只传入第二个参数pair，map提供的接口是有些需要Key值的，比如find和erase。

我们将底层红黑树的模板参数写成：

template<class K,class T>
class RBTree{};

T来接受map和set传进来了第二个参数，他可能是key也可能是pair

相应的红黑树节点的数据类型我们也需要改成T：

enum Colour
{
    BLACK,
    RED
};
template<classT>
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),
        :col(RED),
        :_data(data)
	{}
};

T传key是key，传pair是pair

模板参数中的仿函数

我们前面可以看到红黑树源码当中还有一个模板参数仿函数，这个参数是用来比较键值用的，因为第二个参数是T，set传入的是key，map传入的是pair，在比较键值的时候，是set还可以直接比较，当时map时，pair是不支持比较的，所以上层容器需要给底层红黑树提供一个仿函数，用来重载()获取key值：

template<class K, class V>
class map
{
	//仿函数
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv) //返回键值对当中的键值Key
		{
			return kv.first;
		}
	};
public:
private:
	RBTree<K, pair<K, V>, MapKeyOfT> _t;
};

set也需要写仿函数，传进去，因为底层红黑树没办法知道传进去的是set还是map，所以当需要键值进行比较大小时，红黑树都会根据仿函数来进行比较

set的仿函数：

template<class K>
class set
{
	//仿函数
	struct SetKeyOfT
	{
		const K& operator()(const K& key) //返回键值Key
		{
			return key;
		}
	};
public:
private:
	RBTree<K, pair<K, V>, SetKeyOfT> _t;
};

增加了一个参数仿函数后，红黑树的参数也发生了变化：

template<class K,class T,class KeyOfT>
class RBTree{};

相应的之前实现的红黑树的一些有比较键值的地方就需要改变，比如查找函数和插入函数

红黑树的迭代器的模拟实现

红黑树的迭代器的实现其实就是对节点的指针进行了封装

迭代器的基本结构

template<class T,class Ref,class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
    typedef RBTreeIterator<T,Ref,Ptr> Self;//自身类型的typedef
    Node* _node;
    //构造函数
    RBTreeIterator(Node* node = nullptr)
        :_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、如果it指向节点的右子树不为空，下一个就++到右子树中序第一个节点，也就是右子树的最左节点。

2、如果it指向节点右子树为空，下一个++要访问的节点是，沿着it指向节点到根节点的路径中，遍历寻找孩子是父亲左的那个父亲节点

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 && parent->_right == cur)
            {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }

那么红黑树的迭代器如何实现–呢？和++的思路反一下就好了：

1、如果当前节点的左子树不为空，则–操作后要找到其左子树当中的最右节点

2、如果当前节点的左子树为空，则–操作后应该在该节点到根节点的路径中找到孩子在父亲右的祖先

Self operator--()
{
	if (_node->_left) 
	{
         //左子树中序第一个节点，也就是左子树的最右节点
		//寻找该结点左子树当中的最右结点
		Node* right = _node->_left;
		while (right->_right)
		{
			right = right->_right;
		}
		_node = right; 
	}
	else //结点的左子树为空
	{
		//寻找孩子在父亲右的祖先
		Node* cur = _node;
		Node* parent = cur->_parent;
		while (parent&&cur == parent->_left)
		{
			cur = parent;
			parent = parent->_parent;
		}
		_node = parent; 
	}
	return *this;
}

最后我们需要在红黑树里面实现begin和end：

typedef RBTreeIterator<T,T&,T*> iterator;
typedef RBTreeIterator<T,const T&,const T*> const_iterator; 
iterator begin()
{
    Node* left = _root;
    while(left && left->_left)
    {
        left = left->_left;
    }
    return iterator(left);//返回最左节点的迭代器
}
iterator end()
{
    return iterator(nullptr);
}

我们实现的迭代器和STL当中的是有差别的，我们对end()–理应返回最后一个节点的迭代器，但是上面的实现无法实现此操作，在STL库当中实现红黑树时，他在根节点增加了头节点，它的左指针指向红黑树的最左节点，右指针指向红黑树当中的最右节点，父亲指针指向红黑树的根节点。通过一些逻辑的控制就可以实现上面的操作

红黑树的迭代器的整体代码

template<class T,class Ref,class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
    typedef RBTreeIterator<T,Ref,Ptr> Self;
    Node* _node;
    RBTreeIterator(Node* node = nullptr)
        :_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;
    }
    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 && parent->_right == cur)
            {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }
    Self operator--()
    {
        if (_node->_left) 
        {
             //左子树中序第一个节点，也就是左子树的最右节点
            //寻找该结点左子树当中的最右结点
            Node* right = _node->_left;
            while (right->_right)
            {
                right = right->_right;
            }
            _node = right; 
        }
        else //结点的左子树为空
        {
            //寻找孩子在父亲右的祖先
            Node* cur = _node;
            Node* parent = cur->_parent;
            while (parent&&cur == parent->_left)
            {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent; 
        }
        return *this;
    }
}
#pragma once
enum Colour
{
    BLACK,
    RED
};
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),
    	:col(RED),
    	:_data(data)
	{}
};
template<class T,class Ref,class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
    typedef RBTreeIterator<T,Ref,Ptr> Self;
    Node* _node;
    RBTreeIterator(Node* node = nullptr)
        :_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;
    }
    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 && parent->_right == cur)
            {
                cur = parent;
                parent = parent->_parent;
            }
            _node = parent;
        }
        return *this;
    }
    Self& operator--()
    { 
        //跟++基本是反过来
        return *this;
    }
}    
template<class K,class T,class KeyOfT>
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* left = _root;
        while(left && left->_left)
        {
            left = left->_left;
        }
        return iterator(left);
    }
    iterator end()
    {
        return iterator(nullptr);
    }
    RBTree()
        :_root(nullptr)
    {}
    
    //查找函数
	iterator Find(const K& key)
	{
		KeyOfT kot;
		Node* cur = _root;
		while (cur)
		{
			if (key < kot(cur->_data)) //key值小于该结点的值
			{
				cur = cur->_left; //在该结点的左子树当中查找
			}
			else if (key > kot(cur->_data)) //key值大于该结点的值
			{
				cur = cur->_right; //在该结点的右子树当中查找
			}
			else //找到了目标结点
			{
				return iterator(cur); //返回该结点
			}
		}
		return end(); //查找失败
	}
    
    //插入
    pair<iterator,bool> Insert(const T& data)//插入需要比较大小找位置，此时引入了第三个模板参数KeyOfT
    {
        if(_root == nullptr)
        {
            _root = new Node(data);
            _root->_col = BLACK;
            return make_pair(iterator(_root),true);
        }
        KeyOfT kot;
        Node* parent = nullptr;
        Node* cur = _root;
        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);
            }
        }
        //插入红色可能破坏规则3，插入黑色一定破坏规则4,破坏规则4比较难处理
        //新增节点就新增一个红色节点
        //1、如果新增节点的父亲是黑色，没有影响
        //2、如果新增节点的父亲是红色，则产生了连续的红色节点，破坏了规则3，需要分情况处理：
        
        cur = new Node(data);
       	Node* newnode = cur;
        cur->_col = RED;
        //插入链接
        if(kot(parent->_data) < kot(data))
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        else
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        //控制平衡,控制颜色
        while(parent && parent->_col == RED)
        {
            Node* greandfather = parent->_parent;
            if(parent == greandfather->_right)
            {
                //找到叔叔
                Node* uncle = greandfather->_right;
                //情况一：uncle存在且为红，进行变色处理即可,并且继续往上更新处理
                if(uncle && uncle->_col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    
                    cur = grandfather;
                    parent = cur->_parent;
                }//情况二+三：uncle不存在，uncle存在且为黑，进行旋转+变色处理
                else
                {
                    //情况二：单旋+变色
                    if(cur == parent->_left)
                    {
                        RotateR(greandfather);
                        parent->_col = BLACK;
                        greandfather->_col = RED;
                    }
                    else
                    {
                        //情况三：双旋+变色
                        RotateL(parent);
                        RotateR(greandfather);
                        cur->_col = BLACK;
                        greandfather->_col = RED;
                    }
                    break;
                }
            }
            else//parent == greandfather->_right
            {
                Node* uncle = greandfather->_left; 
                if(uncle && uncle ->col == RED)
                {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    
                    cur = grandfather;
                    parent = cur->_parent;
                }
                else
                {
                    if(parent->_right == cur)
                    {
                        RotateL(grandfather);
                        parent->_col = BLACK;
                        grandfather->COL = RED;
                    }
                    else//parent->_left == cur
                    {
                        //双旋+变色
                        RotateR(parent);
                        RotateL(grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    //不用再继续了，不会有连续红色和黑色个数不一样
                    break;
                }
            }
        }
        _root->_col = BLACK;
        return make_pair(iterator(newnode),true);
    }
    void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

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

	void InOrder()
	{
		_InOrder(_root);
		cout<<endl;
	}
    void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

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

		Node* ppNode = parent->_parent;

		subL->_right = 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;
		}
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

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

		Node* ppNode = parent->_parent;

		subR->_left = 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;
		}
	}
private:
    Node* _root;
}

map的模拟实现

map的实现，成员函数底层都是使用红黑树的接口完成的，对于map来说，除了将插入函数和查找函数返回值改为迭代器之外，还要实现[]运算符的重载

#include"RBTree.h"
namespace Z
{
    template<class K,class V>
    class map
    {
        struct MapKeyOfT
        {
            const K& operator()(const pair<const K,V>& kv)
            {
                return kv.first;
            }
        };
    public:
        typedef typename RBTree<K,K,MapKeyOfT>::iterator iterator;
        iterator begin()
        {
            return _t.begin();
        }
        iterator end()
        {
            return _t.end();
        }
        
        pair<iterator,bool> Insert(const pair<const K,V>& kv)
        {
            return _t.Insert(kv);
        }
        iterator find(const K& key)
        {
            return _t.Find(key);
        }
        V& operator[](const K& key)
        {
            pair<iterator,bool> ret = _t.Insert(make_pair(key,V()));
        	return ret.first->second;
        }
    private:
        RBTree<K,pair<const K,V>,MapKeyOfT> _t;
    };
    void test_map()
    {
        map<string,string> dict;
        dict.insert(make_pair("sort","排序"));
        dict.insert(make_pair("string","字符串"));    
        map<string, string>::iterator it = dict.begin();
		while (it != dict.end())
		{
			cout << it->first << ":" << it->second << endl;
			++it;
		}
		cout << endl;
    }
}

set的模拟实现

成员函数底层都是使用红黑树的接口完成的，将插入函数和查找函数返回值改为迭代器

#include"RBTree.h"
namespace Z
{
    template<class K,class V>
    class set
    {
        struct SetKeyOfT
        {
            K& operator()(const K& key)
            {
                return key;
            }
        };
    private:
        RBTree<K,K,SetKeyOfT> _t;
    public:
        typedef typename RBTree<K,K,SetKeyOfT>::iterator iterator;//生成实例后再去找
        iterator begin()
        {
            return _t.begin();
        }
        iterator end()
        {
            return _t.end();
        }
        pair<iterator, bool> Insert(const K& key)
        {
            return _t.Insert(key);
        }
        iterator find(const K& key)
        {
            return _t.Find(key);
        }
    };
    void test_set()
    {
        set<int> s;
        s.insert(1);
        s.insert(2);
        s.insert(3);    
        s.insert(4);   
        set<int>::iterator it = s.begin();
        while(it!=s.end())
        {
            cout<<*it<<" ";
            ++it;
        }
        cout<<endl;
    }
}

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://blog.csdn.net/attemptendeavor/article/details/123646853

内容来源于网络，如有侵权，请联系作者删除！

c++map和set

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com