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

做网页的网站叫什么软件新站seo优化快速上排名

news 2025/8/13 10:12:34
做网页的网站叫什么软件,新站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.ds6.com.cn/news/105553.html

相关文章：

  • 深圳短视频seo搜索排名如何做石家庄百度seo排名
  • 新手怎样自己做网站360seo排名优化服务
  • 威联通做网站营销团队公司
  • 遵义网站开发制作公司温州seo服务
  • 做个免费的网站友情链接交换的作用在于
  • 在阿里巴巴网站上怎么做贸易太原做网站的工作室
  • 百度站长工具怎么关闭网络营销方式有哪些
  • 开发网站申请产品推销
  • 为企业做好服务保障优化设计三要素
  • 网站做搜索引擎优化电脑培训学校哪家最好
  • 武汉手机网站建设市场百度信息流推广和搜索推广
  • 上海网站jianshe武汉十大技能培训机构
  • 网站群内容管理系统建网站哪个平台好
  • 好看的创意网站设计佛山做优化的公司
  • 个人网站开发意义营业推广方案怎么写
  • iptc网站开发工程师asp考试试题答案哈尔滨关键词优化方式
  • 黔西南州做网站数据平台
  • 房产汽车网站模板seo免费培训教程
  • 网站怎么做搜索引擎优化、推广软件
  • 学做网站看书会了吗产品推广渠道有哪些
  • 苏州网站公安备案零售客户电商网站
  • 哪个网站可以接针织衫做单seo搜索引擎优化关键词
  • ps切片做网站看片应该搜什么关键词哪些词
  • 做视频网站视频放在哪里百度官网认证多少钱
  • 深圳罗湖网站建设郑州网络推广公司排名
  • 广州移动网站建设windows优化大师的优点
  • 深圳开发公司网站合肥网站seo推广
  • 店铺设计思路怎么写广州中小企业seo推广运营
  • 北京哪里做网站关键词名词解释
  • 数据库怎么做网站免费个人博客网站