C++关联式容器详解：map、set与unordered_map

一、核心原理

1. map与set（有序容器）

   • 数据结构：基于红黑树（自平衡二叉搜索树）
   • 特性：
     • 元素按严格弱排序（默认<）自动排序
     • 插入/删除/查找时间复杂度：$O(\log n)$
   • map：存储键值对 (key, value)
   • set：仅存储唯一键 key

2. unordered_map（无序容器）

   • 数据结构：基于哈希表（散列表）
   • 特性：
     • 元素顺序不可控（依赖哈希函数）
     • 平均插入/删除/查找时间复杂度：$O(1)$
     • 最坏情况：$O(n)$（哈希冲突严重时）

二、关键操作对比

操作	map/set	unordered_map
插入	insert()	insert()
查找	find()	find()
删除	erase()	erase()
遍历	有序迭代	无序迭代
自定义排序	支持比较器	不支持
自定义哈希	不支持	需定义哈希函数

三、典型应用场景

1. map示例：词频统计

#include <map>
#include <string>

std::map<std::string, int> wordCount;
for (const auto& word : words) {
    wordCount[word]++; // 自动初始化值为0
}

1. set示例：去重排序

#include <set>
#include <vector>

std::vector<int> nums = {3, 1, 4, 1, 5};
std::set<int> uniqueSet(nums.begin(), nums.end()); // 输出：{1, 3, 4, 5}

1. unordered_map示例：缓存系统

#include <unordered_map>

std::unordered_map<std::string, Data> cache;
if (cache.find(key) == cache.end()) {
    cache[key] = fetchData(); // 快速查找
}

四、性能优化要点

1. map/set：

   • 自定义比较器提升效率

   struct CaseInsensitiveCompare {
       bool operator()(const std::string& a, const std::string& b) const {
           return std::tolower(a[0]) < std::tolower(b[0]);
       }
   };
   std::map<std::string, int, CaseInsensitiveCompare> customMap;
   

2. unordered_map：

   • 预分配桶数量减少冲突

   std::unordered_map<int, std::string> preallocMap;
   preallocMap.reserve(1000); // 预分配空间
   

   • 自定义哈希函数

   struct CustomHash {
       size_t operator()(const MyClass& obj) const {
           return std::hash<int>()(obj.id) ^ std::hash<std::string>()(obj.name);
       }
   };
   

五、选择策略

1. 需有序遍历或范围查询：选map/set
2. 追求极致查找速度且不要求顺序：选unordered_map
3. 内存敏感场景：红黑树（map/set）通常比哈希表更省内存

注意：unordered_map的迭代器失效规则与map不同，插入操作可能导致全部迭代器失效（桶重建时）。