前言
STL容器是存储与管理同类型元素的类模板，其大致可以分为三类：
1.顺序容器：按照线性顺序，连续存储数据，以vector,deque,list为代表
2.关联容器：基于红黑树实现，按照关键字有序访问，以set,map为代表
3.无序关联容器：基于哈希表实现，高效无序访问，以unordered_set/unordered_map为代表
本文介绍的无序容器统一指无序关联容器。
无序容器的优势
与其他容器相比，无序容器舍弃了顺序容器的连续存储，也舍弃了关联容器的有序性，但换来了几乎是全容器最快的速度。
哈希表原理
在无序容器内部分为两步存储，一步是根据哈希函数结果直接定位的桶，另一步是桶内部的链表/树（这一部分通常元素极少）。最核心的就是哈希表通过哈希函数将我们输入的key转换为哈希值，根据该结果映射到桶数组的特定下标，在桶内遍历访问我们要找到的元素。
与其他容器的对比
1. 序列容器（vector/deque/list）
结构：连续内存或链表
查找方式：线性扫描或二分（需先排序）
代价：必须逐个比较元素，直到找到目标
2. 有序关联容器（set/map）
结构：红黑树（平衡二叉搜索树）
查找方式：从根节点向下比较，每次排除一半
代价：需要 log2n 次比较，且每次比较可能涉及指针跳转
3. 无序关联容器（unordered_set/map）
结构：哈希表（桶 + 链表）
查找方式：
计算哈希值 → 直接定位到桶（bucket）
在桶内少量元素中查找
代价：哈希计算 O(1) + 桶内查找（通常 1-2 次比较）
直观一点，画个表格看看时间复杂度的比较，无序容器的优势一目了然^^
| 操作 | vector | set/map(红黑树） | unordered_set/map |
| 查找 | O(n) | O(logn) | 平均O(1) |
| 插入 | 中间O(n)，尾部O(1) | O(logn) | 平均O(1) |
| 删除 | O(n) | O(logn) | 平均O(1) |
| 判存在 | O(n） | O（logn) | 平均O(1) |
平均O(1)的复杂度一定是其他容器望尘莫及的存在。
当数据量达到 1e5 时，O(n) 需要遍历比较 1e5 次，O(logn) 需要比较 17 次，而 O(1) 只需要1 次哈希计算就能精准定位到桶。
实战对比
话不多说，上代码。
1.高频查重
//给定数组，回答 10 万次询问："x 是否在数组中？ #define size 100000 vector<int>queries(size);//十万次查询 // 方法 A：vector vector<int> arr(size) for (int q : queries) { if (find(arr.begin(), arr.end(), q) != arr.end()) ; // O(n) 每次，总复杂度 O(n*m) = 10^10 } // 方法 B：set set<int> s(arr.begin(), arr.end()); for (int q : queries) { if (s.count(q)) ; // O(log n) 每次，总复杂度 O(m*logn) } // 方法 C：unordered_set unordered_set<int> s(arr.begin(), arr.end()); for (int q : queries) { if (s.count(q)) ; // O(1) 每次，总复杂度 O(m) }2.词频统计
// vector + 排序O(n log n) sort(words.begin(), words.end()); // 再线性扫描统计连续相同元素 // map O(n log n) map<string, int> cnt; for (auto& w : words) cnt[w]++; // 每次插入/修改都是 O(log n) // unordered_map O(n) unordered_map<string, int> cnt; for (auto& w : words) cnt[w]++; // 每次 O(1)，总线性时间无序容器简介
一、unordered_set无序集合
无序集合存储不重复的键值，内部基于哈希表实现。提供 O(1) 平均时间的插入、删除和查找。
凭借着高效的增删改查，无序集合非常适合用于维护一个不重复的滑动窗口或者判断存在性，这也是它使用频率较高的地方。它不关注“出现次数”，只关注“存在性”。
特性
1.唯一性
unordered_set<int> s;//声明一个存储int类型的无序集合 s.insert(5); s.insert(5); // 第二次插入无效，s内部元素仍然只有52.无序性
为了追求哈希表的高速，内部通过哈希函数决定顺序，可认为是完全随机
unordered_set<int> s = {3, 1, 4, 1, 5}; for (int x : s) cout << x << ' '; //输出顺序任意，无法提前判断具体操作
1.声明
#include<iostream> #include <unordered_set>//无序集合头文件 using namespace std; unordered_set<int> s; // 存储 int unordered_set<string> strSet; // 存储 string2.插入元素
//单个插入 int x=5; s.insert(x); //返回 pair<iterator, bool>,可以通过返回值来判断插入是否成功 //通常是有重复元素才返回false // 批量插入 vector<int> v = {1, 2, 3}; s.insert(v.begin(), v.end()); //判断插入 for(int&i:v){ if(!s.insert(i).second){ cout<<"有重复";//如果插入失败返回pair<iterator,false>，可通过点运算符直接访问布尔值 } }3.查询元素
unordered_set<int>seen; //count:集合内有该元素时返回1，没有则返回0，平均时间复杂度O(1) for(int i:nums){ if(!seen.count(i)){ cout<<i<<"重复了"<<endl; } seen.insert(i); } //find:返回迭代器，如果集合内有目标元素返回该元素，没有则返回.end() auto it=seen.find(x) //可以通过*it来直接修改集合中的目标元素 if(it!=seen.end())cout<<"有该元素"<<endl; else cout<<"无该元素"<<endl;4.删除元素
s.erase(42); // 按值删除，返回删除个数（0 或 1） s.erase(it); // 按迭代器删除 s.clear(); // 清空所有元素5.容量
s.size(); // 元素个数（不重复的数量） s.empty(); // 是否为空 s.reserve(1000); // 预分配桶数量，避免 rehash适用场景
1.去重
利用它唯一性与插入高效的特点，在不需要关注顺序的情况下，直接利用无序集合复制数组可以达到去重的效果，这是理论上极快的去重，但如果你关注顺序以方便后续的二分等算法，还是sort+unique吧。
//快速无序去重 vector<int> nums = {1, 2, 2, 3, 3, 3}; unordered_set<int> s(nums.begin(), nums.end()); // s 现在包含 {1, 2, 3} vector<int> uniqueNums(s.begin(), s.end()); // 转回 vector（顺序随机） //有序去重 sort(nums.begin(),nums.end()); auto it=unique(nums.begin(),nums.end()); erase(it,nums.end());当然如果不考虑顺序，它将是极方便的思路。
349.两个数组的交集
//给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。 //输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { unordered_set<int>st(nums1.begin(),nums1.end());//set内部自动去重 vector<int>ans; for(const int&i:nums2){ if(st.count(i)){//判断st内部有这个元素 st.erase(i);//去除这个元素，防止重复。因为set内部每个元素只有一次，去除后保证ans内部元素唯一 ans.push_back(i); } } return ans; } };在本题中我们先把nums1复制到st中，顺便去重，然后利用快速判断存在性的特点不断判断nums2中是否有和st相同的元素，即为两个数组的交集。本题中使用无序集合可以让效率提高，这是相比其他容器的优势。
2.存在性查询
以力扣217为例
/*题目：给你一个整数数组 nums 。 如果任一值在数组中出现 至少两次 ，返回 true ； 如果数组中每个元素互不相同，返回 false 。*/ class Solution { public: bool containsDuplicate(vector<int>& nums) { unordered_set<int>seen; for(int i:nums){ if(seen.count(i)){ return true;//有重复直接返回 } seen.insert(i);//插入元素 } return false; } };3.维护滑动窗口
unordered_set中查、增、删的时间复杂度都为O（1），是非常好用的滑动窗口载体。
3.无重复字符的最长字串
//给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。 class Solution { public: int lengthOfLongestSubstring(string s) { unordered_set<char>st; int right=0; int left=0; int ans=0; for(int i=0;i<s.length();i++){ while(st.count(s[right])){//如果新进的字符已经出现，就收缩左边界直到窗口内部字符无重复 st.erase(s[left]);//清除 left++;//收缩 } st.insert(s[i]); right++;//right在循环结束后指向窗口右边界下一个，因此窗口长度为right-left ans=max(ans,(int)st.size());//st.size()返回unsiged类型，显式类型转换一下才可以比较 //st.size()和right-left完全等价，都是窗口长度 } return ans; } };相似的题目还有128.最长连续序列，但两者也有些许区别。
128.最长连续序列
class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int>s(nums.begin(),nums.end());//让无序集合装下nums，直接去重且方便后续的count查找 int ans=0; for(int i:s){ if(s.count(i-1)){ continue;//如果有数字前继，说明此数字一定不是起始点，直接下一个 } int end=i;//设定序列终点 while(s.count(end+1)){//如果终点下一个仍存在，就让end+1，最终end停在最远终点 end++; } ans=max(ans,end-i+1);//i起点，end终点，长度为end-i+1 } return ans; } };3是滑动窗口的直观体现，字符串里每个字符都是连续的，“窗口”相对比较直观。我们需要做的是不断判断新元素的重复性以维护不重复窗口，从而判断长度。
128则是先利用unordered_set的唯一性去重，再通过快速查找目标元素锁定起始点和终点，从而判断出最长的连续序列，可以说是为了unordered_set量身打造的题目。
二、unordered_map无序映射
无序映射存储键值对<const key,value>，将给出的key通过哈希函数算出哈希值，从而对应目标value。它可以提供平均 O(1) 时间的增删查改，是竞赛中最常用的"字典"结构。基于这种特性，常常用于字符频次统计，索引映射等需要映射关系的场景中。
特性
1.键值对存储
无序映射内部存储的是键值对，每个元素都是<const key,value>
#include<unordered_map> unordered_map<string,int>mp; mp["TOM"]=10;//"TOM"是key，映射出10 mp["ccc"]=55;//"ccc"是key，映射出552.唯一性
同一个key只能存储一个value
mp["ccc"]=555;//会把之前的55覆盖掉3.无序性
无序映射和无序集合一样都是无序的，很合理吧，主要意思就是遍历的时候没有固定顺序。
具体操作
1.声明
#include <unordered_map> unordered_map<string, int> mp; // 基本类型 unordered_map<int, vector<int>> graph; // value 是vector<int>类型的2.插入元素
// 方式 A：operator[] mp["apple"] = 5; // 若 "apple" 不存在，会先构造默认值 0，再赋值为 5 // 方式 B：insert mp.insert({"banana", 3}); // 返回 pair<iterator, bool>，bool 表示是否插入成功3.查询元素
int x = mp["grape"]; //危险方法， 若 "grape" 不存在，会自动插入 {grape, 0} //方式 1：count（只查存在性） if (mp.count("apple")) { // 返回 1（存在）或 0（不存在） cout << "存在"; } //和unordered_set还是挺像的。 //推荐使用这种方法，因为不会添加新的键值对污染数据 //方式 2：find（返回迭代器，推荐） auto it = mp.find("apple"); if (it != mp.end()) { cout << "key: " << it->first; // 访问 key（const，不可修改） cout << "value: " << it->second; // 访问 value it->second = 100; // 可以修改 value }值得注意的是：
1.it返回的是键值对的迭代器，所以需要用->first来访问key，->second访问value
2.对于无序映射而言，如果你声明一个先前没有声明的key，它会自动帮你补上value=0
4.删除元素
mp.erase("apple"); // 按 key 删除，返回删除个数（0 或 1） mp.erase(it); // 按迭代器删除 mp.clear(); // 清空一般建议通过迭代器删除
5.遍历方法
无序映射的遍历方式很有意思，主要有三种，酌情自选。
//三种遍历方法 //1.迭代器 for(auto it=map.begin();it!=map.end();it++){ cout<<it->first<<":"<<it->second<<endl;//迭代器->frist指向key,->second指向value } //2.键值对 for(const auto&pair:map){//pair本身就是一个键值对，通过.访问key/value cout<<pair.first<<":"<<pair.second<<endl; } //3.结构绑定 for(const auto&[key,value]:map){//key.value直接把键值对内部的键和值复制出来了 cout<<key<<":"<<value<<endl; }适用场景
1.频次统计
当需要记住某个元素出现的次数时，可以使用mp<type,int>，将元素本身作为key，次数作为value。出现一次时直接mp[key]++，从而统计次数。
350.两个数组的交集II
//给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。 //返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致 //（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。 class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { unordered_map<int,int>mp; vector<int>ans; for(int i:nums1){ mp[i]++;//数值->次数，一次循环map统计数字的出现次数 } for(int i:nums2){ if(mp[i]>0){ mp[i]--;//使用一次就让value-- ans.push_back(i); } } return ans; } };先用map统计nums1中出现的数字及其次数，建立映射关系。再遍历一遍nums2，有重复就让mp中对应的元素--来保证ans内部pb的次数是最小出现次数。
另一题思路类似，也是找到出现次数之间的关系。
383.赎金信
//给你两个字符串：ransomNote 和 magazine //判断 ransomNote 能不能由 magazine 里面的字符构成。 //如果可以，返回 true ；否则返回 false 。 //magazine 中的每个字符只能在 ransomNote 中使用一次。 class Solution { public: bool canConstruct(string ransomNote, string magazine) { unordered_map<char,int>mp; for(int i=0;i<magazine.length();i++){ mp[magazine[i]]++; } for(int j=0;j<ransomNote.length();j++){ if(mp[ransomNote[j]]>0){ mp[ransomNote[j]]--; } else{ return false;//如果不够用即刻处死 } } return true;//bingo^^ } };没啥说的，magazine就是字符仓库，unordered_map统计仓库里面字符类型和数量，最后逐个减少看看是否能够满足消耗需要。
2.分类统计
有些时候我们可以自己设定一个哈希函数，把一类数据哈希成同一个key，从而直接统计一类数据的出现次数。
49.字母异位词分组
//给你一个字符串数组，请你将 字母异位词 组合在一起。 //可以按任意顺序返回结果列表。 class Solution { public: vector<vector<string>> groupAnagrams(vector<string>& strs) { vector<vector<string>>ans; unordered_map<string,vector<string>>mp;//string映射到vector<string>类型 for( string& s:strs){ string s_ans=s;//先记录原始字符串 sort(s.begin(),s.end());//排序，如果排序后相等说明是字母异位词 mp[s].push_back(s_ans);//以排序后的字符串为键，记录排序前的字符串 } //在这里我们就用sort把“字母异位词”哈希成同一个key //再将同一个key映射的value储存到vector<string>内部 for(const auto&pair:mp){ ans.push_back(pair.second); } return ans; } };尾声
感谢你看到这里。
我为这篇文章构思了很久，做了很多准备，写到这里我很开心，希望你也是^^。
