【C++】map和set的模拟实现

一、思路

1. 改造RBTree

现在我们有一棵 R B T r e e RBTree RBTree，那么如何用它实现 m a p map map和 s e t set set？我们知道 m a p map map是 KV 结构， s e t set set是 K 结构，传统思路是两份 R B T r e e RBTree RBTree的代码一个改成 m a p map map，一个改成 s e t set set。这样可以实现但不够完美，重复性较高。那么如何优雅地实现呢？查看源码，学习大佬的思路：

m a p map map:

在这里插入图片描述

s e t set set:

在这里插入图片描述

查看源码发现： m a p map map和 s e t set set向 R B T r e e RBTree RBTree传模板参数时都是<key, value>， m a p map map传的是<Key, pair<const Key, Value>>， s e t set set传的是<Key, Key>。

再看 R B T r e e RBTree RBTree源码的实现：

在这里插入图片描述
也就是说map和set传进RBTree的Key（第一个模板参数）在RBTree的节点里是没有使用的，RBTree的节点只保存Value。

综上一起看：

在这里插入图片描述

R B T r e e RBTree RBTree这一层，第二个模板参数就能决定 R B T r e e RBTree RBTree是 m a p map map还是 s e t set set，那为什么要传第一个模板参数？

不要忘了 R B T r e e RBTree RBTree这一层有一个查找操作:iterator find(const Key& key)是要直接使用第一个模板参数的。

namespace RB
{
	// map --> RBTree<K, pair<const K, V>, MapKeyOfT> _t
	// set --> RBTree<K, K, SetKeyOfT> _t
	template<class K, class T, class KeyOfT>
	class RBTree
	{
	public:
		// 节点
		typedef RBTreeNode<T> Node;
	private:
		Node* _root = nullptr;
	};
}

2. 改造RBTree的节点

namespace RB
{
	// 红黑树的颜色
	enum Color
	{
		RED,
		BLACK
	};
	// 红黑树的节点
	// KV 改造为 T(T是 K 或 pair<const K, V>)
	// KV由map和set层传过来，RBTree这一层看到的都是T
	//template<class K, class V>
	template<class T>
	struct RBTreeNode
	{
		RBTreeNode<T>* _left;
		RBTreeNode<T>* _right;
		RBTreeNode<T>* _parent; //指向父节点的指针
		//pair<K, V> _kv;
		T _data;
		Color _col;
	
		//RBTreeNode(const pair<K, V>& kv)
		RBTreeNode(const T& data)
			:_left(nullptr)
			, _right(nullptr)
			, _parent(nullptr)
			, _data(data)
			, _col(RED)
		{}
	};
}

这样一来新的问题出现了：我们在RBTree这一层看到的类型是T，T是 K 或 pair<const K, V>，那么在查找、插入比较大小时RBTree不知道是其中的哪一个，K可以直接比较大小，库中的pair实现了关系运算符的重载也可以直接比较大小，但是库中的实现并不符合我们的预期。

template <class T1, class T2>
bool operator== (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return lhs.first==rhs.first && lhs.second==rhs.second; }

template <class T1, class T2>
bool operator!= (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return !(lhs==rhs); }

库中的实现是先比较first，再比较second，如果直接使用，在RBTree中就会出现[2, 3] < [2, 4]，[2, 3]插在[2, 4]的左。

如何解决？看看源码在比较大小时是如何做的：

在这里插入图片描述

源码中是使用第三个模板参数KeyOfValue传入一个仿函数用来获取Value中的Key，

二、实现

1. map和set的实现框架

namespace nb
{
	template<class K, class V>
	class map
	{
		struct MapKeyOfT
		{
			const K& operator()(const pair<K, V>& kv)
			{
				return kv.first;
			}
		};
	private:
		RB::RBTree<K, pair<const K, V>, MapKeyOfT> _t;
	};


	template<class K>
	class set
	{
		struct SetKeyOfT
		{
			const K& operator()(const K& key)
			{
				return key;
			}
		};
	private:
		RB::RBTree<K, K, SetKeyOfT> _t;
	};	
}

2. 改造insert

对于RBTree的insert只需要把所有比较大小的地方用KeyOfT获取key之后再比较

bool Insert(const T& data)
{
	// 是空树直接将新增节点作为根
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;
		return true;
	}
	// KeyOfT
	KeyOfT kot;// kot的作用：获取Key用于比较大小
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		// pair的 > 不能满足要求
		// 获取插入data的key和cur->_data的key，比较大小
		if (kot(data) > kot(cur->_data))
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (kot(data) < kot(cur->_data))
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}

	cur = new Node(data);
	cur->_col = RED;

	if (kot(data) > kot(parent->_data))
	{
		parent->_right = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_left = cur;
		cur->_parent = parent;
	}

	// parent为空，则cur是根节点不用继续更新
	// parent节点颜色为红，需要继续相信向上调整
	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;
		// p是g的左孩子
		if (parent == grandfather->_left)
		{
			Node* uncle = grandfather->_right;
			// 所有情况 p、cur都是红，g都是黑，
			// 情况一：u存在且为红
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				cur = grandfather;// cur变g继续更新
				parent = cur->_parent;//更新p
			}
			else// u不存在 或 u存在且为黑
			{
				// 情况二：cur是p的左，p是g的左
				if (cur == parent->_left)
				{
					//      g
					//    p
					// cur
					// 对g右单旋
					RotateR(grandfather);
					// p变黑，g变红
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else// 情况三：cur是p的右，p是g的左
				{
					//     g
					//   p
					//     cur
					RotateL(parent);
					//      g
					//   cur
					// p
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;// 旋转完成后即可退出
			}
		}
		else// p是g的右孩子
		{
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				// 情况二：
				if (cur == parent->_right)
				{
					// g
					//   p
					//    cur
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					// 情况三：
					//   g
					//     p
					// cur
					RotateR(parent);
					//  g
					//    cur
					//       p
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;// 旋转完成后即可退出
			}
		}
	}
	// 避免更新出错，把根节点颜色直接给黑色
	_root->_col = BLACK;
	return true;
}

3. 实现迭代器

3. 1 RBTree的迭代器类

要实现map和set的迭代器实际上就是要实现RBTree的迭代器。

//RBTree迭代器类
template<class T, class Ref, class Ptr>
struct _RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef _RBTreeIterator<T, Ref, Ptr> Self;
	Node* _node;// 与list迭代器相同，有一个节点成员
	_RBTreeIterator(Node* node)// 构造函数：用节点构造一个迭代器
		:_node(node)
	{}
	//  * 和 ->
	Ref operator* ()
	{
		return _node->_data;
	}
	Ptr operator-> ()
	{
		return &_node->_data;
	}
	bool operator!= (const Self& s)
	{
		return _node != s._node;
	}
	// ++ 和 --
	// ……		
};

STL明确规定，begin()与end()代表的是一段前闭后开的区间，而对红黑树进行中序遍历后， 可以得到一个有序的序列

因此：begin()可以放在红黑树中最小节点（即最左侧节点）的位置，end()放在最大节点（最右侧节点）的下一个位置，关键是最大节点的下一个位置在哪里？ 能否给成nullptr呢？

答案是不能，因为对end()位置的迭代器进行--操作，必须要能找最 后一个元素，此处就不行，因此最好的方式是将end()放在头结点的位置

在这里插入图片描述

本文的实现与STL实现不同：不使用header节点。begin()一样是最左节点，end()是nullptr，end()位置的迭代器不能进行--操作。

template<class K, class T, class KeyOfT>
class RBTree
{
public:
	// 节点
	typedef RBTreeNode<T> Node;
	// 迭代器
	typedef _RBTreeIterator<T, T&, T*> iterator;
	typedef _RBTreeIterator<T, const T&, const T*> const_iterator;

	// 普通迭代器
	iterator begin()
	{
		Node* Left = _root;
		// 找最左节点
		while (Left && Left->_left)
		{
			Left = Left->_left;
		}
		return iterator(Left);
	}
	iterator end()
	{
		return iterator(nullptr);
	}
	// const迭代器
	const_iterator begin() const
	{
		Node* Left = _root;
		// 找最左节点
		while (Left && Left->_left)
		{
			Left = Left->_left;
		}
		return const_iterator(Left);
	}
	const_iterator end() const
	{
		return const_iterator(nullptr);
	}

3. 2 迭代器类的operator++

我们不需要考虑整棵树（无需递归），只需要考虑局部的子树的中序遍历（左 根 右），++走到中序的下一个，不需要考虑其他子树的节点。

在这里插入图片描述

Self& operator++()
{
	if (_node->_right)
	{
		Node* minRight = _node->_right;
		while (minRight->left)
		{
			minRight = minRight->_left;
		}
		_node = minRight;// ++到minRight
	}
	else
	{
		Node* parent = _node->_parent;
		Node* cur = _node;
		// cur 不是 parent 的左就一直往上走
		// cur 是 parent 的右说明以 parent 为根的树走完了
		// parent 为空说明走到根节点的 _parent
		while (parent && cur == parent->_right)
		{
			cur = cur->_parent;
			parent = parent->_parent;
		}
		_node = parent;
	}
	return *this;
}

3. 3 迭代器类的operator--

operator--与operator++是相反的逻辑

在这里插入图片描述

Self& operator--()
{
	if (_node->_left)
	{
		// 左子树的最大节点
		Node* maxLeft = _node->_left;
		while (maxLeft->_right)
		{
			maxLeft = maxLeft->_right;
		}
		_node = maxLeft;// --到maxLeft
	}
	else
	{
		Node* cur = _node;
		Node* parent = _node->_parent;
		while (parent && cur == parent->_left)
		{
			cur = cur->_parent;
			parent = parent->_parent;
		}
		_node = parent;
	}
	return *this;
}

3. 4 map的迭代器：

template<class K, class V>
class map
{
	struct MapKeyOfT
	{
		const K& operator()(const pair<K, V>& kv)
		{
			return kv.first;
		}
	};
public:
	// 要使用关键字 typename 显式地指明iterator是一个类型
	// 否则编译器会误认为是一个静态成员变量而产生编译错误
	typedef typename RB::RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
	typedef typename RB::RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
	// 实现map的迭代器
	iterator begin()
	{
		return _t.begin();
	}
	iterator end()
	{
		return _t.end();
	}
	const_iterator begin() const
	{
		return _t.begin();
	}
	const_iterator end() const
	{
		return _t.end();
	}
	void Insert(const pair<K, V>& _kv)
	{
		_t.Insert(_kv);
	}

private:
	RB::RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

3. 5 set的迭代器：

set的迭代器像下面这样实现是有问题的：

template<class K>
class set
{
	struct SetKeyOfT
	{
		const K& operator()(const K& key)
		{
			return key;
		}
	};
public:
	// 要使用关键字 typename 显式地指明const_iterator是一个类型
	// 否则编译器会误认为是一个静态成员变量而产生编译错误
	typedef typename RB::RBTree<K, K, SetKeyOfT>::const_iterator iterator;
	typedef typename RB::RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;
	// 实现set的迭代器
	iterator begin()
	{
		return _t.begin();
	}
	iterator end()
	{
		return _t.end();
	}
	const_iterator begin() const
	{
		return _t.begin();
	}
	const_iterator end() const
	{
		return _t.end();
	}
	void Insert(const K& key)
	{
		_t.Insert(key);
	}
private:
	RB::RBTree<K, K, SetKeyOfT> _t;
};

我们知道set的值是不能修改的，因为它要保证RBTree的结构、性质。所以迭代器也不能修改值。

// 普通迭代器和const迭代器都是const_iterator
typedef typename RB::RBTree<K, K, SetKeyOfT>::const_iterator iterator;
typedef typename RB::RBTree<K, K, SetKeyOfT>::const_iterator const_iterator;

像下面的代码就会编译报错：

auto it = s.begin();
while (it != s.end())
{
	std::cout << (*it) << " ";
	*it *= 10;// 不能修改
	++it;
}

但是将修改操作的代码注释掉后：

在这里插入图片描述

下面代码中，_t.begin()是普通迭代器，而 set 的 iterator 是const迭代器，这两种类型是不兼容的，不能直接进行转换。

// 实现set的迭代器
iterator begin()
{
	return _t.begin();
}

源码里只提供普通迭代器的const修饰版本:

在这里插入图片描述

把set的普通迭代器用const修饰，删除const_iterator的：

// 实现set的迭代器
iterator begin() const
{
	return _t.begin();
}
iterator end() const
{
	return _t.end();
}

4. 实现map的operator[]

map的operator[]底层调用的是insert，所以我们要改造RBTree中的insert：

在所有返回的位置返回pair<iterator, bool>即可。

pair<iterator, bool> Insert(const T& data)
{
	// 是空树直接将新增节点作为根
	if (_root == nullptr)
	{
		_root = new Node(data);
		_root->_col = BLACK;
		// 返回新增节点位置的迭代器和是否插入成功	 
		return std::make_pair(iterator(_root), true);
	}

	KeyOfT kot;// kot的作用：获取Key用于比较大小
	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		// pair的 > 不能满足要求
		// 获取插入data的key和cur->_data的key，比较大小
		if (kot(data) > kot(cur->_data))
		{
			parent = cur;
			cur = cur->_right;
		}
		else if (kot(data) < kot(cur->_data))
		{
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			// 返回已存在值的迭代器，充当查找
			return std::make_pair(iterator(cur), false);;
		}
	}

	cur = new Node(data);
	// cur可能会向上调整发生变化
	// 需要一个newNode用于返回新增节点的迭代器
	Node* newNode = cur;
	cur->_col = RED;

	if (kot(data) > kot(parent->_data))
	{
		parent->_right = cur;
		cur->_parent = parent;
	}
	else
	{
		parent->_left = cur;
		cur->_parent = parent;
	}

	// parent为空，则cur是根节点不用继续更新
	// parent节点颜色为红，需要继续相信向上调整
	while (parent && parent->_col == RED)
	{
		Node* grandfather = parent->_parent;
		// p是g的左孩子
		if (parent == grandfather->_left)
		{
			Node* uncle = grandfather->_right;
			// 所有情况 p、cur都是红，g都是黑，
			// 情况一：u存在且为红
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				cur = grandfather;// cur变g继续更新
				parent = cur->_parent;//更新p
			}
			else// u不存在 或 u存在且为黑
			{
				// 情况二：cur是p的左，p是g的左
				if (cur == parent->_left)
				{
					//      g
					//    p
					// cur
					// 对g右单旋
					RotateR(grandfather);
					// p变黑，g变红
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else// 情况三：cur是p的右，p是g的左
				{
					//     g
					//   p
					//     cur
					RotateL(parent);
					//      g
					//   cur
					// p
					RotateR(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;// 旋转完成后即可退出
			}
		}
		else// p是g的右孩子
		{
			Node* uncle = grandfather->_left;
			if (uncle && uncle->_col == RED)
			{
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;
				cur = grandfather;
				parent = cur->_parent;
			}
			else
			{
				// 情况二：
				if (cur == parent->_right)
				{
					// g
					//   p
					//    cur
					RotateL(grandfather);
					parent->_col = BLACK;
					grandfather->_col = RED;
				}
				else
				{
					// 情况三：
					//   g
					//     p
					// cur
					RotateR(parent);
					//  g
					//    cur
					//       p
					RotateL(grandfather);
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				break;// 旋转完成后即可退出
			}
		}
	}
	// 避免更新出错，把根节点颜色直接给黑色
	_root->_col = BLACK;
	return std::make_pair(iterator(newNode), true);
}

map中的insert和operator[]：

template<class K, class V>
class map
{
	// ……
public:
	// 要使用关键字 typename 显式地指明iterator是一个类型
	// 否则编译器会误认为是一个静态成员变量而产生编译错误
	typedef typename RB::RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;
	typedef typename RB::RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator;
	// 实现map的迭代器
	// ……
	//void Insert(const pair<K, V>& kv)
	//{
	//	_t.Insert(kv);
	//}

	pair<iterator, bool> Insert(const pair<K, V>& kv)
	{
		return _t.Insert(kv);
	}

	V& operator[](const K& key)
	{
		pair<iterator, bool> ret = Insert(make_pair(key, V()));
		return ret.first->second;
	}

private:
	RB::RBTree<K, pair<const K, V>, MapKeyOfT> _t;
};

但是当我们把 set 中 insert 也改成：

pair<iterator, bool> Insert(const K& key)
{
	return _t.Insert(key);
}

又出现了下面的错误：
在这里插入图片描述

出现错误的原因是：RBTree层的迭代器是普通迭代器，set层的迭代器是const迭代器，无法直接转换。

那能不能像前面的begin一样在后面加一个 const 修饰呢？
答案是不能。因为使用 const 修饰符的成员函数，它们不会修改对象的状态，但是insert是需要向树中插入值的，会修改对象的状态。

那么如何解决？

源码是这样解决的：

在这里插入图片描述

照着源码解决：

pair<iterator, bool> Insert(const K& key)
{
	//return _t.Insert(key);
	pair<typename RB::RBTree<K, K, SetKeyOfT>::iterator, bool> ret = _t.Insert(key);
	return pair<iterator, bool>(ret.first, ret.second);
}

除了上面的方法，还可以实现下面的拷贝构造函数，迭代器一般是不需要写拷贝构造的，用一个迭代器拷贝出另一个迭代器，我们的期望就是两个迭代器指向同一个节点，系统默认生成的（浅拷贝）就符合要求。

下面的构造函数，对象是普通迭代器时，使用拷贝构造的方式来初始化新的迭代器，对象是 const 迭代器时，使用构造的方式来初始化 新的迭代器。

在这里插入图片描述

实现这个函数之后，就可以将普通迭代器直接构造转换成const迭代器，set的insert也就可以直接return了。

// 普通迭代器的时候，它是拷贝构造
// const迭代器的时候，它是构造，支持用普通迭代器构造const迭代器
template<class T, class Ref, class Ptr>
typedef _RBTreeIterator<T, T&, T*> iterator;
_RBTreeIterator(const iterator& cit)
	:_node(cit._node)
{
	//std::cout << "_RBTreeIterator(const iterator& cit)" << std::endl;
}

在这里插入图片描述

之前实现的list的如果没有下面这个函数是不能将普通迭代器直接构造转换成const迭代器

// 普通迭代器的时候，它是拷贝构造
// const迭代器的时候，它是构造，支持用普通迭代器构造const迭代器
typedef __list_iterator<T, T&, T*> iterator;
__list_iterator(const iterator& cit)
			:_pnode(cit._pnode)
{
	 //std::cout << "__list_iterator(const __list_iterator& cit)" << std::endl;
}

下图是没有上面的函数，会编译报错。

在这里插入图片描述

整体代码GitHub

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

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

相关文章

【MATLAB图像处理实用案例详解（12）】——利用BP神经网络实现图像压缩

【MATLAB图像处理实用案例详解（12）】——利用BP神经网络实现图像压缩

目录 一、图像压缩二、BP神经网络实现图像压缩原理三、算法步骤3.1 图像块划分3.2 归一化3.3 建立BP神经网络3.4 保存结果 四、效果演示 一、图像压缩 常见的文件压缩软件如WinZip、WinRAR等采用的是无损压缩&#xff0c;能够完全恢复原文件内容。多媒体信息具有信息量大、冗余…
阅读更多...
STM32F4 HAL库使用DMA进行ADC采样实时发送波形到串口显示（包含傅里叶变换）

STM32F4 HAL库使用DMA进行ADC采样实时发送波形到串口显示（包含傅里叶变换）

1.总体逻辑 按下STM32F4的KEY0按键&#xff0c;通过外部中断的方式对按键进行检测&#xff0c;然后开启一次带DMA的固定点数的ADC采集&#xff0c;采集完成后在DMA的中断发送采集到的数据&#xff0c;然后清空数据区准备下一次的按键中断。电脑接受到串口数据后对数据进行简单…
阅读更多...
【JavaEE】SpringBoot的日志

【JavaEE】SpringBoot的日志

目录 日志作用 SpringBoot日志框架 日志打印 日志级别 类型 作用 修改级别 日志永久化 配置日志文件目录 配置日志文件名 简化日志打印和永久化——lombok 日志作用 问题定位&#xff1a;可以帮助开发人员快速找到问题出现的位置系统监控&#xff1a;可以把系统的运…
阅读更多...
跳跃游戏类题目 总结篇

跳跃游戏类题目 总结篇

一.跳跃游戏类题目简单介绍 跳跃游戏是一种典型的算法题目&#xff0c;经常是给定一数组arr&#xff0c;从数组的某一位置i出发&#xff0c;根据一定的跳跃规则&#xff0c;比如从i位置能跳arr[i]步&#xff0c;或者小于arr[i]步&#xff0c;或者固定步数&#xff0c;直到到达某…
阅读更多...
结构型模式-组合模式

结构型模式-组合模式

组合模式 概述 ​ 对于这个图片肯定会非常熟悉&#xff0c;上图我们可以看做是一个文件系统&#xff0c;对于这样的结构我们称之为树形结构。在树形结构中可以通过调用某个方法来遍历整个树&#xff0c;当我们找到某个叶子节点后&#xff0c;就可以对叶子节点进行相关的操作。…
阅读更多...
计算机组成原理4.2.2汉明码

计算机组成原理4.2.2汉明码

编码的最小距离 奇校验和偶校验 看1的个数是奇数 还是偶数 汉明码 汉明码的配置 根据不等式&#xff0c;确定增添几位&#xff0c;根据指数放置增添位 汉明码的检错 分不同检测小组 分组规则&#xff1a;哪位为’1‘就是哪组元素。 1号位为‘1’的都是第一组元素&#…
阅读更多...
基于COM组件实现C#调用C++类对象过程中的注意事项

基于COM组件实现C#调用C++类对象过程中的注意事项

目录 一、基于COM的调用原理二、注意事项如何在C ATL中有效添加方法与属性如何让C#调用C中的属性&#xff08;.idl中声明属性&#xff09;如何对变量类型进行转换C#如何获取C类中的参数变量 一、基于COM的调用原理 调用原理&#xff1a;首先基于C ATL模板类&#xff0c;实现需…
阅读更多...
【网络进阶】服务器模型Reactor与Proactor

【网络进阶】服务器模型Reactor与Proactor

文章目录 1. Reactor模型2. Proactor模型3. 同步IO模拟Proactor模型 在高并发编程和网络连接的消息处理中&#xff0c;通常可分为两个阶段&#xff1a;等待消息就绪和消息处理。当使用默认的阻塞套接字时&#xff08;例如每个线程专门处理一个连接&#xff09;&#xff0c;这两…
阅读更多...
【redis】redis分布式锁（二）可重入锁+设计模式

【redis】redis分布式锁（二）可重入锁+设计模式

【redis】redis分布式锁&#xff08;二&#xff09;可重入锁 文章目录 【redis】redis分布式锁&#xff08;二&#xff09;可重入锁前言一、可重入锁&#xff08;又名递归锁&#xff09;1、说明&#xff1a;2、分开解释&#xff1a;3、可重入锁的种类隐式锁&#xff08;即synch…
阅读更多...
【软件测试】测试用例的设计

【软件测试】测试用例的设计

文章目录 一. 针对没有需求的案例来设计测试用例二. 针对有需求的案例来设计测试用例1. 穷举法2. 等价类3. 边界值4. 判定表法5. 场景设计法5.1 简介5.2 基本设计步骤5.3 基本流和备选流5.4 使用场景5.5 优缺点5.6 实例 6. 错误猜测法 一. 针对没有需求的案例来设计测试用例 针…
阅读更多...
深度强化学习——蒙特卡洛算法(6)

深度强化学习——蒙特卡洛算法(6)

注&#xff1a;本章的内容作为补充插曲&#xff0c;大家可以选看&#xff0c;不过还是建议把最后一个使用蒙特卡洛近似求期望稍微看一下 蒙特卡洛是一大堆随机算法&#xff0c;通过随机样本来估算真实值 使用随机样本来近似Π 1、在[a,b]做随机均匀抽样&#xff0c;抽出n个样…
阅读更多...
YOLO物体检测系列1.经典方法概述及评价指标体现

YOLO物体检测系列1.经典方法概述及评价指标体现

1. 深度学习经典检测方法&#xff1a; two-stage(两阶段)&#xff1a; Faster-rcnn Mask-RCNN系列 one-stage(单阶段)&#xff1a;Yolo系列 两阶段&#xff1a;一阶段实现RPN候选区域预选 二阶段基于候选区域再进行检测回归分类任务 单阶段&#xff1a;一个CNN卷积网络实现检测…
阅读更多...
C++线程的简单学习及了解

C++线程的简单学习及了解

此篇文章只是线程的简单了解。 文章目录 前言一、线程的优缺点二、C线程库 1.thread类的简单介绍2.线程函数参数总结 前言 什么是线程&#xff1f; 在一个程序里的一个执行路线就叫做线程&#xff08;thread&#xff09;。更准确的定义是&#xff1a;线程是“一个进程内部的控…
阅读更多...
day3 TCP/IP协议与五层体系结构

day3 TCP/IP协议与五层体系结构

TCP / IP 四层体系结构 TCP / IP工作流程&#xff1a; 现在互联网使用的 TCP/IP 体系结构已经发生了演变&#xff0c;即某些应用程序可以直接使用 IP 层&#xff0c;或甚至直接使用最下面的网络接口层。 沙漏型展示&#xff1a; 五层体系结构 各层的主要功能 应用层&#xff1…
阅读更多...
搭建外网minecraft服务器方案

搭建外网minecraft服务器方案

很多minecraft服务器主都想自己搭建一个外网可以访问的minecraft服务器&#xff0c;在没有外网IP的情况下&#xff0c;一般都是使用Logmein Hamachi方案。这种方案有它的弊端&#xff0c;需要客户机安装Hamachi&#xff0c;十分不方便。另外&#xff0c;免费版只支持5人&#x…
阅读更多...
mysql如何加行锁

mysql如何加行锁

一、概述 InnoDB 引擎是支持行级锁的&#xff0c;而 MyISAM 引擎并不支持行级锁&#xff0c;所以后面的内容都是基于 InnoDB 引擎的。当我们使用delete、update进行数据库删除、更新的时候&#xff0c;数据库会自动加上行锁。但是&#xff0c;行锁有时也会失效。 数据库版本&a…
阅读更多...
笔记：计算机网络体系结构（OSI七层模型、TCP/IP五层协议）

笔记：计算机网络体系结构（OSI七层模型、TCP/IP五层协议）

计算机网络体系结构 计算机网络是一个复杂的、具有综合性技术的系统&#xff0c;它由计算机系统、通信处理机、通信线路和通信设备、操作系统以及网络协议等组成。为了更好地描述计算机网络结构&#xff0c;使计算机网络系统有条不紊地处理工作&#xff0c;需要定义一种较好的…
阅读更多...
CH9121网络串口透传应用

CH9121网络串口透传应用

概述 随着物联网技术的普及&#xff0c;越来越多的传统设备出现联网功能需求。串口作为使用较为广泛的一种通信接口&#xff0c;串口转以太网&#xff0c;进行远程数据传输需求逐渐显现出来。CH9121内部集成TCP/IP协议栈&#xff0c;无需编程&#xff0c;即可轻松实现网络数据…
阅读更多...
【SWAT水文模型】SWAT水文模型建立及应用第二期：土地利用数据的准备

【SWAT水文模型】SWAT水文模型建立及应用第二期：土地利用数据的准备

SWAT水文模型建立及应用&#xff1a;土地利用数据的准备 1 简介2 土地利用数据的下载2.1 数据下载方式2.1.1 中科院1km土地利用数据2.1.2 清华大学高精度土地利用数据 2.2 数据下载 3 土地利用数据的准备3.1 矢量转栅格3.2 土地利用类型的重分类3.3 土地利用分布图投影调整3.4 …
阅读更多...
【LeetCode】213. 打家劫舍 II

【LeetCode】213. 打家劫舍 II

213. 打家劫舍 II&#xff08;中等&#xff09; 思路 这道题是 198.打家劫舍 的拓展版&#xff0c;区别在于&#xff1a;本题的房间是环形排列&#xff0c;而198.题中的房间是单排排列。 将房间环形排列&#xff0c;意味着第一间房间和最后一间房间不能同时盗窃&#xff0c;因…
阅读更多...
最新文章

Copyright @ 2022~2023