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树的插入

 

上一篇：淘宝商品评论数据获取：从API调用到应用实践

下一篇：Elasticsearch：开启高效搜索与分析的新篇章