（unordered）map和set封装（底层红黑树）

map和set封装

设计问题（知其所以然）

为什么要对iterator进行封装？

是否需要分装和指向的类型有关：

• 如果迭代器指向的是内置类型，不需要分装
• 如果是自定义类型，则需要重载一系列操作符，因此需要分装

在STL的实现中，string的实现就没有用到封装，是因为string的迭代器为char* ，进行*（解引用），++等操作时不需要重载

为什么要引入Self Ref Ptr这些模板参数？

这里和list的底层实现道理一致

因为迭代器有const 和non_const两种，而不同的迭代器种类要有不同的返回值类型，也就是说如果我们不传入模板参数，很多函数要写两次（返回值类型不同），造成代码的冗余

template
	class list
	{
		.......

	public:
		typedef list_iterator iterator;
		typedef list_iterator const_iterator;

		typedef Reverse_Iterator reverse_iterator;
		typedef Reverse_Iterator const_reverse_iterator;
    }
		
1
2
3
4
5
6
7
8
9
10
11
12
13

下面的注释可以帮助理解如何解决冗余：

	template
	class list_iterator
	{
		typedef listNode Node;
	public:
		Node* _pnode;
        
		list_iterator(Node* pnode)
			:_pnode(pnode)
		{}

        //const T& 或 T& 
		Ref operator*()
		{
			return _pnode->_val;//->结构体指针访问结构体成员变量的方式
		}
         //const T* 或 T*
		Ptr operator->()
		{
			return &(_pnode->_val);
		}
		
		typedef list_iterator Self;
        //iterator 或 const_iterator
		Self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}
        
        .......
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

为什么是试图从non_const转变为const，而不是const转为non_const

	class Set
	{
	private:
		struct setKeyofT{...}
		RBTree _t;

	public:
		//底层是对树的封装
		typedef typename RBTree::const_iterator iterator;//两个迭代器都是const迭代器
		typedef typename RBTree::const_iterator const_iterator;
		
		iterator begin()
		{
			return _t.begin();
		}
		const_iterator begin()const
		{
			return _t.begin();
		}

		iterator end()
		{
			return _t.end();//此行报错
		}
		const_iterator end()const
		{
			return _t.end();
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

	s.Insert(3);
	s.Insert(1);
	s.Insert(6);
	s.Insert(5);
	s.Insert(9);
	s.Insert(4);

	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

报错原因，无法转变树中的迭代器，需要自己实现转变：

为什么是试图从non_const转变为const：

• 此时调用的是第一个begin

• 返回的是树的iterator，但是set的iterator相当于树的const_iterator,类型不匹配而且不能自动发生转换，因此报错

如何解决

set在STL中源码是这样解决的：

这样写非常的巧妙，大佬不愧是大佬:

这样传进来的_t就有const修饰，调用的是RBTree中const_iterator begin()，const可以满足和set中（const）iterator的配对，

解决了上述转化的问题

此时只需要写一个就可以满足要求，多了是重复的，会报错

		typedef typename RBTree::const_iterator iterator;
		typedef typename RBTree::const_iterator const_iterator;
		
		iterator begin()const
		{
			return _t.begin();
		}

		/*const_iterator begin()const
		{
			return _t.begin();
		}*/
1
2
3
4
5
6
7
8
9
10
11
12

为什么说能加const把const加上

因为权限可以缩小，普通对象是可以调用的，但如果不加const，const对象就无法调用

增加构造函数解决set调用红黑树实现插入时iterator的转换

template
class Set
{
	
	RBTree _t;
public:
	typedef typename RBTree::const_iterator iterator;
	typedef typename RBTree::const_iterator const_iterator;
		
	pair Insert(const K& k)
	{
		return _t.Insert(k);
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

map可以正常调用而set不行，因为_t调用的红黑树的insert返回的是普通itereator,但是set的iterator实际上是const_iterator，所以报错。要想办法转换

解决方法

构造一个转换的函数拿iterator构造成const_iterator

大佬还是大佬，再来膜拜一下大佬的思路

struct _TreeIterator
{
	.....
        
	typedef _TreeIterator Self;//迭代器本身，受Ref和Ptr影响
    
	typedef _TreeIterator iterator;//始终是普通迭代器，在 _TreeIterator中封装了一个普通迭代器(的类型)
    
	_TreeIterator(const iterator& it)//支持传入普通迭代器调用构造函数
		:_node(it._node)
	{}
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 当这个迭代器被实例化为const迭代器，这是一个构造函数
• 当实例化为普通迭代器，这是一个拷贝构造
  

unordered_map/set封装

为什么迭代器中指向哈希表的指针要加const？为什么可以加const？

为什么指针要加const

HashTable中，const对象调用迭代器，传入的指针是const类型，会造成权限的放大

const_iterator end()const
{
	return const_iterator(nullptr, this);//因为是const,所以this是const
}
1
2
3
4

为什么可以加const，不会影响对哈希表的增加删除吗？

迭代器里不用修改哈希表，哈希表的修改是基于Node改变，Node不为const

老生常谈的问题

为什么要在迭代器中增加不受传值影响的iterator迭代器类型（不是对象）

因为set的两个迭代器都是const迭代器，但返回的时候是哈希表中的普通迭代器，因为是自定义类型，需要添加构造函数实现转换（同map和set）

两个由const引发的bug

• 图一：加上const以后，323行调用的end函数为const对象调用的，返回对象为cosnt_iterator，const_iterator不能转换为iterator
  

• 图二：多加了一个const，在初始化的时候出现错误（const const T*）