当前位置：首页 > news >正文

【C++】set和map的系统性学习：

news 2026/5/8 23:00:30

本文基于 C++ 关联式容器核心知识点，从底层原理、基础用法、核心 API、避坑指南全方面讲解set/map/multiset/multimap，适合 STL 入门学习、面试备考、日常开发使用

前言：（关联式容器的简介）

在 C++ STL 中，容器主要分为两大类：

序列式容器：vector、list、array、forward_list等，元素顺序由插入位置决定，需要手动维护顺序；
关联式容器：set、map、multiset、multimap、unordered_map、unordered_set，底层通过红黑树 / 哈希表实现，自动按照规则排序。

其中：

set/map/multiset/multimap：有序关联式容器，底层红黑树，增删查效率 \(O(logN)\)；
unordered_map/unordered_set：无序关联式容器，底层哈希表，增删查效率接近 \(O(1)\)。

一、std::set 详解

1.1 核心特性

底层实现：红黑树（平衡二叉搜索树）；
元素特性：键值唯一，不可重复，自动去重；
排序规则：默认按小于号比较排序（string按 ASCII 码排序）；
关键限制：元素不可修改！修改会破坏红黑树结构，导致容器失效；
迭代器类型：双向迭代器（支持++/--，不支持下标访问、随机访问）。

1.2 set 模板定义

template <class T, class Compare = less<T>, class Alloc = allocator<T>> class set;

T：存储元素的类型；
Compare：比较函数，默认less<T>升序，可自定义仿函数修改排序；
Alloc：空间配置器，默认无需修改。

1.3 核心 API 与用法

#include<iostream> #include<set> #include<vector> using namespace std; int main() { vector<int> V1 = { 1,2,34,345,45,4,2 }; set<int> S1; // 声明set // 1. 插入元素：自动去重+排序 for (auto e : V1) { S1.insert(e); } // 2. 迭代器遍历：中序遍历，有序输出 auto it = S1.begin(); while (it != S1.end()) { cout << *it << " "; // 解引用获取key it++; } cout << endl; // 3. find查找：返回迭代器，未找到返回end() if (S1.find(1) != S1.end()) { cout << "成功找到1" << endl; } // 4. 删除：两种方式 auto del_it = S1.find(45); if (del_it != S1.end()) S1.erase(del_it); // 迭代器删除，仅删当前元素 S1.erase(4); // 按值删除，返回删除个数(0/1) // 5. count：判断元素是否存在，返回0/1 cout << "3是否存在：" << S1.count(3) << endl; // 6. 边界查找 cout << "第一个大于34的元素：" << *S1.upper_bound(34) << endl; cout << "第一个大于等于32的元素：" << *S1.lower_bound(32) << endl; // 7. 其他常用接口 cout << "元素个数：" << S1.size() << endl; cout << "是否为空：" << S1.empty() << endl; S1.clear(); // 清空所有元素 return 0; }

1.4 重点 API 总结

find()：返回迭代器，效率 \(O(logN)\)，远优于算法库的find()（暴力查找\(O(N)\)）；
erase()：迭代器删除仅删单个元素，按值删除返回删除个数；
count()：仅用于判断存在，返回0/1；
lower_bound/upper_bound：有序容器专用，可配合erase删除区间。

二、std::multiset 详解

2.1 与 set 的核心区别

multiset=允许重复元素的 set，其余特性与 set 完全一致。

特性	set	multiset
元素唯一性	唯一，不可重复	允许重复
insert 返回值	`pair<迭代器,bool>`	仅迭代器（必成功）
count 返回值	0/1	任意非负整数
find 返回值	唯一元素迭代器	第一个匹配元素迭代器
erase (值)	删除 0/1 个	删除所有匹配元素

2.2 核心用法

插入：支持重复元素插入；
查找：find返回第一个匹配元素，可通过迭代器遍历所有重复值；
删除：erase(值)会删除所有相同元素，迭代器删除仅删单个。

三、std::map 详解

3.1 核心特性

底层：红黑树，按键key有序存储；
结构：存储键值对pair<const key, value>；
特性：key 唯一不可重复，value 可重复；
key 限制：key是const类型，不可修改；
迭代器：双向迭代器，支持[]运算符。

3.2 pair 键值对（map 基础）

map 存储的元素是pair结构体，包含两个成员：

first：键key；
second：值value。

// pair构造方式 map<string, string> M1; M1.insert({ "1","2" }); // 最常用 M1.insert(pair<string, string>("2", "1")); M1.insert(make_pair("3", "2"));

3.3 map 核心：[] 运算符（高频坑点）

map[]是「查找 + 插入 + 修改」三合一运算符：

key 存在：返回value的引用，可直接修改；
key 不存在：自动插入默认值，再返回引用。

⚠️警告：仅查询元素是否存在时，禁止用[]，会无意插入空值！

// 错误示范：查询会自动插入元素 if(dict["right"] != "") {} // 正确示范：用find查询 if(dict.find("right") != dict.end()) {}

3.4 insert 与 [] 的区别

操作	key 存在	key 不存在
`map[key]`	覆盖旧 value	自动插入默认 value
`insert()`	不覆盖，插入失败	插入新键值对

3.5 map 基础代码

#include <iostream> #include <map> #include <string> using namespace std; int main() { map<string, string> dict; // [] 插入+修改 dict["left"] = "左边"; cout << dict["left"] << endl; // insert 插入（不覆盖） dict.insert({"left", "左侧"}); cout << dict["left"] << endl; // 仍为"左边" // find查找 if (dict.find("left") != dict.end()) { cout << "key存在" << endl; } return 0; }