map和set
1. 关联式容器
vector、list、deque这些容器都是序列式容器。因为底层是线性序列的数据结构，里面存储的是元素本身。那么什么是关联式容器？
关联式容器也是用来存储数据的，但是里面存储的是<key, value>结构的键值对。在进行数据检索式比序列式容器效率更高
2. 键值对
用来表示有一一对应的一种结构，这个结构当中一般有两个成员key和value。key代表的是键值，value表示与key对应的信息。
比如我们现在建立一个英汉互译的字典。字典当中必然有英文单词对应的中文含义。并且英文单词与中文含义是一一对应的关系
3. 树形结构的关联式容器
树形结构与哈希结构。树型结构的关联容器主要有四种：map、set、mulitmap、multiset。这四种容器的共同特点是：使用平衡搜索树（即红黑树）作为底层，容器中的元素是一个有序的序列。
3.1 set
- set是按照一定次序存储元素的容器
- 在set中，元素的value也标识它（value就是key），并且每一个value必须是唯一的。set中的元素不能在容器中修改。但是可以从容器中插入和删除它们
- 在内部，set中的元素总是按照内部比较对象（类型比较）所指示的特定严格排序准则进行排序
注意：
- set插入元素的时候，只需要插入value，不需要构造键值对
- set中的元素不可以重复（因此可以使用set进行去重）
- 使用set的迭代器遍历元素，可以得到一个有序序列
- set中的元素默认是按照小于来比较的
3.2 set的模板参数列表
template < class T, // set::key_type/value_type
class Compare = less<T>, // set::key_compare/value_compare
class Alloc = allocator<T> // set::allocator_type > class set;
T：set当中存放元素的类型，实际在底层存储<value, value> 键值对
Compare：set中元素按照小于来比较
Alloc：set当中元素空间的管理方式，使用STL提供的空间适配器来管理
3.3 set的构造
从上到下依次为：
- 构造空的set
- 用【first，last）空间内的元素构造set
- set的拷贝构造
剩下的操作文档当中，都有显示，使用的时候查看即可
3.4 set的使用举例
#include <iostream> #include <set> using namespace std; int main() { int arr[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 }; set<int> s(arr, arr + (sizeof(arr) / sizeof(arr[0]))); cout << s.size() << endl; for (auto& e : s) { cout << e << " "; } cout << endl; for (auto i = s.rbegin(); i != s.rend(); i++) { cout << *i << " "; } cout << endl; cout << s.count(3) << endl; }
4. map
- 在map当中，键值key通常用于排序和唯一标识元素，值value当中存储与此值key 关联的内容。键值key和value类型可能不同，并且在map的内部，key与value通过成员类型
value_type绑定在一起，别名为pair - 在内部，map中的元素总是按照键值key进行比较排序的
- map允许根据顺序对元素进行直接迭代（对map进行迭代时，可以得到一个有序的序列）
- map支持下标访问
4.1 map的使用
可以看文档，了解使用。
在key不在map当中时，通过operator获取会发生什么问题？
有一个与operator[]类似的操作at()都是通过key找到与key对应的value返回其引用。不同的是：operator[]用默认value与key构造键值对然后插入，返回该默认value，at()函数直接抛出异常
#include "iostream" #include "map " using namespace std; int main() { map<string, string> map; map.insert(pair<string, string>("peach", "桃子")); map.insert(make_pair("banan", "香蕉")); //operator[]的原理是： // 用<key, T()>构造一个键值对，然后调用insert()函数将该键值对插入到map中 // 如果key已经存在，插入失败，insert函数返回该key所在位置的迭代器 // 如果key不存在，插入成功，insert函数返回新插入元素所在位置的迭代器 // operator[]函数最后将insert返回值键值对中的value返回 map["apple"] = "苹果"; cout << map.size() << endl; cout << endl; for (const auto &item: map) { cout << item.first << "----->" << item.second << endl; } cout << endl; auto ret = map.insert(make_pair("peach", "桃子")); if (ret.second) { cout << "插入成功" << endl; } else { cout << "插入失败" << endl; } map.erase("peach"); if (map.count("apple") == 1) { cout << map.find("apple")->second << "已经存在" << endl; } else { cout << "不存在"; } return 0; }
5. multiset
注意：
- multiset在底层存储的是<value, value>键值对
- multiset插入接口中，只需要插入即可
- multiset当中的元素是可以重复的，当时set当中的value是唯一的
5.1 multiset的使用
#include "iostream" #include "set" using namespace std; int main() { int arr[] = {1, 2, 3, 4, 2, 1, 3, 9, 0, 2, 3, 5}; multiset<int> multiset(arr, arr + (sizeof(arr)/ sizeof(arr[0]))); for (const auto &item: multiset) { cout << item << " "; } cout << endl; return 0; }
6. multimap
注意：multimap与map唯一不同的是：map当中的key是唯一的，但是multimap当中的值是可以重复的
7. 经典题目
class Solution { class Compare { public: bool operator()(const pair<string, int>& left, const pair<string, int>& right) { return left.second > right.second; } }; public: vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> mapCount; for (const auto &item: words) { mapCount[item]++; } vector<pair<string, int>> v(mapCount.begin(), mapCount.end()); stable_sort(v.begin(), v.end(), Compare()); vector<string> ret; for (int i = 0; i < k; ++i) { // cout << v[i].first << ":" << v[i].second << endl; ret.push_back(v[i].first); } return ret; } };
注意：以上都是排序的情况下
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> t1(nums1.begin(), nums1.end()); set<int> t2(nums2.begin(), nums2.end()); auto it1 = t1.begin(); auto it2 = t2.begin(); vector<int> v; while (it1 != t1.end() && it2 != t2.end()) { if (*it1 < *it2) { it1++; } else if (*it1 > *it2) { it2++; } else { v.push_back(*it1); it1++; it2++; } } // for (const auto &item: v) { // cout << item << " "; // } return v; } };
