目录

1、set 

1.1、了解set

1.2、set的使用

         1、set的模板参数

        2、set的构造

        3、set的迭代器

        4、set的容量    

        5、set的修改

2、map

2.1、认识map

 2.2、map的使用

        1、map的模板参数

        2、map的构造

         3、map的迭代器

         4、map的容量与元素访问

         5、map元素修改

3、multiset

3.1、认识multiset

4、multimap

4.1、认识multimap

5、底层结构

5.1、AVL树

5.1.1、AVL树概念

5.1.2、AVL树节点的定义

5.1.3、AVL的插入

5.1.4、AVL树的旋转

5.2、红黑树

5.2.1、概念

5.2.2、性质 

5.2.3、红黑树节点定义

5.2.4、红黑树的插入操作

1、set 

1.1、了解set

1.2、set的使用

         1、set的模板参数

                

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

        2、set的构造

set (const key_compare& comp = key_compare(),      const allocator_type& alloc =      allocator_type());

set (InputIterator first, InputIterator last,      const key_compare& comp = key_compare(),      const allocator_type& alloc =      allocator_type());

set (const set& x);

        3、set的迭代器

        4、set的容量    

        5、set的修改

2、map

2.1、认识map

 2.2、map的使用

        1、map的模板参数

                key: 键值对中key的类型
                T： 键值对中value的类型
                Compare: 比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下(内置类型元素)该参数不需要传递，如果无法比较时(自定义类型)，需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)
                Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器

        2、map的构造

map (const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type());

map (InputIterator first, InputIterator last,
     const key_compare& comp = key_compare(),
     const allocator_type& alloc = allocator_type());

map (const map& x);

         3、map的迭代器

         4、map的容量与元素访问

         5、map元素修改

3、multiset

3.1、认识multiset

        1. multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
        2. 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成 的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器 中进行修改(因为元素总是const的)，但可以从容器中插入或删除。
        3. 在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。
        4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
        5. multiset底层结构为二叉搜索树(红黑树)。

4、multimap

4.1、认识multimap

5、底层结构

5.1、AVL树

5.1.1、AVL树概念

template<class T>
struct AVLTreeNode
{
	AVLTreeNode(const T& data = T())
		: _pLeft(nullptr)
		, _pRight(nullptr)
		, _pParent(nullptr)
		, _data(data)
		, _bf(0)
	{}

	AVLTreeNode<T>* _pLeft;
	AVLTreeNode<T>* _pRight;
	AVLTreeNode<T>* _pParent;
	T _data;
	int _bf;   // 节点的平衡因子
};

bool Insert(const T& data)
	{
		if (_pRoot == nullptr)
		{
			_pRoot = new Node(data);
			_pRoot->_bf = 0;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _pRoot;
		while (cur)
		{
			if (cur->_data < data)
			{
				parent = cur;
				cur = cur->_pRight;
			}
			else if (cur->_data > data)
			{
				parent = cur;
				cur = cur->_pLeft;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(data);
		if (parent->_data > data)
		{
			parent->_pLeft = cur;
		}
		else
		{
			parent->_pRight = cur;
		}
		cur->_pParent = parent;

		while (parent)
		{
			if (cur == parent->_pRight)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}

			if (parent->_bf == 0)
			{
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = cur->_pParent;
				parent = parent->_pParent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				break;
			}
			else
			{
				assert(false);
			}
		}
		return true;
	}

void RotateR(Node* pParent)
	{
		Node* subL = pParent->_pLeft;
		Node* subLR = subL->_pRight;

		pParent->_pLeft = subLR;
		if (subLR)
		{
			subLR->_pParent = pParent;
		}

		Node* ppNode = pParent->_pParent;

		subL->_pRight = pParent;
		pParent->_pParent = subL;

		if (pParent == _pRoot)
		{
			_pRoot = subL;
			_pRoot->_pParent = nullptr;
		}
		else
		{
			if (ppNode->_pLeft == pParent)
			{
				ppNode->_pLeft = subL;
			}
			else
			{
				ppNode->_pRight = subL;
			}
			subL->_pParent = ppNode;
		}
		subL->_bf = pParent->_bf = 0;
	}

void RotateL(Node* pParent)
	{
		Node* subR = pParent->_pRight;//父节点的右孩子
		Node* subRL = subR->_pLeft;//subR的左孩子

		pParent->_pRight = subRL;
		if (subRL)//若subRL不为空，将subRL的父亲改成pParent
		{
			subRL->_pParent = pParent;
		}

		Node* ppNode = pParent->_pParent;//记录父节点的父节点
		
		subR->_pLeft = pParent;//将pParent设为subR的左孩子
		pParent->_pParent = subR;//将pParent的父节点设为subR

		if (pParent == _pRoot)//如果是根节点
		{
			_pRoot = subR;
			_pRoot->_pParent = nullptr;
		}
		else
		{
			if (pParent == ppNode->_pLeft)
			{
				ppNode->_pLeft = subR;
			}
			else
			{
				ppNode->_pRight = subR;
			}
			subR->_pParent = ppNode;
		}
		pParent->_bf = 0;
		subR->_bf = 0;
	}

	void RotateLR(Node* pParent)
	{
		Node* subL = pParent->_pLeft;
		Node* subLR = subL->_pRight;
		int bf = subLR->_bf;

		RotateL(pParent->_pLeft);
		RotateR(pParent);

		if (bf == 0)
		{
			pParent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			pParent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			pParent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

void RotateRL(Node* pParent)
	{
		Node* subR = pParent->_pRight;
		Node* subRL = subR->_pLeft;
		int bf = subRL->_bf;

		RotateR(pParent->_pRight);
		RotateL(pParent);

		if (bf == 0)
		{	
			subRL->_bf = 0;
			pParent->_bf = 0;
			subR->_bf = 0;
			
		}
		else if (bf == -1)
		{	subRL->_bf = 0;
			pParent->_bf = 0;
			subR->_bf = 1;
			
		}
		else if (bf == 1)
		{	subRL->_bf = 0;
			pParent->_bf = -1;
			subR->_bf = 0;
			
		}
		else
		{
			assert(false);
		}
	}

// 节点的颜色
enum Color
{
    RED, 
    BLACK
};
// 红黑树节点的定义
template<class ValueType>
struct RBTreeNode
{
     RBTreeNode(const ValueType& data = ValueType()，Color color = RED)
     : _pLeft(nullptr)
     , _pRight(nullptr)
     , _pParent(nullptr)
     , _data(data)
     , _color(color)
     {}
     RBTreeNode<ValueType>* _pLeft;   // 节点的左孩子
     RBTreeNode<ValueType>* _pRight;  // 节点的右孩子
     RBTreeNode<ValueType>* _pParent; // 节点的双亲(红黑树需要旋转，为了实现简单给出该字段)
     ValueType _data;            // 节点的值域
     Color _color;               // 节点的颜色
};

                 情况三: cur为红，p为红，g为黑，u不存在/u存在且为黑    p为g的左孩子，cur为p的右孩子，则针对p做左单旋转；相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转，则转换成了情况2

pair<iterator, bool> Insert(const T& data)
	{
		Node*& pRoot = GetRoot();
		if (pRoot == nullptr)
		{
			pRoot = new Node(data);
			pRoot->_parent = _pHead;
			pRoot->_color = BLACK;
			_size = 1;
			return make_pair((iterator)pRoot, true);
		}
		else
		{
			KeyOfValue Kof;
			Node* cur = pRoot;
			Node* parent = nullptr;
			while (cur)
			{
				if (Kof(cur->_data) > Kof(data))
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (Kof(cur->_data) < Kof(data))
				{
					parent = cur;
					cur = cur->_right;
				}
				else
				{
					return make_pair((iterator)cur, false);
				}
			}

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

			while (parent != _pHead && parent->_color == RED)
			{
				Node* grandfater = parent->_parent;
				assert(grandfater);
				if (grandfater->_left == parent)
				{
					Node* uncle = grandfater->_right;
					if (uncle && uncle->_color == RED)
					{
						parent->_color = uncle->_color = BLACK;
						grandfater->_color = RED;

						cur = grandfater;
						parent = cur->_parent;
					}
					else
					{
						if (cur == parent->_left)
						{
							//    g
							//   p
							//  c
							RotateR(grandfater);
							parent->_color = BLACK;
							grandfater->_color = RED;
						}
						else
						{
							//    g
							//   p
							//    c
							RotateL(parent);
							RotateR(grandfater);

							cur->_color = BLACK;
							grandfater->_color = RED;
						}
						break;
					}
				}
				else
				{
					Node* uncle = grandfater->_left;
					if (uncle && uncle->_color == RED)
					{
						parent->_color = uncle->_color = BLACK;
						grandfater->_color = RED;

						cur = grandfater;
						parent = cur->_parent;
					}
					else
					{
						if (cur == parent->_right)
						{
							//    g
							//     p
							//      c
							RotateL(grandfater);
							parent->_color = BLACK;
							grandfater->_color = RED;
						}
						else
						{
							//    g
							//     p
							//    c
							RotateR(parent);
							RotateL(grandfater);

							cur->_color = BLACK;
							grandfater->_color = RED;
						}
						break;
					}
				}
			}
		}
		_size++;
		pRoot->_color = BLACK;
		return true;
	}