【C++】模拟map和set以及改造红黑树

news/2024/10/18 0:33:47/

文章目录

    • 1、set和map的基础用法
      • 1.1 set的基本使用
      • 1.2 map的基本使用
    • 2、set和map的模拟实现
      • 2.1 建立map和set类
      • 2.1 红黑树的完善

1、set和map的基础用法

stl中，像vector、list、deque等这样的容器，称之为序列式容器，其底层是线性序列的数据结构，里面存储的元素本身。
关联式容器，关联式容器不同的是，其存储是一个<key, value>键值对。
STL中关于键值对的定义:
在这里插入图片描述
简单来说就是可以通过一个pair对象访问其两个成员变量first和second，达到键值对的目的。

树型结构中的关联式容器主要有set、multiset、map和multimap。这四个容器的底层都是用的红黑树。
下面先一个一个看。

1.1 set的基本使用

在这里插入图片描述
set存储的是一值，和大部分容器一样，有着基本的begin、end、insert、erase、find、empty、size，这也是主要的功能。
值得说的是set由于底层是一个红黑树，其存储的数据没有重复的，并且set不允许修改数据，所以相较于map缺少了[]访问符，因为会打乱其结构。
 
如果需要重复的数据，multiset就派上了用场，multiset除了存储的数据可以重复外，其它的用法和set基本一致。
在这里插入图片描述

#include <iostream>
#include <set>
using std::cout;
using std::endl;template<class T>
void testCont();void testSet()
{//set默认less->升序 greater->降序testCont< std::set<int, std::greater<int>> >();
}void testMultiset()
{testCont< std::multiset<int, std::greater<int>> >();
}template<class T>
void testCont()
{T s;int arr[] = { 1,4,6,7,9,2,5,6 };//set不仅可以排序，也有去重功能for (auto& e : arr){s.insert(e);}typename T::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;it = s.find(4);s.erase(it);for (auto& k : s){cout << k << " ";}cout << endl;
}int main()
{testSet();testMultiset();return 0;
}

在这里插入图片描述
 

1.2 map的基本使用

这里是引用
map存储的是一个键值对，有着基本的begin、end、insert、erase、find、empty、size、[]，这也是主要的功能。

 
在这里插入图片描述
multimap和map基本上一样，除了可以存储重复数据以及没有[]操作符。

 

值得注意的是map的[]操作符:
在官方文档中，将[]操作符等价于
在这里插入图片描述
其中insert，返回一个键值对，如果插入新值，返回新结点的迭代器和true，如果已有结点返回指向已有结点的迭代器和false。
在这里插入图片描述
在这里插入图片描述

简化后如下

value& operator[](const K& key)
{pair<iterator, bool> ret = this->insert(make_pair(key, K()));return *(ret.first).second;
}

常规用法

#include <iostream>
#include <map>
using std::cout;
using std::endl;template<class T>
void testCont();void testMap()
{testCont< std::map<int, int, std::greater<int>> >();
}void testMultimap()
{testCont< std::multimap<int, int, std::greater<int>> >();
}template<class T>
void testCont()
{T s;int arr[] = { 1,4,6,7,9,2,5,6 };//map不仅可以排序，也有去重功能for (auto& e : arr){s.insert(std::make_pair(e, e));}typename T::iterator it = s.begin();while (it != s.end()){cout << (*it).first << ":" << (*it).second << " ";++it;}cout << endl;it = s.find(4);s.erase(it);for (auto& kv : s){cout << kv.first << ":" << kv.second << " ";}cout << endl;cout << endl;
}void testinsert()
{std::map<int, int, std::greater<int>> m;std::multimap<int, int, std::greater<int>> ml;//multimap 不支持[]操作符，因为其存储重复数据int arr[] = { 1,4,6,7,9,2,5,6 };for (auto& e : arr){m[e] = e;//ml[e] = e; errorml.insert(std::make_pair(e, e));}for (auto& kv : m){cout << kv.first << ":" << kv.second << " ";}cout << endl;for (auto& kv : ml){cout << kv.first << ":" << kv.second << " ";}}int main()
{testMap();testMultimap();testinsert();return 0;
}

 

2、set和map的模拟实现

为了更好的认识set和map，通过了解它们的stl源码，简单实现它们的功能。
 
set和map底层都是通过红黑树实现的。
在这里插入图片描述

2.1 建立map和set类

1、首先为了避免于std中重名，将创建的类放入test命名空间。
2、在stl源码中，map给红黑树传的模板参数是一个key和一个键值对
3、为了应对对红黑树结点取值不同的情况，通过传一个keyofValue类型，再通过仿函数的形式区分map和set访问的不同类型。
4、定义map迭代器的时候，typaname是为了表示
RBTree<K, pair<const K, V>, mapKeyOfValue>::iterator
是一个类型而不是一个其他的具体的值。（因为类::这样是可以访问类中定义的static类型和静态方法的）
5、注意键值对中的key不能修改。

//map.h
#pragma once
#include "RBTree.h"namespace test
{template<class K, class V>class map{struct mapKeyOfValue{//专门放在mapKeyOfValue中，这样可读性好const K& operator()(const pair<const K, V>& kv){return kv.first;}};public:typedef typename RBTree<K, pair<const K, V>, mapKeyOfValue>::iterator iterator;typedef typename RBTree<K, pair<const K, V>, mapKeyOfValue>::const_iterator const_iterator;pair<iterator, bool> insert(const pair<const K, V>& kv){return _t.insert(kv);}iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin() const{return _t.begin();}const_iterator end() const{return _t.end();}V& operator[](const K& k){pair<iterator, bool> ret = insert(make_pair(k, V()));return ret.first->second;}iterator find(const K& k){return _t.find(k);}/*const_iterator find(const K& k) const{return _t.find(k);}*/private:RBTree<K, pair<const K, V>, mapKeyOfValue> _t;};

1、set要求的是迭代器返回指向的结点不能被修改，所以定义的iterator和const_iterator，都用的是红黑树的const_iterator进行定义。
2、set中的insert调用红黑树中的insert会返回一个键值对，这个键值对里面的iterator返回的是红黑树中的普通迭代器，这个普通迭代器再返回给set中的insert键值对时，会发生键值对的拷贝构造，对应红黑树的普通迭代器需要转换成const迭代器（因为set中iterator是用红黑树const迭代器实现的）。（我们在红黑树迭代器类中看具体是怎么处理的）

#pragma once
#include "RBTree.h"namespace test
{template<class K>class set{struct setKeyOfValue{const K& operator()(const K& k){return k;}};public:typedef typename RBTree<K, K, setKeyOfValue>::const_iterator iterator;typedef typename RBTree<K, K, setKeyOfValue>::const_iterator const_iterator;pair<iterator, bool> insert(const K& k){//这里返回的一个pair，然后调用pair的拷贝构造，pair拷贝构造又要调用iterator的拷贝构造（调用默认拷贝构造），//因为这里的iterator是RBTree中的const迭代器，返回的pair里是RBTree的普通迭代器//所以出现了如何将普通迭代器转换成const迭代器的问题//return _t.insert(k);//这样写就好理解一点pair<typename RBTree<K, K, setKeyOfValue>::iterator, bool> ret = _t.insert(k);return pair<iterator, bool>(ret.first, ret.second);}//这里只需要提供普通迭代器版本就行，因为const this指针会调用RBTree里的const迭代器iterator begin() const{return _t.begin();}iterator end() const{return _t.end();}iterator find(const K& k){return _t.find(k);}private:RBTree<K, K, setKeyOfValue> _t;};

2.1 红黑树的完善

在红黑树的结点中，只存一个值，map中存键值对，set中存一个值。

//RBTree.h
#pragma once
#include <iostream>
#include <string>
#include <assert.h>
using namespace std;enum Color { RED = 0, BLACK };template<class T>
struct RBTreeNode
{struct RBTreeNode<T>* _left;struct RBTreeNode<T>* _right;struct RBTreeNode<T>* _parent;T _data;Color _col;RBTreeNode(const T& data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(BLACK){}
};

实现红黑树迭代器

迭代器中通过模板参数有这几个妙手：
1、比较常见的，对应普通迭代器需要返回T&、T*，对应const迭代器需要返回const T&、const T*，通过template<class T, class Ref, class Ptr>，就能实现普通迭代器和const迭代器的转换。
2、如果需要将普通迭代器转换成const迭代器，通过
typedef RBTreeIterator<T, T&, T*> iterator;表示普通迭代器。
在需要用普通迭代器构造成const迭代器的时候，通过调用RBTreeIterator(const iterator& s)这个构造就能实现。

//RBTree.h
// 对于红黑树类中定义迭代器
//	typedef RBTreeIterator<T, T&, T*> iterator;
//	typedef RBTreeIterator<T, const T&, const T*> const_iterator;
template<class T, class Ref, class Ptr>
struct RBTreeIterator
{typedef RBTreeNode<T> Node;typedef RBTreeIterator<T, Ref, Ptr> Self;typedef RBTreeIterator<T, T&, T*> iterator;RBTreeIterator(Node* node):_node(node){}//当是普通迭代器的时候，Self和iterator都一样这时候下面的函数是一个拷贝构造//当是const迭代器的时候，Ref是const T&，Ptr是const T*//这个时候，Self代表const迭代器，iterator还是一个普通迭代器下面的函数就成了一个构造函数（用普通构造const的构造函数)。RBTreeIterator(const iterator& s):_node(s._node){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}Self& operator++(){if (_node->_right){Node* minRight = _node->_right;while (minRight->_left){minRight = minRight->_left;}_node = minRight;}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* maxLeft = _node->_left;while (maxLeft->_right){maxLeft = maxLeft->_right;}_node = maxLeft;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && parent->_left == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}Node* _node;
};

改造红黑树插入

template<class K, class T, class KeyOfValue>
class RBTree
{typedef RBTreeNode<T> Node;
public:typedef RBTreeIterator<T, T&, T*> iterator;typedef RBTreeIterator<T, const T&, const T*> const_iterator;//树的最左结点iterator begin(){if (_root == nullptr){return iterator(nullptr);}Node* pbegin = _root;while (pbegin->_left){pbegin = pbegin->_left;}return iterator(pbegin);}iterator end(){return iterator(nullptr);}//迭代器指向的结点不能改变const_iterator begin() const{if (_root == nullptr){return const_iterator(nullptr);}Node* pbegin = _root;while (pbegin->_left){pbegin = pbegin->_left;}return const_iterator(pbegin);}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);}//类实例化KeyOfValue kov;Node* cur = _root;Node* parent = _root;while (cur){//仿函数if (kov(cur->_data) < kov(data)){parent = cur;cur = cur->_right;}else if (kov(cur->_data) > kov(data)){parent = cur;cur = cur->_left;}else{return make_pair(iterator(cur), false);}}cur = new Node(data);Node* ret = cur;cur->_col = RED;if (kov(parent->_data) < kov(cur->_data)){parent->_right = cur;cur->_parent = parent;}else{parent->_left = cur;cur->_parent = parent;}while (parent && parent->_col == RED){Node* grandparent = parent->_parent;if (parent == grandparent->_left){Node* uncle = grandparent->_right;if (uncle && uncle->_col == RED){//第一种情况parent->_col = BLACK;uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{//需要判断cur在parent的哪边if (parent->_right == cur){//情况四RotateL(parent);RotateR(grandparent);cur->_col = BLACK;grandparent->_col = RED;}else{//情况二/三RotateR(grandparent);parent->_col = BLACK;grandparent->_col = RED;}break;}}else{Node* uncle = grandparent->_left;if (uncle && uncle->_col == RED){//第一种情况parent->_col = BLACK;uncle->_col = BLACK;grandparent->_col = RED;cur = grandparent;parent = cur->_parent;}else{//需要判断cur在parent的哪边if (parent->_right == cur){//情况二/三RotateL(grandparent);parent->_col = BLACK;grandparent->_col = RED;}else{//情况四RotateR(parent);RotateL(grandparent);cur->_col = BLACK;grandparent->_col = RED;}break;}}}_root->_col = BLACK;return make_pair(iterator(ret), true);}void RotateL(Node* parent){Node* sub = parent->_right;Node* subL = sub->_left;parent->_right = subL;if (subL){subL->_parent = parent;}sub->_left = parent;Node* ppnode = parent->_parent;parent->_parent = sub;if (ppnode == nullptr){_root = sub;_root->_parent = nullptr;}else{if (ppnode->_right == parent){ppnode->_right = sub;}else{ppnode->_left = sub;}sub->_parent = ppnode;}}void RotateR(Node* parent){Node* sub = parent->_left;Node* subR = sub->_right;parent->_left = subR;if (subR){subR->_parent = parent;}sub->_right = parent;Node* ppnode = parent->_parent;parent->_parent = sub;if (ppnode == nullptr){_root = sub;_root->_parent = nullptr;}else{if (ppnode->_right == parent){ppnode->_right = sub;}else{ppnode->_left = sub;}sub->_parent = ppnode;}}iterator find(const K& k){if (_root == nullptr){return iterator(nullptr);}KeyOfValue kov;Node* cur = _root;while (cur){if (kov(cur->_data) < k){cur = cur->_right;}else if (kov(cur->_data) > k){cur = cur->_left;}else{return iterator(cur);}}return iterator(nullptr);}
private:Node* _root = nullptr;
};

结果测试

#include "map.h"
#include "set.h"void maptest(){test::map<int, int> m;int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto& e : arr){m[e] = e;}test::map<int, int>::iterator it = m.begin();while (it != m.end()){cout << (*it).first << ":" << (*it).second << endl;++it;}test::map<string, int> countMap;string arr1[] = { "苹果", "西瓜", "香蕉", "草莓", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };for (auto& e : arr1){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}test::map<string, int>::iterator it1 = countMap.find("西瓜");cout << "西瓜: " << (*it1).second << endl;}void settest(){test::set<int> s;int arr[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };for (auto& e : arr){s.insert(e);}test::set<int>::iterator it = s.begin();while (it != s.end()){//*it += 10; //set不能修改数据cout << *it << " ";++it;}cout << endl;it = s.find(4);cout << *it << endl;}int main(){settest();maptest();return 0;}

在这里插入图片描述

本节完~


http://www.ppmy.cn/news/26599.html

相关文章

RT-Thread SPI使用教程

RT-Thread SPI使用教程

RT-Thread SPI 使用教程 实验环境使用的是正点原子的潘多拉开发板。 SPI从机设备使用的是BMP280温湿度大气压传感器。 使用RT-Thread Studio搭建基础功能。 1. 创建工程 使用RT-Thread Studio IDE创建芯片级的工程。创建完成后&#xff0c;可以直接编译下载进行测试。 2.…
阅读更多...
Java多线程——Thread类的基本用法

Java多线程——Thread类的基本用法

一.线程的创建继承Thread类//继承Thread类class MyThread extends Thread{Overridepublic void run() {System.out.println("线程运行的代码");} } public class Demo1 {public static void main(String[] args) {MyThread t new MyThread();t.start();//启动线程&a…
阅读更多...
数值方法笔记3：线性和非线性方程组求解

数值方法笔记3：线性和非线性方程组求解

前置知识1&#xff1a;矩阵范数前置知识2&#xff1a;舒尔补前置知识3&#xff1a;可约矩阵前置知识4&#xff1a;谱半径1.【线性方程组】直接求解&#xff1a;高斯消元法(LULULU分解)、LDVLDVLDV分解、LDLTLDL^TLDLT分解、UDUTUDU^TUDUT分解1.1 高斯消元法(LULULU分解)1.2 LDV…
阅读更多...
fuzz测试之libfuzzer使用小结

fuzz测试之libfuzzer使用小结

fuzz测试之libfuzzer使用小结背景基本原理使用方法主调DEMO参考资料背景 项目中&#xff0c;为测试算法的鲁棒性&#xff0c;经常会用到fuzz测试进行压力测试。fuzz测试是一种模糊测试方法&#xff0c;本质是通过灌入各种变异的随机数据&#xff0c;去遍历不同函数分支&#xf…
阅读更多...
简洁易用的记账小程序——微点记账

简洁易用的记账小程序——微点记账

背景 由于每个月的信用卡账单太过吓人&#xff0c;记性也不是特别的好&#xff0c;加上微信支付宝账单中有些明细不是很明确。比如在京东花销的明细不会记录用户购买了什么&#xff0c;只会记录那个通道支出的。所以&#xff0c;才会有了想自己开发一款记账小程序&#xff0c;…
阅读更多...
两年外包生涯做完，感觉自己废了一半....

两年外包生涯做完，感觉自己废了一半....

先说一下自己的情况。大专生&#xff0c;17年通过校招进入湖南某软件公司&#xff0c;干了接近2年的点点点&#xff0c;今年年上旬&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落&#xff01;而我已经在一个企业干了五年的功能测试…
阅读更多...
信息系统项目管理师知识点汇总（2023最新）

信息系统项目管理师知识点汇总（2023最新）

信息系统项目管理师 信息系统项目管理师简介如何应对考试考试细节与学习 十大管理 十大管理四十七过程 信息化和信息系统 项目管理基础 项目整体管理 项目范围管理 项目进度管理 项目成本管理 项目质量管理 项目人力资源管理 项目沟通管理 项目干系人管理 项目风险…
阅读更多...
【C++】引用、内联函数、auto关键字、范围for、nullptr

【C++】引用、内联函数、auto关键字、范围for、nullptr

引用什么叫引用引用的特性常引用使用场景传值、传引用效率比较引用和指针的区别内联函数auto关键字(C11)基于范围的for循环(C11)指针空值nullptr(C11)引用 什么叫引用 引用不是新定义一个变量&#xff0c;而是给已存在变量取了一个别名&#xff0c;编译器不会为引用变量开辟内…
阅读更多...
最新文章

Copyright @ 2022~2023