温馨提示：这篇文章已超过464天没有更新，请注意相关的内容是否还可用！
摘要：Map和Set是两种常见的数据结构，它们在数据存储和检索方面非常有用。Map是一种键值对的数据结构，可以存储和查找任何类型的数据，通过键来快速访问对应的值。Set则是一种不包含重复元素的无序集合，可以用于检查某个元素是否存在于集合中，或者进行集合运算等。这两种数据结构在编程中广泛应用，提供了高效的数据处理能力。
前言
![[数据结构]-map和set，数据结构中的Map和Set简介 第1张](https://img-blog.csdnimg.cn/f55a07090b3541518429c3017449bf1b.png "[数据结构]-map和set，数据结构中的Map和Set简介 第1张"){kind=small}
作者：小蜗牛向前冲
名言：我可以接受失败，但我不能接受放弃
如果觉的博主的文章还不错的话，还请![[数据结构]-map和set，数据结构中的Map和Set简介 第3张](https://img-blog.csdnimg.cn/b51eb37fe01249319b930193c6662039.png "[数据结构]-map和set，数据结构中的Map和Set简介 第3张"){kind=small}
点赞，收藏，关注👀支持博主。如果发现有问题的地方欢迎❀大家在评论区指正
目录
一、键值对
二、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
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在底层是用二叉搜索树(红黑树)实现的。
![[数据结构]-map和set，数据结构中的Map和Set简介 第4张](https://img-blog.csdnimg.cn/a1f1b12c64304782a8aa4f97bf359cea.png "[数据结构]-map和set，数据结构中的Map和Set简介 第4张")
- T: set中存放元素的类型，实际在底层存储的键值对。
- Compare：set中元素默认按照小于来比较 Alloc：set中元素空间的管理方式，使用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() ); 构造空的set set (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Allocator& = Allocator() ); 用[first, last)区 间中的元素构造 set set ( const set& x ); set的拷贝构造 set的迭代器
![[数据结构]-map和set，数据结构中的Map和Set简介 第5张](https://img-blog.csdnimg.cn/2413af4def0c478abe3b9643af3c2d18.png "[数据结构]-map和set，数据结构中的Map和Set简介 第5张")
set的容量
![[数据结构]-map和set，数据结构中的Map和Set简介 第6张](https://img-blog.csdnimg.cn/d3b9d8660c714d3f8b6d0b36b0d72005.png "[数据结构]-map和set，数据结构中的Map和Set简介 第6张")
set修改操作![[数据结构]-map和set，数据结构中的Map和Set简介 第7张](https://img-blog.csdnimg.cn/461fa68c3c764af186ca43079fdd54a3.png "[数据结构]-map和set，数据结构中的Map和Set简介 第7张")
这些接口和前面的设计都非常类似，这里就不在一一分析了。
下面我们快速使用上面的接口，了解一下set
void test1() { set 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 left) { cur = cur->_parent; parent = parent->_parent; } _node = parent; } }其他细节的完善，逻辑都比较简单，可以参考下面代码自行完成：
//红黑树的迭代器 template struct _RBTreeIterator { typedef RBTreeNode Node; typedef _RBTreeIterator Self; typedef _RBTreeIterator 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 Self&s)const { return _node != s._node; } bool operator==(const Self& s)const { return _node == s._node; } };对于之前写的红黑树，我们还做一些变更比如insert的返回值不是简单判断是否插入成功，而是返回一个键值对，返回是当前插入节点的迭代器，并判断是否插入成功。
红黑树完整实现：
#pragma once enum Colour { RED, BLACK, }; template struct RBTreeNode { T _data; RBTreeNode* _left; RBTreeNode* _right; RBTreeNode* _parent; Colour _col; RBTreeNode(const T& data) :_data(data) , _left(nullptr) , _right(nullptr) , _parent(nullptr) , _col(RED) {} }; //红黑树的迭代器 template struct _RBTreeIterator { typedef RBTreeNode Node; typedef _RBTreeIterator Self; typedef _RBTreeIterator 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 Self&s)const { return _node != s._node; } bool operator==(const Self& s)const { return _node == s._node; } }; // map->RBTree _t; // set->RBTree _t; template class RBTree { typedef RBTreeNode Node; public: typedef _RBTreeIterator iterator; typedef _RBTreeIterator 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); } pair 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) _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) _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 // c if (cur == parent->_right) { RotateL(grandfater); parent->_col = BLACK; grandfater->_col = RED; } else { // g // p // c RotateR(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 _kv.first _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 #include"RBTree.h" namespace pjb { template class set { struct setKeyOfT { const K& operator()(const K& key) { return key; } }; public: //在C++中，typename 关键字通常用于表示一个依赖于模板参数的类型。在模板中， // 有时候编译器无法确定某个名字到底是一个类型还是一个值，这时候就需要使用 typename // 来明确告诉编译器某个名字是一个类型。 typedef typename RBTree::iterator iterator; typedef typename RBTree::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(); } pair insert(const K& key) { pair ret = _t.Insert(key); return pair(ret.first, ret.second); /*return _t.Insert(key);*/ } private: RBTree _t; }; void test_set() { int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 }; set s; for (auto e : a) { s.insert(e); } set::iterator it = s.begin(); while (it != s.end()) { cout
文章版权声明：除非注明，否则均为VPS857原创文章，转载或复制请以超链接形式并注明出处。
还没有评论，来说两句吧...