阅读量:0
文章目录
1. 关联式容器
- 什么是关联式容器
我们已经接触过STL中的部分容器，比如：vector、list、deque、priority_queue等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。
- 树形结构的关联式容器
根据应用场景的不同，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。
树型结构的关联式容器主要有四种：map、set、multimap、multiset。
这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。
2. set
2.1 set的介绍
- 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则(二叉搜索树的规则)进行排序。
- 在set中，使用value标识元素(value就是key，类型为T)，并且每个value必须是唯一的。所以在插入元素时，
只需要插入value即可，不需要构造键值对。 - set中的元素不能在容器中修改其值(修改后可能不满足搜索树的规则，所以元素总是const)，但是可以从容器中插入或删除它们。
set中的元素不可以重复(因此可以使用set进行去重)。- 使用set的迭代器遍历set中的元素，可以得到有序序列
- set中的
元素默认按照小于来比较 - 与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放value，但在底层实际存放的是由<value, value>构成的键值对（因为它们底层都是用红黑树作为数据结构）。
2.2 set的使用
T: set中存放元素的类型，实际在底层存储<value, value>的键值对。
Compare：set中元素默认按照小于来比较
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理
- set的构造
- set的迭代器
set的迭代器也很多，我们最常用的式begin()和end()
不同于其它容器的迭代器，set的迭代器返回的是二叉搜索树中序遍历时的第一个元素，因此使用迭代器遍历后的结果是有序的
- set的其它操作
- insert
在set中插入元素x，实际插入的是<x, x>构成的键值对，
使用第一种方式插入时，如果插入成功，返回<该元素在set中的位置，true>；如果插入失败，说明x在set中已经存在，返回<x在set中的位置，false>
迭代区间插入
- erase
- swap与clear
这两个会用即可
- find函数
该函数如果找到了val，则返回其对应位置的迭代器；找不到则返回迭代器end()。
- count函数
该函数是查找元素val的个数。在map中，一个元素的个数要么为1，要么为0。所以，它还可以充当find函数的功能(并且无需判断是否 != end() )。
- lower_bound、upper_bound与equal_range
lower_bound：返回一个迭代器，该迭代器指向容器中的第一个元素（该元素是set中大于val的最小值），该元素不被视为在 val 之前（即，它等效或之后）
upper_bound：返回一个迭代器，该迭代器指向容器中的第一个元素（该元素是set中大于val的最小值），该元素被视为在 val 之后
对于equal_range来说，它是lower_bound、upper_bound的结合体，它的返回值是一个pair，pair中的两个值就是
lower_bound、upper_bound函数的结果
2.3 multiset
multiset的使用和操作与set基本一样，multiset仅仅是允许元素重复，在插入时不会失败。
其中，由几个操作有不同：
- find函数
对于查找，既然它有重复的元素，那它找的是哪一个呢？
查找的是中序遍历时该数的第一个（好处：迭代器++即可拿到其它元素）
- count函数
count函数在这里更加有用
- erase函数
对于erase函数而言，删除val是删除哪一个呢？还是将全部val删除呢？—val全部删除
3. map
3.1 map的介绍
- map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
- 在map中，
键值key通常用于排序和唯一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value被绑定在一起，为其取别名称为pair。
在SGI-STL中，pair是这样定义的：
使用：pair< key , val > _kv;
template <class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair(): first(T1()), second(T2()) {} pair(const T1& a, const T2& b): first(a), second(b) {} }; pair是一个结构体，它存了key和value，并将二者更名为first与second。
map支持下标访问符，即在[]中放入key，就可以找到与key对应的value（谨慎使用，有坑）- map中的key是唯一的，并且不能修改，因此key用const修饰；value可以改
- 默认按照小于的方式对key进行比较， map中的元素如果用迭代器去遍历，可以得到一个有序的序列
- map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。
3.2 map的使用
map的使用与set差不多，但是map多了一个operator[ ]。
map中和set类似的功能和使用就不介绍了，大家可以自己查阅文档。
在这里，我们仅仅列举出map和set不同的地方
- insert函数
在使用单个键值对进行插入时，它要求的参数是pair。
所以，我们有以下几种方式（推荐3、4）：
对于make_pair函数，它就类似于在函数内部创建了一个pair对象，然后返回。
对于insert的返回值，其是这样规定的：对于使用pair插入的函数，它返回一个pair。、
其成员pair::first迭代器，指向新插入的元素或set中具有等效键的元素。
如果插入了新元素，则将 pair::second 元素设置为 true，如果已存在等效键，则设置为 false。
- operator[ ]
其是按照key进行查找，然后找到了返回value的引用
对于该功能的实现，等价于这句代码：
(*((this->insert(make_pair(k,mapped_type()))).first)).second pair里面存放的是key，这里的value使用默认值。
在使用该pair插入时，如果key对应元素存在，insert会返回key对应位置的迭代器；如果key对应元素不存在，则会先将key插入进map中，其value为默认值，然后返回该位置的迭代器。
根据insert返回的pair，访问pair中的first（即迭代器）。该迭代器指向新插入的元素或与插入元素key相等的位置，再对该迭代器解引用，取它的value返回。
对于operato [ ]要谨慎使用，弄清它是否会改变map的size.
- 对于已经存在的元素，它的功能相当于查找+修改
- 对于不存在的元素，它相当于插入
3.3 multimap
multimap和map的唯一不同就是：map中的key是唯一的，而multimap中key是可以重复的；
multimap没有重载operator[ ]，因为其重载没有意义（如果有多个key，返回哪一个key对应的value呢？）
4. 相关题目
1. 两个数组的交集
对于该题目，如果不使用容器去写，是比较麻烦的。需要先排序，然后使用“双指针”的思想依次比较两数组中的内容，比较的同时还需要去重
所以，在有些题目中解法要求排序+去重时，就可以使用set容器来简化我们的代码。
而且在这种求交集的题目中，有时还会让你求一下差集。
对于差集若使用set，那就需要在比较时保存小的那一个，最后将一个数组中未比较的元素再全部保存即可。
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> s1, s2; for (auto& e : nums1) s1.insert(e); for (auto& e : nums2) s2.insert(e); vector<int> ret; set<int>::iterator it1 = s1.begin(); auto it2 = s2.begin(); while (it1 != s1.end() && it2 != s2.end()) { if (*it1 < *it2) it1++; else if (*it1 > *it2) it2++; else { ret.push_back(*it1); it1++; it2++; } } return ret; } 2. 前K个高频单词
对于该题目，我们可以使用map。将单词作为key，单词出现的次数作为value；让value统计每个单词出现的次数。然后将map统计好的结果放进数组中，再次按照题目要求排序
struct Compare { bool operator() (const pair<string,int>& x,const pair<string,int>& y) { //先按照单词出现的次数比较 //次数相等，字典序小的在前面 return x.second > y.second || (x.second == y.second && x.first < y.first); } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string,int> mTree; for(auto& e : words) mTree[e]++;//使用map重载的[ ]，统计次数 //放进数组中 vector<pair<string,int>> arr(mTree.begin(),mTree.end()); //传递一个仿函数，排序 sort(arr.begin(),arr.end(),Compare()); vector<string> ret; //统计前K个 for(int i = 0; i < k; i++) { ret.push_back(arr[i].first); } return ret; } 3. 复杂链表的复制
之前我们做这个题时，是先拷贝当前节点再其后面，然后使拷贝节点的random指向原节点random的后面那个节点，最后再将拷贝的节点从原链表摘下来，组成新的链表。
在学习完map后，我们就可以这样来写：
- 使用map实现原节点和拷贝节点的映射关系（此时完成了val的拷贝与next的连接）
- 处理random指针，map中存储的是节点的指针，map中使用原节点的指针，则可找到拷贝节点
Node* copyRandomList(Node* head) { map<Node*, Node*> old_newmap; Node* copyHead = nullptr; Node* copyTail = nullptr; Node* cur = head; //复制原链表 while (cur) { if (copyTail == nullptr) copyHead = copyTail = new Node(cur->val); else { copyTail->next = new Node(cur->val); copyTail = copyTail->next; } //原链表与新链表进行映射 old_newmap.insert(make_pair(cur, copyTail)); //old_newmap[cur] = copyTail; cur = cur->next; } //处理random指针 cur = head; copyTail = copyHead; while (cur) { if (cur->random == nullptr) copyTail->random = nullptr; else { //old_newmap[Node* old]返回 所复制的新的节点的指针 copyTail->random = old_newmap[cur->random]; } cur = cur->next; copyTail = copyTail->next; } return copyHead; } 