AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2024-06-19 177
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 用改造后的红黑树，模拟实现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的引用，可以直接插入或修改


真诚点赞，手有余香


文章标签：
C++
存储
编译器
容器
关键词：
C++ stl
C++类
Map类
C++ stl set map
stl Map
快乐的流畅
目录
相关文章
凉凉心.
|
2月前
|
存储 JavaScript Java
（Python基础）新时代语言！一起学习Python吧！（四）：dict字典和set类型；切片类型、列表生成式；map和reduce迭代器；filter过滤函数、sorted排序函数；lambda函数
dict字典 Python内置了字典：dict的支持，dict全称dictionary，在其他语言中也称为map，使用键-值（key-value）存储，具有极快的查找速度。 我们可以通过声明JS对象一样的方式声明dict
凉凉心.
209 1
john散漫
|
5月前
|
存储 缓存 JavaScript
Set和Map有什么区别？
Set和Map有什么区别？
john散漫
447 1
胖咕噜的稞达鸭
|
2月前
|
存储 算法 容器
set_map的实现+set/map加持秒杀高频算法题锻炼算法思维
`set`基于红黑树实现，支持有序存储、自动去重，增删查效率为O(logN)。通过仿函数可自定义排序规则，配合空间配置器灵活管理内存。不支持修改元素值，迭代器失效需注意。`multiset`允许重复元素。常用于去重、排序及查找场景。
胖咕噜的稞达鸭
206 3
码字猴儿
|
6月前
|
存储 JavaScript 前端开发
for...of循环在遍历Set和Map时的注意事项有哪些？
for...of循环在遍历Set和Map时的注意事项有哪些？
码字猴儿
337 121
hahaha无
|
6月前
|
存储 C++ 容器
unordered_set、unordered_multiset、unordered_map、unordered_multimap的介绍及使用
unordered_set是不按特定顺序存储键值的关联式容器，其允许通过键值快速的索引到对应的元素。在unordered_set中，元素的值同时也是唯一地标识它的key。在内部，unordered_set中的元素没有按照任何特定的顺序排序，为了能在常数范围内找到指定的key，unordered_set将相同哈希值的键值放在相同的桶中。unordered_set容器通过key访问单个元素要比set快，但它通常在遍历元素子集的范围迭代方面效率较低。它的迭代器至少是前向迭代器。前向迭代器的特性。
hahaha无
289 0
hahaha无
|
6月前
|
编译器 C++ 容器
用一棵红黑树同时封装出map和set
再完成上面的代码后，我们的底层代码已经完成了，这时候已经是一个底层STL的红黑树了，已经已符合库里面的要求了，这时候我们是需要给他穿上对应的“衣服”，比如穿上set的“衣服”，那么这个穿上set的“衣服”，那么他就符合库里面set的要求了，同样map一样，这时候我们就需要实现set与map了。因此，上层容器map需要向底层红黑树提供一个仿函数，用于获取T当中的键值Key，这样一来，当底层红黑树当中需要比较两个结点的键值时，就可以通过这个仿函数来获取T当中的键值了。我们就可以使用仿函数了。
hahaha无
86 0
hahaha无
|
6月前
|
存储 编译器 容器
set、map、multiset、multimap的介绍及使用以及区别，注意事项
set是按照一定次序存储元素的容器，使用set的迭代器遍历set中的元素，可以得到有序序列。set当中存储元素的value都是唯一的，不可以重复，因此可以使用set进行去重。set默认是升序的，但是其内部默认不是按照大于比较，而是按照小于比较。set中的元素不能被修改，因为set在底层是用二叉搜索树来实现的，若是对二叉搜索树当中某个结点的值进行了修改，那么这棵树将不再是二叉搜索树。
hahaha无
255 0
hahaha无
|
6月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果：注意：类模板中的成员函数若是放在类外定义时，需要加模板参数列表。return 0;
hahaha无
190 0
hahaha无
|
6月前
|
存储 编译器 程序员
c++的类（附含explicit关键字，友元，内部类）
本文介绍了C++中类的核心概念与用法，涵盖封装、继承、多态三大特性。重点讲解了类的定义（`class`与`struct`）、访问限定符（`private`、`public`、`protected`）、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数（构造函数、析构函数、拷贝构造、赋值重载）以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员（变量与函数）、友元（友元函数与友元类）的概念及其使用场景，并简要介绍了内部类的特性。
hahaha无
281 0

热门文章

最新文章

  • 1
    C++ ＜windows.h＞库函数探究初步：句柄操作
  • 2
    C++ 对象的内存布局(上)
  • 3
    C++ 多线程系统编程精要
  • 4
    C++语言基础 例程 静态成员
  • 5
    C++ 插件机制的实现原理、过程、及使用
  • 6
    C++静态数据成员实现
  • 7
    设计模式学习--组合模式，c++代码
  • 8
    34、C++ Primer 4th笔记，特殊工具与技术，优化内存分配（1）
  • 9
    C/C++中int128的那点事
  • 10
    C++中int int& int * int**的区别、联系和用途
  • 1
    set_map的实现+set/map加持秒杀高频算法题锻炼算法思维
    206
  • 2
    【Golang】（3）条件判断与循环？切片和数组的关系？映射表与Map？三组关系傻傻分不清？本文带你了解基本的复杂类型与执行判断语句
    155
  • 3
    （Python基础）新时代语言！一起学习Python吧！（四）：dict字典和set类型；切片类型、列表生成式；map和reduce迭代器；filter过滤函数、sorted排序函数；lambda函数
    209
  • 4
    深入理解 go sync.Map - 基本原理
    236
  • 5
    如何在Map中获取元素的数量？
    289
  • 6
    在JavaScript中，Set和Map的性能有什么区别？
    372
  • 7
    Set和Map有什么区别？
    447
  • 8
    让我们讲解一下 Map 集合遍历的方式
    260
  • 9
    基于Logistic-Map混沌序列的数字信息加解密算法matlab仿真,支持对文字,灰度图,彩色图,语音进行加解密
    163
  • 10
    for...of循环在遍历Set和Map时的注意事项有哪些？
    337

    • 相关课程

    更多
  • Go语言核心编程 - 基础语法、数组、切片、Map
  • C++ 入门教程开发文档

    • 相关电子书

    更多
  • 使用C++11开发PHP7扩展
  • GPON Class C++ SFP O;T Transce
  • GPON Class C++ SFP OLT Transce
    • 下一篇
    安全设备篇——WAF