STL--map、set的使用和模拟实现

1.set

1.1 set的概念

set 是一种基于 平衡二叉搜索树（通常是红黑树） 实现的容器，它提供了有序集合的功能。set 用于存储唯一的元素，并且元素是按照某种顺序排列的（通常是升序）。

set 确实是一个关联式容器，底层实现使用的是类似于 红黑树 这种自平衡的二叉搜索树，元素在 set 中是以键值对的形式存储的。从底层的实现来看，可以理解为每个元素实际上是一个 pair<value, value>，其中 key 和 value 都是相同的。

set 的底层实现

  • 底层结构：set 是一个关联容器，它的元素是有序的，并且每个元素都是唯一的。底层通常使用 红黑树 来实现，这是一个自平衡的二叉搜索树。在红黑树中，节点包含一个键（key），而对于 set 来说，这个键就是元素的值本身。
  • 元素存储形式：尽管在 set 中我们仅插入一个值（例如一个 int），但这些值实际上存储在底层红黑树的节点中，每个节点包含一个 键 和一个 值，但对于 set 来说，键和值是相同的。C++ 标准库中使用的 pair<const T, T> 结构来表示每个元素，其中 const T 表示键值，T 表示存储的值。因此，在 C++ set 中，元素的形式是 pair<const value, value>，不过这种 pair 结构对于开发者来说是透明的，我们使用者只需要插入和访问 value，并不需要显式操作 pair。

性能

由于底层使用红黑树实现，set 中的插入、删除和查找操作的时间复杂度为 O(log n)，其中 n 是集合中的元素数量。这使得 set 在需要保证元素唯一性且还要支持快速查找和排序时非常高效。

适用于那些需要存储唯一且有序数据的场景，例如去重、排序和高效查找

1.2 set常用方法

         1.模板参数

Compare: 这个类型控制了集合中元素的排序方式。它必须是一个可以进行元素比较的类型，通常是一个函数对象，或是重载了 operator() 的类。最常用的默认比较器是 std::less<T>，它将元素按升序排列。

         2.构造

以下是具体用法

源码：

#include<iostream>#include<set>using namespace std;void test1() {set<int> s1;int a[] = { 1,2,3,4,5,6 };for (auto ch : a) {s1.insert(ch);   // 调用迭代器函数，直接放入val}set<int> s2(s1.begin(), s1.end()); // 迭代器的构造，和s1一样set<int> s3(s2); // 拷贝构造for (auto key : s1) {cout << key << " ";}cout << endl;for (auto key : s2) {cout << key << " ";}cout << endl;for (auto key : s3) {cout << key << " ";}cout << endl;}int main() {test1();return 0;}

         3.set插入

以下是具体用法

源码：

void print(const set<int>& s) {for (auto val : s) {cout << val << " ";}cout << endl;}void test2() {set<int> s1;int a[] = { 1,2,3,4,5,6 };for (auto ch : a) {s1.insert(ch);  }print(s1);// 插入s1.insert(s1.begin(), 0);print(s1);set<int>s2 = { 10,20,30 };s1.insert(s2.begin(), s2.end());print(s1);}

其他的使用在这里就不详细示例，自己根据cplusplus.com - The C++ Resources Network中的模板解释来实现

<set>模板里面包含两个类，还有一个是 multiset

其原理和set几乎一致，只是multiset能存多个相同的值了
注意点：是find查找时是返回第一个遇到的value，count将返回该值存在的个数
其中还要交代一个函数(set中也有不过不够实用)

最明显的区别应该是这：

set容器中的所有元素都是唯一的，因此返回的范围最多包含一个元素

他返回的是pair<iterator,iterator>，这两个迭代器分别表示的就是value值的lower_bound和upper_bound，这样就能一次性删除所有相同的元素！

2.map

map中也是类似

先来看模板

同样，compare默认为less也就是升序

我们来主要看看最重要的构造函数

来看其使用

在这里涉及到一个make_pair函数，我们还是来看看std中是怎么解释的

我们可以发现，make_pair实际上是一个template

需要注意的点：

  1. 用make_pair(key,value)构造出K,V类型的pair<K,V>当参数传递进去，或者写成用pair的构造pair<K,V>(key,value)
  2. 返回pair<iterator,bool>。
  3. 若返回的iterator，需要注意的是其类型是pair<K,V>型

除了构造函数，map中有一个特别重要的就是”[]”的重载


我们来详细看看

这是我自己的模拟实现，和std中还是有些许差别，但是std中，本人觉得很巧妙，但是由于适配其他东西，不免有些冗杂

operator[]中，std的底层实质就是：

(*((this->insert(make_pair(k,mapped_type()))).first)).second

其中能看到他是调用了插入函数，所以[]能实现插入功能

就像上图我自己的实现所说，自举，利用insert实现插入功能

而我们map的插入返回的类型是：pair<iterator,bool>

所以就能简化为：(*pair<iterator,bool>.first).second

      //此处.的优先级高于*所以是先访问，得到iterator后，再(*iterator).second

得到其迭代器的value值，也就是插入时的第二个参数

我们再了解以下其他的一系列基本功能函数

当然，<map>的template里面，也封装了multimap这个类，与multiset类似，在此不过多赘述

我们主要来看底层的详情

主要就是对红黑树的修改：

  1. 模板的改变：将原本第二个参数V改成T，T代表的是K，V组成成的键值对pair<K,V>

  1. 添加迭代器以及begin、end函数，让map、set也能用迭代器
  2. 修改插入的返回值：将原本的iterator改成pair<iterator,bool>，（这是STL源码内的设计，也是为了map的[]做准备）

RBTree的源码修改，底层实现

源码：

见后文附录

运行效果

些许总结：

/*

查阅 STL，

我们知道set和map的底层均是使用红黑树实现的，

只不过set存储的是key，

而map存储的是key_value

STL明确规定，begin()与end()代表的是一段前闭后开的区间，

而对红黑树进行中序遍历后，可以得到一个有序的序列，

因此：begin()可以放在红黑树中最小节点(即最左侧节点)的位置，

end()放在最大节点(最右侧节点)的下一个位置，关键是最大节点的下一个位置在哪块？

能否给成nullptr呢？答案是行不通的，

因为对end()位置的迭代器进行- -操作，必须要能找最后一个元素，

此处就不行，因此最好的方式是将end()放在头结点的位置

*/

/*

* 问题列表：

* 1.operator[]的重载，返回的是插入的insert的second

* 实质上就是return insert({ key, V() }).first->second

*【insert({ key, V() }).first】对应的就是insert中的key，

* 通过查看类型，我们知道key就是属于const K& key,而K是pair<const K, V>的

*      

* 我们再次看定义的 pair<iterator, bool> result = insert({ key, V() });

* 也就是iterator类型，我们对该容器就能使用迭代器来操作了

*

* 2.map和set的底层都是红黑树，而map和set中存储的键不同(map是键值对<K,V>；set是键K)，

*   那么如何用一棵红黑树来封装出map和set这两种容器呢?

*   为适应不同的类型(键/键值对)，也就是泛型编程，

*   之前的红黑树是RBTree<class K,class V>,而现在的红黑树RBTree<class K,class T>,

*   当set调用红黑树时这个T会是K，当map调用时T则是 pair<K,V>

*

*

*/

附录（源码）模拟实现

RBTree.h

#include<iostream>
#include<cassert>
#include<initializer_list>
#include<stack>using namespace std;// 结点颜色
// 0和1
enum Color
{RED,BLACK
};// 红黑树结点
// set中v为key，map中T是pair<key,value>
template<class T>
struct RBTreeNode
{T data_;	struct RBTreeNode* _left;struct RBTreeNode* _right;struct RBTreeNode* _parent;Color color;// 结点构造// 一个类型为 T 的常量引用，表示存储在节点中的数据。默认值 T() 表示使用 T 类型的默认构造函数来初始化数据成员 data_。RBTreeNode(const T& data = T(),Color color = RED):data_(data),_left(nullptr),_right(nullptr),_parent(nullptr),color(color){}
};// 红黑树迭代器
template<class T, class Ref, class Ptr>
struct RBTreeIterator {typedef RBTreeNode<T> Node;Node* node;  // 当前节点// 构造函数RBTreeIterator(Node* node) : node(node) {}// 拷贝构造函数RBTreeIterator(const RBTreeIterator& other) : node(other.node) {}// 赋值运算符RBTreeIterator& operator=(const RBTreeIterator& other) {if (this != &other) {node = other.node;}return *this;}// ++itRBTreeIterator& operator++() {if (node == nullptr) return *this; // 防止空指针Node* current = node;if (current->_right) {// 如果有右子树，找到右子树中的最左边节点node = current->_right;while (node->_left) {node = node->_left;}}else {// 如果没有右子树，回溯到父节点Node* parent = current->_parent;while (parent && parent->_right == current) {current = parent;parent = current->_parent;}node = parent;  // 如果 parent 为空，node 将会变为 nullptr。}return *this;}// it++RBTreeIterator operator++(int) {RBTreeIterator tmp(*this);++(*this);return tmp;}// --itRBTreeIterator& operator--() {if (node == nullptr) return *this; // 防止空指针Node* current = node;if (current->_left) {// 如果有左子树，找到左子树中的最右节点node = current->_left;while (node->_right) {node = node->_right;}}else {// 否则回溯到父节点Node* parent = current->_parent;while (parent && parent->_left == current) {current = parent;parent = current->_parent;}node = parent;  // 如果 parent 为空，node 将会变为 nullptr。}return *this;}// it--RBTreeIterator operator--(int) {RBTreeIterator tmp(*this);--(*this);return tmp;}// * 运算符Ref operator*() {if (node == nullptr) {throw std::out_of_range("Dereferencing a null iterator");}return node->data_;}// -> 运算符Ptr operator->() {if (node == nullptr) {throw std::out_of_range("Dereferencing a null iterator");}return &node->data_;}// != 运算符bool operator!=(const RBTreeIterator& it) const {return node != it.node;}// == 运算符bool operator==(const RBTreeIterator& it) const {return node == it.node;}
};// 反向迭代器
// 其实就是正向的逆转，只有自增和自减才会有区别
/*
只需对自增 (operator++) 和自减 (operator--) 做适当调整。
在反向迭代器中，operator++ 和 operator-- 分别要执行与正向迭代器相反的逻辑
简化反向迭代器的实现，主要只在 operator++ 和 operator-- 中做适当的调整：自增（operator++）：反向迭代器自增是向前移动一个元素，实际上是正向迭代器自减的效果。
自减（operator--）：反向迭代器自减是向后移动一个元素，实际上是正向迭代器自增的效果。
*/template<class T, class Ref,class Ptr>
struct RBTreeReverseIterator
{// 简化typedef RBTreeNode<T> Node;Node* node;	// 要操作的结点// 迭代器构造RBTreeReverseIterator(Node* node) : node(node) {}// 重载// ++it 正向的自减RBTreeReverseIterator& operator++() {Node* current = node;// 两种情况if (current->_left) {// 当前结点有左子树，则下一个元素就是左子树的最右结点Node* rightMost = current->_left;while (rightMost->_right){rightMost = rightMost->_right;}node = rightMost;}else {// 如果没有左子树，则回溯到父节点，直到当前节点是父节点的右子节点Node* parent = current->_parent;while (parent && parent->_left == current){current = parent;parent = current->_parent;}node = parent;}return *this;}RBTreeReverseIterator operator++(int) {RBTreeReverseIterator tmp(*this);++(*this);return tmp;}// --it,也就是正向的自增RBTreeReverseIterator& operator--() {Node* current = node;// 两种情况if (current->_right) {// 当前结点有右子树，则下一个元素就是右子树的最左结点Node* lefttMost = current->_right;while (lefttMost->_left){lefttMost = lefttMost->_left;}node = lefttMost;}else {// 如果没有右子树，则回溯到父节点，直到当前节点是父节点的左子节点Node* parent = current->_parent;while (parent && parent->_right == current){current = parent;parent = current->_parent;}node = parent;}return *this;}// it--RBTreeReverseIterator operator--(int) {RBTreeReverseIterator tmp(*this);--(*this);return tmp;}// *Ref operator*() {// 解引用，取值return node->data_;}// -> Ptr operator->() {return &node->data_;}// !=和==bool operator!=(const RBTreeReverseIterator& it) {return node != it.node;}bool operator==(const RBTreeReverseIterator& it) {return node == it.node;}
};

// 红黑树底层源码，也在RBTree.h文件中

// 红黑树底层实现// 红黑树
template<class K,class T,class KeyOfT>
class RBTree
{
private:typedef RBTreeNode<T> Node;// 当前属性Node* header_;// /*销毁树的递归函数// 最后销毁到根结点*///void destroy(Node*& root) {//	/*if (root)//		return;*///	//	assert(root);//	// 必须后序销毁结点，保证先左右，后当前，避免野指针//	// 当前的先销毁了以后，左右的子结点就丢失地址，就乱指了//	destroy(root->_left);//	root->_left = nullptr;//	destroy(root->_right);//	root->_right = nullptr;//	// 最后删除当前//	delete root;//	root = nullptr;//}void destroy(Node*& root) {if (!root) {return;}//assert(root);// 使用栈来模拟递归stack<Node*> stack;Node* current = root;// 深度优先遍历，模拟递归while (current != nullptr || !stack.empty()) {if (current != nullptr) {// 将当前节点压入栈，并遍历左子树stack.push(current);current = current->_left;}else {// 当前节点没有左子树，则处理栈顶元素，并遍历右子树current = stack.top();stack.pop();// 删除当前节点之前，处理父节点与子节点的连接Node* right = current->_right;// 断开与父节点的链接if (current->_parent) {if (current->_parent->_left == current) {current->_parent->_left = nullptr;}else if (current->_parent->_right == current) {current->_parent->_right = nullptr;}}// 删除当前节点delete current;// 继续处理右子树current = right;}}}private://调整旋转函数// 左旋void rotateLeft(Node* parent) {// 保存节点，后面链接Node* grandpa = parent->_parent;Node* sub = parent->_right;Node* subleft = parent->_left;// 重链parent->_right = subleft;if (subleft) {subleft->_parent = parent;}sub->_left = parent;parent->_parent = sub;// 与上面的链接if (grandpa == header_) {// parent 原来是 rootheader_->_parent = sub;sub->_parent = header_;}else {if (grandpa->_left == parent) {// 原来是上面节点的左子树grandpa->_left = sub;}else {grandpa->_right = sub;}sub->_parent = grandpa;}}// 右旋void rotateRight(Node* parent) {// 保存节点，后面链接Node* grandpa = parent->_parent;Node* sub = parent->_left;Node* subright = parent->_right;// 重链parent->_left = subright;if (subright) {subright->_parent = parent;}sub->_right = parent;parent->_parent = sub;// 与上面的链接if (grandpa == header_) {// parent 原来是 rootheader_->_parent = sub;sub->_parent = header_;}else {if (grandpa->_left == parent) {// 原来是上面节点的左子树grandpa->_left = sub;}else {grandpa->_right = sub;}sub->_parent = grandpa;}}// 左旋后右旋void rotateLeft_Right(Node* parent) {rotateLeft(parent->_left);rotateRight(parent);}// 右旋后左旋void rotateRight_Left(Node* parent) {rotateRight(parent->_right);rotateLeft(parent);}// 最左节点Node* leftMost() {Node* MostLeftChild = header_->_parent;while (MostLeftChild->_left){MostLeftChild = MostLeftChild->_left;}return MostLeftChild;}// 最右节点Node* rightMost() {Node* MostRightChild = header_->_parent;while (MostRightChild->_right){MostRightChild = MostRightChild->_right;}return MostRightChild;}public:// 空参构造RBTree() {// 创建空的头结点header_ = new Node(T());}// 拷贝构造RBTree(const RBTree& rbTree) {// 要先创建结点所带空间header_ = new Node(T());// 复制，以达到插入的效果for (const auto elem : rbTree) {// 调用插入函数，在基本功能函数列表中insert(elem);}}// 初始化列表构造RBTree(initializer_list<T> initList) {header_ = new Node(T());for (const auto& elem : initList) {inserter(elem);}}// 在析构函数中，确保 header_ 不会被误修改~RBTree() {// 如果树为空，直接返回if (header_->_parent == nullptr) {delete header_;header_ = nullptr;return;}// 销毁树中的节点destroy(header_->_parent);header_->_parent = nullptr;  // 确保 header_->_parent 被清空// 删除头结点delete header_;header_ = nullptr;  // 清空头节点指针}// 赋值重载RBTree& operator=(const RBTree& binarySTree) {// 现代C++写法，通过构造临时对象并交换RBTree tmp(binarySTree);// 使用交换方式来节省空间std::swap(header_, tmp.header_);return *this;}/* * const RBTree& bst：左值引用，* 意味着传入的对象是一个常量引用（不会修改原始对象），* 这样可以避免不必要的拷贝，并且保证赋值时不修改源对象。* * 局部的临时对象，调用拷贝构造来初始化，赋值binarySTree数据* * 使用了 std::swap * 交换当前对象（即 *this）和临时对象 temp 的成员 _header。也就是说：* 交换当前对象和临时对象的头指针 _header，* 这实际上交换了两个对象的内部状态（例如树的结构）。* 交换操作是高效的，因为它只涉及指针的交换，而不是复制大量的节点数据。这使得赋值操作更加高效。*/// 迭代器typedef RBTreeIterator<T, T&, T*> iterator;typedef RBTreeIterator<T, const T&, const T*> const_iterator;using reverse_iterator = typename RBTreeReverseIterator<T, T&, T*>;using const_reverse_iterator = typename RBTreeReverseIterator<T, const T&, const T*>;// 各类迭代器begin，end// 返回树中的最小结点（从头）iterator begin() {return iterator(header_->_left); // 头节点的左孩子是最小节点}// 常量版本，不能修改const_iterator begin() const {return const_iterator(header_->_left);}iterator end() {return iterator(header_);}const_iterator end() const {return const_iterator(header_);}// 反向reverse_iterator rbegin() {return reverse_iterator(header_->_right); // 头节点的右孩子是最小节点}const_reverse_iterator rbegin() const {return const_reverse_iterator(header_->_right);}reverse_iterator rend() {return reverse_iterator(header_);}const_reverse_iterator rend() const {return const_reverse_iterator(header_);}//此时需要注意key是set中的key，是map中pair<key,value>中的key，// 因此我们需要取出想要的key// 依据键值，以给定键的结点，返回迭代器iterator find(const K& key) const {Node* current = header_->_parent;	// 根结点开始遍历查找while (current){if (key < KeyOfT()(current->data_)) {// 比较键值current = current->_left;// 小就在左边}else if (key > KeyOfT()(current->data_)) {// 比较键值current = current->_right;// 大就在右边}else {// 找到，返回return iterator(current);}}// 没找到就回头结点位置return iterator(header_);}// 插入元素，如果插入成功返回一个指向新元素的迭代器，并返回 truepair<iterator, bool> insert(const T& data) {if (header_->_parent == nullptr) {// 树空，插入新节点为根节点header_->_parent = new Node(data);// 赋色header_->_parent->color = BLACK;header_->_parent->_parent = header_;//插入成功的 pair<iterator, bool>，其中 iterator 是指向新根节点的迭代器，true 表示插入成功。return { iterator(header_->_parent),true };	}// 查找位置Node* parent = header_;Node* current = header_->_parent;while (current){//比较待插入元素 t 与当前节点 cur->_t 的值。通过这个比较来决定向左子树或右子树继续查找。if (KeyOfT()(data) < KeyOfT()(current->data_)) {parent = current;current = current->_left;}else if (KeyOfT()(data) > KeyOfT()(current->data_)) {parent = current;current = current->_right;}else {// 相同就返回迭代器，表示已经有该元素,找到该元素位置// 该iterator一定要是非const的return { iterator(current),false };}}// 插入新节点current = new Node(data);current->_parent = parent;if (KeyOfT()(data) < KeyOfT()(current->data_)) {parent->_left = current;}else {parent->_right = current;}// 对插入的节点做一下保存Node* result = current;// 红黑树平衡调整//情况一：parent存在且为黑，不需要调整//情况二：parent存在且为红，需要调整while (parent != header_ && parent->color == RED){//确定 g 和 u 节点Node* grandpa = parent->_parent;Node* uncle = nullptr;if (parent == grandpa->_left) {// 父亲为祖父左孩子，那么叔叔就为右孩子uncle = grandpa->_right;}else {uncle = grandpa->_left;}//在情况二下又有如下情况：// 叔叔节点为红色if (uncle && uncle->color == RED) {parent->color = BLACK;uncle->color = BLACK;// 祖父节点也要调整grandpa->color = RED;current = grandpa;parent = current->_parent;}// 叔叔节点不存在或者为黑色//else if (!uncle || uncle->color == BLACK) {else{// 改变颜色//parent 是 grandfather 的左孩子if (parent == grandpa->_left) {//cur 是 parent 的左孩子if (current == parent->_left) {// 右旋且变色rotateRight(grandpa);parent->color = BLACK;grandpa->color = RED;}//cur 是 parent 的右孩子else {// 左旋后右旋rotateLeft_Right(grandpa);current->color = BLACK;grandpa->color = RED;}}//parent 是 grandfather 的右孩子else {//cur 是 parent 的左孩子if (current == parent->_left) {// 右旋后左旋rotateRight_Left(grandpa);current->color = BLACK;grandpa->color = RED;}//cur 是 parent 的右孩子else {// 左旋rotateLeft(grandpa);current->color = BLACK;grandpa->color = RED;}}break;}}// 根节点为黑色header_->_parent->color = BLACK;header_->_left = leftMost();	// 更新左子树最小节点header_->_right = rightMost();	// 更新右子树最大节点return { iterator(result),true };}// 功能函数bool empty() {return header_->_parent == nullptr;}size_t size() {size_t count = 0;auto it = begin();while (it != end()){count++;++it;}return count;}void clear() {// 如果 header_ 存在且 _parent 不是 nullptr，销毁树结构if (header_ && header_->_parent) {destroy(header_->_parent); // 销毁树header_->_parent = nullptr; // 清空根节点指针}// 如果 header_ 是动态分配的并且不再需要，考虑释放 header_ 自身// 例如：如果 header_ 是 new 创建的，可以在这里 delete// delete header_;   // 如果 header_ 是动态分配的，可以选择删除 header_// header_ = nullptr; // 置为 nullptr 防止悬空指针（如果需要删除）}
};

set.h

#pragma once
#include"RBTree.h"template<class K>
class set
{typedef const K T;	// 与map匹配/*这是一个辅助结构体，用于告诉红黑树如何从元素中提取键（key）。在这个类中，键就是元素本身，所以 operator() 实现了返回元素本身的功能。operator()(const T& key) 让 KeyOfT 对象作为一个仿函数，可以接受 const T& 类型的元素，并返回该元素（key）。*/struct KeyOfT{const K& operator()(const T& key) {return key;}};//using reverse_iterator = typename RBTreeReverseIterator<T, T&, T*>;//using iterator = typename RBTree<K, T, KeyOfT>::iterator;typedef typename RBTree<K, T, KeyOfT>::iterator iterator;typedef typename RBTree<K, T, KeyOfT>::const_iterator const_iterator;typedef typename RBTree<K, T, KeyOfT>::reverse_iterator reverse_iterator;typedef typename RBTree<K, T, KeyOfT>::const_reverse_iterator const_reverse_iterator;private:RBTree<K, T, KeyOfT> _rbt;
public:// 空参构造set(){}set(initializer_list<T> initlist) {_rbt = { initlist };}// 迭代器iterator begin() { return _rbt.begin(); }const_iterator begin() const { return _rbt.begin(); }iterator end() { return _rbt.end(); }const_iterator end() const { return _rbt.end(); }// 反向迭代器reverse_iterator rbegin() { return _rbt.rbegin(); }const_reverse_iterator rbegin() const { return _rbt.rbegin(); }reverse_iterator rend() { return _rbt.rend(); }const_reverse_iterator rend() const { return _rbt.rend(); }// set 功能函数// 基于红黑树的实现bool empty() {return _rbt.empty();}size_t size(){return _rbt.size();}void clear(){_rbt.clear();}iterator find(const K& key) const{return _rbt.find(key);}// 这里的T就是const Kpair<iterator, bool> insert(const T& t){return _rbt.insert(t);}
};

map.h

#pragma once
#include"RBTree.h"template<class K,class V>
class map
{/*T 代表存储在 map 中的元素类型。pair<const K, V> 意味着 map 中的每个元素是一个键值对，其中键是常量（const K），值是可变的（V）。iterator 与之对应，也应该是可变的键是常量的，防止在 map 中修改键。*/typedef /*const*/ pair<const K, V> T;/*KeyOfT 是一个帮助提取键（key.first）的仿函数。RBTree 底层需要一个函数对象来提取键以便进行排序或查找。这个结构体实现了一个 operator()，接受一个 pair<const K, V> 类型的元素并返回其 first 成员，即键。*/struct KeyOfT{const K& operator()(const T& key) {return key.first;}};/*typedef typename RBTree<K, T, KeyOfT>::iterator iterator;typedef typename RBTree<K, T, KeyOfT>::const_iterator const_iterator;typedef typename RBTree<K, T, KeyOfT>::reverse_iterator reverse_iterator;*/using iterator = typename RBTree<K, T, KeyOfT>::iterator;using const_iterator = typename RBTree<K, T, KeyOfT>::const_iterator;using reverse_iterator = typename RBTree<K, T, KeyOfT>::reverse_iterator;using const_reverse_iterator = typename RBTree<K, T, KeyOfT>::const_reverse_iterator;private:RBTree<K, pair<const K, V>, KeyOfT> _rbt;	// key不能修改
public:// 空参构造map() {}map(initializer_list<T> initlist) {_rbt = { initlist };}// 迭代器iterator begin() { return _rbt.begin();}const_iterator begin() const { return _rbt.begin(); }iterator end() { return _rbt.end(); }const_iterator end() const { return _rbt.end(); }// 反向迭代器reverse_iterator rbegin() { return _rbt.rbegin(); }const_reverse_iterator rbegin() const { return _rbt.rbegin(); }reverse_iterator rend() { return _rbt.rend(); }const_reverse_iterator rend() const { return _rbt.rend(); }// map 功能函数// 基于红黑树的实现bool empty() {return _rbt.empty();}size_t size(){return _rbt.size();}void clear(){_rbt.clear();}iterator find(const K& key) const{return _rbt.find(key);}// 这里的T就是const pair<const K,V>/*将一个 pair<const K, V> 插入到 map 中。返回一个 pair，其中：first 是插入的元素的迭代器。second 是一个布尔值，表示是否成功插入。如果键已经存在，则插入失败，返回 false；如果键不存在，则插入成功，返回 true。*/pair<iterator, bool> insert(const T& t){return _rbt.insert(t);}/*如果指定的键存在，则返回对应的值。如果键不存在，会插入一个 *默认构造的值（V())* 并返回该值。注意，插入是通过 insert 完成的。*/V& operator[](const K& key) {// 使用插入操作，插入一个空的 V 值pair<iterator, bool> result = insert({ key, V() });iterator it = result.first; // 获取对应的迭代器//iterator it = insert({ key, V() }).first;return it->second; // 返回非 const 引用}};

test.cpp

#include"mymap.h"
#include"myset.h"
#include<iostream>
#include<string>using namespace std;void TestMap_Set() {// mapcout << "map测试:" << endl;map<int, string> m;// 插入m.insert({ 1,"One" });m.insert({ 2,"Two" });m.insert({ 3,"Three" });m.insert({ 4,"Four" });m.insert({ 10,"Ten" });// 重载的[]m[6] = "Six";	// 使用 [] 来插入// 查找auto mapfind = m.find(3);if (mapfind != m.end()) {cout << "找到的键 3 对应的值：" << mapfind->second << endl;}else {cout << "键 3 对应的值没找到!" << endl;}auto ifind = m.find(5);if (ifind != m.end()) {cout << "找到的键 5 对应的值：" << ifind->second << endl;}else {cout << "键 5 对应的值没找到!" << endl;}// 遍历cout << "map 遍历:" << endl;for (auto& key_val : m) {cout << key_val.first << "->" << key_val.second << endl;}// 测试 map 的 size 和 emptycout << "Map 大小: " << m.size() << endl;cout << "map 为空? " << (m.empty() ? "Yes" : "No") << endl;// 清空 map/*  m.clear();cout << "清空过后, map 大小: " << m.size() << endl;*/// 测试 setcout << "\nset测试:" << endl;set<int> s;// 插入数据s.insert(10);s.insert(20);s.insert(30);s.insert(40);// 查找if (s.find(20) != s.end()) {cout << "找到 20 在set中!" << endl;}else {cout << "20 没有在set中!" << endl;}// 遍历 setcout << "set 遍历:" << endl;for (auto& key : s) {cout << key << endl;}// 测试 set 的 size 和 emptycout << "set 大小: " << s.size() << endl;cout << "set 是否为空? " << (s.empty() ? "Yes" : "No") << endl;// 清空 set/* s.clear();cout << "清空过后，set 大小: " << s.size() << endl;*/
}int main() {TestMap_Set();return 0;
}

对照测试函数，再来看运行效果

总结：

  • set：基于红黑树实现的 set 是一个有序的集合，确保每个元素唯一，并且按升序排列。主要操作有插入、查找和删除，复杂度均为 O(log⁡n)O(logn)。
  • map：基于红黑树实现的 map 是一个有序的映射，存储键值对，按照键排序，提供高效的插入、查找、更新和删除操作。
  • 红黑树的优点：通过自平衡的特性，红黑树保证了高效的查找、插入和删除操作，同时能保持数据的有序性。

总的来说，set 和 map 基于红黑树的实现使得它们在 STL 中成为非常强大的数据结构，既能保证操作的高效性，又能提供有序的元素访问。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/15428.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

软件测试之什么是缺陷

软件测试之什么是缺陷

软件测试之什么是缺陷 1. 缺陷定义2. 缺陷判定标准3. 缺陷产生原因3.1 缺陷产生的原因3.2 缺陷的生命周期 4. 缺陷核心内容5. 缺陷提交要素6. 缺陷类型 1. 缺陷定义 软件在使用过程中存在的任何问题都叫软件的缺陷, 简称Bug. 2. 缺陷判定标准 3. 缺陷产生原因 3.1 缺陷产生的…
阅读更多...
二叉树的遍历（手动）

二叉树的遍历（手动）

树的遍历分四种&#xff1a; 层序遍历 前序遍历 中序遍历 后序遍历 层序遍历&#xff1a; 很好理解&#xff0c;就是bfs嘛&#xff08;二不二叉都行&#xff09; 前序遍历&#xff1a; 又叫先跟遍历&#xff0c;遍历顺序是根->左->右&#xff08;子树里也是&#…
阅读更多...
Unix进程

Unix进程

文章目录 命令行参数进程终止正常结束异常终止exit和_exitatexit 环境变量环境变量性质环境表shell中操作环境变量查看环境变量设置环境变量 环境变量接口获取环境变量设置环境变量 环境变量的继承性 进程资源shell命令查看进程的资源限制 进程关系进程标识进程组会话控制终端控…
阅读更多...
供应链管理、一件代发系统功能及源码分享 PHP+Mysql

供应链管理、一件代发系统功能及源码分享 PHP+Mysql

随着电商行业的不断发展&#xff0c;传统的库存管理模式已经逐渐无法满足市场需求。越来越多的企业选择“一件代发”模式&#xff0c;即商家不需要自己储备商品库存&#xff0c;而是将订单直接转给供应商&#xff0c;由供应商直接进行发货。这种方式极大地降低了企业的运营成本…
阅读更多...
关于离散模型优化的一份介绍

关于离散模型优化的一份介绍

离散模型优化是运筹学和计算机科学领域中的一个重要分支&#xff0c;它主要研究如何在有限的、通常是计数的决策变量空间中寻找最优解。这类问题通常出现在资源分配、生产计划、物流管理、网络设计等实际应用场景中。在这篇文章中就将介绍离散模型优化中关于线性规划等部分内容…
阅读更多...
hadoop_yarn详解

hadoop_yarn详解

YARN秒懂 YARN定义基础架构ResourceManagerNodeManagerApplicationMasterContainer 工作流程资源调度器FIFO SchedulerCapacity SchedulerFair Scheduler 常用命令 YARN定义 YARN&#xff08;Yet Another Resource Negotiator&#xff09;是Hadoop的一个框架&#xff0c;它负责…
阅读更多...
【MYSQL】数据库日志 （了解即可）

【MYSQL】数据库日志 （了解即可）

一、错误日志 可以通过 tail查看文件的日志的&#xff0c;如果发生错误&#xff0c;就会在日志里出现问题。 二、二进制日志&#xff08;binlog&#xff09; BINLOG记录了insert delete update 以及 alter create drop 等语句。作用是灾难时的数据恢复&#xff0c;还有就是主…
阅读更多...
接口测试整体框架

接口测试整体框架

接口测试 1. 接口 接口&#xff0c;也叫api&#xff08;Application Programming Interface&#xff0c;应用程序编程接口&#xff09;&#xff0c;接口&#xff08;Interface&#xff09;是指不同软件组件或系统之间进行交互的点。接口定义了组件之间如何通信&#xff0c;包括…
阅读更多...
递归搜索与回溯算法

递归搜索与回溯算法

递归搜索与回溯算法 名词解释 递归 在解决⼀个规模为n的问题时&#xff0c;如果满⾜以下条件&#xff0c;我们可以使⽤递归来解决&#xff1a; a. 问题可以被划分为规模更⼩的⼦问题&#xff0c;并且这些⼦问题具有与原问题相同的解决⽅法。 b. 当我们知道规模更⼩的⼦问题&…
阅读更多...
基于java+SpringBoot+Vue的中小型医院网站设计与实现

基于java+SpringBoot+Vue的中小型医院网站设计与实现

项目运行 环境配置&#xff1a; Jdk1.8 Tomcat7.0 Mysql HBuilderX&#xff08;Webstorm也行&#xff09; Eclispe&#xff08;IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持&#xff09;。 项目技术&#xff1a; Springboot mybatis Maven mysql5.7或8.0等等组成&#x…
阅读更多...
图神经网络研究综述(GNN)，非常详细收藏我这一篇就够了！

图神经网络研究综述(GNN)，非常详细收藏我这一篇就够了！

图神经网络由于其在处理非欧空间数据和复杂特征方面的优势&#xff0c;受到广泛关注并应用于推荐系统、知识图谱、交通道路分析等场景。 大规模图结构的不规则性、节点特征的复杂性以及训练样本的依赖性给图神经网络模型的计算效率、内存管理以及分布式系统中的通信开销带来巨…
阅读更多...
36.安卓逆向-壳-脱壳实战

36.安卓逆向-壳-脱壳实战

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a;图灵Python学院 本人写的内容纯属胡编乱造&#xff0c;全都是合成造假&#xff0c;仅仅只是为了娱乐&#xff0c;请不要盲目相信。第一…
阅读更多...
办公耗材管理新纪元：系统化解企业挑战，助力高效运营

办公耗材管理新纪元：系统化解企业挑战，助力高效运营

在当今竞争激烈的商业环境中&#xff0c;无论是大型企业还是中小型企业&#xff0c;办公耗材管理都是关乎企业运营效率与成本控制的关键环节。有效的办公耗材管理不仅能显著降低运营成本&#xff0c;还能提升整体工作效率&#xff0c;确保业务的顺畅进行。然而&#xff0c;许多…
阅读更多...
2、 家庭网络发展现状

2、 家庭网络发展现状

上一篇我们讲了了解家庭网络历史(https://blog.csdn.net/xld_hung/article/details/143639618?spm1001.2014.3001.5502),感兴趣的同学可以看对应的文章&#xff0c;本章我们主要讲家庭网络发展现状。 关于家庭网络发展现状&#xff0c;我们会从国内大户型和小户型的网络说起&…
阅读更多...
时序论文20｜ICLR20 可解释时间序列预测N-BEATS

时序论文20｜ICLR20 可解释时间序列预测N-BEATS

论文标题&#xff1a;N-BEATS N EURAL BASIS EXPANSION ANALYSIS FOR INTERPRETABLE TIME SERIES FORECASTING 论文链接&#xff1a;https://arxiv.org/pdf/1905.10437.pdf 前言 为什么时间序列可解释很重要&#xff1f;时间序列的可解释性是确保模型预测结果可靠、透明且易…
阅读更多...
hadoop_capacity-scheduler.xml

hadoop_capacity-scheduler.xml

hadoop3.2.3capacity-scheduler.xml配置实例 <configuration><property><!-- 可以处于等待和运行状态的应用程序的最大数量 --><name>yarn.scheduler.capacity.maximum-applications</name><value>10000</value></property>&l…
阅读更多...
小白必看：知识库搭建的详细拆解步骤

小白必看：知识库搭建的详细拆解步骤

在当今信息爆炸的时代&#xff0c;企业知识库成为了企业积累、管理和分享知识的重要工具。对于初学者来说&#xff0c;搭建一个企业知识库可能看起来是一项复杂的任务&#xff0c;但通过以下步骤&#xff0c;即使是小白也能轻松上手。本文将详细拆解搭建企业知识库的步骤&#…
阅读更多...
042 异步编排

042 异步编排

文章目录 什么是异步Future异步编排1串行关系执行thenRunthenApplythenAcceptthenCompose 2聚合ANDthenCombinethenAcceptBothrunAfterBoth 3OR聚合applyToEiteracceptEitherrunAfterEither 4异常处理exceptionallywhenCompletehandle 异步开启1RunAsync:没有使用自定义线程池&…
阅读更多...
【算法设计与分析】采用特征方程求解递归方程

【算法设计与分析】采用特征方程求解递归方程

文章目录 K阶常系数线性齐次递归方程K阶常系数线性【非】齐次递归方程例题例1&#xff1a;齐次无重根例2&#xff1a;齐次有重根例3&#xff1a;非齐次&#xff0c;g(n)是n的多项式例4&#xff1a;非齐次&#xff0c;g(n)是n的指数形式&#xff0c;a不是重根 练习其它求解递归方…
阅读更多...
SAP ABAP开发学习——function alv复选框设置

SAP ABAP开发学习——function alv复选框设置

1.关于报表复选框的创建 首先该报表要调用功能函数 这里参照SLIS_LAYOUT_ALV定义字段 参照来源 具体字段的定义 双击 双击这两个查看需要的字段 box_fieldname就是复选框 需要在内表定义需要的名称&#xff0c;这里使用‘BOX 相关内容完成
阅读更多...
最新文章

Copyright @ 2022~2023