在 C 中容器是存放数据的重要数据结构分为序列式容器和关联式容器。序列式容器如 vector、list、deque按线性顺序存储元素元素的位置与值无关而关联式容器则通过键key建立元素间的关联实现高效的查找、插入和删除操作。本文将详细介绍关联式容器中最常用的map和set包括它们的底层实现、核心特性、使用方法及实际应用。一、关联式容器的核心概念1. 容器分类与特点关联式容器的核心是 “关联关系”即通过键key快速定位元素而无需像序列式容器那样遍历整个容器。其特点如下元素按特定规则排序有序容器或无序存储无序容器插入位置由元素的键决定而非用户指定查找效率极高平均时间复杂度为 O(logN)有序容器或 O(1)无序容器。2. 底层实现有序容器set、map 等的底层通常采用平衡二叉搜索树红黑树实现其特性为左子树所有节点的值 根节点的值右子树所有节点的值 根节点的值树的高度保持平衡确保查找、插入、删除操作的时间复杂度为 O(logN)。无序容器unordered_set、unordered_map 等的底层采用哈希表实现通过哈希函数将键映射到存储位置平均时间复杂度为 O(1)但最坏情况下可能退化为 O(N)。3. 搜索模型关联式容器分为两种搜索模型K 模型仅存储键key如 set核心功能是判断元素是否存在KV 模型存储键值对key-value如 map核心功能是通过键查找对应的值。二、set 的原理与使用1. set 的核心特性set 是有序、不重复的 K 模型容器底层为红黑树。其核心特性自动排序插入元素后容器会按键的升序默认排列自动去重插入重复元素时操作会失败容器中仅保留一个实例不可修改元素set 中的元素是 const 类型修改元素会破坏红黑树的结构需通过 “删除旧元素 插入新元素” 实现。2. set 的常用操作1插入操作set 不支持 push_back/push_front需使用insert()插入元素123456#include setusingnamespacestd;setint s;s.insert(3);s.insert(1);s.insert(3);// 重复插入操作失败插入后set 中的元素会自动排序为{1, 3}。2遍历操作set 支持迭代器遍历和范围 for 遍历12345678910111213141516171819202122voidtest(){setint s;s.insert(3);s.insert(4);s.insert(1);s.insert(2);s.insert(3);s.insert(7);//排序去重setint::iterator it s.begin();while(it ! s.end()){cout *it ;it;}cout endl;for(auto e : s){cout e ;}cout endl;}3删除操作set 支持两种删除方式通过迭代器删除需先通过find()查找元素直接通过值删除。123456789// 方式 1通过迭代器删除setint::iterator pos s.find(7);//log(N)//setint::iterator pos find(s.begin(), s.end(), 4); //OP(N)if(pos ! s.end()){s.erase(pos);}// 方式 2直接通过值删除s.erase(1);// 删除元素 1若不存在则无操作4查找操作set 的查找功能是其核心提供两种方式成员函数find()利用红黑树特性时间复杂度 O(logN)算法std::find()线性遍历时间复杂度 O(N)。示例对比12345#include algorithm // 包含 std::find// 成员函数 find()setint::iterator pos1 s.find(3);// 高效查找// 算法 find()setint::iterator pos2 find(s.begin(), s.end(), 3);// 低效遍历使用建议优先使用 set 的成员函数find()以获得最佳性能。3. set 的实际应用set 的核心优势是快速存在性检查和高效去重排序适用于以下场景存储学号、身份证号等唯一标识快速验证是否存在对输入数据去重并排序如统计考试成绩的不重复分数实现集合运算交集、并集、差集。示例验证学号是否存在123456789student_ids.insert(001);student_ids.insert(002);student_ids.insert(003);string id 002;if(student_ids.find(id) ! student_ids.end()) {cout 学号 id 存在 endl;}else{cout 学号 id 不存在 endl;}三、map 的原理与使用1. map 的核心特性map 是有序、键唯一的 KV 模型容器底层为红黑树。其核心特性存储键值对key-value键key唯一值value可重复按键自动排序默认升序通过键快速查找对应的值时间复杂度 O(logN)支持通过键修改值但键不可修改否则会破坏红黑树结构。2. map 的常用操作1pair 类型介绍map 中的元素是pairconst key_type, value_type类型pair是一个模板结构体包含两个成员first键key不可修改second值value可修改。创建pair的方式1234// 方式 1显式指定模板参数pairint, string p1(1,张三);// 方式 2使用 make_pair自动推导类型pairint, string p2 make_pair(2,李四);2插入操作map 通过insert()插入pair类型元素123456789#include mapusingnamespacestd;mapint, string student_info;// 方式 1插入 pair 对象student_info.insert(pairint, string(1,张三));// 方式 2使用 make_pair推荐更简洁student_info.insert(make_pair(2,李四));// 方式 3C11 统一初始化student_info.insert({3,王五});插入后map 会按键的升序排列{1:张三, 2:李四, 3:王五}。3遍历操作map 支持迭代器遍历和范围 for 遍历通过it-first访问键it-second访问值12345678910// 迭代器遍历mapint, string::iterator it student_info.begin();while(it ! student_info.end()) {cout 学号 it-first 姓名 it-second endl;it;}// 范围 for 遍历for(auto e : student_info) {cout 学号 e.first 姓名 e.second endl;}4查找与修改操作通过键查找值有两种方式成员函数find()返回指向该键值对的迭代器下标运算符[]直接通过键访问值若键不存在会自动插入一个默认构造的键值对。123456789// 方式 1find() 查找推荐避免误插入mapint, string::iterator pos student_info.find(2);if(pos ! student_info.end()) {cout 找到 pos-second endl;// 输出李四pos-second 李小四;// 修改值}// 方式 2下标访问注意键不存在时会自动插入string name student_info[3];// 访问键 3 的值存在则返回 王五student_info[4] 赵六;// 键 4 不存在插入 {4:赵六}5删除操作map 的删除方式与 set 类似支持迭代器删除和键删除1234567// 方式 1通过迭代器删除mapint, string::iterator pos student_info.find(2);if(pos ! student_info.end()) {student_info.erase(pos);}// 方式 2通过键删除student_info.erase(3);// 删除键 3 对应的键值对3. map 的实际应用map 的核心优势是通过键快速查找值适用于以下场景存储键值对映射关系如字典单词 - 翻译、学号 - 成绩统计元素出现次数如统计字符串中每个单词的出现次数实现缓存机制键为缓存 key值为缓存数据。示例统计字符串出现次数1234567891011121314string str[] {西瓜,圣女果,圣女果,西瓜,西瓜,香蕉,葡萄,葡萄,菠萝,西瓜,桃子,西瓜,栗子,水蜜桃,西瓜,葡萄};mapstring,int countMap;for(auto e : str){mapstring,int::iterator pos countMap.find(e);if(pos countMap.end())countMap.insert(make_pair(e, 1));elsepos-second;}for(auto e : countMap){cout e.first:e.secondendl;}四、map 与 set 的区别与联系1. 相同点底层均为红黑树有序容器操作时间复杂度均为 O(logN)均支持自动排序和去重set 去重键map 去重键均不支持直接修改元素set 元素不可修改map 键不可修改。2. 不同点特性setmap存储类型仅键K 模型键值对KV 模型核心功能快速存在性检查快速键值映射查找元素访问仅访问键访问键和值修改方式不可修改需删插可修改值键不可改五、使用注意事项元素不可修改set 的元素和 map 的键均为 const 类型修改会破坏红黑树结构需通过 “删插” 实现迭代器有效性插入元素时红黑树可能重新平衡迭代器不会失效删除元素时仅被删除元素的迭代器失效其他迭代器有效比较规则默认按键的升序排序若需自定义排序可在定义容器时指定比较函数如setint, greaterint按降序排序效率选择需有序存储且高效查找时使用 set/map无需排序且追求极致查找效率时使用 unordered_set/unordered_map哈希表实现仅需线性存储时使用 vector/list 等序列式容器。六、总结map 和 set 是 C 中最常用的关联式容器其核心优势在于高效的查找、插入和删除操作底层依赖红黑树实现有序存储和去重。set 专注于 “键的存在性检查”map 专注于 “键值对的映射查找”二者在实际开发中应用广泛如数据去重、统计计数、字典映射等场景。掌握 map 和 set 的使用需理解其底层实现原理和核心特性根据实际需求选择合适的容器以优化程序性能。
