# C++ STL set与map operator[]

一、容器成员find与算法库find的区别

核心区别概述

详细解析

• STL 算法的find：通用算法，适用于任何提供迭代器的容器，通过线性遍历查找元素，时间复杂度 O(n)。
• setmap成员函数find：利用底层红黑树（平衡二叉搜索树）的有序性，通过二分查找定位元素，时间复杂度 O(log n)，效率更高。

常见容器的find方法分析

1. 有序关联容器（set、map、multiset、multimap）：

   • 成员find：基于红黑树的二分查找，时间复杂度 O(log n)。
   • 算法库find：线性遍历，时间复杂度 O(n)。

2. 无序关联容器（unordered_set、unordered_map等）：

   • 成员find：基于哈希表的查找，平均时间复杂度 O(1)。
   • 算法库find：线性遍历，时间复杂度 O(n)。

3. 顺序容器（vector、list、deque）：

   • 无内置find成员函数，必须使用算法库的find。

二、map的operator[]实现原理

核心功能

map::operator[]的核心功能是：返回指定键对应的值的引用。如果键不存在，则自动插入该键，并使用值类型的默认构造函数初始化其值。

实现原理

mapped_type&operator[](constkey_type&k){return(*(this->insert(make_pair(k,mapped_type()))).first).second;}

逐部分解析

1. make_pair(k, mapped_type())：构造一个临时的pair<key_type, mapped_type>对象，键为k，值为默认构造的mapped_type。

2. this->insert(...)：调用map的insert方法，尝试插入这个临时pair。返回pair<iterator, bool>，其中：

   • first：指向插入位置的迭代器（如果键已存在，则指向已存在的元素）。
   • second：布尔值，表示是否插入了新元素。

3. .first：获取insert返回的pair中的迭代器。

4. *(...)：解引用迭代器，得到pair<key_type, mapped_type>对象的引用。

5. .second：获取pair中的值（mapped_type）。

6. 返回值：返回值的引用（mapped_type&），允许直接修改值。

执行流程示例

map<string,int>m;m["a"]=1;// 插入 "a" → 0，然后赋值为 1int&val=m["a"];// 键 "a" 已存在，直接返回对应值的引用val=2;// 修改值为 2int&val2=m["b"];// 键 "b" 不存在，插入并返回默认值 0 的引用val2=3;// 修改为 3

注意事项

• 只能用于非 const map：可能会修改容器。
• 默认构造函数的要求：值类型T必须有默认构造函数。
• 性能考虑：键不存在时会触发插入操作，频繁查找且键可能不存在的场景下，使用find方法可能更高效。

三、力扣692题：前K个高频单词

题目要求

给定一个单词列表words和整数k，返回前k个出现次数最多的单词。要求按出现频率由高到低排序，频率相同时按字典顺序排序。

解决方案

步骤 1：统计单词频率

使用map<string, int>统计每个单词的出现次数：

map<string,int>m;for(auto&e:words){m[e]++;}

步骤 2：按频率排序

使用multimap<int, string, greater<int>>按频率排序：

• 键：出现次数，使用greater<int>使键按从大到小排序。
• 值：单词，利用map的遍历顺序保证频率相同时的字典序。

multimap<int,string,greater<int>>mm;for(auto&e:m){mm.insert(make_pair(e.second,e.first));}

步骤 3：提取前k个结果

vector<string>res;autoit=mm.begin();while(k--){res.push_back(it->second);++it;}returnres;

完整代码

classSolution{public:vector<string>topKFrequent(vector<string>&words,intk){map<string,int>m;for(auto&e:words){m[e]++;}multimap<int,string,greater<int>>mm;for(auto&e:m){mm.insert(make_pair(e.second,e.first));}vector<string>res;autoit=mm.begin();while(k--){res.push_back(it->second);++it;}returnres;}};

四、总结

set与map的核心特性

• set与map：有序集合，基于红黑树实现，元素唯一，查找时间复杂度 O(log n)。
• multiset/multimap：允许数据冗余，multimap没有operator[]操作。