【C++】用手搓的红黑树手搓set和map


目录

一、set/map的底层结构

1、set/map的源码

2、利用模板区分set/map

3、利用仿函数控制比较大小

二、set/map的迭代器(红黑树的迭代器)

1、红黑树的begin、end迭代器

2、红黑树迭代器的operator++

3、红黑树迭代器的operator--

三、set的const迭代器

四、map的const迭代器

五、迭代器类的拷贝构造

六、整体代码

1、RBTree.h

2、Set.h

3、map.h


本文相关往期内容,可按需查阅:
1、【C++】set/multiset、map/multimap的使用

2、【数据结构】二叉搜索树的实现

3、【数据结构】平衡二叉树

4、【数据结构】手撕红黑树

本文难点:使用红黑树封装set和map,必须保证两种数据结构复用同一棵红黑树;且满足set和map的性质,set的value不可被改变,而map的value可以被改变。

一、set/map的底层结构

1、set/map的源码

扒一扒STL库中set和map的底层结构,不难发现,set和map的底层用的都是红黑树且均为key/value模型。

只不过set的key/value均为key值填充,而map的key/value使用key和pair<const Key,T>进行填充。因此,set和map中底层虽然都是红黑树,但这两种数据结构中的红黑树实例化类型并不相同

那么使用同一颗红黑树的模板,如何实例化出适配set和/map的对象?

2、利用模板区分set/map

template <class T>//T类型代表value
struct RBTreeNode
{
	RBTreeNode(const T& data)
		:_parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
		, _data(data)
		, _col(RED)
	{}
	RBTreeNode<T>* _parent;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	T _data;
	Color _col;
};

map和set的区别在于value的不同,红黑树模板参数T,代表value用以区分set和map。

3、利用仿函数控制比较大小

我们会发现红黑树的插入等接口会对key值进行比较大小,像set直接对key进行比较,这没问题,但是map中的节点装的是pair<K,V>,pair的比较规则是first比完之后可能会再去比较second(而我们仅仅想要比较first,该比较规则不适用)。

通过源码启发,我们可以对红黑树新增一个模板参数:仿函数KeyOfT,在set和map类中完善该仿函数的比较对象,用于区分set和map的比较:

template <class K>
class set
{
	//仿函数用于比较大小
    struct SetKeyOfT
    {
        const K& operator()(const K& key)//传入节点的值
        {
            return key;//返回key
        }
    };
private:
    RBTree<K, K, SetKeyOfT> _t;
};
class map
{
    struct MapKeyOfT
    {
        const K& operator()(const pair<K, V>& kv)//传入节点的值
        {
            return kv.first;//返回kv.first
        }
    };
private:
    RBTree<const K, pair<K,V>, MapKeyOfT> _t;
};
//利用模板确定传入对象是set还是map
template <class K, class T,class KeyOfT>
class RBTree//红黑树
{};

利用仿函数,传入节点的值,set将会返回key值,map将会的返回pair的first。这样就解决了比较大小的规则问题。

二、set/map的迭代器(红黑树的迭代器)

因为红黑树的中序遍历是有序的,可以根据中序遍历作为迭代器++--的依据。

STL源码采用下图结构,多搞了一个头结点。迭代器begin()可以指向header的左,迭代器end()指向header。

不过本文采用无头结点的常规红黑树仿写红黑树的迭代器。

1、红黑树的begin、end迭代器

2、红黑树迭代器的operator++

1、如果当前节点的右不为空,迭代器++返回右子树的最左节点

2、如果当前节点的右为空,迭代器++返回祖先(当前节点是父亲的左)(end()-1迭代器++返回nullptr即end())

template <class T>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __RBTreeIterator<T> Self;
	Node* _node;
	__RBTreeIterator(Node* node)
		:_node(node)
	{}
	//1、右不为空,下一个节点是右树的最小节点
	//2、右为空,去找右是父亲左的最近祖先
	Self& operator++()//找中序的下一个节点,即根的右树的最左节点,返回值是一个迭代器的对象
	{
		if (_node->_right != nullptr)
		{
			Node* min = _node->_right;
			while (min->_left != nullptr)
			{
				min = min->_left;
			}
			_node = min;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent != nullptr && cur == parent->_right)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	bool operator!=(const Self& s)
	{
		return _node != s._node;
	}
};

3、红黑树迭代器的operator--

1、如果当前节点的左不为空,迭代器--返回左子树的最右节点

2、如果当前节点的左为空,迭代器--返回祖先(当前节点是父亲的右)

template <class T>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __RBTreeIterator<T> Self;
	Node* _node;
	__RBTreeIterator(Node* node)
		:_node(node)
	{}
	Self& operator--()
	{
		if (_node->_left!=nullptr)
		{
			Node* max = _node;
			while (max->_right)
			{
				max = max->_right;
			}
			_node = max;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent != nullptr && cur == parent->_left)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
};

三、set的const迭代器

对于set和map,它们的key都是不能改的。set的value不能修改,map的value可以修改。

因为set的value是不能改的,所以它的底层将普通迭代器和const迭代器全部封装成const迭代器来“解决”:

//自己实现的,不代表STL
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

封装之后又会出现新问题,set使用迭代器其实都是在使用const迭代器,但是自己实现的红黑树的迭代器接口返回普通类型的迭代器,在Set.h中对this加上const“解决”:

iterator begin()const
{
    return _t.begin();
}
iterator end()const
{
    return _t.end();
}

这时使用迭代器调用上方函数会发现红黑树返回了普通迭代器类型的迭代器,类型不匹配。在红黑树中补齐const版本的迭代器函数解决:

const_iterator begin()const//找红黑树最左节点
{
    Node* left = _root;
    while (left != nullptr && left->_left != nullptr)
    {
        left = left->_left;
    }
    return const_iterator(left);
}
const_iterator end()const
{
    return const_iterator(nullptr);
}

四、map的const迭代器

map的value是可以改的,所以要分别设计普通迭代器和const迭代器。

typedef typename RBTree<const K, pair<const K, V>, MapKeyOfT>::iterator iterator;
typedef typename RBTree<const K, pair<const K, V>, MapKeyOfT>::const_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();
}

五、迭代器类的拷贝构造

STL库中的普通迭代器都可以转换为const迭代器,这是迭代器类的拷贝构造所支持的。

这个拷贝构造有点特殊:

//红黑树的迭代器
template <class T,class Ref,class Ptr>//key/value、T&、T*
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __RBTreeIterator<T, Ref, Ptr> Self;
	typedef __RBTreeIterator<T, T&, T*> iterator;
	Node* _node;
	__RBTreeIterator(Node* node)
		:_node(node)
	{}
	__RBTreeIterator(const iterator& it)//const iterator本质还是普通迭代器
		:_node(it._node)
	{}
};

1、当这个模板的的Ref和PTR被实例化为T&和T*时,__RBTreeIterator(const iterator& it)就是一个拷贝构造(没啥意义)

2、当这个模板的的Ref和PTR被实例化为const T&和const T*时,__RBTreeIterator(const iterator& it)就是一个构造函数,支持用普通迭代器去构造const迭代器。此时const迭代器的拷贝构造函数则由编译器自动生成,刚好满足迭代器值拷贝的特点。

六、整体代码

1、RBTree.h

#pragma once
#include <iostream>
#include <map>
#include <set>
#include <string>
using namespace std;
enum Color
{
	RED,
	BLACK,
};
template <class T>//T类型代表value
struct RBTreeNode
{
	RBTreeNode(const T& data)
		:_parent(nullptr)
		, _left(nullptr)
		, _right(nullptr)
		, _data(data)
		, _col(RED)
	{}
	RBTreeNode<T>* _parent;
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	T _data;
	Color _col;
};
//红黑树的迭代器
//        key/value T&        T*
template <class T,class Ref,class Ptr>
struct __RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef __RBTreeIterator<T, Ref, Ptr> Self;
	typedef __RBTreeIterator<T, T&, T*> iterator;
	Node* _node;
	__RBTreeIterator(Node* node)
		:_node(node)
	{}
	__RBTreeIterator(const iterator& it)
		:_node(it._node)
	{}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()//返回类型的地址
	{
		return &_node->_data;
	}
	//1、右不为空,下一个节点是右树的最小节点
	//2、右为空,去找右是父亲左的最近祖先
	Self& operator++()//找中序的下一个节点,即根的右树的最左节点,返回值是一个迭代器的对象
	{
		if (_node->_right != nullptr)
		{
			Node* min = _node->_right;
			while (min->_left != nullptr)
			{
				min = min->_left;
			}
			_node = min;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent != nullptr && cur == parent->_right)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	Self& operator--()
	{
		if (_node->_left!=nullptr)
		{
			Node* max = _node;
			while (max->_right)
			{
				max = max->_right;
			}
			_node = max;
		}
		else
		{
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent != nullptr && cur == parent->_left)
			{
				cur = cur->_parent;
				parent = parent->_parent;
			}
			_node = parent;
		}
		return *this;
	}
	bool operator!=(const Self& s)const
	{
		return _node != s._node;
	}
	bool operator==(const Self& s)const
	{
		return _node == s._node;
	}
};
//pair的比较是如果first小还要比second,我们只要比first,所以加了仿函数KeyOfT,用以取出first进行比较
//set->RBTree<K, K, SetKeyOfT>
//map->RBTree<const K, pair<K,V>, MapKeyOfT>
template <class K, class T,class KeyOfT>
class RBTree
{
public:
	typedef __RBTreeIterator<T,T&,T*> iterator;
	typedef __RBTreeIterator<T, const T&, const T*> const_iterator;
	iterator begin()//找红黑树最左节点
	{
		Node* left = _root;
		while (left!=nullptr&&left->_left!=nullptr)
		{
			left = left->_left;
		}
		return iterator(left);
	}
	iterator end()
	{
		return iterator(nullptr);
	}
	const_iterator begin()const//找红黑树最左节点
	{
		Node* left = _root;
		while (left != nullptr && left->_left != nullptr)
		{
			left = left->_left;
		}
		return const_iterator(left);
	}
	const_iterator end()const
	{
		return const_iterator(nullptr);
	}
	typedef RBTreeNode<T> Node;
	pair<iterator,bool> Insert(const T& data)//对于map来说data是pair
	{
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;//根节点给黑色
			return make_pair(iterator(_root), true);//返回插入的节点
		}
		KeyOfT kot;//搞一个仿函数对象
		//_root不为空
		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的地址,make_pair返回插入节点的地址
		cur->_col = RED;//新插入节点给红色,可能违反规则。如果给黑色会导致其他路径的黑色节点数量不相同,必定违反规则。  
		if (kot(parent->_data) < kot(data))
		{
			parent->_right = cur;
			cur->_parent = parent;//维护cur的父指针
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}
		//调整
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;//找到祖父
			if (grandfather->_left == parent)//如果父亲是祖父的左孩子
			{
				Node* uncle = grandfather->_right;//找到叔叔
				//情况一:叔叔存在且为红
				if (uncle != nullptr && uncle->_col == RED)
				{
					//变色
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else//情况二或情况三
				{
					if (cur == parent->_left)//情况二,直线
					{
						RotateRight(grandfather);//右单旋
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//情况三,折线
					{
						RotateLeft(parent);//左单旋
						RotateRight(grandfather);//右单旋
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else//如果父亲是祖父的右孩子
			{
				Node* uncle = grandfather->_left;
				if (uncle != nullptr && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)//情况二,直线
					{
						//g
						//  p
						//    c
						RotateLeft(grandfather);//左单旋
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else//情况三,折线
					{
						//g
						//  p
						//c   
						RotateRight(parent);//右单旋
						RotateLeft(grandfather);//左单旋
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}
		_root->_col = BLACK;
		return make_pair(iterator(newNode), true);//返回插入的节点
	}
	void Inorder()
	{
		_Inorder(_root);
	}
	bool IsBalance()
	{
		return _IsBalance();
	}
private:
	void _Inorder(Node* root)
	{
		if (root == nullptr)
			return;

		_Inorder(root->_left);
		cout << kot(root->_data) << ":" << root->_data.second << endl;
		_Inorder(root->_right);
	}
	bool Check(Node* root, int blackNum, const int ref)//检查有没有连续红节点
	{
		if (root == nullptr)
		{
			if (blackNum != ref)
			{
				cout << "路径上黑节点数量不一致" << endl;
				return false;
			}
			return true;
		}
		if (root->_col == BLACK)
		{
			++blackNum;
		}

		if (root->_col == RED && root->_parent->_col == RED)
		{
			cout << "违反规则,父子均为红" << endl;
			return false;
		}
		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 != nullptr)
		{
			if (left->_col == BLACK)
			{
				++ref;
			}
			left = left->_left;
		}
		return Check(_root, 0, ref);
	}
	void RotateLeft(Node* parent)//左单旋
	{
		Node* grandfather = parent->_parent;
		Node* cur = parent->_right;
		if (parent == _root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (grandfather->_left == parent)//需要判定parent原来属于grandfather的哪一边
				grandfather->_left = cur;
			else
				grandfather->_right = cur;
			cur->_parent = grandfather;
		}
		parent->_right = cur->_left;
		if (cur->_left != nullptr)
			cur->_left->_parent = parent;
		cur->_left = parent;
		parent->_parent = cur;
	}
	void RotateRight(Node* parent)//右单旋
	{
		Node* grandfather = parent->_parent;
		Node* cur = parent->_left;
		if (parent == _root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (grandfather->_left == parent)
			{
				grandfather->_left = cur;
				cur->_parent = grandfather;
			}
			else
			{
				grandfather->_right = cur;
				cur->_parent = grandfather;
			}
		}
		parent->_parent = cur;
		parent->_left = cur->_right;
		if (cur->_right != nullptr)
			cur->_right->_parent = parent;
		cur->_right = parent;
	}
private:
	Node* _root = nullptr;
};

迭代器的begin(),end()接口放在红黑树这个类中,而operator++--放在迭代器这个类中,自己写一下循环遍历红黑树的代码就知道为什么这样设计了。

2、Set.h

#pragma once
#include "RBTree.h"
namespace jly
{
	template <class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)//传入value
			{
				return key;
			}
		};
	public:
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;
		typedef typename RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
		pair<iterator, bool> insert(const K& key)
		{
			pair<typename RBTree<K, K, SetKeyOfT>::iterator,bool> ret= _t.Insert(key);
			return pair<iterator, bool>(ret.first, ret.second);
		}
		
		iterator begin()const
		{
			return _t.begin();
		}
		iterator end()const
		{
			return _t.end();
		}
	private:
		RBTree<K, K, SetKeyOfT> _t;

	};
	void test2()
	{
		//int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
		int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
		//int a[] = { 9,8,7,6,5,4,3,2,1};
		set<int> s;
		for (auto e : a)
		{
			s.insert(e);
		}
		set<int>::iterator it = s.begin();
		while (it != s.end())
		{
			cout << *it << " ";
			++it;
		}
	}
}

3、map.h

#pragma once
#include "RBTree.h"
namespace jly
{
	template <class K,class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)//传入value
			{
				return kv.first;
			}
		};
	public:
		//typename是C++中用于指定一个类的类型的关键字。
		//通常用于表示某个类型是一个类类型,而不是其他类型,如int等。
		//这里不加typedef编译器无法区分iterator是一个类型还是一个静态变量。因为他俩都可以这么写。。
		//所以从类模板取出内嵌类型就需要加typedef
		typedef typename RBTree<const K, pair<const K, V>, MapKeyOfT>::iterator iterator;
		typedef typename RBTree<const K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
		pair<iterator,bool> insert(const pair<K, V>& kv)
		{
			return _t.Insert(kv);
		}
		
		iterator begin()
		{
			return _t.begin();
		}
		iterator end()
		{
			return _t.end();
		}
		const_iterator begin()const
		{
			return _t.begin();
		}
		const_iterator end()const
		{
			return _t.end();
		}
		V& operator[](const K& key)//传入key值
		{
			pair<iterator,bool> ret= _t.Insert(key,V());
			return ret.first->second;//找到ret(make_pair<iterator,bool>)的first,解引用找到节点value
		}
	private:
		RBTree<const K, pair<const K,V>, MapKeyOfT> _t;
	};
	void test1()
	{
		int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
		//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
		//int a[] = { 9,8,7,6,5,4,3,2,1};
		map<int,int> m;
		for (auto e : a)
		{
			m.insert(make_pair(e,e));
		}
		map<int, int>::iterator it = m.begin();
		while (it != m.end())
		{
			cout << (* it).first << " ";
			++it;
		}
		cout << endl;
		for (auto& e : m)
		{
			cout << e.first<<" ";
		}
	}
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

人工智能大模型之ChatGPT原理解析

前言 近几个月ChatGPT爆火出圈&#xff0c;一路狂飙&#xff1b;它功能十分强大&#xff0c;不仅能回答各种各样的问题&#xff0c;还可以信写作&#xff0c;给程序找bug…我经过一段时间的深度使用后&#xff0c;十分汗颜&#xff0c;"智障对话"体验相比&#xff0c…

Spring-Data-Redis 和 Redisson TLS/SSL 连接

先决条件已经部署好redis tls环境。如未部署好&#xff0c;可参考&#xff1a;Redis 6.0 Docker容器使用SSL/TLS已知redis tls环境使用的证书&#xff1a;其中&#xff1a;ca.crt :服务器证书ca.key:服务器私钥redis.crt:客户端证书redis.key:客户端私钥证书处理生成证书p12文件…

Linux环境C语言开发基础

C语言是一门面向过程的计算机编程语言&#xff0c;与C、C#、Java等面向对象编程语言有所不同。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、仅产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。C语言诞生于美国的贝尔实验室&#xff0c;由丹…

信创办公–基于WPS的PPT最佳实践系列(表格和图标常用动画)

信创办公–基于WPS的PPT最佳实践系列&#xff08;表格和图标常用动画&#xff09; 目录应用背景操作步骤图表常用动画效果&#xff1a;擦除效果表格常用动画效果&#xff1a;轮子效果应用背景 文不如表&#xff0c;表不如图。在平时用ppt做总结时&#xff0c;我们会经常用到图…

手撕数据结构与算法——树(三指针描述一棵树)

&#x1f3c6;作者主页&#xff1a;king&南星 &#x1f384;专栏链接&#xff1a;数据结构 &#x1f3c5;文章目录&#x1f331;树一、&#x1f332;概念与定义二、&#x1f333;定义与预备三、&#x1f334;创建结点函数四、&#x1f340;查找五、&#x1f341;插入六、&a…

SpringBoot接口 - 如何生成接口文档之Swagger技术栈

SpringBoot开发Restful接口&#xff0c;有什么API规范吗&#xff1f;如何快速生成API文档呢&#xff1f;Swagger 是一个用于生成、描述和调用 RESTful 接口的 Web 服务。通俗的来讲&#xff0c;Swagger 就是将项目中所有&#xff08;想要暴露的&#xff09;接口展现在页面上&am…

我的创作纪念日——一年的时间可以改变很多

机缘 不知不觉来到CSDN已经创作一年了。打心底讲&#xff0c;对于在CSDN开始坚持创作的原因我用一句话来概括最合适不过了——“无心插柳柳成荫” 为什么这么说呢&#xff1f; 这要从我的一篇博客说起——《输入命令Javac报错详解》&#xff1a; 那也是我第一次接触到Java这…

PostMan工具的使用

PostMan工具的使用 1 PostMan简介 代码编写完后&#xff0c;我们要想测试&#xff0c;只需要打开浏览器直接输入地址发送请求即可。发送的是GET请求可以直接使用浏览器&#xff0c;但是如果要发送的是POST请求呢? 如果要求发送的是post请求&#xff0c;我们就得准备页面在页…

基于OpenCV的传统视觉应用 -- OpenCV图像处理 图像模糊处理 图像锐化处理

图像处理 图像处理是用计算机对图像进行分析&#xff0c;以获取所需结果的过程&#xff0c;又称为影像处理。图像处理一般是指数字图像的处理。数字图像是用工业相机、摄像机、扫描仪等设备经过拍摄得到的一个大的二维数组&#xff0c;该数组的元素称为像素&#xff0c;其值称…

C++造轮子飙车现场之无锁、有锁环形队列实现

先看带锁的实现。 带锁版本 circular_queue.h // 头文件防卫 #ifndef CIRCULAR_QUEUE_H #define CIRCULAR_QUEUE_H#include <mutex> // 互斥量 #include <condition_variable> // 条件变量template <typename T> class CircularQueue { public:// 构造函数…

公司测试员用例写得乱七八糟,测试总监制定了这份《测试用例编写规范》

统一测试用例编写的规范&#xff0c;为测试设计人员提供测试用例编写的指导&#xff0c;提高编写的测试用例的可读性&#xff0c;可执行性、合理性。为测试执行人员更好执行测试&#xff0c;提高测试效率&#xff0c;最终提高公司整个产品的质量。 一、范围 适用于集成测试用…

vue3 项目搭建教程(基于create-vue,vite,Vite + Vue)

vue3 项目搭建教程&#xff08;基于create-vue&#xff0c;vite&#xff0c;Vite Vue&#xff09; 目录 一、搭建vue3 项目前提条件 二、通过create-vue搭建vue3 项目 三、搭建一个 Vite 项目 四、构建一个 Vite Vue 项目 五、打开Vue 项目管理器 六、Vite Vue 项目目…

云开发--实现发送邮件+短信+链接跳转小程序功能

目录 1、小程序实现发送邮件 准备一个qq邮箱&#xff0c;并启动SMTP服务 确定小程序云开发环境&#xff0c;并新建云函数 2、小程序实现发送短信 确定应用 确定签名 确定模板 编写云函数-发送短信 3、链接跳转小程序 H5 配置 生成 URL Link 学习记录&#xff1a; …

【洛谷刷题】蓝桥杯专题突破-深度优先搜索-dfs(4)

目录 写在前面&#xff1a; 题目&#xff1a;P1149 [NOIP2008 提高组] 火柴棒等式 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述&#xff1a; 输入格式&#xff1a; 输出格式&#xff1a; 输入样例&#xff1a; 输出样例&#xff1a; 解题思路&#xff1a; …

Java进阶2 排序查找与Lambda、正则表达式

排序查找与Lambda、正则表达式● 导图一、 基础算法1.排序1.1 冒泡排序1.2 选择排序2. 查找2.1 基础查找2.2 二分查找二、Lambda表达式1&#xff09;初识Lambda2&#xff09;函数式编程3&#xff09;.Lambda表达式的标准格式4&#xff09;Lambda的注意事项5&#xff09;Lambda表…

k8s 1.18.20版本部署

身为k8s初学者&#xff0c;在掌握k8s理论知识的同时&#xff0c;也需要掌握一下实际部署k8s的过程&#xff0c;对于理论的学习起到一定的帮助作用。罗列了一下相关步骤&#xff0c;请各位参考&#xff1a; 一、环境准备 三台虚机&#xff1a; 操作系统&#xff1a; CentOS L…

【计算机组成原理 - 第二章】系统总线(完结)

本章参考王道考研相关课程&#xff1a; 【2019版】6.1.1 总线的概念与分类_哔哩哔哩_bilibili 【2019版】6.1.2 总线的性能指标_哔哩哔哩_bilibili 【2019版】6.2 总线仲裁_哔哩哔哩_bilibili 【2019版】6.3 总线操作和定时_哔哩哔哩_bilibili 【2019版】6.4 总线标准_哔哩哔哩…

Mac 和 Win,到底用哪个系统学编程?

今天来聊一个老生常谈的问题&#xff0c;学编程时到底选择什么操作系统&#xff1f;Mac、Windows&#xff0c;还是别的什么。。 作为一个每种操作系统都用过很多年的程序员&#xff0c;我会结合我自己的经历来给大家一些参考和建议。 接下来先分别聊聊每种操作系统的优点和不…

springCloud学习【2】之Nacnos配置管理Fegin远程调用gateway服务网关

文章目录前言一 Nacos配置管理1.1 统一配置管理1.1.1 nacos中添加配置文件1.1.2 从微服务拉取配置1.2 配置热更新1.2.1 方式一&#xff1a;添加注解RefreshScope1.2.2 方式二&#xff1a;使用ConfigurationProperties注解1.3 配置共享二 搭建Nacos集群2.1 集群结构图2.2 搭建集…

【函数】JavaScript 全栈体系(七)

JavaScript 基础 第十三章 函数 一、为什么需要函数 函数&#xff1a; function&#xff0c;是被设计为执行特定任务的代码块 说明&#xff1a; 函数可以把具有相同或相似逻辑的代码“包裹”起来&#xff0c;通过函数调用执行这些被“包裹”的代码逻辑&#xff0c;这么做…