前言

本篇博客讲解c++中stl的set/map，本篇讲的如何使用

💓 个人主页：普通young man-CSDN博客

⏩ 文章专栏：C++_普通young man的博客-CSDN博客

⏩ 本人giee:   普通小青年 (pu-tong-young-man) - Gitee.com

      若有问题 评论区见📝

🎉欢迎大家点赞👍收藏⭐文章

————————————————

---

看这篇博客之前请先去看：C++ | 二叉搜索树-CSDN博客

---

目录

序列式容器和关联式容器

set的使用

参考文档

set的基本介绍

set的构造和迭代器

构造

迭代器

正向迭代器

反向迭代器

set的增删查

插入操作

单个数据插入

列表插入

区间插入

查找操作

查找特定值

计算特定值的个数

删除操作

删除指定位置的元素

删除特定值

删除区间内的元素

边界查找

查找大于等于特定值的位置

查找大于特定值的位置

insert和迭代器遍历使⽤样例

find和erase使⽤样例：

multiset和set的差异

multiset 与 set 的差异

第一部分：遍历 multiset

第二部分：查找、计数和删除元素

题目练习

map的使用

map类的介绍

std::map 的声明及特性

功能特性表格

pair类型介绍

什么是 pair？

pair 的工作原理

1. 定义 pair

2. 构造 pair

3. 访问 pair 的成员

map的构造

std::map 的构造接口

std::map 的迭代遍历

支持范围 for 循环

修改 value 数据

不支持修改 key 数据

map的增删查

std::map 的增删查接口

插入（Insert）

查找（Find）

删除（Erase）

map的数据修改

std::map 数据修改接口

修改 mapped_type 数据

插入接口

operator[] 的内部实现

operator[] 的内部实现示例

构造遍历及增删查使用样例

map的迭代器和[]功能样例

示例 1：使用 find 和迭代器修改功能统计水果出现次数

示例 2：使用 operator[] 插入和修改功能统计水果出现次数

示例 3：使用 std::map operator[]

multimap和map的差异

std::map 和 std::multimap 的主要差异

1. 键的唯一性

2. 查找操作

3. 插入操作

4. 计数操作

5. 删除操作

6. operator[]

使用 std::map

题目练习

---

序列式容器和关联式容器

想象一下你有两个盒子来存放你的东西，一个是用来放T恤的，另一个是用来放袜子的。

序列式容器就像是你的T恤盒子：

它们存放的东西是按照一定的顺序排列的，比如你可以根据颜色或者大小来摆放T恤。如果你想换一件T恤的位置，比如把红色的T恤放在最上面，这是可以做到的，并且不会影响其他T恤的位置。序列式容器的例子包括<code>vector（向量）、list（列表）、deque（双端队列）等，它们的特点就是里面的元素是按照插入的顺序存放的，你可以很容易地通过位置来找到一个元素。

关联式容器则像是你的袜子盒子：

这个盒子里的每只袜子都有一个标签，比如图案或者材质，用来区分不同的袜子。如果你想把两只袜子的位置对调，比如把图案A的袜子和图案B的袜子换一下位置，那么这个盒子的整个组织方式就会被打乱，因为袜子的位置是由它们的标签决定的。关联式容器包括map（映射）和set（集合），set是专门用来存放没有重复的关键字，而map则是用来存放关键字和对应值的配对。在这些容器里，元素是按照关键字的顺序来存放的，而不是它们插入的顺序。

---

set的使用

参考文档

<set> - C++ Reference (cplusplus.com)

---

set的基本介绍

特性/操作	描述
声明	std::set<T, Compare, Allocator>;
底层实现	使用红黑树（Red-Black Tree），保证插入、删除和查找操作的时间复杂度为 O(log N)。
默认比较	默认使用 std::less<T>，即元素按照升序排列。
自定义比较	可以通过第二个模板参数传递自定义的比较函数对象。
内存管理	默认使用 std::allocator<T> 管理内存，可以通过第三个模板参数自定义内存分配策略。
插入	insert(value_type val); - 插入值 val，如果已存在则不插入。
删除	erase(iterator it); - 删除指定迭代器指向的元素。<br>erase(const key_type& k); - 删除键值为 k 的元素。<br>clear(); - 删除所有元素。
查找	find(const key_type& k); - 查找键值为 k 的元素。<br>count(const key_type& k); - 返回键值为 k 的元素数量（0 或 1）。<br>contains(const key_type& k); - 如果包含键值为 k 的元素则返回 true（C++20）。
迭代器	begin(), end(); - 分别返回指向容器首尾的迭代器。<br>cbegin(), cend(); - 对于 const 容器。<br>rbegin(), rend(); - 返回反向迭代器。
状态检查	empty(); - 如果集合为空则返回 true。<br>size(); - 返回集合中元素的数量。<br>max_size(); - 返回容器所能容纳的最大元素数量。

---

set的构造和迭代器

构造

std::set 支持多种构造方式，常用的构造接口包括：

构造函数	描述
std::set();	默认构造函数，创建一个空的 set 容器。
std::set(InputIterator first, InputIterator last);	创建一个 set 容器，并初始化该容器，使其包含从 [first, last) 范围内的元素。
std::set(const set& other);	复制构造函数，创建一个新的 set 容器，并用另一个 set 容器的内容初始化它。
std::set(set&& other);	移动构造函数，创建一个新的 set 容器，并用另一个 set 容器的内容初始化它，通常更高效。
std::set(initializer_list<T> il);	使用 initializer_list 初始化 set 容器。
std::set(InputIterator first, InputIterator last, const Compare& comp);	创建一个 set 容器，并初始化该容器，同时指定自定义比较器 comp。
std::set(const set& other, const Allocator& alloc);	复制构造函数，同时允许指定不同的分配器 alloc。
std::set(initializer_list<T> il, const Compare& comp);	使用 initializer_list 初始化 set 容器，并指定自定义比较器 comp。

迭代器

std::set 支持正向和反向迭代，用于遍历容器中的元素。由于 std::set 底层使用的是红黑树，迭代器遍历采用的是中序遍历，因此遍历结果是按照元素的升序排列。

正向迭代器

std::set 的正向迭代器支持从前往后的遍历：

方法	描述
begin();	返回一个指向容器中第一个元素的迭代器。
cbegin();	返回一个指向容器中第一个元素的常量迭代器。适用于 const 容器。
end();	返回一个超出最后一个元素的迭代器。
cend();	返回一个超出最后一个元素的常量迭代器。适用于 const 容器。

反向迭代器

std::set 的反向迭代器支持从后往前的遍历：

方法	描述
rbegin();	返回一个指向容器中最后一个元素的反向迭代器。
crbegin();	返回一个指向容器中最后一个元素的常量反向迭代器。适用于 const 容器。
rend();	返回一个超出容器中第一个元素位置的反向迭代器。
crend();	返回一个超出容器中第一个元素位置的常量反向迭代器。适用于 const 容器。

set的增删查

其实这里就是接口的使用，这些都可以通过参考文档学会

插入操作

单个数据插入

pair<iterator,bool> insert (const value_type& val);

插入单个元素 val。返回一个 pair，其中包含一个迭代器和一个布尔值。迭代器指向新插入元素的位置（如果插入成功）或尝试插入元素的位置（如果插入失败），布尔值表示插入是否成功。

列表插入

void insert (initializer_list<value_type> il);

插入由 initializer_list 表达的多个元素。

template <class T>

class initializer_list {

public:

typedef T value_type;

typedef T* iterator;

typedef const T* const_iterator;

private:

T* begin_;

T* end_;

public:

// 构造函数，接受一对指针，表示元素的起始和结束位置

initializer_list(T* begin, T* end) noexcept : begin_(begin), end_(end) {}

// 返回迭代器，指向列表的第一个元素

iterator begin() const noexcept { return begin_; }

// 返回迭代器，指向列表的结束位置

iterator end() const noexcept { return end_; }

// 返回列表中元素的数量

size_t size() const noexcept { return end_ - begin_; }

// 判断列表是否为空

bool empty() const noexcept { return begin_ == end_; }

// 访问列表的第一个元素（如果存在）

reference front() const { return *begin_; }

// 访问列表的最后一个元素（如果存在）

reference back() const { return *(end_ - 1); }

// 返回指向第一个元素的指针

pointer data() const noexcept { return begin_; }

};

// 非成员函数，用于创建 initializer_list 实例

template <typename T>

inline initializer_list<T> make_initializer_list(T* begin, T* end) {

return initializer_list<T>(begin, end);

}

构造函数，它会接收指向数组首元素的指针 和指向数组末尾之后的指针 首元素<code> + sizeof(*) / sizeof(*)。

已经存在于容器中的值不会被插入。

区间插入

template <class InputIterator>

void insert (InputIterator first, InputIterator last);

插入从迭代器 first 到 last 的区间内的所有元素。已经存在于容器中的值不会被插入。

查找操作

查找特定值

iterator find (const value_type& val);

查找值为 val 的元素。返回指向该元素的迭代器，如果没有找到，则返回 end()。

计算特定值的个数

size_type count (const value_type& val) const;

返回值为 val 的元素的数量。对于 std::set，返回值只能是 0 或 1。

删除操作

删除指定位置的元素

iterator erase (const_iterator position);

删除由 position 指向的元素。返回紧接着被删除元素之后的下一个元素的迭代器。

删除特定值

size_type erase (const value_type& val);

删除值为 val 的元素。返回删除的元素数量，如果值不存在则返回 0。

删除区间内的元素

iterator erase (const_iterator first, const_iterator last);

删除由 [first, last) 区间内的所有元素。返回紧接着被删除元素之后的下一个元素的迭代器。

边界查找

查找大于等于特定值的位置

iterator lower_bound (const value_type& val) const;

返回指向容器中第一个大于等于 val 的元素的迭代器。

查找大于特定值的位置

iterator upper_bound (const value_type& val) const;

返回指向容器中第一个大于 val 的元素的迭代器。

---

insert和迭代器遍历使⽤样例

//set插入

int main() {

set<int> s1;

s1.insert(1);

s1.insert(2);

s1.insert(3);

s1.insert(4);

s1.insert(5);

auto it = s1.begin();

while (it != s1.end())

{

cout << *it << " ";

it++;

}

cout << endl;

// 插⼊⼀段initializer_list列表值，已经存在的值插⼊失败

set<int> s2;

s2.insert({ 1,2,3,4,5,6 });

//范围for遍历

for (auto it : s2)

{

cout << it << " ";

}

cout << endl;

string s3[] = { "张三","李四","王五" };

set<string> s4;

//通过指针来遍历

s4.insert(s3, s3 + sizeof(s3) / sizeof(string));

for (auto it : s4)

{

cout << it << " ";

}

cout << endl;

set<string> strset = { "sort", "insert", "add" };

for (auto it : strset)

{

cout << it << " ";

}

cout << endl;

return 0;

}

find和erase使⽤样例：

//set删除/查找

//int main() {

//set<int> s1 = {4,2,7,2,8,5,9};

#if 0

for (auto it : s1)

{

cout << it << " ";

}

cout << endl;

//删除最小值()

s1.erase(s1.begin());

for (auto it : s1)

{

cout << it << " ";

}

cout << endl;

int x;

cin >> x;

int ret = s1.erase(x);

if (ret == 0)

{

cout << "不存在" << endl;

}

else

{

cout << x << "删除成功" << endl;

for (auto it : s1)

{

cout << it << " ";

}

cout << endl;

}

#endif // 0

#if 0

//利用查找删除

int xx;

cin >> xx;

auto pos = s1.find(xx);

if (pos != s1.end())

{

s1.erase(pos);

cout << "删除成功！" << endl;

for (auto it : s1)

{

cout << it << " ";

}

}

else

{

cout << "不存在" << endl;

}

#endif // 0

#if 0

//直接调用erase接口删除

int i;

cin >> i;

int ret = s1.erase(i);

if (ret) {

cout << "删除成功！" << endl;

for (auto it : s1)

{

cout << it << " ";

}

}

else

{

cout << "不存在" << endl;

}

#endif // 0

#if 0

//库中find算法O(N)

auto tmp1 = find(s1.begin(),s1.end(),5);

//set中find算法O(logN) (1)

auto tmp2 = s1.find(5);

#endif // 0

#if 0

//count -- 计数，如果容器包含等效于 val 的元素，则为 1，否则为 0。

int i;

cin >> i;

if (s1.count(i))

cout << "找到了" << endl;

else

cout << "没有找到" << endl;

return 0;

#endif // 0

#if 0

//实现区间查找

set<int> s2;

for (int i = 1; i < 10; i++)

{

s2.insert(i * 10);

}

for (auto it : s2)

{

cout << it << " ";

}

cout << endl;

//删除[10,50]

auto itlow = s2.lower_bound(10);

auto itup = s2.upper_bound(50);

s2.erase(itlow, itup);

for (auto it : s2)

{

cout << it << " ";

}

cout << endl;

#endif // 0

multiset和set的差异

multiset 与 set 的差异

支持重复元素：

std::set 不允许重复的元素，而 std::multiset 支持重复元素的存储。

插入元素：

std::set 和 std::multiset 都支持插入元素，但是 std::set 在插入重复元素时不会插入，而 std::multiset 会保留所有重复元素。

查找元素：

std::set 中查找元素时，如果元素存在，则返回指向该元素的迭代器；如果不存在，则返回 end()。std::multiset 中查找元素时，返回指向第一个匹配元素的迭代器。由于可能有多个相同的元素，因此需要循环遍历找到所有匹配的元素。

计数元素：

std::set 的 count() 成员函数总是返回 0 或 1，表示元素是否存在。std::multiset 的 count() 成员函数返回指定元素的实际个数。

删除元素：

std::set 中删除元素时，只会删除一个匹配的元素（实际上只可能有一个）。std::multiset 中删除元素时，如果提供了一个值而不是迭代器，则会删除所有匹配的元素。

第一部分：遍历 multiset

#if 0

multiset<int> s1 = { 4,2,7,2,4,8,4,5,4,9 };

auto it = s1.begin();

while (it != s1.end())

{

cout << *it << " ";

++it;

}

#endif // 0

这一部分代码创建了一个 multiset 并插入了一些重复的整数。然后通过迭代器遍历整个 multiset 并打印出每个元素。

第二部分：查找、计数和删除元素

#if 0

int i;

cin >> i;

multiset<int> s1 = { 4,2,7,2,4,8,4,5,4,9 };

auto pos = s1.find(i);

while (pos != s1.end() && *pos == i)

{

cout << *pos << " ";

++pos;

}

cout << endl;

// 相⽐set不同的是，count会返回x的实际个数

cout << s1.count(i) << endl;

// 相⽐set不同的是，erase给值时会删除所有的x

s1.erase(i);

for (auto e : s1)

{

cout << e << " ";

}

cout << endl;

#endif // 0

这一部分代码首先从用户输入一个整数 i，然后查找 multiset 中是否存在这个整数，并打印出来。接着使用 count() 函数统计 i 在 multiset 中出现的次数，并打印出来。最后，使用 erase() 函数删除所有值为 i 的元素，并再次遍历 multiset 打印剩余的元素。

题目练习

 

利用了set去重的特点

349. 两个数组的交集 - 力扣（LeetCode）

class Solution {

public:

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {

//将两个num

set<int> s1(nums1.begin(),nums1.end());

set<int> s2(nums2.begin(),nums2.end());

//定义一个数组

vector<int> ret;

//利用双指针法(迭代器)

auto it_one = s1.begin();

auto it_two = s2.begin();

//小进行++（小的前面的数不可能和大的相等）

while(it_one != s1.end() && it_two != s2.end()){

if(*it_one > *it_two){

it_two++;

}

else if(*it_one < *it_two){

it_one++;

}

else{

ret.push_back(*it_one);

it_one++;

it_two++;

}

}

return ret;

}

};

步骤	操作	描述
1	set<int> s1(nums1.begin(), nums1.end());	将向量 nums1 转换为 set 类型，去除重复元素并排序。
2	set<int> s2(nums2.begin(), nums2.end());	将向量 nums2 转换为 set 类型，去除重复元素并排序。
3	vector<int> ret;	创建一个空的 vector 用于存储交集元素。
4	auto it_one = s1.begin();	初始化指向 s1 集合起始位置的迭代器 it_one。
5	auto it_two = s2.begin();	初始化指向 s2 集合起始位置的迭代器 it_two。
6	while (it_one != s1.end() && it_two != s2.end()) { ... }	循环直到至少有一个迭代器达到其对应集合的末尾。
6.1	if (*it_one > *it_two) { it_two++; }	如果 s1 中的元素大于 s2 中的元素，则移动 s2 的迭代器 it_two。
6.2	else if (*it_one < *it_two) { it_one++; }	如果 s1 中的元素小于 s2 中的元素，则移动 s1 的迭代器 it_one。
6.3	else { ret.push_back(*it_one); it_one++; it_two++; }	如果两个元素相等，则将该元素添加到结果向量 ret 中，并同时移动两个迭代器。
7	return ret;	返回包含交集元素的结果向量 ret。

142. 环形链表 II - 力扣（LeetCode）

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

*/

class Solution {

public:

ListNode* detectCycle(ListNode* head) {

set<ListNode*> s1;

ListNode* cur = head;

while (cur) {

//直接判断是否(注意这里判断的是地址，而不是值)

if (s1.count(cur)) {

return cur;

} else {

s1.insert(cur);

}

cur = cur->next;

}

return nullptr;

}

};

步骤	操作	描述
1	struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} };	定义链表节点结构，包含值 val 和指向下一个节点的指针 next。
2	ListNode* detectCycle(ListNode* head)	定义检测环的函数，接收链表头节点 head 作为参数。
3	set<ListNode*> s1;	创建一个 set 用于存储遍历过的节点指针。
4	ListNode* cur = head;	初始化一个指针 cur 指向链表头节点 head。
5	while (cur)	当 cur 不为 nullptr 时执行循环。
5.1	if (s1.count(cur))	检查当前节点是否已经在 set 中。
5.1.1	return cur;	如果当前节点在 set 中，则返回该节点（环的起始节点地址）。
5.2	else { s1.insert(cur); }	如果当前节点不在 set 中，则将其插入 set 中。
5.3	cur = cur->next;	将 cur 指向下一个节点。
6	return nullptr;	如果遍历完链表都没有发现环，则返回 nullptr。

---

map的使用

参考文档

<map> - C++ Reference (cplusplus.com)

map类的介绍

std::map 的声明及特性

声明

template <class Key, // map::key_type

class T, // map::mapped_type

class Compare = less<Key>, // map::key_compare

class Alloc = allocator<pair<const Key, T>> // map::allocator_type

> class map;

功能特性表格

模板参数	描述
Key	映射的键类型，用于唯一标识一个条目。
T	映射的值类型，即每个键所关联的数据类型。
Compare	比较函数对象类型，默认为 std::less<Key>，用于比较键的大小。可以根据需要自定义。
Alloc	分配器类型，默认为 std::allocator<std::pair<const Key, T>>，用于管理内存分配。

特性	描述
底层实现	使用红黑树（Red-Black Tree），保证插入、删除和查找操作的时间复杂度为 O(log N)。
比较机制	默认使用 <code>std::less<Key> 进行比较，可以自定义比较函数对象。
内存管理	内存从分配器申请，默认使用 std::allocator。可以根据需要自定义分配器。
迭代器遍历	迭代器遍历按照键的升序顺序（中序遍历），因此遍历结果是有序的。

---

pair类型介绍

什么是 <code>pair？

std::pair 是 C++ 标准库中的一个模板类，用于将两个不同类型的数据组合在一起。它可以看作是一个简单的容器，用来存储两个相关的值。这两个值可以是任意类型，但必须是已知的类型。

pair 的工作原理

1. 定义 pair

假设我们需要存储一个整数和一个字符串，我们可以这样定义一个 pair：

#include <utility> // 包含pair定义

#include <iostream>

int main() {

std::pair<int, std::string> myPair;

}

这里 myPair 是一个 pair，它的第一个类型是 int，第二个类型是 std::string。

2. 构造 pair

std::pair 提供了几种构造函数来初始化它的成员变量：

默认构造函数：

std::pair<int, std::string> myPair; // 默认构造

这会创建一个 pair，其中 first 和 second 都会被初始化为各自类型的默认值（例如 int 为 0，std::string 为一个空字符串）。

初始化构造函数：

std::pair<int, std::string> myPair(42, "hello"); // 初始化构造

这里直接给 pair 的 first 和 second 成员赋初值。

从其他类型的 pair 构造：

std::pair<double, char> otherPair(3.14, 'a');

std::pair<int, std::string> convertedPair(otherPair); // 从其他类型构造

这里可以使用一个不同类型的 pair 来构造一个新的 pair。

使用 make_pair：

std::pair<int, std::string> myPair = std::make_pair(42, "hello");

make_pair 是一个方便的函数，用于创建 pair 对象。

3. 访问 <code>pair 的成员

std::pair 有两个成员变量 first 和 second，可以用来访问存储的值：

std::pair<int, std::string> myPair = std::make_pair(42, "hello");

std::cout << "First: " << myPair.first << std::endl; // 输出 First: 42

std::cout << "Second: " << myPair.second << std::endl; // 输出 Second: hello

---

map的构造

std::map 的构造接口

构造函数	描述	示例代码
map();	创建一个空的 std::map。
template <class InputIterator>\nmap(InputIterator first, InputIterator last);	创建一个 std::map，包含从迭代器 first 到 last 的所有元素。	cpp\nstd::vector<std::pair<std::string, int>> vec = { {"apple", 1}, {"banana", 2}, {"orange", 3}};\nstd::map<std::string, int> myMap(vec.begin(), vec.end());\n
map(const map& x);	创建一个 std::map，包含另一个 std::map 的所有元素。	cpp\nstd::map<std::string, int> myMap1 = { {"apple", 1}, {"banana", 2}, {"orange", 3}};\nstd::map<std::string, int> myMap2(myMap1);\n
template <class InputIterator>\nmap(InputIterator first, InputIterator last,\nconst key_compare& comp,\nconst allocator_type& alloc = allocator_type());	创建一个 std::map，包含从迭代器 first 到 last 的所有元素，并使用指定的比较函数和分配器。	cpp\nstd::vector<std::pair<std::string, int>> vec = { {"apple", 1}, {"banana", 2}, {"orange", 3}};\nstd::map<std::string, int, std::greater<std::string>> myMap(vec.begin(), vec.end());\n

std::map 的迭代遍历

遍历方式	描述	示例代码
正向迭代	使用正向迭代器遍历 std::map，默认按照键的升序顺序。	cpp\nfor (const auto &entry : myMap) {\n std::cout << entry.first << ": " << entry.second << std::endl;\n}\n
反向迭代	使用反向迭代器遍历 std::map，按照键的降序顺序。	cpp\nfor (auto rit = myMap.rbegin(); rit != myMap.rend(); ++rit) {\n std::cout << rit->first << ": " << rit->second << std::endl;\n}\n

支持范围 for 循环

描述	示例代码
std::map 支持范围 for 循环，可以直接遍历 std::map 的键值对。	cpp\nfor (const auto &entry : myMap) {\n std::cout << entry.first << ": " << entry.second << std::endl;\n}\n

修改 value 数据

描述	示例代码
可以修改 std::map 中的 value 数据，即 pair 的 second 成员。	cpp\nmyMap["apple"] = 2;\n

不支持修改 key 数据

描述	示例代码
由于 std::map 的键值（key）决定了元素在红黑树中的位置，因此不允许直接修改键值。	（不推荐）cpp\nmyMap["apple"] = "orange"; // 错误做法，实际修改的是 value\n

#include <iostream>

#include <map>

#include <vector>

int main() {

// 默认构造

std::map<std::string, int> myMap;

// 初始化构造

std::vector<std::pair<std::string, int>> vec = { {"apple", 1}, {"banana", 2}, {"orange", 3}};

std::map<std::string, int> myMapInit(vec.begin(), vec.end());

// 拷贝构造

std::map<std::string, int> myMapCopy(myMapInit);

// 区间构造

std::map<std::string, int, std::greater<std::string>> myMapDesc(vec.begin(), vec.end());

// 正向迭代遍历

std::cout << "Forward iteration:" << std::endl;

for (const auto &entry : myMapInit) {

std::cout << entry.first << ": " << entry.second << std::endl;

}

// 反向迭代遍历

std::cout << "Reverse iteration:" << std::endl;

for (auto rit = myMapInit.rbegin(); rit != myMapInit.rend(); ++rit) {

std::cout << rit->first << ": " << rit->second << std::endl;

}

// 修改 value 数据

myMapInit["apple"] = 2;

return 0;

}

---

map的增删查

std::map 的增删查接口

插入（Insert）

方法	描述	返回值	示例代码
pair<iterator,bool> insert (const value_type& val);	插入一个键值对 pair，如果键已存在则插入失败。	返回一个 pair，其中 first 是插入位置的迭代器，second 是一个布尔值，表示是否插入成功。	cpp\nstd::pair<std::map<std::string, int>::iterator, bool> result = myMap.insert({ {"apple", 2}});\n
void insert (initializer_list<value_type> il);	插入一个初始化列表，已存在的值不会插入。	无返回值。	cpp\nmyMap.insert({ {"apple", 1}, {"banana", 2}, {"orange", 3}});\n
template <class InputIterator>\nvoid insert (InputIterator first, InputIterator last);	插入一个迭代器区间内的元素，已存在的值不会插入。	无返回值。	cpp\nstd::vector<std::pair<std::string, int>> vec = { {"apple", 1}, {"banana", 2}, {"orange", 3}};\nmyMap.insert(vec.begin(), vec.end());\n

查找（Find）

方法	描述	返回值	示例代码
iterator find (const key_type& k);	查找键 k，返回指向键 k 的迭代器，如果没有找到则返回 end()。	迭代器	cpp\nauto it = myMap.find("apple");\nif (it != myMap.end()) {\n std::cout << it->first << ": " << it->second << std::endl;\n}\n
size_type count (const key_type& k) const;	计算键 k 在 std::map 中出现的次数。	键 k 的出现次数（对于 std::map，最多为 1）。	cpp\nsize_t count = myMap.count("apple");\nstd::cout << "Count of 'apple': " << count << std::endl;\n
iterator lower_bound (const key_type& k);	返回大于等于键 k 的第一个元素的迭代器。	迭代器	cpp\nauto it = myMap.lower_bound("banana");\n
const_iterator lower_bound (const key_type& k) const;	返回大于等于键 k 的第一个元素的常量迭代器。	常量迭代器	cpp\nauto it = myMap.lower_bound("banana");\n

删除（Erase）

方法	描述	返回值	示例代码
iterator erase (const_iterator position);	删除一个迭代器位置的值，返回下一个元素的迭代器。	迭代器	cpp\nauto it = myMap.find("apple");\nif (it != myMap.end()) {\n auto nextIt = myMap.erase(it);\n}\n
size_type erase (const key_type& k);	删除键 k，返回删除的元素数量（对于 std::map，最多为 1）。	删除的元素数量	cpp\nsize_t count = myMap.erase("apple");\nstd::cout << "Erased 'apple': " << count << std::endl;\n
iterator erase (const_iterator first, const_iterator last);	删除一段迭代器区间的值，返回最后一个未删除元素的迭代器。	迭代器	cpp\nauto rangeBegin = myMap.lower_bound("apple");\nauto rangeEnd = myMap.upper_bound("orange");\nmyMap.erase(rangeBegin, rangeEnd);\n

#include <iostream>

#include <map>

#include <vector>

int main() {

// 创建一个空的 map

std::map<std::string, int> myMap;

// 插入键值对

std::pair<std::map<std::string, int>::iterator, bool> result = myMap.insert({ {"apple", 1}});

if (result.second) {

std::cout << "Inserted 'apple': " << result.first->second << std::endl;

}

// 使用初始化列表插入

myMap.insert({ {"banana", 2}, {"orange", 3}});

// 使用迭代器区间插入

std::vector<std::pair<std::string, int>> vec = { {"grape", 4}, {"mango", 5}};

myMap.insert(vec.begin(), vec.end());

// 查找键 "apple"

auto it = myMap.find("apple");

if (it != myMap.end()) {

std::cout << "Found 'apple': " << it->second << std::endl;

}

// 计算键 "apple" 的出现次数

size_t count = myMap.count("apple");

std::cout << "Count of 'apple': " << count << std::endl;

// 找到大于等于 "banana" 的元素

auto lbIt = myMap.lower_bound("banana");

if (lbIt != myMap.end()) {

std::cout << "Lower bound of 'banana': " << lbIt->first << ": " << lbIt->second << std::endl;

}

// 删除 "apple"

size_t erasedCount = myMap.erase("apple");

std::cout << "Erased 'apple': " << erasedCount << std::endl;

// 删除一段迭代器区间的值

auto rangeBegin = myMap.lower_bound("banana");

auto rangeEnd = myMap.upper_bound("orange");

myMap.erase(rangeBegin, rangeEnd);

return 0;

}

---

map的数据修改

std::map 数据修改接口

修改 mapped_type 数据

方法	描述	返回值	示例代码
iterator find (const key_type& k);	查找键 k，返回指向键 k 的迭代器，如果没有找到则返回 end()。通过迭代器可以修改键对应的 mapped_type 值。	迭代器	cpp\nauto it = myMap.find("apple");\nif (it != myMap.end()) {\n it->second = 2;\n}\n
mapped_type& operator[] (const key_type& k);	多功能接口，支持查找、插入和修改数据。如果键 k 已经存在，则返回键对应的 mapped_type 的引用；如果不存在，则插入默认值并返回引用。	mapped_type 的引用	cpp\nmyMap["apple"] = 2;\n

插入接口

方法	描述	返回值	示例代码
pair<iterator,bool> insert (const value_type& val);	插入一个键值对 pair，如果键已存在则插入失败。返回一个 pair，其中 first 是插入位置的迭代器，second 表示是否插入成功。	pair<iterator, bool>，其中 first 是迭代器，second 是布尔值，表示是否插入成功。	cpp\nstd::pair<std::map<std::string, int>::iterator, bool> result = myMap.insert({ {"apple", 2}});\n

<code>operator[] 的内部实现

方法	描述	返回值	示例代码
mapped_type& operator[] (const key_type& k);	多功能接口，支持查找、插入和修改数据。如果键 k 已经存在，则返回键对应的 mapped_type 的引用；如果不存在，则插入默认值并返回引用。	mapped_type 的引用	cpp\nmapped_type& ref = myMap["apple"];\nref = 2;\n

operator[] 的内部实现示例

描述	示例代码
如果键 k 不在 std::map 中，insert 会插入键 k 和 mapped_type 的默认值，并返回结点中存储的 mapped_type 值的引用。	cpp\nmapped_type& ref = myMap["newKey"];\nref = 5;\n
如果键 k 已经在 std::map 中，insert 会插入失败，但返回的 pair 对象的 first 指向键结点的迭代器，并返回结点中存储的 mapped_type 值的引用。	cpp\nmapped_type& ref = myMap["existingKey"];\nref = 3;\n

---

构造遍历及增删查使用样例

<code>#include <iostream>

#include <map>

using namespace std;

int main() {

// initializer_list构造及迭代遍历

map<string, string> dict = {

{"left", "左边"},

{"right", "右边"},

{"insert", "插入"},

{"string", "字符串"}

};

// 使用 auto 自动推导类型

auto it = dict.begin();

while (it != dict.end()) {

// 使用迭代器的 operator-> 和 operator* 访问元素

cout << it->first << ":" << it->second << endl;

++it;

}

cout << endl;

// insert 插入 pair 对象的 4 种方式，对比之下，最后一种最方便

pair<string, string> kv1("first", "第一个");

dict.insert(kv1);

dict.insert(pair<string, string>("second", "第二个"));

dict.insert(make_pair("sort", "排序"));

dict.insert({"auto", "自动的"});

// "left" 已经存在，插入失败

dict.insert({"left", "左边，剩余"});

// 范围 for 遍历

for (const auto& e : dict) {

cout << e.first << ":" << e.second << endl;

}

cout << endl;

string str;

while (cin >> str) {

auto ret = dict.find(str);

if (ret != dict.end()) {

cout << "->" << ret->second << endl;

} else {

cout << "无此单词，请重新输入" << endl;

}

}

// erase 接口跟 set 完全类似，这里就不演示讲解了

return 0;

}

map的迭代器和[]功能样例

为了更好地展示 std::map 的迭代器和 operator[] 功能，我们将给出的示例代码整理并加以解释。以下是两个不同的实现方法，用于统计水果出现的次数，以及一个使用 std::map 的其他功能的示例。

示例 1：使用 find 和迭代器修改功能统计水果出现次数

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main() {

string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",

"苹果", "香蕉", "苹果", "香蕉" };

map<string, int> countMap;

for (const auto& str : arr) {

// 先查找水果在不在map中

auto ret = countMap.find(str);

if (ret == countMap.end()) {

// 如果不在，说明水果第一次出现，则插入 {水果, 1}

countMap.insert({str, 1});

} else {

// 如果在，则查找到的节点中水果对应的次数++

ret->second++;

}

}

for (const auto& e : countMap) {

cout << e.first << ":" << e.second << endl;

}

cout << endl;

return 0;

}

示例 2：使用 operator[] 插入和修改功能统计水果出现次数

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main() {

string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",

"苹果", "香蕉", "苹果", "香蕉" };

map<string, int> countMap;

for (const auto& str : arr) {

// [] 先查找水果在不在map中

// 如果不在，说明水果第一次出现，则插入 {水果, 0}，同时返回次数的引用，++ 一下就变成1次了

// 如果在，则返回水果对应的次数++

countMap[str]++;

}

for (const auto& e : countMap) {

cout << e.first << ":" << e.second << endl;

}

cout << endl;

return 0;

}

示例 3：使用 std::map operator[]

#include <iostream>

#include <map>

#include <string>

using namespace std;

int main() {

map<string, string> dict;

dict.insert(make_pair("sort", "排序"));

// key不存在->插入 {"insert", ""} （默认构造）

dict["insert"];

// 插入+修改

dict["left"] = "左边";

// 修改

dict["left"] = "左边、剩余";

// key存在->查找

cout << dict["left"] << endl;

return 0;

}

multimap和map的差异

让我们以通俗易懂的方式解释 std::map 和 std::multimap 的主要差异，以及它们各自的使用场景。

std::map 和 std::multimap 的主要差异

1. 键的唯一性

std::map：在 std::map 中，键是唯一的。这意味着每个键只能对应一个值。如果你试图插入一个已经存在的键，插入操作将不会成功。

std::map<std::string, int> myMap;

myMap.insert({"apple", 1});

myMap.insert({"apple", 2}); // 这个操作不会成功

std::multimap：在 std::multimap 中，键可以重复。这意味着同一个键可以对应多个值。如果你插入一个已经存在的键，新的键值对将会被插入到适当的位置。

 

例子：

std::multimap<std::string, int> myMultimap;

myMultimap.insert({"apple", 1});

myMultimap.insert({"apple", 2}); // 这个操作会成功

2. 查找操作

std::map：由于键是唯一的，因此 find 方法总是返回指向特定键的迭代器，如果没有找到，则返回 end()。

 

例子：

auto it = myMap.find("apple");

if (it != myMap.end()) {

// 找到了 "apple"

}

std::multimap：由于键可以重复，find 方法返回的是指向键的第一个匹配项的迭代器。此外，equal_range 方法可以返回键的第一个和最后一个匹配项之间的范围。

 

例子：

auto range = myMultimap.equal_range("apple");

for (auto it = range.first; it != range.second; ++it) {

// 遍历所有 "apple" 的匹配项

}

3. 插入操作

std::map：如果键已经存在，插入操作不会成功。

 

例子：

bool inserted = myMap.insert({"apple", 2}).second; // inserted 为 false

std::multimap：如果键已经存在，插入操作仍然会成功，并将新的键值对插入到适当的位置。

 

例子：

bool inserted = myMultimap.insert({"apple", 2}).second; // inserted 为 true

4. 计数操作

std::map：count 方法对于任何键总是返回 1 或 0（键存在与否）。

 

例子：

int count = myMap.count("apple"); // count 为 1 或 0

std::multimap：count 方法可以返回一个键的出现次数，可以大于 1。  

例子：

int count = myMultimap.count("apple"); // count 可能大于 1

5. 删除操作

std::map：删除操作通常删除一个键值对。

 

例子：

myMap.erase("apple");

std::multimap：删除操作可以删除一个键的所有匹配项。  

        例子：

myMultimap.erase("apple");

6. operator[]

std::map：支持 operator[]，可以用于查找、插入和修改键对应的值。

 

例子：

myMap["apple"] = 1;

std::multimap：不支持 operator[]，因为键可以重复，operator[] 只能用于插入新的键值对，而不能用于修改值。  

        例子：

// 不支持

// myMultimap["apple"] = 1;

使用 <code>std::map

#include <iostream>

#include <map>

int main() {

std::map<std::string, int> myMap;

myMap.insert({"apple", 1});

myMap.insert({"banana", 2});

// 插入重复键，不会成功

myMap.insert({"apple", 2});

// 使用 operator[] 修改值

myMap["apple"] = 3;

// 输出

for (const auto& e : myMap) {

std::cout << e.first << ": " << e.second << std::endl;

}

return 0;

}

使用 std::multimap

---

题目练习

138. 随机链表的复制 - 力扣（LeetCode）

/*

// Definition for a Node.

class Node {

public:

int val;

Node* next;

Node* random;

Node(int _val) {

val = _val;

next = NULL;

random = NULL;

}

};

*/

class Solution {

public:

Node* copyRandomList(Node* head) {

map<Node*, Node*> Map;

Node *tmphead = nullptr, *tmptail = nullptr;

Node* cur = head;

// 建立关系

while (cur) {

if (tmptail == nullptr) {

tmphead = tmptail = new Node(cur->val);

} else {

tmptail->next = new Node(cur->val);

tmptail = tmptail->next;

}

// 建立map

Map[cur] = tmptail;

cur = cur->next;

}

// 处理random

cur = head;

Node* copy = tmphead;

while (cur) {

if (cur->random == nullptr) {

copy->random = nullptr;

} else {

//Map返回cur的value

copy->random = Map[cur->random];

}

cur = cur->next;

copy = copy->next;

}

return tmphead;

}

};

步骤	描述	目的	代码示例
1	初始化辅助变量	用于存储复制链表的头节点和尾节点	<code>Node *tmphead = nullptr, *tmptail = nullptr;
2	遍历原链表	复制每个节点，并构建新链表	while (cur) {...}
3	新建节点	创建新节点，并设置其值	tmphead = tmptail = new Node(cur->val);
4	连接新节点	将新节点连接到新链表的末尾	tmptail->next = new Node(cur->val);
5	更新尾指针	更新新链表的尾指针	tmptail = tmptail->next;
6	建立映射关系	在 map 中记录原节点与其副本的关系	Map[cur] = tmptail;
7	遍历原链表（第二次）	设置新链表中节点的 random 指针	while (cur) {...}
8	设置 random 指针	根据原节点的 random 指针设置新节点的 random 指针	copy->random = Map[cur->random];
9	返回新链表头节点	最终返回复制的新链表的头节点	return tmphead;

class Solution {

public:

class Compare {

public:

//比较单词出现数

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

// 统计所有单词

for (auto it : words) {

constmap[it]++;

}

// 将所有数据放进一个vector

vector<pair<string, int>> v(constmap.begin(), constmap.end());

// 排序(stable_sort--稳定排序)

//stable_sort(v.begin(), v.end(), Compare());

sort(v.begin(), v.end(), Compare());

// for (auto it : v) {

// cout<<it.first<<":"<<it.second<<" ";

// }

cout<<endl;

// 取前k个

vector<string> ret;

for (int i = 0; i < k; i++) {

ret.push_back(v[i].first);

}

return ret;

}

};

步骤	描述	目的	代码示例
1	初始化辅助数据结构	存储单词及其出现次数	std::map<std::string, int> freqMap;
2	统计单词出现次数	记录每个单词出现的次数	for (const auto& word : words) { freqMap[word]++; }
3	创建优先队列	用于存储前 k 个频繁元素	std::priority_queue<std::pair<std::string, int>, std::vector<std::pair<std::string, int>>, Compare> pq;
4	遍历统计结果	将统计结果加入优先队列	for (const auto& item : freqMap) { pq.push(item); if (pq.size() > k) { pq.pop(); } }
5	提取前 k 个单词	从优先队列中提取前 k 个单词	std::vector<std::string> result(k); for (int i = k - 1; i >= 0; --i) { result[i] = pq.top().first; pq.pop(); }
6	返回结果	返回前 k 个频繁单词	return result;

---