供应邯郸做网站市场监督管理局职责范围

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所在节点的iteratorpair<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;elsecout << "键值为peach的元素已经存在：" << ret.first->first << "--->"
<< ret.first->second <<" 插入失败"<< endl;// 删除key为"apple"的元素m.erase("apple");if (1 == m.count("apple"))cout << "apple还在" << endl;elsecout << "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 factorAVLTreeNode(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:// logNbool 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;
};