个人主页：敲上瘾-CSDN博客

个人专栏：游戏、数据结构、c语言基础、c++学习、算法

目录

一、序列式容器和关联式容器

二、set和multiset

1.insert

2.erase

3.find

4.count

三、map和mapmulti

1.pair

2.insert

3.find

4.operator[ ]

5.erase

6.lower_bound和upper_bound

四、习题

1.环形链表||

1.算法原理

2.代码编写

2.随机链表的复制

​编辑

1.算法原理

2.代码编写

---

一、序列式容器和关联式容器

        在正式讲解set和map之前需要先了解这个概念——序列式容器和关联式容器。比如string、vector、list、deque等这些储存结构都是序列式容器。序列式容器的特点是它们的逻辑结构都是线性的，而且数据之间都没有关联性，对一个数据的增删查并不对其他数据造成影响，也不会对这个结构造成影响。

        而关联式容器就恰好相反，它的逻辑结构是非线性的，而且数据之间的关联性非常强，对其中一个数据进行改变会对整个数据结构造成影响，比如set，setmulti，map，mapmulti，undered_set，undered_map。

        这一章的主角set和map它们是一种树形结构，它们的底层是红黑树，即⼀颗平衡⼆叉搜索树
。不过这一章主要是来讲它们的使用，对底层的结构并不做探讨。

二、set和multiset

        首先区分一下set和multiset：set中一个值只能出现一次（即同一个key只能在set里面插入一个）。multiset内允许储存多个相同的值。

set的学习网址：set - C++ Reference (cplusplus.com)

1.insert

        insert接口主要作用是来插入元素的，它支持直接插入某一个元素，也支持插入某个迭代器区间。

如下：

	set<int> st;st.insert(999);vector<int> arr = { 1,5,3,2 };st.insert(arr.begin(), arr.end());

2.erase

        erase支持删除一个值，删除一个迭代器区间或一个迭代器。

如下：

st.erase(7);//删除某个值
st.erase(st.begin());//删除最小值
st.erase(st.begin(), st.end());//删除整个区间

注意：对于set迭代器的遍历是中序遍历，所以迭代器遍历结果是有序的。 

3.find

        find的使用比较简单，传入一个值然后会返回一个该值的迭代器，不存在则返回空，就不再多讲。

4.count

        count接口是用来返回set / multiset / map / multimap中某一个数据出现的个数，也可用来查找某个数据是否存在。

三、map和mapmulti

map的学习网址：map - C++ Reference (cplusplus.com)

        map和set的区别：set一块区域只储存一个关键字（记为key），而map储存的是一个key和value，key和value是一个映射关系，通过key可以找到对应的vaule。而它们的函数接口的用法都一样就不分开讲。

        map和multimap：map中一个键值对（key和value）只能出现一次（即同一个键值对只能在map里面插入一个）。multiset内允许储存多个相同的键值对。

1.pair

 pair学习网址：pair - C++ Reference (cplusplus.com)

    pair是一种模板类型，用于存储一对值，其中这两个值可以是不同类型。它位于头文件 utility 中。使用 pair 可以非常方便地存储和操作一对相关联的数据，比如一个键（key）和一个值（value），这在许多算法和数据结构中都非常有用，如哈希表、映射（map）等。

    pair 有两个成员变量，通常称为 first 和 second，分别用来存储这一对值。这两个成员的类型可以不同，但它们都是在 pair 被声明时指定的。

pair有映射和集合的作用，标准库中的 map、multimap、unordered_map 和 unordered_multimap 等容器内部都使用 pair 来存储键值对。

2.insert

        因为map在做插入和各种处理时，key和value的关联性很强，而且如果kay和value分散开放的话会使map的迭代器无法获取到key和value的值。所以使用了pair结构，pair的作用相当于把key和value绑定在一起。

所以insert的插入方法有以下几种：

2.1.先创建一个pair变量并储入键值对，然后再利用插入map中。

map<string, string> dict;
pair<string, string> kv1("left", "左");
dict.insert(kv1);

 2.2.创建匿名pair对象插入map中

map<string, string> dict;
dict.insert(pair<string, string>("left", "左"));

2.3.使用make_pair 

map<string, string> dict;
dict.insert(make_pair("left", "左"));

make_pair这个接口的底层同样用了pair，不过它可以自动识别数据类型，减少了模板类型的填写。

2.4.c++11之后支持pair的隐式构造。

map<string, string> dict;
dict.insert({ "left", "左" });

        对于以上的几种插入，insert都会返回pair<interator, bool>，即如果插入失败，返回的就是nullptr和false，如果插入成功或该数据已经存在则返回该位置的迭代器和true。所以insert同时具备插入和查找功能。

注意在做迭代器遍历的时候，pair的first成员是key，second成员是value。

3.find

        map的查找呢是传入一个key值，然后对其查找，然后返回对应的迭代器，注意：map不支持对key进行修改，但支持对value进行修改。

4.operator[ ]

        这个运算符重载的功能比较全面，它既有查找的功能，也有修改和插入的功能。它需要传入一个key，注意只能是key，因为是要用key去查找。

如果找到则返回这个key对应的value的引用。

如果没找到则插入这个key然后返回对应的value的引用。

所以我们可以完成下面的操作：

map<string, string> dict;
dict["right"];//right不存在完成插入操作
dict["left"]="左边";//left不存在进行插入并且修改
dict["left"] = "左边，剩余的";//left存在完成查找并且修改

5.erase

        传入一个key，按中序遍历找到key并且删除所有key关键字的键值对。其他性质与set类似。

6.lower_bound和upper_bound

lower_bound 的作用：

    lower_bound 函数用于在一个有序器中查找第一个大于等于给定值的元素。它返回一个迭代器，指向该元素。如果容器中不存在大于等于给定值的元素，则返回指向容器末尾的迭代器。

upper_bound 的作用：

    upper_bound 函数用于在一个有序容器中查找第一个大于给定值的元素。它同样返回一个迭代器，指向该元素。如果容器中不存在大于给定值的元素，则返回指向容器末尾的迭代器。

    lower_bound 和 upper_bound 搭配使用可以确定一个左闭右开的迭代器区间。这个区间由 lower_bound 返回的迭代器（包含）和 upper_bound 返回的迭代器（不包含）界定。

这两个函数对于set、map、vector等等使用方法都是相同的。

四、习题

1.环形链表||

1.算法原理

        这个题是链表学习中的一个经典的题目，给一个链表然后判断这个链表是否有环，如果有环返回入环口处的节点，如果没有则返回空。

        方法一：快慢指针。该题可以用一个快慢指针同时从链表头开始走，如果快指针走到空节点还未与慢指针相遇，则该链表无环。如果快指针与慢指针相遇，则有环并记录相遇点，找两个速度相同的指针一个从头开始走，一个从相遇点开始走，那么它们相遇时的点就为环的入口点。这个算法比较难以想到，而且一眼难以看出它的正确性需要有严谨的证明。我在以下文章中有详细讲解：链表经典面试题-CSDN博客

        方法二：使用一个指针从链表的头走到尾，并且使用一个set容器，每走一步判断set中是否已存入该值，如果没有则存入，如果有那么这个链表一定有环并且该点就是环的入口点，直接返回该值即可。如果指针走到空依旧没有找到set中的重复值则这个链表不带环，返回空。该方法灵活运用了数据结构，而且很容易理解，相比上一个解法直接就是降维打击。

2.代码编写

class Solution {
public:ListNode *detectCycle(ListNode *head) {set<ListNode*> pt;ListNode* cur=head;while(cur){if(pt.count(cur)) return cur;else pt.insert(cur);cur=cur->next;}return nullptr;}
};

2.随机链表的复制

1.算法原理

        该题是对一个随机链表进行深拷贝，给一个链表要求原模原样拷贝一份，而这个题的难点并不在于拷贝节点本身，而是在于拷贝节点后random指向的节点是什么。尽管我们知道原链表的random指向什么但很难根据旧空间random的指向来判断新空间random的指向。不过因为旧空间与新空间有一个一一映射关系，所以我们可以使用一个map，key储存旧空间的值，value储存新空间的值。这个时候就非常好办只需旧空间的random找到指向的key就能找到新空间random应该指向的value。

2.代码编写

class Solution
{
public:Node* copyRandomList(Node* head){map<Node*,Node*> mp;Node* cur=head;Node* rhead=nullptr,*ret=nullptr,*perv=nullptr;while(cur){Node* ret=new Node(cur->val);if(rhead==nullptr) rhead=ret;else perv->next=ret;mp[cur]=perv=ret;cur=cur->next;}ret=rhead;cur=head;while(ret){ret->random=mp[cur->random];ret=ret->next;cur=cur->next;}return rhead;}
};