【C++练级之路】【Lv.17】【STL】set类和map类的模拟实现

简介: 用改造后的红黑树,模拟实现set和map
远方有一堆篝火,在为久候之人燃烧!

@[TOC]

引言

STL库中的set类和map类,其底层原理都是==通过红黑树来实现==的。尽管set和map可以各自实现一棵红黑树,但是为了提高代码的复用率,STL库中将红黑树进行了一定的改造,实现==以相同的底层实现不同的容器==。

一、红黑树(改造版)

1.1 结点

enum Color
{
   
   
    RED,
    BLACK
};

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

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

细节:

  • 将==数据类型改为T==,因为要同时适用set(存储键值)和map(存储键值对)

1.2 迭代器

改造后的红黑树,最重要的功能之一就是支持双向迭代器,以最左结点为首,以最右结点为尾。

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

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

    RBTreeIterator(const Iterator& it)
        : _node(it._node)
    {
   
   }

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

    Ptr operator->()
    {
   
   
        return &(operator*());
    }

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

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

细节:

  1. 一些基本的迭代器范式操作已经给出,重点的++与- -操作后面详细实现
  2. 迭代器的拷贝构造函数有两个用途:
    • 以普通迭代器拷贝出普通迭代器(普通迭代器调用时)
    • ==以普通迭代器拷贝出const迭代器==(const迭代器调用时)

1.2.1 operator++

Self& operator++()
{
   
   
    if (_node->_right)//右不为空,找右子树的最左结点
    {
   
   
        Node* subLeft = _node->_right;
        while (subLeft->_left)
        {
   
   
            subLeft = subLeft->_left;
        }
        _node = subLeft;
    }
    else//右为空,向上找孩子是父亲左的那个父亲
    {
   
   
        Node* parent = _node->_parent;
        Node* cur = _node;
        while (parent && parent->_right == cur)
        {
   
   
            cur = parent;
            parent = cur->_parent;
        }
        _node = parent;
    }
    return *this;
}

Self operator++(int)
{
   
   
    Self tmp = *this;
    ++*this;
    return tmp;
}

细节:

  1. 前置++的思路:
    • 右不为空,找右子树的最左结点
    • 右为空,向上找孩子是父亲左的那个父亲
  2. 后置++:复用前置++,返回临时对象

1.2.2 operator- -

Self& operator--()
{
   
   
    if (_node->_left)//左不为空,找左子树的最右结点
    {
   
   
        Node* subRight = _node->_left;
        while (subRight->_right)
        {
   
   
            subRight = subRight->_right;
        }
        _node = subRight;
    }
    else//左为空,向上找孩子是父亲右的那个父亲
    {
   
   
        Node* parent = _node->_parent;
        Node* cur = _node;
        while (parent && parent->_left == cur)
        {
   
   
            cur = parent;
            parent = cur->_parent;
        }
        _node = parent;
    }
    return *this;
}

Self operator--(int)
{
   
   
    Self tmp = *this;
    --*this;
    return tmp;
}

细节:

  1. 前置- -的思路:
    • 左不为空,找左子树的最右结点
    • 左为空,向上找孩子是父亲右的那个父亲
  2. 后置- -:复用前置- -,返回临时对象

1.3 本体

1.3.1 成员变量

template<class K, class T, class KeyOfT>
class RBTree
{
   
   
protected:
    typedef RBTreeNode<T> Node;
public:
protected:
    Node* _root = nullptr;
};

细节:

  1. 模板参数第一个为K,键值类型(比较时会用到)
  2. 模板参数第二个为T,同时适用set(存储键值)和map(存储键值对)
  3. 模板参数第三个为KeyOfT(仿函数类型),用于==获取不同数据T的键值key==来进行比较

1.3.2 begin和end

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

iterator begin()
{
   
   
    Node* cur = _root;
    while (cur->_left)
    {
   
   
        cur = cur->_left;
    }
    return iterator(cur);
}

const_iterator begin() const
{
   
   
    Node* cur = _root;
    while (cur->_left)
    {
   
   
        cur = cur->_left;
    }
    return const_iterator(cur);
}

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

const_iterator end() const
{
   
   
    return const_iterator(nullptr);
}

细节:begin返回最左节点的迭代器,end返回空迭代器

1.3.3 Find

iterator Find(const K& key)
{
   
   
    if (_root == nullptr)
    {
   
   
        return iterator(nullptr);
    }

    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 iterator(nullptr);
}

细节:

  1. 返回迭代器
  2. 运用仿函数进行键值比较

1.3.4 Insert

pair<iterator, bool> Insert(const T& data)
{
   
   
    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);
        }
    }

    Node* newnode = new Node(data);
    cur = newnode;
    if (kot(parent->_data) < kot(data))
    {
   
   
        parent->_right = cur;
    }
    else
    {
   
   
        parent->_left = cur;
    }
    cur->_parent = parent;

    while (parent && parent->_col == RED)
    {
   
   
        Node* grandparent = parent->_parent;
        if (grandparent->_right == parent)//uncle在左,parent在右
        {
   
   
            Node* uncle = grandparent->_left;
            if (uncle && uncle->_col == RED)//uncle为红,变色+向上调整
            {
   
   
                parent->_col = uncle->_col = BLACK;
                grandparent->_col = RED;

                cur = grandparent;
                parent = cur->_parent;
            }
            else//uncle为空或为黑,变色+旋转
            {
   
   
                if (parent->_right == cur)//左单旋
                {
   
   
                    RotateL(grandparent);
                    parent->_col = BLACK;
                    grandparent->_col = RED;
                }
                else//右左旋
                {
   
   
                    RotateR(parent);
                    RotateL(grandparent);
                    cur->_col = BLACK;
                    grandparent->_col = RED;
                }
            }
        }
        else//parent在左,uncle在右
        {
   
   
            Node* uncle = grandparent->_right;
            if (uncle && uncle->_col == RED)
            {
   
   
                parent->_col = uncle->_col = BLACK;
                grandparent->_col = RED;

                cur = grandparent;
                parent = cur->_parent;
            }
            else
            {
   
   
                if (parent->_left == cur)//右单旋
                {
   
   
                    RotateR(grandparent);
                    parent->_col = BLACK;
                    grandparent->_col = RED;
                }
                else//左右旋
                {
   
   
                    RotateL(parent);
                    RotateR(grandparent);
                    cur->_col = BLACK;
                    grandparent->_col = RED;
                }
            }
        }
    }
    _root->_col = BLACK;

    return make_pair(iterator(newnode), true);
}

细节:

  1. 返回pair,第一个参数为迭代器,第二个参数为布尔值(记录是否插入成功)
  2. 运用仿函数进行键值比较

二、set

2.1 成员变量与仿函数

template<class K>
class set
{
   
   
    struct SetKeyOfT
    {
   
   
        const K& operator()(const K& key)
        {
   
   
            return key;
        }
    };
public:
protected:
    RBTree<K, K, SetKeyOfT> _t;
};

细节:

  1. set类仿函数,直接返回参数key
  2. 成员变量的第二个模板参数为K,第三个模板参数为SetKeyOfT

    2.2 begin和end

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

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

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

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

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

细节:

  1. 加上typename关键字,编译器才能识别类型
  2. set中存储的键值key均不允许修改,所以其普通迭代器和const迭代器均为红黑树的const迭代器
  3. 由于set的普通迭代器也是红黑树的const迭代器,调用普通begin()时,便有==从普通迭代器到const迭代器的转换==,此时之前写的拷贝构造(以普通迭代器拷贝构造const迭代器)便派上用场了。

2.3 find

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

2.4 insert

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

细节:

  1. 插入参数类型为K(键值)
  2. 此时也有从普通迭代器到const迭代器的转换

三、map

3.1 成员变量与仿函数

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

细节:

  1. map类仿函数,返回参数pair的first
  2. 成员变量的第二个模板参数为pair,第三个模板参数为MapKeyOfT

3.2 begin和end

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

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

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

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

细节:

  1. 加上typename关键字,编译器才能识别类型
  2. map同样不允许修改key,故加上const修饰,但是允许修改存储的value,所以普通和const迭代器一一对应

此时,可能有人会问,那刚刚set不允许修改key,为什么不也直接用const修饰呢?请看以下这段代码:

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

如果变成第二个模板参数T传入const K,那么就会形成两个连续的const,这是不被允许的。所以才想了其他方法来补救。

3.3 find

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

3.4 insert

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

细节:插入参数类型为pair(键值对)

3.5 operator[ ]

map最好用的重载运算符[ ],我们肯定也要实现,平常插入和修改使用[ ]更加方便。

V& operator[](const K& key)
{
   
   
    pair<iterator, bool> ret = _t.Insert(make_pair(key, V()));
    return ret.first->second;
}

细节:

  1. 插入成功便是插入,插入失败便是查找+修改
  2. 返回value的引用,可以直接插入或修改


真诚点赞,手有余香


相关文章
|
10天前
|
C++ 容器
【C++】map和set封装
【C++】map和set封装
12 2
|
10天前
|
存储 C++ 容器
【C++】map和set深度讲解(下)
【C++】map和set深度讲解(下)
21 2
|
10天前
|
存储 自然语言处理 Java
【C++】map和set深度讲解(上)
【C++】map和set深度讲解(上)
17 2
|
10天前
|
设计模式 算法 Java
【c++】STL之stack和queue详解
【c++】STL之stack和queue详解
10 1
|
10天前
|
存储 C++ 容器
【C++】开散列实现unordered_map与unordered_set的封装
【C++】开散列实现unordered_map与unordered_set的封装
16 0
|
17天前
|
存储 算法 C++
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
【C++高阶】探索STL的瑰宝 map与set:高效数据结构的奥秘与技巧
26 0
|
27天前
|
Dart
Dart之集合详解(List、Set、Map)
Dart之集合详解(List、Set、Map)
22 1
|
1月前
|
存储 JavaScript 前端开发
JavaScript进阶-Map与Set集合
【6月更文挑战第20天】JavaScript的ES6引入了`Map`和`Set`,它们是高效处理集合数据的工具。`Map`允许任何类型的键,提供唯一键值对;`Set`存储唯一值。使用`Map`时,注意键可以非字符串,用`has`检查键存在。`Set`常用于数组去重,如`[...new Set(array)]`。了解它们的高级应用,如结构转换和高效查询,能提升代码质量。别忘了`WeakMap`用于弱引用键,防止内存泄漏。实践使用以加深理解。
|
12天前
|
存储 安全 Java
Java基础之集合Map
【7月更文挑战第8天】Java中的Map集合以键值对方式存储数据,如`Map&lt;&quot;name&quot;, &quot;张三&quot;&gt;`。Map接口定义了存取、判断、移除等操作,包括`put`、`get`、`containsKey`等方法。HashMap是最常用的实现,基于哈希表,允许null键值,但不保证顺序。其他实现包括同步的Hashtable、处理属性文件的Properties、保持插入顺序的LinkedHashMap、基于红黑树的TreeMap、弱引用的WeakHashMap、并发安全的ConcurrentHashMap和针对枚举优化的EnumMap。
17 4
|
28天前
|
缓存 Java 测试技术
探讨Java中遍历Map集合的最快方式
探讨Java中遍历Map集合的最快方式
18 1