浙江建设网一官方网站,dede模板蓝色大气简洁企业网站模板下载,网站模板 红色,茂名网站建设方案书前言 作者#xff1a;小蜗牛向前冲 名言#xff1a;我可以接受失败#xff0c;但我不能接受放弃 如果觉的博主的文章还不错的话#xff0c;还请点赞#xff0c;收藏#xff0c;关注#x1f440;支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录
一、键值对… 前言 作者小蜗牛向前冲 名言我可以接受失败但我不能接受放弃 如果觉的博主的文章还不错的话还请点赞收藏关注支持博主。如果发现有问题的地方欢迎❀大家在评论区指正 目录
一、键值对
二、set
1、set的基本知识
2、set的使用
三、map
1、map的基本知识
2、map的使用
3、multiset和multimap
4、oj的运用
四、map和set的模拟实现
1、红黑树迭代器
2、set.h模拟实现
3、map.h模拟实现 本期学习目标理解什么是键值对实现红黑树的迭代器模拟实现map和set.
一、键值对
键值对是一种简单但强大的数据表示方式通常用于构建关联关系。它由两部分组成键Key和值Value。每个键都唯一地标识一个值。这种数据结构被广泛用于编程中的各种场景
举例来说考虑一个电话簿其中每个人的名字键都对应着他们的电话号码值。在这个例子中名字就是键电话号码就是值。这样的组织方式使得我们可以通过名字快速查找到对应的电话号码。
SGI-STL中关于键值对的定义
template class T1, class T2
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1 a, const T2 b): first(a), second(b)
{}
}
在map和set我们的都有键值对的运用具体运用场景下面会一一道来这里我们知要明白键值对有二个按键都能唯一 标识一个值。
二、set
1、set的基本知识 1. set是按照一定次序存储元素的容器2. 在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。 set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们。3. 在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。4. set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对 子集进行直接迭代。5. set在底层是用二叉搜索树(红黑树)实现的。 T: set中存放元素的类型实际在底层存储的键值对。Compareset中元素默认按照小于来比较 Allocset中元素空间的管理方式使用STL提供的空间配置器管理 注意 set中只放 value但在底层实际存放的是由构成的键值对。set中插入元素时只需要插入value即可不需要构造键值对。set中的元素不可以重复(因此可以使用set进行去重)。使用set的迭代器遍历set中的元素可以得到有序序列。set中的元素默认按照小于来比较set中查找某个元素时间复杂度为log_2 n 2、set的使用
set的构造
函数声明功能介绍set (const Compare comp Compare(), const Allocator Allocator() );构造空的setset (InputIterator first, InputIterator last, const Compare comp Compare(), const Allocator Allocator() );用[first, last)区 间中的元素构造 setset ( const setkey,compare,Allocator x );set的拷贝构造
set的迭代器 set的容量
set修改操作 这些接口和前面的设计都非常类似这里就不在一一分析了。 下面我们快速使用上面的接口了解一下set
void test1()
{setint s;s.insert(4);s.insert(67);s.insert(2);s.insert(1);s.insert(55);s.insert(11);s.insert(5);for (auto v : s){cout v ;v;}cout endl;auto it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;/*auto pos s.find(55);*/auto pos find(s.begin(), s.end(), 55);if (pos ! s.end()){s.erase(pos);}cout s.erase(67) endl;cout s.erase(11) endl;it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;//s.count的功能和find类似
}三、map
1、map的基本知识 1. map是关联容器它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的 素。2. 在map中键值key通常用于排序和惟一地标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型 value_type绑定在一起为其取别名称为pair: typedef pair value_type;3. 在内部map中的元素总是按照键值key进行比较排序的。4. map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序 对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列)。5. map支持下标访问符即在[]中放入key就可以找到与key对应的value。6. map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。 注意 1. map中的的元素是键值对 2. map中的key是唯一的并且不能修改 3. 默认按照小于的方式对key进行比较 4. map中的元素如果用迭代器去遍历可以得到一个有序的序列 5. map的底层为平衡搜索树(红黑树)查找效率比较高O(log_2 N) 6. 支持[]操作符operator[]中实际进行插入查找 2、map的使用
map的构造
函数声明功能介绍map()构造一个空的map
map的迭代器
函数声明功能介绍begin()和end()begin:首元素的位置end最后一个元素的下一个位置cbegin()和cend()与begin和end意义相同但cbegin和cend所指向的元素不 能修改rbegin()和rend()反向迭代器rbegin在end位置rend在begin位置其 和--操作与begin和end操作移动相反crbegin()和crend()与rbegin和rend位置相同操作相同但crbegin和crend所 指向的元素不能修改 map的容量与元素访问
函数声明功能介绍bool empty ( ) const检测map中的元素是否为空是返回 true否则返回falssize_type size() const返回map中有效元素的个数mapped_type operator[] (const key_type k)返回去key对应的value
这里我们要特别的注意
重载的[]不仅仅能够插入和修改元素还能查找元素。 map中元素的修改 快速上手map
void test1()
{mapstring,string dict;dict.insert(pairstring, string(右, right));dict.insert(pairstring, string(传说, legend));dict.insert(make_pair(字符串, string));dict[迭代器] iterator;for (auto kv : dict){cout kv.first : kv.second endl;}string arr[] { 苹果, 西瓜, 香蕉, 草莓, 苹果, 西瓜, 苹果, 苹果, 西瓜, 苹果, 香蕉, 苹果, 香蕉 };mapstring, int countMap;for (auto e : arr){auto it countMap.find(e);if (it countMap.end()){// 元素不存在插入它并初始化计数为 1countMap.insert(make_pair(e, 1));}else{//元素以及存在递增it-second;}}for (const auto kv : countMap){cout kv.first kv.second endl;}
} 这里我们用map就完美的实现了kv模型
这里我们特别注意map的插入和以前学习的数据结构不一样不在是仅仅直接插入数据这里插入的是一个pair类型类型内容1,内容2
3、multiset和multimap
这二个容器的用法和前面一样与set和map的区别是set和map里面的值都是不可重复的而multiset和multimp里面是可以存放相同的值
4、oj的运用
为了加深对map和set的运用为大家分享了二道oj题 题1
代码实现
class Solution {
public:struct compare{bool operator()(const pairint, string l, const pairint, string r){return l.first r.first;}};vectorstring topKFrequent(vectorstring words, int k) {mapstring, int countMap;for (auto str : words){countMap[str];}vectorpairint, string v;//将map去重后的元素入vfor (auto kv : countMap){v.push_back(make_pair(kv.second, kv.first));}//排序stable_sort(v.begin(), v.end(), compare());vectorstring vv;for (int i 0; i k; i){vv.push_back(v[i].second);}return vv;}
};
题2 class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {//用set排序去重setint s1(nums1.begin(),nums1.end());setint s2(nums2.begin(),nums2.end());auto it1 s1.begin();auto it2 s2.begin();vectorint v;while(it1 ! s1.end() it2 ! s2.end()){if(*it1 *it2){v.push_back(*it1);it1;it2;}else if(*it1 *it2){it1;}else{it2;}}return v;}
};
四、map和set的模拟实现
上面我们说了map和set的底层实现是红黑树前面文章也模拟实现了红黑树但是为了更加契合map和set的功能我们还需要对红黑树进行改造。
1、红黑树迭代器
红黑树的迭代器基本框架
templateclass T,class Ref,class Ptr
struct _RBTreeIterator
{typedef RBTreeNodeT Node;typedef _RBTreeIteratorT,Ref,Ptr Self;typedef _RBTreeIteratorT, T, T* iterator;Node* _node;};
这里大家可能会有疑惑的是为什么要重命名二个模板类型不一样的_RBTreeIteratorself 是表示迭代器自身的类型而 iterator 是公开接口的迭代器类型。这样由利用不同编程场景的适应
*(解引用)和-(成员访问运算符) Ref operator*()
{return _node-_data;
}Ptr operator-()
{return (_node-_data);
}
对于 *我们应该返回的是当前节点中的数据对于-返回的是存放当前节点数据的地址。
operator()和 operator--()
对于红黑树的操作就是指向比当前节点更大的树但是对于一课红黑树来说是存在二种情况的 如果右子树存在就找右子树的最小如果右子树不存在情况1 如果如果当前节点是其父节点的右子树或者当前节点是树的根节点其某个祖先节点。情况2如果当前节点是其父节点的左子树,那下一个节点就是其父节点 代码实现
Self operator()
{//如果右子树存在就找右子树的最小if (_node-_right){Node* min _node-_right;while (min-_left){min min-_left;}//找到了右树的最小_node min;}else{Node* cur _node;Node* parent cur-_parent;//找到一个节点是其父节点的左孩子或者到达根节点//如果当前节点是其父节点的左子树,那下一个节点就是其父节点//如果如果当前节点是其父节点的右子树或者当前节点是树的根节点其某个祖先节点while (parent cur parent-_right){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;
}
对于红黑树的--操作情行可以对比操作的分类完成 Self operator--(){//左子树存在if (_node-_left){//找左子树中最大Node* max _node-_left;while (max-_right){max max-_right;}_node max;}else{Node* cur _node;Node* parent cur-_parent;//cur在parent的左while (parent cur cur-left){cur cur-_parent;parent parent-_parent;}_node parent;}}
其他细节的完善逻辑都比较简单可以参考下面代码自行完成
//红黑树的迭代器
templateclass T,class Ref,class Ptr
struct _RBTreeIterator
{typedef RBTreeNodeT Node;typedef _RBTreeIteratorT,Ref,Ptr Self;typedef _RBTreeIteratorT, T, T* iterator;Node* _node;//构造函数_RBTreeIterator(Node* node):_node(node){}// const迭代器的时候他是构造支持用普通迭代器构造const迭代器_RBTreeIterator(const iterator s):_node(s._node){}Ref operator*(){return _node-_data;}Ptr operator-(){return (_node-_data);}Self operator(){//如果右子树存在就找右子树的最小if (_node-_right){Node* min _node-_right;while (min-_left){min min-_left;}//找到了右树的最小_node min;}else{Node* cur _node;Node* parent cur-_parent;//找到一个节点是其父节点的左孩子或者到达根节点//如果当前节点是其父节点的左子树,那下一个节点就是其父节点//如果如果当前节点是其父节点的右子树或者当前节点是树的根节点其某个祖先节点while (parent cur parent-_right){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}Self operator--(){//左子树存在if (_node-_left){//找左子树中最大Node* max _node-_left;while (max-_right){max max-_right;}_node max;}else{Node* cur _node;Node* parent cur-_parent;//cur在parent的左while (parent cur cur-left){cur cur-_parent;parent parent-_parent;}_node parent;}}bool operator!(const Selfs)const{return _node ! s._node;}bool operator(const Self s)const{return _node s._node;}
};对于之前写的红黑树我们还做一些变更比如insert的返回值不是简单判断是否插入成功而是返回一个键值对返回是当前插入节点的迭代器并判断是否插入成功。
红黑树完整实现
#pragma onceenum Colour
{RED,BLACK,
};templateclass T
struct RBTreeNode
{T _data;RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Colour _col;RBTreeNode(const T data):_data(data), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}
};//红黑树的迭代器
templateclass T,class Ref,class Ptr
struct _RBTreeIterator
{typedef RBTreeNodeT Node;typedef _RBTreeIteratorT,Ref,Ptr Self;typedef _RBTreeIteratorT, T, T* iterator;Node* _node;//构造函数_RBTreeIterator(Node* node):_node(node){}// const迭代器的时候他是构造支持用普通迭代器构造const迭代器_RBTreeIterator(const iterator s):_node(s._node){}Ref operator*(){return _node-_data;}Ptr operator-(){return (_node-_data);}Self operator(){//如果右子树存在就找右子树的最小if (_node-_right){Node* min _node-_right;while (min-_left){min min-_left;}//找到了右树的最小_node min;}else{Node* cur _node;Node* parent cur-_parent;//找到一个节点是其父节点的左孩子或者到达根节点//如果当前节点是其父节点的左子树,那下一个节点就是其父节点//如果如果当前节点是其父节点的右子树或者当前节点是树的根节点其某个祖先节点while (parent cur parent-_right){cur cur-_parent;parent parent-_parent;}_node parent;}return *this;}Self operator--(){//左子树存在if (_node-_left){//找左子树中最大Node* max _node-_left;while (max-_right){max max-_right;}_node max;}else{Node* cur _node;Node* parent cur-_parent;//cur在parent的左while (parent cur cur-left){cur cur-_parent;parent parent-_parent;}_node parent;}}bool operator!(const Selfs)const{return _node ! s._node;}bool operator(const Self s)const{return _node s._node;}
};// map-RBTreeK, pairconst K, V, MapKeyOfT _t;
// set-RBTreeK, K, SetKeyOfT _t;
templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:typedef _RBTreeIteratorT,T,T* iterator;typedef _RBTreeIteratorT, const T,const T* const_iterator;iterator begin(){Node* left _root;while (left left-_left){left left-_left;}return iterator(left);}const_iterator begin()const{Node* left _root;while (left left-_left){left left-_left;}return iterator(left);}iterator end(){return iterator(nullptr);}const_iterator end() const{return iterator(nullptr);}pairiterator,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);}}cur new Node(data);Node* newnode cur;//保存插入节点位置cur-_col RED;if (kot(parent-_data) kot(data)){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}while (parent parent-_col RED){Node* grandfater parent-_parent;if (parent grandfater-_left){Node* uncle grandfater-_right;// 情况一 uncle存在且为红if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;cur grandfater;parent cur-_parent;}else{if (cur parent-_left){// 情况二RotateR(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况三RotateL(parent);RotateR(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}else // (parent grandfater-_right){Node* uncle grandfater-_left;if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;cur grandfater;parent cur-_parent;}else{// g // p// cif (cur parent-_right){RotateL(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// g // p// cRotateR(parent);RotateL(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}}_root-_col BLACK;return make_pair(iterator(newnode),true);}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (ppNode nullptr){_root subR;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR){subLR-_parent parent;}Node* ppNode parent-_parent;subL-_right parent;parent-_parent subL;//if (_root parent)if (ppNode nullptr){_root subL;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}void Inorder(){_Inorder(_root);}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first : root-_kv.second endl;_Inorder(root-_right);}bool Check(Node* root, int blackNum, const int ref){if (root nullptr){//cout blackNum endl;if (blackNum ! ref){cout 违反规则本条路径的黑色节点的数量跟最左路径不相等 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout 违反规则出现连续红色节点 endl;return false;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, ref) Check(root-_right, blackNum, ref);}bool IsBalance(){if (_root nullptr){return true;}if (_root-_col ! BLACK){return false;}int ref 0;Node* left _root;while (left){if (left-_col BLACK){ref;}left left-_left;}return Check(_root, 0, ref);}private:Node* _root nullptr;
};
2、set.h模拟实现 #pragma once#includeRBTree.hnamespace pjb
{templateclass Kclass set{struct setKeyOfT{const K operator()(const K key){return key;}};public://在C中typename 关键字通常用于表示一个依赖于模板参数的类型。在模板中// 有时候编译器无法确定某个名字到底是一个类型还是一个值这时候就需要使用 typename // 来明确告诉编译器某个名字是一个类型。typedef typename RBTreeK, K, setKeyOfT::iterator iterator;typedef typename RBTreeK, K, setKeyOfT::iterator const_iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}const_iterator begin()const{return _t.begin();}const_iterator end()const{return _t.end();}pairiterator,bool insert(const K key){pairtypename RBTreeK, K, setKeyOfT::iterator, bool ret _t.Insert(key);return pairiterator, bool(ret.first, ret.second);/*return _t.Insert(key);*/}private:RBTreeK, K, setKeyOfT _t;};void test_set(){int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };setint s;for (auto e : a){s.insert(e);}setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;for (auto e : s){cout e ;}cout endl;}
}
测试 3、map.h模拟实现
#pragma once
#includeRBTree.hnamespace pjb
{templateclass K,class Vclass map{struct MapKeyOfT{const K operator()(const pairconst K, V kv){return kv.first;}};public:typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator;typedef typename RBTreeK, pairconst 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();}pairiterator,bool insert(const pairconst K, V kv){return _t.Insert(kv);}V operator[](const K key){pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;}private:RBTreeK, pairconst K, V, MapKeyOfT _t;};void test_map(){int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };mapint, int m;for (auto e : a){m.insert(make_pair(e, e));}mapint, int::iterator it m.begin();while (it ! m.end()){//it-first;it-second;cout it-first : it-second endl;it;}cout endl;mapstring, int countMap;string arr[] {西游记,红楼梦,水浒传,三国演义,三国演义 ,三国演义,水浒传 };for (auto e : arr){countMap[e];}for (auto kv : countMap){cout kv.first : kv.second endl;}}}测试:
