略谈set与map的pair封装与进入哈希

引子：之前我们讲了红黑树的自实现，与小小的接口实现，那set与map的pair封装是如何实现的呢？，今天我们来一探究竟，而且我们也要进入新章节--哈希

对于operator--()的封装：

注意：牢记思考的方向始终是中序

示意图：

stl代码实现：

  void decrement(){if (node->color == __rb_tree_red &&node->parent->parent == node)node = node->right;else if (node->left != 0) {base_ptr y = node->left;while (y->right != 0)y = y->right;node = y;}else {base_ptr y = node->parent;while (node == y->left) {node = y;y = y->parent;}node = y;}}
};

自实现：我们在传的时候要传一下_root,因为我们不是通过以上stl中hearer的方式

迭代器部分更改：

Node* _root;RBTreeIterator(Node*node,Node*root):_node(node),_root(root)
{}

self& operator--()
{if (_node == nullptr) {//找最右节点Node* rightMost = _root;while (rightMost && rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else if (_node->_left){Node* rightMost = _node->_left;while (rightMost->_right){rightMost = rightMost->_right;}_node = rightMost;}else{Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_left){cur = parent;parent = cur->_parent;}_node = parent;}return *this;
}

对于set的insert封装：

//插入
pair<iterator,bool>insert(const T& data)
{//空树新增节点，也是红黑树Node* root = _root;if (root == nullptr){root = new Node(data);_root = root;_root->_col = BLACK;return make_pair(iterator(_root, _root), true);}//红黑树大逻辑K_of_T kot;Node* cur = _root;Node* parent = nullptr;//要先找到，插入位置while (cur){if (kot(data) < kot(cur->_Data)){parent = cur;cur = cur->_left;}else if (kot(data) > kot(cur->_Data)){parent = cur;cur = cur->_right;}else{return make_pair(iterator(cur, _root), false);}}cur = new Node(data);// 新增节点。颜色红色给红色cur->_col = RED;Node* newNode = cur;if (kot(parent->_Data) < kot(data)){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//更改颜色//现在cur为新增节点while (parent && parent->_col==RED){Node* grandfather = parent->_parent;//找出叔叔节点if (parent == grandfather->_left){Node* uncle = grandfather->_right;//情况一if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{//情况二//    g//  p   u//cif (parent->_left == cur){RotateR(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{//情况三//    g//  p   u//    c// //双旋RotateL(parent);RotateR(grandfather);//注意cur与parent调了一下位置cur->_col = BLACK;grandfather->_col = RED;}break;}}else{Node* uncle = grandfather->_left;//情况一if (uncle && uncle->_col == RED){parent->_col = BLACK;uncle->_col = BLACK;grandfather->_col = RED;cur = grandfather;parent = cur->_parent;}else{ //情况二//    g//  u   p//        cif (cur == parent->_right){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}//情况三//    g//  u   p//    c    else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}//确保根节点为黑的_root->_col = BLACK;return make_pair(iterator(newNode, _root), true);
}

对于：map的话，只要将k对应的vaule输出就行！，注意调用的时候也要改为pair<iterator,bool>！

什么是哈希？

一，哈希是一种数学函数，它接受一个输入（或“消息”），然后返回一个通常更小的固定大小的输出，这个输出称为“哈希值”或“哈希码”。

二，哈希也是一种思想：映射：哈希思想通过哈希函数将任意长度的数据映射到固定长度的哈希值。这个映射过程是单向的，即从数据到哈希值是容易的，但从哈希值回溯到原始数据几乎是不可能的。快速性：哈希函数的设计旨在快速计算，以便在大数据集中实现高效的数据访问。均匀分布：理想情况下，哈希函数应该能够将输入数据均匀地分布在哈希值空间中，以减少冲突并提高查找效率。

哈希的应用：

哈希思想在数据库索引、密码存储、信息检索、数据同步、数字签名、区块链技术等多个领域都有广泛的应用。通过哈希，可以有效地管理和访问大量数据，同时保证数据的安全性和完整性。

由哈希来的哈希表（unordered）

一，背景：

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到log_2N，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个 unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，

以下是unordered_set与set的区别图，我们可以更加看到底层结构为哈希表的优势！

对于调试性能，大家可以通过以下代码进行测试：

#include<unordered_set>
#include<iostream>
#include<set>using namespace std;int test_set2()
{const size_t N = 10000000;unordered_set<int> us;set<int> s;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; ++i){//v.push_back(rand()); // N比较大时，重复值比较多//v.push_back(rand()+i); // 重复值相对少v.push_back(i); // 没有重复，有序}size_t begin1 = clock();for (auto e : v){s.insert(e);}size_t end1 = clock();cout << "set insert:" << end1 - begin1 << endl;size_t begin2 = clock();for (auto e : v){us.insert(e);}size_t end2 = clock();cout << "unordered_set insert:" << end2 - begin2 << endl;int m1 = 0;size_t begin3 = clock();for (auto e : v){auto ret = s.find(e);if (ret != s.end()){++m1;}}size_t end3 = clock();cout << "set find:" << end3 - begin3 << "->" << m1 << endl;int m2 = 0;size_t begin4 = clock();for (auto e : v){auto ret = us.find(e);if (ret != us.end()){++m2;}}size_t end4 = clock();cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl;cout << "插入数据个数：" << s.size() << endl;cout << "插入数据个数：" << us.size() << endl << endl;size_t begin5 = clock();for (auto e : v){s.erase(e);}size_t end5 = clock();cout << "set erase:" << end5 - begin5 << endl;size_t begin6 = clock();for (auto e : v){us.erase(e);}size_t end6 = clock();cout << "unordered_set erase:" << end6 - begin6 << endl << endl;return 0;
}int main()
{test_set2();return 0;
}

可以有以下的结果：只展示一种