lower_bound

iterator lower_bound (const value_type& val);
const_iterator lower_bound (const value_type& val) const;

该函数将返回一个指向不小于val的第一个元素的迭代器

upper_bound

 iterator upper_bound (const value_type& val);
const_iterator upper_bound (const value_type& val) const;

该函数将返回一个指向大于val的第一个元素的迭代器

multiset

#include <set>
void TestSet()
{
  int array[] = { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };
 
 // 注意：multiset在底层实际存储的是<int, int>的键值对
 multiset<int> s(array, array + sizeof(array)/sizeof(array[0]));
 for (auto& e : s)
 cout << e << " ";
 cout << endl;
 return 0;
}

map

map的使用

map的迭代器

//pair<K,V>
V& operator[](const K& key)
{
	// 不管插入成功还是失败，pair中iterator始终指向key所在节点的iterator
	pair<iterator, bool> ret = insert(make_pair(key, V()));
	iterator it = ret.fisrt;
	return it->second;
}

key存在，插入失败 返回 --> pair<存在的key所在节点的迭代器，false>

key不存在，插入成功 返回 --> pair<新插入key所在节点的迭代器，true>

string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };
	map<string, int> countMap;
	for (auto& e : arr)
	{
		countMap[e]++;
		//auto it = countMap.find(e);
		//if (it != countMap.end())
		//{
		//	it->second++;
		//}
		//else
		//{
		//	//const pair<string, int>& val = { e, 1 };
		//	countMap.insert({ e, 1 });
		//}
	}

	for (auto& kv : countMap)
	{
		cout << kv.first << ":" << kv.second << endl;
	}
	cout << endl;

  map<string, string> dict;
	pair<string, string> kv1("sort", "排序");
	dict.insert(kv1);
	dict.insert(pair<string, string>("left", "左边"));
	dict.insert(make_pair("right", "右边"));
	dict.insert(make_pair("right", "xxxx"));


	// 隐式类型转换
	//pair<string, string> kv2 = { "string", "字符串" };
	dict.insert({ "string", "字符串" });


	//map<string, string>::iterator it = dict.begin();
	auto it = dict.begin();
	while (it != dict.end())
	{
		// iterator key不能修改 value可以修改
		// const_iterator key不能修改 value不能修改
		//it->first += 'x';
		it->second += 'x';

		//cout << (*it).first << ":" << (*it).second << endl;
		cout << it->first << ":" << it->second << endl;
		//cout << it.operator->()->first << ":" << it.operator->()->second << endl;
		++it;
	}
	cout << endl;

	for (auto& kv : dict)
	{
		//auto& [x, y] = kv;
		cout << kv.first << ":" << kv.second << endl;
	}
	cout << endl;

	/*for (auto& [x, y] : dict)
	{
		cout << x << ":" << y << endl;
	}
	cout << endl;*/

	//map<string, string> dict2 = { {"string", "字符串"}, {"left", "左边"},{"right", "右边"} };
	map<string, string> dict2 = { kv1, {"left", "左边"},{"right", "右边"} };

#include <string>
#include <map>
void TestMap()
{
 map<string, string> m;
 // 向map中插入元素的方式：
 // 将键值对<"peach","桃子">插入map中，用pair直接来构造键值对
 m.insert(pair<string, string>("peach", "桃子"));
 // 将键值对<"peach","桃子">插入map中，用make_pair函数来构造键值对
 m.insert(make_pair("banan", "香蕉"));
 
 // 借用operator[]向map中插入元素
    /*
 operator[]的原理是：
  用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中
  如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器
  如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器
  operator[]函数最后将insert返回值键值对中的value返回
 */
    // 将<"apple", "">插入map中，插入成功，返回value的引用，将“苹果”赋值给该引用结果，
 m["apple"] = "苹果";
 // key不存在时抛异常
//m.at("waterme") = "水蜜桃";
 cout << m.size() << endl;
 // 用迭代器去遍历map中的元素，可以得到一个按照key排序的序列
 for (auto& e : m)
 cout << e.first << "--->" << e.second << endl;
 cout << endl;
 // map中的键值对key一定是唯一的，如果key存在将插入失败
 auto ret = m.insert(make_pair("peach", "桃色"));
 if (ret.second)
 cout << "<peach, 桃色>不在map中, 已经插入" << endl;
 else
 cout << "键值为peach的元素已经存在：" << ret.first->first << "--->"
<< ret.first->second <<" 插入失败"<< endl;
 // 删除key为"apple"的元素
 m.erase("apple");
 if (1 == m.count("apple"))
 cout << "apple还在" << endl;
 else
 cout << "apple被吃了" << endl;
}

【总结】

1. map中的的元素是键值对

2. map中的key是唯一的，并且不能修改

3. 默认按照小于的方式对key进行比较

4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列

5. map的底层为平衡搜索树(红黑树)，查找效率比较高$O(log_2 N)$

6. 支持[]操作符，operator[]中实际进行插入查找。

multimap

•  multimap中的key是可以重复的。
•  multimap中的元素默认将key按照小于来比较
•  使用时与map包含的头文件相同

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
   // 先去重
        set<int> s1(nums1.begin(),nums1.end());       
        set<int> s2(nums2.begin(),nums2.end());
        
        // set排过序，依次比较，小的一定不是交集，相等的是交集
        auto it1 = s1.begin();
        auto it2 = s2.begin();
        vector<int> ret;
        while(it1 != s1.end() && it2 != s2.end())
       {
            if(*it1 < *it2)
           {
                it1++;
           }
            else if(*it2 < *it1)
           {
                it2++;
           }
            else
           {
                ret.push_back(*it1);
                it1++;
                it2++;
           }
       }
        return ret;
   }
};

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

底层结构

AVL 树

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1）

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;  // 该节点的左孩子
	AVLTreeNode<K, V>* _right; // 该节点的右孩子
	AVLTreeNode<K, V>* _parent;// 该节点的父亲
	pair<K, V> _kv;

	int _bf;  // 该节点的平衡因子

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

AVL树的插入

 1. 先按照二叉搜索树的规则将节点插入到AVL树中  

 2. 新节点插入后，AVL树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否破坏了AVL树的平衡性

   

Cur插入后，Parent的平衡因子一定需要调整

在插入之前，Parent的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：

  1. 如果Cur插入到Parent的左侧，只需给Parent的平衡因子-1即可

 2. 如果Cur插入到Parent的右侧，只需给Parent的平衡因子+1即可

此时：Parent的平衡因子可能有三种情况：0，正负1， 正负2

 1. 如果Parent的平衡因子为0，说明插入之前Parent的平衡因子为正负1，插入后被调整

成0，此时满足AVL树的性质，插入成功

 2. 如果Parent的平衡因子为正负1，说明插入前Parent的平衡因子一定为0，插入后被更

新成正负1，此时以pParent为根的树的高度增加，需要继续向上更新

 3. 如果Parent的平衡因子为正负2，则Parent的平衡因子违反平衡树的性质，需要对其进

行旋转处理

AVL树的旋转

总结：

• 当SubR的平衡因子为1时，执行左单旋
• 当SubR的平衡因子为-1时，执行右左双旋

• 当SubL的平衡因子为-1是，执行右单旋
• 当SubL的平衡因子为1时，执行左右双旋

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;

	int _bf;  // balance factor

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

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	// logN
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;

		//...
		// 更新平衡因子
		while (parent)
		{
			if (cur == parent->_left)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}

			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 (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{

				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{

				}
				
				break;
			}
			else
			{
				// 理论而言不可能出现这个情况
				assert(false);
			}
		}


		return true;
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}


	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if(subLR)
			subLR->_parent = parent;

		subL->_right = parent;

		Node* ppNode = parent->_parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}

			subL->_parent = ppNode;
		}

		parent->_bf = subL->_bf = 0;
	}

	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		subR->_left = parent;
		Node* ppNode = parent->_parent;

		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_right == parent)
			{
				ppNode->_right = subR;
			}
			else
			{
				ppNode->_left = subR;
			}
			subR->_parent = ppNode;
		}

		parent->_bf = subR->_bf = 0;
	}

	void RotateRL(Node* parent)
	{
		RotateR(parent->_right);
		RotateL(parent);
	}

private:
		void _InOrder(Node* root)
		{
			if (root == nullptr)
			{
				return;
			}

			_InOrder(root->_left);
			cout << root->_kv.first << ":" << root->_kv.second << endl;
			_InOrder(root->_right);
		}
private:
	Node* _root = nullptr;
};