当前位置： 首页 > news >正文

做网页的网站叫什么软件昆明网站seo服务

news 2025/7/27 9:17:26
做网页的网站叫什么软件,昆明网站seo服务,深圳公司注册地址可以是住宅吗,wordpress支付宝即时到帐目录 1、map和set的底层 2、map与set中的key关键值 3、红黑树迭代器的实现。 1、操作 2、-- 操作 3、和!操作 4、在红黑树中封装迭代器 5、map和set对迭代器的封装 1、map map中[]的重载 2、set 1、map和set的底层 map和set都是基于红黑树实现的。红黑树是一种自平衡…

目录

1、map和set的底层

2、map与set中的key关键值

3、红黑树迭代器的实现。

1、++操作

2、-- 操作

3、==和!=操作

4、在红黑树中封装迭代器

5、map和set对迭代器的封装

1、map

map中[]的重载

2、set

1、map和set的底层

        map和set都是基于红黑树实现的。红黑树是一种自平衡的二叉搜索树，它保持着良好的平衡性能，插入、删除、查找的时间复杂度都是O(log n)。在C++ STL中，map和set都是使用红黑树作为底层数据结构来实现的。红黑树在前面文章模拟实现过，可以参考

rep_type通常是用来表示set容器内部红黑树的节点类型。在STL头文件中，通常会定义rep_type作为红黑树节点的类型，用于表示set容器和map容器内部的数据结构。 

可以看到set和map的源代码中都使用了红黑树作为底层数据结构。

可以看到红黑树中的数据类型只有一个，

而在map和set中都有key值，也有数据类型，map的数据类型是键值对pair<const key,T>,set中的数据类型也是key。

2、map与set中的key关键值

那么我们该如何模拟实现呢？

🚀map传给红黑树的模板参数是pair键值对

🚀set传给红黑树的模板参数是key值

 红黑树该如何判断key值来比较大小呢，这个时候我们需要使用仿函数的方法，因为红黑树比较节点只看key值。我们选择仿函数的方法：

map.h文件：

template<class K,class V>
class MYmap
{struct KeyofMap{const K& operator ()(const pair<K,V> &kv){return kv.first;}};
private:RBTree<K, pair<const K, V>, KeyofMap> _t;
};

set.h文件：

template<class T>
class Myset
{struct SetKeyofvalue{const T& operator()(const T& key){return key;}};
private:RBTree<T, const T, SetKeyofvalue> _t;
};

set存放的数据本身就是key，但是为了与红黑树结构：

以及map的结构统一，所以也需要实现一个。

3、红黑树迭代器的实现。

1、++操作

++操作也就是找到下一个比它大的值，那么就有两种可能：

1.右子树的最小值。

//如果右子树不为空，那么比这个元素大的下一个节点就是右子树的最小元素

//也就是右子树的最左节点

2.如果没有右子树，那么向上查找，直到找到一个节点是其父节点的左字数，该父节点就是符合条件的值。

Self& operator++(){//如果右子树不为空，那么比这个元素大的下一个节点就是右子树的最小元素//也就是右子树的最左节点if (_node->_right){Node* subrm = _node->_right;while (subrm->_left){subrm = subrm->_left;}_node = subrm;}//如果右子树为空，那么向上查找，直到找到一个节点是其父节点的左子树else{Node* cur = _node;Node* parent = cur->_parent;while (parent&& parent->_right == cur){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}

2、-- 操作

--操作也就是找到下一个比它小的值，那么就有两种可能：

1.左子树存在

//找出这个迭代器前面一个比它小的元素，如果左子树存在，那么就先找左边最大的节点
//也就是右子树的最右节点

2.左子树不存在

 //如果左子树为空，那么向上查找，直到找到一个节点是其父节点的右子树

Self& operator --(){//找出这个迭代器前面一个比它小的元素，如果左子树存在，那么就先找左边最大的节点//也就是右子树的最右节点if (_node->_left){Node* sublmax = _node->_left;while (sublmax->_right){sublmax = sublmax->_right;}_node = sublmax;}//如果左子树为空，那么向上查找，直到找到一个节点是其父节点的右子树else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}

3、==和!=操作

//重载！=运算符bool operator!=(const Self& s){return _node != s._node;}//重载==运算符bool operator == (const Self & s){return _node == s._node;}

比较的内容是迭代器指向的节点是不是相同，不是比较节点的key值，同时也不需要修改，所以这里只需要const引用即可。

红黑树迭代器完整实现代码：


//红黑树迭代器
template<class T>
struct __RBTreeIterator
{typedef RBTreeNode<T> Node;typedef __RBTreeIterator<T> Self;Node* _node;__RBTreeIterator(Node* node):_node(node){}T& operator *(){return _node->_data;}T* operator ->(){return &_node->_data;}Self& operator++(){//如果右子树不为空，那么比这个元素大的下一个节点就是右子树的最小元素//也就是右子树的最左节点if (_node->_right){Node* subrm = _node->_right;while (subrm->_left){subrm = subrm->_left;}_node = subrm;}//如果右子树为空，那么向上查找，直到找到一个节点是其父节点的左子树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* sublmax = _node->_left;while (sublmax->_right){sublmax = sublmax->_right;}_node = sublmax;}//如果左子树为空，那么向上查找，直到找到一个节点是其父节点的右子树else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = parent->_parent;}_node = parent;}return *this;}//重载！=运算符bool operator!=(const Self& s){return _node != s._node;}//重载==运算符bool operator == (const Self & s){return _node == s._node;}};

4、在红黑树中封装迭代器

在红黑树中，起始节点begin()是最左节点

结束位置是空位置节点

本文采用上面的实现方法。

为了实现左闭右开，STL库采用的是end指向哨兵位头结点，最左边节点也和头相连。


template<class K,class T,class KeyofT>
class RBTree
{
public:typedef __RBTreeIterator<T> iterator;typedef RBTreeNode<T> Node;KeyofT kot;iterator begin(){Node* subleft = _root;while (subleft && subleft->_left){subleft = subleft->_left;}return iterator(subleft);}iterator end(){return iterator(nullptr);}
private:Node* _root=nullptr;
};

5、map和set对迭代器的封装

1、map

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

这里要使用typename

当在模板中使用嵌套类型或依赖于模板参数的类型推导时，需要使用typename关键字来告诉编译器这是一个类型而不是一个变量。这通常出现在模板中使用嵌套类型或依赖于模板参数的类型推导时。

map中[]的重载

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

 map中的[]可以实现查找，修改，插入三个功能。

当使用[]操作符访问map中的元素时，

如果该键已经存在，则返回对应的值；

如果该键不存在，则会插入一个新的键值对，并返回一个默认构造的值。

在红黑树中也要对insert进行修改来匹配 

 

我们来测试一下修改（更改value值）:

#pragma once
#include"RBTree.h"template<class K,class V>
class MYmap
{struct KeyofMap{const K& operator ()(const pair<K,V> &kv){return kv.first;}};
public:typedef typename RBTree<K, pair<const K, V>, KeyofMap>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}V& operator[](const K& key){pair<iterator, bool> ret = Insert(make_pair(key, V()));return ret.first->second;}pair<iterator,bool> Insert(const pair<const K, V>& kv){return _t.Insert(kv);}private:RBTree<K, pair<const K, V>, KeyofMap> _t;
};

2、set

#pragma once
#include"RBTree.h"
template<class T>
class Myset
{struct SetKeyofvalue{const T& operator()(const T& key){return key;}};public:typedef typename RBTree<T,const T, SetKeyofvalue>::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}pair<iterator,bool> Insert(const T& key){return _t.Insert(key);}private:RBTree<T, const T, SetKeyofvalue> _t;
};

在C++的std::map和std::set容器中，元素的键值是不可更改的，这是因为这两个容器是基于红黑树实现的，红黑树的性质要求元素的键值在插入后不能被修改，否则会破坏红黑树的结构。

所以在实现时，map使用了

RBTree<K, pair<const K, V>, KeyofMap> _t;

set使用了

RBTree<T, const T, SetKeyofvalue> _t; 

来保证key值不会被修改。 

下面给出红黑树完整的插入函数：

pair<iterator,bool> Insert(const  T& data){if (_root == nullptr){_root = new Node(data, BLACK);Node* newnode = _root;//根的双亲为头结点return make_pair(iterator(newnode), true);}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(cur,false);}}cur = new Node(data, RED);Node* newnode = cur;if (kot(cur->_data) < kot(parent->_data)){parent->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;while (parent && parent->_color == RED){Node* grandparent = parent->_parent;if (parent == grandparent->_left){Node* uncle = grandparent->_right;if (uncle && uncle->_color == RED){grandparent->_color = RED;parent->_color = BLACK;uncle->_color = BLACK;cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_left){RotateR(grandparent);parent->_color = BLACK;grandparent->_color = RED;}else{RotateL(parent);RotateR(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}else{Node* uncle = grandparent->_left;if (uncle && uncle->_color == RED){grandparent->_color = RED;parent->_color = BLACK;uncle->_color = BLACK;cur = grandparent;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandparent);parent->_color = BLACK;grandparent->_color = RED;}else{RotateR(parent);RotateL(grandparent);cur->_color = BLACK;grandparent->_color = RED;}break;}}}_root->_color = BLACK;return make_pair(iterator(newnode),true);}

通过封装实现Map和Set，可以使用红黑树的特性来实现键值对的存储和查找，同时保持数据结构的平衡性和高效性。以上就是用红黑树封装实现map和set，当然这只是简单实现，对于更好地理解和使用这个容器比较有帮助。

http://www.zhongyajixie.com/news/59698.html

相关文章：

  • 怎么用vps的linux做网站天津seo培训
  • 开源企业cms建站系统营销型网站制作公司
  • 做网站可以找设计公司吗搜狗seo刷排名软件
  • 可以做策略回测的网站seo百度刷排名
  • 百度做网站免费快速seo软件
  • 儋州网站建设培训学校义乌最好的电商培训学校
  • 优美女人女性网站模版友情链接交易平台源码
  • 儿童摄影网站模板英文seo外链
  • 门户网站中综合性程度高的是四川省最新疫情情况
  • 做黑帽需不需要搭建网站semir是什么牌子衣服
  • wordpress登录主题seo排名优化app
  • 自己网站做seo今日头条新闻最新疫情
  • 做的网站 如何在局域网内访问宁波网站关键词排名推广
  • 荔浦网站开发seo分析seo诊断
  • 如何对网站做压力测试百度推广客户端下载
  • 做soho一定要做网站吗百度大搜
  • 深圳 网站建设培训学管理培训班去哪里学
  • 凯里网站设计品牌推广是做什么的
  • 网站三要素怎么做线上推广宣传方式有哪些
  • 电子商务网站建设理解sem是什么品牌
  • 宿迁定制网站建设成人培训班有哪些课程
  • 网站建设服务费税率多少seo外包资讯
  • 设计一个网站加盟教育培训机构
  • 如何让自己的网站被搜索引擎收录如何自己开发网站
  • 点餐网站模板火星时代教育培训机构怎么样
  • 创意网站 模板莆田seo推广公司
  • 织梦网站上传及安装步骤短视频营销常用平台有
  • 唐山网站建设哪家专业杭州网络推广公司
  • 女生做网站开发爱站网ip反查域名
  • 室内设计素材网站推荐北京官网seo收费