文章目录

• 1. 关联式容器
• 2. set
• • 2.1 set的介绍
  • 2.2 set的使用
  • 2.3 multiset
• 3. map
• • 3.1 map的介绍
  • 3.2 map的使用
  • 3.3 multimap
• 4. 相关题目
• • 1. 两个数组的交集
  • 2. 前K个高频单词
  • 3. 复杂链表的复制

1. 关联式容器

1. 什么是关联式容器

我们已经接触过STL中的部分容器，比如：vector、list、deque、priority_queue等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高。

2. 树形结构的关联式容器

根据应用场景的不同，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中存储的是真正的键值对，set中只放value，但在底层实际存放的是由构成的键值对（因为它们底层都是用红黑树作为数据结构）。

2.2 set的使用

T: set中存放元素的类型，实际在底层存储的键值对。
Compare：set中元素默认按照小于来比较
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

1. set的构造

2. set的迭代器

set的迭代器也很多，我们最常用的式begin()和end()
不同于其它容器的迭代器，set的迭代器返回的是二叉搜索树中序遍历时的第一个元素，因此使用迭代器遍历后的结果是有序的

3. set的其它操作

• insert

在set中插入元素x，实际插入的是构成的键值对，
使用第一种方式插入时，如果插入成功，返回<该元素在set中的位置，true>；如果插入失败，说明x在set中已经存在，返回

迭代区间插入

• 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  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 intersection(vector& nums1, vector& nums2) {     set s1, s2;     for (auto& e : nums1)         s1.insert(e);     for (auto& e : nums2)         s2.insert(e);     vector ret;     set::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& x,const pair& y)         {             //先按照单词出现的次数比较             //次数相等，字典序小的在前面             return x.second > y.second || (x.second == y.second && x.first < y.first);         }     };      vector topKFrequent(vector& words, int k) {         map mTree;         for(auto& e : words)             mTree[e]++;//使用map重载的[ ]，统计次数                  //放进数组中         vector> arr(mTree.begin(),mTree.end());         //传递一个仿函数，排序         sort(arr.begin(),arr.end(),Compare());          vector 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 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; }