【C++杂货铺】会杂耍的二叉搜索树——AVLTree

这篇具有很好参考价值的文章主要介绍了【C++杂货铺】会杂耍的二叉搜索树——AVLTree。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习

一、前言

在上一篇文章中对 set、multiset、map、multimap 进行了简单的介绍,在其文档介绍中发现,这几个容器都有一个共同点:其底层都是借助二叉搜索树来实现的。但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成为单支树,时间复杂度会退化成 O ( N ) O(N) O(N),因此 set、map 等关联式容器的底层结构是对二叉树进行了平衡处理,即采用平衡树来实现。那么今天就让我们对 set 和 map 的底层结构一探究竟。

二、AVL 树的概念

二叉搜索树虽然可以缩短查找的效率,但是如果数据有序或者接近有序,二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率就会变得低下。因此,两位俄罗斯的数学家 G.M.Adelson-Velskii 和E.M.Landis 在 1962 年发明了一种解决上述问题的方法:当向二叉搜索树中插入新节点后,如果能保证每个节点的左右子树高度之差的绝对值不超过 1(超过 1 需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。一颗 AVL 树或者是空树,或者是具有以下性质的二叉搜索树:

  • 它的左右子树都是 AVL 树。

  • 左右子树高度之差(简称平衡因子)的绝对值不超过 1(-1、0、1)。

【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习
小Tips:如果一颗二叉搜索树是高度平均的,它就是 AVL 树。如果它有 n 个结点,其高度可保持在 O ( l o g 2 n ) O(log2^n) O(log2n),搜索时间复杂度为 O ( l o g 2 n ) O(log2^n) O(log2n)。平衡二叉搜索树中平衡并不是说要让平衡因子始终保持 0,这是做不到的,以两个结点为例,根节点的平衡因子只可能是 1 或者 -1,不可能是 0。二叉搜索树在实际中基本不太可能实现完全平衡,但是理论上可以,即满二叉树。后面我们学的多叉平衡搜索树在现实中可以做到完全平衡。

三、AVL 树结点的定义

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode(const pair<K, V>& kv = pair<K, V>())
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_bf(0)
	{}

	pair<K, V> _kv;//存储key和value
	AVLTreeNode<K, V>* _left = nullptr;//指向左孩子
	AVLTreeNode<K, V>* _right = nullptr;//指向右孩子
	AVLTreeNode<K, V>* _parent = nullptr;//指向父亲结点
	int _bf = 0;//平衡因子
};

四、AVL 树的框架

template<class K, class V>
	class AVLTree
	{
		typedef AVLTreeNode<K, V> Node;
	private:
		Node* _root = nullptr;
	};

五、AVL 树的插入

AVL 树就是在二叉搜索树的基础上引入平衡因子,因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步:

  • 按照二叉搜索树的方式插入新节点。

  • 调整结点的平衡因子。

5.1 平衡因子的更新

新结点插入后,AVL 树的平衡性可能会遭到破坏,此时就需要更新平衡因子,并检测是否破坏了 AVL 树的平衡性。假设新插入的结点为 cur,那么 cur 的平衡因子一定是 0,因为它的左后孩子都是 nullptr。但是 cur 的双亲结点 parent 的平衡因子一定需要调整,在插入之前,parent 的平衡因子分为三种情况:-1、0、1。对 parent 平衡因子的调整分为以下两种情况:

  • 如果 cur 插入到 parent 的左侧,只需要给 parent 的平衡因子 − 1 -1 1 即可。

  • 如果 cur 插入到 parent 的右侧,只需要给 parent 的平衡因子 + 1 +1 +1 即可。

此时更新后 parent 的平衡因子有以下三种情况: 0 0 0 ± 1 ±1 ±1 ± 2 ±2 ±2

  • 如果 parent 的平衡因子为 0 0 0,说明插入前 parent 的平衡因子一定为 ± 1 ±1 ±1,即左右孩子中一定有一个是 nullptr,并且新结点就插入在为空的一侧,插入后平衡因子被调整成 0 0 0,整棵树的高度任然不变,满足 AVL 树的性质,插入成功。

  • 如果 parent 的平衡因子是 ± 1 ±1 ±1,说明插入前 parent 的平衡因子一定是 0 0 0,即插入前 parent 的左右孩子都为 nullptr,并未新结点就插入在 parent 的任意一侧,所以插入后平衡因子被调整成了 ± 1 ±1 ±1,此时以 parent 为跟的树的高度增加了,需要继续沿着祖先结点向上更新,知道某一个祖先节点的平衡因子变成了 0 0 0,此时更新结束,插入成功。

  • 如果 parent 的平衡因子为 ± 2 ±2 ±2,则 parent 的平衡因子违反了平衡树的性质,需要对其进行旋转处理。

情况一:
【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习
情况二:
【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习
情况三:
【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习

5.2 AVL 树的旋转

如果在一颗原本是平衡的 AVL 树中插入一个新结点,可能造成不平衡,此时必须调整树的结构,使之平衡化。根据结点插入位置的不同,AVL 树的旋转分为四种:

5.2.1 左单旋

新结点插入在较高右子树的右侧----右右:即 parent 的平衡因子是 2 2 2cur 的平衡因子是 1 1 1,此时就需要左单旋。下面举两个左单旋的例子。

例一:
【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习
例二:
【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习
抽象图:
【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习

小Tips:无论是这四种旋转中的哪一个,都要保证以下两点:首先在旋转的过程中要保证这棵树是搜索树,其次经过旋转后,这棵树应该变成平衡树,且降低这个子树的高度。这两点就决定了左旋的核心操作就是将 cur 的左子树给 parent 的右子树,再让 parent 成为 cur 的左子树。

void RotateL(Node* parent)
{
	Node* cur = parent->_right;
	Node* curleft = cur->_left;

	parent->_right = curleft;
	cur->_left = parent;

	if (curleft)
	{
		curleft->_parent = parent;
	}
	
	Node* ppnode = parent->_parent;
	parent->_parent = cur;

	if (parent == _root)
	{
		_root = cur;
		cur->_parent = nullptr;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = cur;
		}
		else
		{
			ppnode->_right = cur;
		}
		cur->_parent = ppnode;
	}
	parent->_bf = cur->_bf = 0;
}

5.2.2 右单旋

新结点插入在较高左子树的左侧----左左:即 parent 的平衡因子是 − 2 -2 2cur 的平衡因子是 − 1 -1 1,此时就需要右单旋。

抽象图:
【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习

//右单旋
void RotateR(Node* parent)
{
	Node* cur = parent->_left;
	Node* curright = cur->_right;//此时的情况是curright比cur大,比parent小

	parent->_left = curright;
	cur->_right = parent;

	if (curright)
	{
		curright->_parent = parent;
	}
	
	Node* ppnode = parent->_parent;
	parent->_parent = cur;

	if (ppnode)
	{
		cur->_parent = ppnode;
		if (ppnode->_left == parent)
		{
			ppnode->_left = cur;
		}
		else
		{
			ppnode->_right = cur;
		}
	}
	else
	{
		_root = cur;
		cur->_parent = nullptr;
	}
	parent->_bf = cur->_bf = 0;
}

5.2.3 先右单旋再左单旋

新结点插入在较高右子树的左侧----右左:即 parent 的平衡因子是 2 2 2cur 的平衡因子是 − 1 -1 1。此时就需要先以 cur 为旋转点进行一个右单旋,再以 parent 为旋转点进行一个左单旋。下面给大家举两个例子。

例一:
【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习
例二:
【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习
抽象图:
【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习
小Tips:右左双旋的本质是把 60 结点的右边给了 90 结点的左边,把 60 结点的左边给了 30 结点的右边,然后 60 结点变成了这颗子树的跟结点。进行右左双旋后,平衡因子的更新有以下三种情况:

  • 插入后 60 结点的平衡因子是 0 0 0,说明 60 自己就是新增节点,此时 parentcur 的平衡因子都是 0 0 0

  • 插入后 60 结点的平衡因子是 − 1 -1 1,说明是在 60 结点的左侧插入,此时 parent 的平衡因子是 0 0 0cur 的平衡因子是 − 1 -1 1

  • 插入后 60 结点的平衡因子是 1 1 1,说明是在 60 结点的右侧插入,此时 parent 的平衡因子是 − 1 -1 1cur 的平衡因子是 0 0 0

//右左双旋
void RotateRL(Node* parent)
{
	Node* cur = parent->_right;
	Node* curleft = cur->_left;
	int bf = curleft->_bf;

	RotateR(parent->_right);
	RotateL(parent);

	if (bf == 0)
	{
		parent->_bf = cur->_bf = curleft->_bf = 0;
	}
	else if (bf == 1)
	{
		cur->_bf = 0;
		parent->_bf = -1;
		curleft->_bf = 0;
	}
	else if (bf == -1)
	{
		cur->_bf = 1;
		parent->_bf = 0;
		curleft->_bf = 0;
	}
}

5.2.4 先左单旋再右单旋

新结点插入在较高左子树的右侧----左右:即 parent 的平衡因子是 − 2 -2 2cur 的平衡因子是 1 1 1。此时就需要先以 cur 为旋转点进行一个左单旋,然后再以 parent 为旋转点进行一个右单旋。下面为大家举两个具体的实例。

例一:
【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习
例二:
【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习
抽象图:
【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习

5.3 AVL 树插入完整代码

/*AVLTree.h*/
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;//插入成功
		}
	
		//找插入位置
		Node* cur = _root;
		Node* parent = nullptr;
	
		while (cur)
		{
			if (kv.first < cur->_kv.first)//小于往左走
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)//大于往右走
			{
				parent = cur;
				cur = cur->_right;
			}
			else//相等插入不了
			{
				return false;
			}
		}
	
		//找到待插入位置了,进行插入
		cur = new Node(kv);
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
	
		cur->_parent = parent;
	
		//控制平衡
		//更新衡因子
		while (parent)//我们这里始终更新的是parent的平衡银子,当parent为nullptr说明根节点_root的平衡因子已经被我们更新过了
		{
			//更新平衡因子
			if (cur == parent->_left)
			{
				--(parent->_bf);
			}
			else if (cur == parent->_right)
			{
				++(parent->_bf);
			}
	
			//判断更新后parent的平衡因子
			if (parent->_bf == 0)//输入成功
			{
				break;
			}
			else if (parent->_bf == -1 || parent->_bf == 1)
			{
				//继续往上更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == -2 || parent->_bf == 2)
			{
				//需要旋转
				if (cur->_bf == 1 && parent->_bf == 2)//左单旋
				{
					RotateL(parent);
				}
				else if (cur->_bf == -1 && parent->_bf == -2)//右单旋
				{
					RotateR(parent);
				}
				else if (cur->_bf == -1 && parent->_bf == 2)//右左单旋
				{
					RotateRL(parent);
				}
				else if (cur->_bf == 1 && parent->_bf == -2)//左右单旋
				{
					RotateLR(parent);
				}
	
				break;
			}
			else
			{
				assert(false);
			}
		}
	
		return true;
	}
	
	
private:
	//左单旋
	void RotateL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
	
		parent->_right = curleft;
		cur->_left = parent;
	
		if (curleft)
		{
			curleft->_parent = parent;
		}
		
		Node* ppnode = parent->_parent;
		parent->_parent = cur;
	
		if (parent == _root)
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}
			cur->_parent = ppnode;
		}
	
		parent->_bf = cur->_bf = 0;
	}
	
	//右单旋
	void RotateR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;//此时的情况是curright比cur大,比parent小
	
		parent->_left = curright;
		cur->_right = parent;
	
		if (curright)
		{
			curright->_parent = parent;
		}
		
		Node* ppnode = parent->_parent;
		parent->_parent = cur;
	
		if (ppnode)
		{
			cur->_parent = ppnode;
			if (ppnode->_left == parent)
			{
				ppnode->_left = cur;
			}
			else
			{
				ppnode->_right = cur;
			}
		}
		else
		{
			_root = cur;
			cur->_parent = nullptr;
		}
		parent->_bf = cur->_bf = 0;
	}
	
	//右左双旋
	void RotateRL(Node* parent)
	{
		Node* cur = parent->_right;
		Node* curleft = cur->_left;
		int bf = curleft->_bf;
	
		RotateR(parent->_right);
		RotateL(parent);
	
		if (bf == 0)
		{
			parent->_bf = cur->_bf = curleft->_bf = 0;
		}
		else if (bf == 1)
		{
			cur->_bf = 0;
			parent->_bf = -1;
			curleft->_bf = 0;
		}
		else if (bf == -1)
		{
			cur->_bf = 1;
			parent->_bf = 0;
			curleft->_bf = 0;
		}
	}
	
	//左右双旋
	void RotateLR(Node* parent)
	{
		Node* cur = parent->_left;
		Node* curright = cur->_right;
		int bf = curright->_bf;
	
		RotateL(cur);
		RotateR(parent);
	
		if (bf == 0)
		{
			parent->_bf = cur->_bf = curright->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			cur->_bf = -1;
			curright->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			cur->_bf = 0;
			curright->_bf = 0;
		}
	}

5.4 AVL 树的验证

AVL 树是在二叉搜索树的基础上加入了平衡的限制,因此要验证 AVL 树,可以分为两步:

  • 验证其为二叉搜索树。如果中序遍历可以得到一个有序的序列,就说明为二叉搜索树。

  • 验证其为平衡树。每个结点左右子树高度差的绝对值不超过 1 1 1。其次检查结点的平衡因子是否计算正确。

public:
	//中序
	void Inorder()
	{
		return _Inorder(_root);
	}
	//检测平衡因子
	bool IsBlance()
	{
		return _IsBalance(_root);
	}
private:
	//中序
	void _Inorder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
	
		_Inorder(root->_left);
		cout << root->_kv.first << ' ';
		_Inorder(root->_right);
	
		return;
	}
	
	
	//求树的高度
	int Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}

		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
	}
	
	//检测平衡因子
	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}

		int leftHeight = Height(root->_left);
		int rightHeight = Height(root->_right);

		if (rightHeight - leftHeight != root->_bf)
		{
			cout << "平衡因子异常:" << root->_bf << endl;
			return false;
		}

		return abs(leftHeight - rightHeight) < 2
			&& _IsBalance(root->_left)
			&& _IsBalance(root->_right);
	}
/*test.c*/
int main()
{
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
	wcy::AVLTree<int, int> t;
	for (auto e : a)
	{
		t.Insert(make_pair(e, e));
		t.Inorder();
		cout << endl;
		if (t.IsBlance())
		{
			cout << "成功插入:" << e << endl;
		}
		else
		{
			cout << e << "插入失败" << endl;
		}
	}
	return 0;
}

【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习

六、AVL 树的删除

因为 AVL 树也是二叉搜索树,可以按照二叉搜索树的方式将结点删除,然后再更新平衡因子,只不过与删除插入不同的是,删除结点后的平衡因子更新,最差情况下一直要调整到根结点的位置。具体的实现感兴趣的小伙伴可以参考《算法导论》或者《数据结构-用面向对象方法与C++描述》殷人昆版。

七、AVL 树的性能

AVL 树是一颗绝对平衡的二叉搜索树,其要求每个结点的左右子树高度差的绝对值都不超过 1 1 1,这样在查询时可以保证高效的时间复杂度,即 O ( l o g 2 n ) O(log2^n) O(log2n)。但是如果要对 AVL 树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。因此,如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑 AVL 树,但一个结构经常修改,就不太适合。

八、结语

今天的分享到这里就结束啦!如果觉得文章还不错的话,可以三连支持一下,春人的主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是春人前进的动力!

【C++杂货铺】会杂耍的二叉搜索树——AVLTree,C++杂货铺,c++,开发语言,人工智能,计算机视觉,机器学习文章来源地址https://www.toymoban.com/news/detail-714521.html

到了这里,关于【C++杂货铺】会杂耍的二叉搜索树——AVLTree的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【C++杂货铺】内管管理

    目录 🌈前言🌈 📁 C/C++中内存分布 📁 new 和 delete的使用 📁 new 和 delete的优点 📁 new 和 delete的原理  📂 operator new 和 operator delete函数  📂 内置类型  📂 自定义类型 📁 内存泄漏 📁 总结         欢迎收看本期【C++杂货铺】,本期内容讲解C++内存管理。包含了C++中内存

    2024年04月14日
    浏览(43)
  • 【C++杂货铺】拷贝构造函数

    📖 定义 拷贝构造函数 是构造函数的一个重载 ,它的本质还是 构造函数 ,那就意味着,只有在创建对象的时候,编译器才会自动调用它,那他和普通的构造函数有什么区别呢? 拷贝构造函数,是创建对象的时候,用一个已存在的对象,去初始化待创建的对象 。简单来说,

    2024年02月16日
    浏览(47)
  • 【C++杂货铺】运算符重载

    本文将以日期类为基础,去探寻运算符重载的特性与使用方法,下面先给出日期类的基础定义: 备注 :拷贝构造函数和析构函数,均可以不写,因为当前日期类的三个成员变量都是内置类型,没有动态申请空间,使用浅拷贝就可以。 📖 如何比较两个日期的大小? 现如今,

    2024年02月16日
    浏览(69)
  • 【C++杂货铺】缺省参数、函数重载

     缺省参数是 声明或定义函数时为函数的参数指定一个缺省值 。在调用该函数时,如果没有指定实参则采用该形参的缺省值,否则使用指定的实参。  上面代码在 fun 函数的形参部分给了缺省值10,这意味着在调用 fun 函数的时候可以传参,也可以不传参,如果传参了那形参

    2024年02月16日
    浏览(37)
  • 【C++杂货铺】详解list容器

    目录 🌈前言🌈 📁 介绍 📁 使用  📂 构造  📂 迭代器iterator  📂 capacity  📂 modifiers  📂 迭代器失效 📁 模拟实现  📂 迭代器的实现 📂 代码展示 📁 和vector的区别 📁 总结         欢迎收看本期【C++杂货铺】,本期内容将讲解STL中关于list的内容,会分为一下几个方

    2024年04月14日
    浏览(48)
  • 【C++杂货铺】C++介绍、命名空间、输入输出

     C语言是 结构化 和 模块化 的语言,适合处理 较小规模 的程序。对于复杂的问题,规模较大的程序,需要高度的抽象和建模时,C语言则不合适。为了解决软件危机,20世纪80年代,计算机界提出了 OOP (object oriented programming: 面向对象 )思想,支持面向对象的程序设计语言应

    2024年02月16日
    浏览(39)
  • 【C++杂货铺】初识类和对象

    📖 面向过程 C语言是 面向过程的 ,关注的是过程,分析出求解问题的步骤,通过函数调用逐步解决问题。以洗衣服这件事为例,下图是C语言完成洗衣服这件事的过程。 📖 面向对象 C++是 基于面向对象的 ,关注的是对象,将一件事情拆分成不同的对象,靠对象之间的交互完

    2024年02月16日
    浏览(49)
  • 【C++杂货铺】再谈类和对象

    在创建对象的时候,编译器通过调用构造函数,在构造函数体中,给对象中的各个成员变量一个合适的初值。 虽然上述构造函数调用之后,对象中已经有了一个初始值,但是不能将其称为对对象中成员变量的初始化, 构造函数体中的语句只能将其称为赋初值,而不能称作初

    2024年02月16日
    浏览(37)
  • 【C++杂货铺】string使用指南

    2024年02月14日
    浏览(43)
  • 【C++杂货铺】探索string的底层实现

    string 本质上是一个动态顺序表,它可以根据需要动态的扩容,所以字符串一定是通过在堆上动态申请空间进行存储的,因此 _str 指向存储字符串的空间, _size 用来表示有效字符数, _capacity 用来表示可以存储有效字符的容量数。 注意 :默认构造函数需要注意的地方是:首先

    2024年02月11日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包