文章目录

1. 关联式容器2. set2.1 set的介绍2.2 set的使用2.3 multiset

3. map3.1 map的介绍3.2 map的使用3.3 multimap

4. 相关题目1. 两个数组的交集2. 前K个高频单词3. 复杂链表的复制

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必须是唯一的。所以在插入元素时，<code>只需要插入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>；如果插入<code>失败，说明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中，<code>键值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中具有等效键的元素。

如果<code>插入了新元素，则将 pair::second 元素设置为 true，如果已存在等效键，则设置为 false。

operator[ ]

其是<code>按照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，那就需要在比较时保存小的那一个，最后将一个数组中未比较的元素再全部保存即可。

<code>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统计好的结果放进数组中，再次按照题目要求排序

<code>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中使用原节点的指针，则可找到拷贝节点

<code>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;

}