【C++】map与set容器——红黑树底层封装

这篇具有很好参考价值的文章主要介绍了【C++】map与set容器——红黑树底层封装。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


前言

  • 💭STL中,容器大概可分为两种类型——序列式容器和关联式容器。在前面的系列文章中,我们已经介绍了诸多序列式容器,如:vector、list、stack、queue等,它们以序列的形式存储数据。

  • 💭而关联式容器也是一种非常重要的容器。标准的STL关联式容器分为set(集合)和map(映射表)两大类,以及这两大类的衍生体multiset和multimap。这些容器的底层机制均以RBTree实现,也就是上文我们所说的红黑树,这正是本文的重点所在。怎么用红黑树实现map和set?为什么?本文将解决这一系列问题。

🔎下面是关联式容器 (associative containers) 的概念

所谓关联式容器,观念上类似关联式数据库(实际上则简单许多):每笔数据(每个元素),都有一个键值(key)和一个实值(valve),当元素被插入到关联式容器中时,容器内部结构(可能是 RB-tree,也可能是 hash-table)便依照其键值大小,以某种特定规则将这个元素放置于适当位置。关联式容器没有所谓头尾(只有最大元素和最小元素),所以不会有所谓 push_ back()、push_ front()、pop_back()、pop_front()这样的操作行为。

节选自《STL源码剖析》一书


1. set


1.1 set的概念

📝 set是一种关联式容器,其特性如下:

  1. set的所有元素都会根据元素的键值被自动排列
  2. set的底层是红黑树
  3. set不像map同时拥有键值(key)和实值(value),set的键值就是实值
  4. set不允许两个元素有相同的键值,即每个键值都是唯一的
  5. set的元素不能在容器中修改,但是可以插入或删除。

🔎为什么set的元素不能在容器中修改?

因为set元素值就是其键值,其关系到set元素的排列规则,一旦任意修改了set元素值,会严重破坏set的组织结构。


1.2 set的使用

包含头文件:#include <set>

1️⃣set的模板参数

【C++】map与set容器——红黑树底层封装

  • T:set中存放元素的类型,实际在底层存储<value, value>的键值对。
  • Compare:set的元素排序比较方式,默认按照小于来比较。
  • Alloc:set中元素空间的管理方式,使用STL提供的空间配置器管理。

2️⃣set的接口使用

💭set的构造函数有三种,主要的接口有insert、find、erase,比较简单,此处不再展开介绍。

构造函数功能 接口
默认构造(构造一个空set) set (const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());
迭代器区间构造(按两个迭代器指向的一系列元素构造set) set (InputIterator first, InputIterator last)
拷贝构造 set (const set& x);

📃set的文档介绍

💡基于set的特性,可以用于对一个序列进行去重+排序的操作。

⭕下面是一段set的测试代码

void test_set()
{
	set<int> s;
	// set插入数据
	s.insert(7);
	s.insert(8);
	s.insert(6);
	s.insert(5);

	// set的迭代器支持了范围for
	for (auto& k : s)
	{
		cout << k << " ";
	}
	cout << endl;

	int a[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };

	// 迭代器范围,构造set
	set<int> ss(a, a + sizeof(a) / sizeof(a[0]));

	// set的迭代器支持了范围for
	for (auto& k : ss)
	{
		cout << k << " ";
	}
}

⭕运行结果,可见set确实可以达到去重+排序的目的

5 6 7 8
0 1 2 3 4 5 6 7 8 9


2. map


2.1 map的概念

📝map是一种关联式容器,其特性如下:

  1. map它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
  2. 在map中,键值key通常用于排序和惟一地标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair:typedef pair<const key, T> value_type;
  3. 在内部,map中的元素总是按照键值key进行比较排序的。
  4. map支持下标访问符,即在[]中放入key,就可以找到与key对应的value。
  5. map的底层是红黑树

map支持下标访问符[],体现了其映射的特点,即一个key值映射一个value,二者紧密关联。


2.2 map的使用

包含头文件:#include <map>

1️⃣map的模板参数
【C++】map与set容器——红黑树底层封装

2️⃣map的接口使用

📃map的文档介绍

map的其他接口与set类似,不再过多介绍,此处重点介绍 map::operator[],即它的下标访问符重载函数。

map::operator[]不仅能够找到key对应的value,还有插入的功能,因此平时在使用map容器时,会频繁用到它。

【C++】map与set容器——红黑树底层封装

观察operator[]的接口可以看到,参数是一个键值,返回值是键值对应的实值(后面统称为value值)。

  • 若map容器中键值为k的元素已经存在,则插入元素不会发生,直接返回键值k对应的value值。
  • 若map容器中键值为k的元素不存在时,则会发生一个插入,插入一个键值为k的元素,对应value值为默认值(即value类型调用默认构造)。

A call to this function is equivalent to(该函数调用等价于):

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

🔎为了解operator[]的详细实现机制,还需了解map::insert()的实现

【C++】map与set容器——红黑树底层封装
可见 operator[]调用了insert的单元素插入版本。

🔎map::insert()的机制是,向map容器插入一个元素:

  • 若该元素已经存在(键值相同),则插入失败,并返回一个pair,pair.first是指向已存在元素结点的迭代器,pair.second是false;
  • 若该元素不存在,则进行插入操作,并返回一个pair,pair.first是指向新元素结点的迭代器,pair.second是true;

💭由此便可以解释operator[]的实现机制,它调用insert,利用insert的返回值,取得键值对应元素节点的迭代器,再通过迭代器取得键值对应的value值,达成了通过key映射value的目的。

⭕map的插入通常有三种写法

void test_map()
{
	map<int, int> m;

	// 1.构造pair的匿名对象传给m.insert()
	m.insert(pair<int, int>(1, 1));
	m.insert(pair<int, int>(2, 2));

	// 2.利用make_pair函数构造键值对
	m.insert(make_pair(3, 3));
	m.insert(make_pair(4, 4));

	// 3.方括号(比较简洁)
	m[5] = 5;
	m[6] = 6;
}

⭕利用map可以做一些统计工作,例如:统计人名出现的次数

void toCountName()
{
	string names[] = { "张三","张三","李四","王五","李四","王五" ,"张三" ,"张三" ,"李四" ,"赵六" };

	// 键值为人名, value值为人名出现次数
	map<string, int> countName;

	for (auto& name : names)
	{
		// 人名存在,次数加1;人名不存在,先插入再次数加1
		countName[name]++;
	}

	// 输出人名及其出现次数
	for (auto& kv : countName)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
}

【C++】map与set容器——红黑树底层封装


3. multiset和multimap

🔎multiset和set大致相同,唯一的不同点就是multiset中的键值允许相同,即其元素是可以重复的。

void test_multiset()
{
	int a[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };

	// 迭代器范围,构造multiset
	multiset<int> ms(a, a + sizeof(a) / sizeof(a[0]));

	for (auto k : ms)
	{
		cout << k << " ";
	}
}

⭕运行结果,可发现有相同的元素,可见multiset的作用之一是对序列排序而不去重

0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9

🔎同理,multimap和map也大致相同,唯一的不同点就是multimap中的键值允许重复。

而在STL标准库中,multimap中并没有重载operator[]操作,因为multimap一个键值key可能对应多个value值,无法达成一对一映射的效果,因此重载operator[]并无意义。

💭至于相同的元素节点应该如何插入,STL标准库源代码规定,multiset和multimap插入时使用rb_tree的insert_equal()函数,其中相同元素的节点插到它的右边。但其实插左插右并没有区别,经过旋转后结构相同。



4. 红黑树模拟实现map和set

💭重点来了!!STL已经帮我们造好了map和set两个轮子,而我们学习模拟实现不是为了造出更好的轮子,而是学会更好的使用轮子,熟悉其底层实现。

由于map和set所开放的各种操作接口,红黑树也都提供了,所以它们的操作都只是转调用了红黑树的操作行为而已,在红黑树的接口上略作修改,突出其二者各自的特性。


4.1 改造红黑树

💬RBTree的模板参数应该改成如下这样,才能适应map和set的配接。

//RBTree的节点
template <class V>
struct RBTreeNode
{
	typedef RBTreeNode<V> Self;

	V _v;// 数据域
	Self* _left;
	Self* _right;
	Self* _parent;
	COLOR _col;

	RBTreeNode(const V& v)
		:_v(v)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

//RBTree
template <class K, class V, class KeyOfValue>
class RBTree
{
	typedef RBTreeNode<V> node;
public:
	//...
private:
	node* _root;
}
  • K:key,键值类型
  • V:value,实值类型。若是map,则为pair<k,v>;若是set,则为k。
  • KeyOfValue:仿函数,用于取出存储在value中的key值。因为map和set有不同的取key方式,所以需要有这样一个仿函数。

map和set的大致框架:

// set
template <class K>
class set
{
	// set的KeyofValue仿函数,取key == 取value
	struct setKov
	{
		const K& operator()(const K& v)
		{
			return v;
		}
	};

public:
	//...
	
private:
	// 对于set来说,键值类型等同于数据类型
	// 故键值类型为K,实值类型也为K
	RBTree<K, K, setKov> _t;
};
// map
template <class K, class V>
class map
{
	// map的KeyofValue仿函数,value是一个键值对,取key == 取value的first
	struct mapKov
	{
		const K& operator()(const pair<const K, V>& kv)
		{
			return kv.first;
		}
	};
	
public:
	//...
	
private:
	// 键值类型为K,实值类型为pair<const K, V>(key值不可修改)
	RBTree<K, pair<const K, V>, mapKov> _t;
};

4.2 红黑树的迭代器

4.2.1 STL中的rb_tree结构与其迭代器设计

💭迭代器是STL六大组件之一,对于容器的实现非常重要。因此,想要用红黑树封装map和set,红黑树必须提供迭代器。下面来看如何设计红黑树的迭代器(iterator

红黑树是关联式容器,并没有所谓的头或尾,只有最大元素节点和最小元素节点(以键值大小为准),因此红黑树不能像vector、list一样将begin迭代器定义在序列头,end在序列尾。那么它的结构是如何设计的?我们先来看看标准库的实现方法。

【C++】map与set容器——红黑树底层封装

💡STL标准库中,为了简化处理,特别为根节点再设计了一个父节点,名为header。header的左子节点指向最小节点,右子节点指向最大节点。以指向header的左子节点的迭代器为begin(),header为end()。

4.2.2 模拟实现红黑树的迭代器

为了方便实现,我们不完全仿照标准库的实现方法。我们将begin()定义为指向最小节点的迭代器,将end()定义为指向空的迭代器。

  1. 红黑树迭代器的定义:
//RBTree的节点
template <class V>
struct RBTreeNode
{
	typedef RBTreeNode<V> Self;
	
	V _v;
	Self* _left;
	Self* _right;
	Self* _parent;
	COLOR _col;

	RBTreeNode(const V& v)
		:_v(v)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _col(RED)
	{}
};

// RBTree的迭代器
// 模板参数设置引用类型Ref和指针类型Ptr, 便于实现const迭代器
template <class V, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeIterator<V, Ref, Ptr> Self;
	typedef RBTreeNode<V> node;
	
	// 构造函数,用指针构造迭代器
	RBTreeIterator(node* pNode)
		:_pNode(pNode)
	{}

	// 常见的迭代器接口,类似list的迭代器
	
	Ref operator*()
	{
		return _pNode->_v;
	}

	// it->first ⇒ it->->first ⇒ (&_pNode->_v)->first
	Ptr operator->()
	{
		return &_pNode->_v;
	}

	bool operator!=(const Self& it) const
	{
		return _pNode != it._pNode;
	}

	bool operator==(const Self& it) const
	{
		return _pNode == it._pNode;
	}

	// 指向红黑树节点的指针
	node* _pNode;
};
  1. 红黑树迭代器的自增和自减
  • 自增 (++)
    红黑树迭代,走的是中序遍历的顺序,因此迭代器的自增要寻找中序遍历顺序(即key值大小顺序)的下一个。以下面这棵红黑树为例。

【C++】map与set容器——红黑树底层封装

二叉搜索树中,比当前元素大的都在其右边,而红黑树的begin又指向最小(最左)节点,因此其迭代器自增要向右走。由于中序顺序为:左->根->右,因此从左向右走的途径有:左子树到根,根到右子树两种。也就是说,若当前节点想要向右走,则有可能是右子树的父节点,也可能是某个节点的左子树。那么红黑树的迭代器自增可分为两种情况:

  1. 右子树存在,则当前节点为其右子树的父节点,下一个节点为右子树的最小节点。
  2. 右子树不存在,则当前节点存在于某个节点的左子树,下一个节点应是向上找到第一个以当前子树为左子树的节点。

情况1当前节点右子树存在(根->右)
【C++】map与set容器——红黑树底层封装

情况2当前节点右子树不存在(左->根)
【C++】map与set容器——红黑树底层封装

  • 自减 (--)
    道理和自增类似,可以理解为自增的逆过程。自减要向左走,因此根据中序遍历顺序有两个途径:根->左,右->根。也就是说,若当前节点想要向左走,则有可能是左子树的父节点,也可能是某个节点的右子树。那么红黑树的迭代器自减可分为两种情况:
  1. 左子树存在,则当前节点为左子树的父节点,下一个节点为左子树的最大(最右)节点。
  2. 左子树不存在,则当前节点存在于某个节点的右子树,下一个节点应为向上找到第一个以当前子树为右子树的节点。

情况1:当前节点的左子树存在(根->左)
【C++】map与set容器——红黑树底层封装

情况2: 当前节点的左子树不存在
【C++】map与set容器——红黑树底层封装

最终,加上自增自减的接口,RBTreeIterator的代码如下:

template <class V, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeIterator<V, Ref, Ptr> Self;
	typedef RBTreeNode<V> node;
	
	RBTreeIterator(node* pNode)
		:_pNode(pNode)
	{}

	Ref operator*()
	{
		return _pNode->_v;
	}

	Ptr operator->()
	{
		return &_pNode->_v;
	}

	// 自增,前置++,返回自增后的迭代器
	Self& operator++()
	{
		if (_pNode == nullptr)
		{
			assert(false);
		}

		if (_pNode->_right) // 根 -> 右
		{
			// 找到右子树的最左节点
			node* minRight = _pNode->_right;

			while (minRight->_left)
			{
				minRight = minRight->_left;
			}

			_pNode = minRight;
		}
		else // 左 -> 根
		{
			node* cur = _pNode;
			node* parent = cur->_parent;

			while (parent && parent->_left != cur)
			{
				cur = parent;
				parent = parent->_parent;
			}

			_pNode = parent;
		}
		return *this;
	}

	// 自减,前置--,返回自减后的迭代器
	Self& operator--()
	{
		if (_pNode == nullptr)
		{
			assert(false);
		}

		if (_pNode->_left) // 找到左边最大节点
		{
			node* maxLeft = _pNode->_left;
			while (maxLeft->_right)
			{
				maxLeft = maxLeft->_right;
			}
			_pNode = maxLeft;
		}

		else // 找到孩子是右的根节点
		{
			node* cur = _pNode;
			node* parent = _pNode->_parent;
			while (parent && parent->_right != cur)
			{
				cur = parent;
				parent = parent->_parent;
			}

			if (parent)
				_pNode = parent;
			else
				assert(false);			
		}

		return *this;
	}

	bool operator!=(const Self& it) const
	{
		return _pNode != it._pNode;
	}

	bool operator==(const Self& it) const
	{
		return _pNode == it._pNode;
	}

	node* _pNode;
};
  1. 在RBTree中对迭代器进行定义,并实现begin()end()
template <class K, class V, class KeyOfValue>
class RBTree
{
	typedef RBTreeNode<V> node;

public:

	typedef RBTreeIterator<V, V&, V*> iterator; // 普通迭代器
	typedef RBTreeIterator<V, const V&, const V*> const_iterator;// const迭代器

public:
	//构造函数
	RBTree()
		:_root(nullptr)
	{}
	
	// begin是整棵树的最小节点,即从根节点开始的最左节点
	iterator begin()
	{
		// 最左节点
		node* left = _root;
		
		//_root有可能为空
		while (left && left->_left)
		{
			left = left->_left;
		}

		return iterator(left);
	}

	// end规定为空迭代器
	iterator end()
	{
		return iterator(nullptr);
	}

	//const类型RBTree对象调用时,需要返回const迭代器
	const_iterator begin() const
	{
		// 最左节点
		node* left = _root;

		//_root有可能为空
		while (left && left->_left)
		{
			left = left->_left;
		}

		return const_iterator(left);
	}

	const_iterator end() const
	{
		return const_iterator(nullptr);
	}

	// insert的返回值要修改成pair<iterator, bool>,以便map重载[]时使用
	pair<iterator, bool> insert(const V& v)
	{
		//具体代码太长,而且与之前实现的RBTree::insert大差不差,只有一点点区别
		//后面再一并列出,这里主要看的是有关迭代器的代码 
		//...
	}
private:
	node* _root;
};


4.3 map和set的迭代器

💭OK,底层的红黑树提供了迭代器,接下来就要给map和set提供迭代器了。map和set的迭代器各有特点。

  • set的迭代器:无法通过迭代器修改元素(因为set的元素就是键值,不能被修改)。因此,在STL中,set的普通迭代器和const迭代器都是const类型,保证了无法通过迭代器修改key值。
  • map的迭代器:map的迭代器有普通迭代器和const迭代器两种,普通迭代器可以修改指向的元素的value值,const迭代器则无法修改。

💬综上所述,在map和set中定义迭代器如下:

//set
template <class K>
class set
{
	struct setKov
	{
		const K& operator()(const K& v)
		{
			return v;
		}
	};
public:
	// 迭代器的定义
	// 同一个类型
	typedef typename RBTree<K, K, setKov>::const_iterator iterator;
	typedef typename RBTree<K, K, setKov>::const_iterator const_iterator;

public:
	// const对象和非const对象(权限缩小)都能调用,且返回的都是const类型的迭代器
	iterator begin() const
	{
		return _t.begin();
	}

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

private:
	RBTree<K, K, setKov> _t;
};
// map
template <class K, class V>
class map
{
	struct mapKov
	{
		const K& operator()(const pair<const K, V>& kv)
		{
			return kv.first;
		}
	};
public:
	// 迭代器的定义
	typedef typename RBTree<K, pair<const K, V>, mapKov>::iterator iterator;// 普通迭代器,可修改value值
	typedef typename RBTree<K, pair<const K, V>, mapKov>::const_iterator const_iterator;// const迭代器,不可修改value值

public:
	// 普通对象调用返回普通迭代器,const对象调用返回const迭代器
	iterator begin()
	{
		return _t.begin();
	}

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

	const_iterator begin() const
	{
		return _t.begin();
	}

	const_iterator end() const
	{
		return _t.end();
	}
private:
	RBTree<K, pair<const K, V>, mapKov> _t;
};

4.4 map和set的插入操作

map的插入操作,很简单,直接复用红黑树的插入即可。

template <class K,class V>
class map
{
//...
		pair<iterator, bool> insert(const pair<const K, V>& kv)
		{
			return _t.insert(kv);
		}

		//重载方括号
		V& operator[](const K key)
		{
			pair<iterator, bool> p = _t.insert(make_pair(key, V()));
			
			return (p.first)->second;
		}
//...
}

而set的插入操作就需要注意一些小小的细节,如果直接复用红黑树的插入。

template <class K>
class set
{
//...
	pair<iterator, bool> insert(const K& k)
	{
		return _t.insert(v);//error
	}
//...
}

这里面,_t.insert(v)返回的pair中的迭代器是普通迭代器,而set::insert返回值接收时,pair中的迭代器是const迭代器。这里会出现类型不匹配的问题。因此我们需要一个将普通迭代器转化为const迭代器的 “中转站”。

⭕STL中是这样设计的,在RBTreeIterator定义一个iterator类型,它始终是普通迭代器类型,无论Self是普通迭代器还是const迭代器。借此,可以写一个函数RBTreeIterator(const iterator& it),对于普通迭代器来说,它只是一个拷贝构造;而对于const迭代器来说,它是一个能够用普通迭代器构造const迭代器的构造函数。这样一来便实现了将普通迭代器转化const迭代器的目的。

template <class V, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeIterator<V, Ref, Ptr> Self;
	typedef RBTreeIterator<V, V&, V*> iterator;// 固定的普通迭代器类型
	typedef RBTreeNode<V> node;
	
	RBTreeIterator(node* pNode)
		:_pNode(pNode)
	{}

	// 拷贝构造编译器会默认实现
	//RBTreeIterator(const Self& it)
	//	:_pNode(it._pNode)
	//{}

	// 普通迭代器->const迭代器

	// 对于普通迭代器:拷贝构造
	// 对于const迭代器:用普通迭代器构造const迭代器的构造函数
	RBTreeIterator(const iterator& it)
		:_pNode(it._pNode)
	{}
	//...
}

💬set的插入操作正确示例:

template <class K>
class set
{
//...
	// 返回值的iterator是const_iterator,不能直接接收_t.insert的返回值,中间要有一层
	// 普通迭代器转化为const迭代器
	pair<iterator, bool> insert(const K& v)
	{
		auto pRet = _t.insert(v); // 先接受_t.insert的返回值
		iterator it = pRet.first;// 用普通迭代器构造const迭代器
		return make_pair(it, pRet.second);// 再用const迭代器构造pair,最后返回
	}
//...
}

4.5 map和set最终实现

💬 完整的map和set模拟实现代码总览:

// set

template <class K>
class set
{
	struct setKov
	{
		const K& operator()(const K& v)
		{
			return v;
		}
	};

public:

	typedef typename RBTree<K, K, setKov>::const_iterator iterator;
	typedef typename RBTree<K, K, setKov>::const_iterator const_iterator;

public:
	pair<iterator, bool> insert(const K& v)
	{
		auto pRet = _t.insert(v);
		iterator it = pRet.first;
		return make_pair(it, pRet.second);
	}

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

	iterator end() const
	{
		return _t.end();
	}
	
private:
	RBTree<K, K, setKov> _t;
};
// map

template <class K, class V>
class map
{
	struct mapKov
	{
		const K& operator()(const pair<const K, V>& kv)
		{
			return kv.first;
		}
	};

public:

	typedef typename RBTree<K, pair<const K, V>, mapKov>::iterator iterator;
	typedef typename RBTree<K, pair<const K, V>, mapKov>::const_iterator const_iterator;

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

	V& operator[](const K key)
	{
		pair<iterator, bool> p = _t.insert(make_pair(key, V()));

		return (p.first)->second;
	}

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

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

	const_iterator begin() const
	{
		return _t.begin();
	}

	const_iterator end() const
	{
		return _t.end();
	}

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

完整的红黑树、map、set代码及其测试代码已经存放在我的gitee上了,有需要的读者可以自取噢~
📃map和set博客的代码文章来源地址https://www.toymoban.com/news/detail-410229.html


  • 完结撒花🎊写作不易,如果觉得本文对你有帮助,不妨点点关注支持一下博主!

到了这里,关于【C++】map与set容器——红黑树底层封装的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • C++ 改造红黑树,封装map和set

    set是Key模型的红黑树 map是Key-Value模型的红黑树 我们之前已经把红黑树实现并测试过了 这是Key-Value模型的红黑树 RBTree.h 要想用红黑树来封装set和map,我们首先想到的是在搞一份Key模型的红黑树, 然后用Key模型红黑树来封装set,Key-Value模型红黑树封装map 但是STL库中set和map的设计却

    2024年03月17日
    浏览(50)
  • C++【一棵红黑树封装 set 和 map】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎃操作环境: Visual Studio 2019 版本 16.11.17 红黑树的基本情况我们已经在上一篇文章中学习过了,本文主要研究的是红黑树的实际应用:封装实现 set 和 map ,看看如何通过一棵红黑树满足两个不同的数据结构;在正式封装之前,

    2024年02月11日
    浏览(40)
  • C++ | 红黑树以及map与set的封装

    目录 前言 一、红黑树 1、红黑树的基本概念 2、红黑树相关特性 3、红黑树结点的定义 4、红黑树的查找 5、红黑树的插入 6、二叉树的拷贝构造与析构 7、红黑树的检测 8、红黑树总结 二、map与set的封装 1、红黑树的结点 2、红黑树迭代器 3、set的封装 4、map的封装 三、源码仓库

    2024年02月14日
    浏览(37)
  • 【C++】使用红黑树进行封装map和set

    🌇个人主页:平凡的小苏 📚学习格言:命运给你一个低的起点,是想看你精彩的翻盘,而不是让你自甘堕落,脚下的路虽然难走,但我还能走,比起向阳而生,我更想尝试逆风翻盘 。 🛸 C++专栏 : C++内功修炼基地 家人们更新不易,你们的👍点赞👍和⭐关注⭐真的对我真

    2024年02月07日
    浏览(46)
  • 【C++】用红黑树迭代器封装map和set

    封装有点难 - . - 文章目录 前言 一、红黑树原先代码的修改 二、红黑树迭代器的实现 总结 因为我们要将红黑树封装让map和set使用,所以我们要在原来的基础上将红黑树代码进行修改,最主要的是修改模板参数,下面我们直接进入正题: 首先我们拿出STL中的源代码,看看大佬

    2024年02月06日
    浏览(42)
  • 【C++】用一棵红黑树同时封装出map和set

    苦厄难夺凌云志,不死终有出头日。 1. 在源码里面,对于map和set的实现,底层是用同一棵红黑树封装出来的,并不是用了两棵红黑树,一个红黑树结点存key,一个红黑树结点存key,value的键值对,这样的方式太不符合大佬的水准了,实际上在红黑树底层中用了一个模板参数Va

    2023年04月13日
    浏览(43)
  • Learning C++ No.23【红黑树封装set和map】

    北京时间:2023/5/17/22:19,不知道是以前学的不够扎实,还是很久没有学习相关知识,对有的知识可以说是遗忘了许多,以该篇博客有关知识为例,我发现我对迭代器和模板的有关知识的理解还不够透彻,不知道是对以前知识的遗忘,还是现在所学确实有难度,反正导致我很懵

    2024年02月05日
    浏览(50)
  • 【C++】STL——用一颗红黑树封装出map和set

    我们都知道set是K模型的容器,而map是KV模型的容器,但是它俩的底层都是用红黑树实现的,上篇博文中我们模拟实现了一颗红黑树,接下来将对其进行改造,继而用一颗红黑树封装出map和set。 本质上map和set其内部的主要功能都是套用了红黑树现成的接口,只是稍作改动即可

    2023年04月15日
    浏览(35)
  • AVL树,红黑树,红黑树封装map和set

    二叉搜索树虽可以缩短查找的效率,但如果 数据有序或接近有序二叉搜索树将退化为单支树 ,查找元素相当于在顺序表中搜索元素, 效率低下 。因此,咱们中国的邻居俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法: 当向二叉搜索树中插入

    2023年04月25日
    浏览(61)
  • 红黑树封装set和map(插入部分)

    之前我们实现了红黑树的插入的部分,本文主要介绍将之前实现的红黑树封装成map和set。我们是以学习的角度来封装容器,不用非要把库中容器所有功能都实现出来。我们主要目的是学习库中代码设计技巧和模板复用的思想。 我们在实现之前还是和以前一样去看看库中是怎么

    2024年02月07日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包