C++中unordered_map与unordered_set的使用
作者：袖梨
2026-07-23
1. unordered_set系列的使用
1.1 unordered_set和unordered_multiset参考文档
参考文档
1.2 unordered_set类的介绍
- unordered_set的声明如下，Key就是unordered_set底层关键字的类型
- unordered_set默认要求Key支持转换为整形，如果不支持或者想按自己的需求走可以自行实现支持将Key转成整形的仿函数传给第二个模板参数
- unordered_set默认要求Key支持比较相等，如果不支持或者想按自己的需求走可以自行实现支持将Key比较相等的仿函数传给第三个模板参数
- unordered_set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第四个参数。
- 一般情况下，我们都不需要传后三个模板参数
- unordered_set底层是用哈希桶实现，增删查平均效率是 ，迭代器遍历不再有序，为了跟set区分，所以取名unordered_set。O(1)
- 前面部分我们已经学习了set容器的使用，set和unordered_set的功能高度相似，只是底层结构不同，有一些性能和使用的差异，这里我们只讲他们的差异部分。
// unordered_set模板声明：一个不保证元素顺序的集合容器
template <
class Key, // 键与值的类型(因为是集合，键就是值)
// 例如：unordered_set<int>, unordered_set<string>
class Hash = hash<Key>, // 哈希函数对象类型,用于计算元素的哈希值
// 默认使用标准库的hash
class Pred = equal_to<Key>, // 判断两个键是否相等的函数对象类型
// 默认使用标准库的equal_to
class Alloc = allocator<Key> // 内存分配器类型
// 默认使用标准分配器allocator
>
class unordered_set;
1.3 unordered_set和set的使用差异
- 查看文档我们会发现unordered_set的支持增删查且跟set的使用一模一样，关于使用我们这里就不再赘述和演示了。
- unordered_set和set的第一个差异是对key的要求不同，set要求Key支持小于比较，而unordered_set要求Key支持转成整形且支持等于比较，要理解unordered_set的这个两点要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。
- unordered_set和set的第二个差异是迭代器的差异，set的iterator是双向迭代器，unordered_set是单向迭代器，其次set底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以set迭代器遍历是有序+去重。而unordered_set底层是哈希表，迭代器遍历是无序+去重。
- unordered_set和set的第三个差异是性能的差异，整体而言大多数场景下，unordered_set的增删查改更快一些，因为红黑树增删查改效率是 ，而哈希表增删查平均效率是 ，具体可以参看下面代码的演示的对比差异。
// 插入函数：插入元素到容器 // 参数：待插入的值 // 返回：pair<迭代器,bool> // 迭代器指向插入位置或已存在元素位置 // bool为true表示插入成功,false表示已存在 pair<iterator,bool> insert(const value_type& val); // 删除函数：删除指定key的元素 // 参数：要删除的key // 返回：删除的元素个数(0表示元素不存在,1表示删除成功) size_type erase(const key_type& k); // 查找函数：查找指定key的元素 // 参数：要查找的key // 返回：指向找到元素的迭代器,未找到返回end() iterator find(const key_type& k);
#include<unordered_set> // 无序集合容器
#include<unordered_map> // 无序映射容器
#include<set> // 有序集合容器
#include<iostream>
using namespace std;
int test_set2()
{
const size_t N = 1000000; // 测试数据量100万
unordered_set<int> us; // 声明无序集合
set<int> s; // 声明有序集合
vector<int> v; // 存储测试数据的vector
v.reserve(N); // 预留空间,避免动态扩容
srand(time(0)); // 随机种子
// 生成测试数据
for (size_t i = 0; i < N; ++i)
{
//v.push_back(rand()); // N较大时重复值较多
v.push_back(rand()+i); // 加上i使重复值较少
//v.push_back(i); // 完全有序无重复
}
// 测试set的插入性能
size_t begin1 = clock();
for (auto e : v)
{
s.insert(e);
}
size_t end1 = clock();
cout << "set insert:" << end1 - begin1 << endl;
// 测试unordered_set的插入性能
size_t begin2 = clock();
us.reserve(N); // 预留空间,避免rehash
for (auto e : v)
{
us.insert(e);
}
size_t end2 = clock();
cout << "unordered_set insert:" << end2 - begin2 << endl;
// 测试set的查找性能
int m1 = 0; // 记录查找成功次数
size_t begin3 = clock();
for (auto e : v)
{
auto ret = s.find(e);
if (ret != s.end()) // 找到元素
{
++m1;
}
}
size_t end3 = clock();
cout << "set find:" << end3 - begin3 << "->" << m1 << endl;
// 测试unordered_set的查找性能
int m2 = 0; // 记录查找成功次数
size_t begin4 = clock();
for (auto e : v)
{
auto ret = us.find(e);
if (ret != us.end()) // 找到元素
{
++m2;
}
}
size_t end4 = clock();
cout << "unorered_set find:" << end4 - begin4 << "->" << m2 << endl;
// 输出实际插入数据量(因为有重复值,所以小于N)
cout << "插入数据个数：" << s.size() << endl;
cout << "插入数据个数：" << us.size() << endl << endl;
// 测试set的删除性能
size_t begin5 = clock();
for (auto e : v)
{
s.erase(e);
}
size_t end5 = clock();
cout << "set erase:" << end5 - begin5 << endl;
// 测试unordered_set的删除性能
size_t begin6 = clock();
for (auto e : v)
{
us.erase(e);
}
size_t end6 = clock();
cout << "unordered_set erase:" << end6 - begin6 << endl << endl;
return 0;
}
int main()
{
test_set2(); // 执行性能测试
return 0;
}
1.4 unordered_map和map的使用差异
- 查看文档我们会发现unordered_map的支持增删查改且跟map的使用一模一样，关于使用我们这里就不再赘述和演示了。
- unordered_map和map的第一个差异是对key的要求不同，map要求Key支持小于比较，而unordered_map要求Key支持转成整形且支持等于比较，要理解unordered_map的这个两点要求得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。
- unordered_map和map的第二个差异是迭代器的差异，map的iterator是双向迭代器，unordered_map是单向迭代器，其次map底层是红黑树，红黑树是二叉搜索树，走中序遍历是有序的，所以map迭代器遍历是Key有序+去重。而unordered_map底层是哈希表，迭代器遍历是Key无序+去重。
- unordered_map和map的第三个差异是性能的差异，整体而言大多数场景下，unordered_map的增删查改更快一些，因为红黑树增删查改效率是 ，而哈希表增删查平均效率是 ，具体可以参看下面代码的演示的对比差异。
// 插入函数 // 参数：要插入的键值对或元素值 // 返回：pair<迭代器,bool>组合 // 迭代器指向插入位置或已存在元素位置 // bool表示是否插入成功(true插入成功,false表示已存在) pair<iterator,bool> insert(const value_type& val); // 删除函数 // 参数：要删除元素的key // 返回：实际删除的元素个数 // 对于set/map返回0(不存在)或1(删除成功) size_type erase(const key_type& k); // 查找函数 // 参数：要查找的key // 返回：指向找到元素的迭代器 // 如果没找到返回end()迭代器 iterator find(const key_type& k); // map中的[]运算符重载 // 参数：关键字key // 返回：key对应的value的引用 // 特点：如果key不存在则自动插入,value默认初始化 mapped_type& operator[](const key_type& k);
1.5 unordered_multimap/unordered_multiset
- unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似，支持Key冗余。
- unordered_multimap/unordered_multiset跟multimap/multiset的差异也是三个方面的差异，key的要求的差异，iterator及遍历顺序的差异，性能的差异。
1.6 UnOrderedMap.h代码实现
UnOrderedMap.h
#pragma once // 防止头文件被重复包含
#include"HashTable.h" // 引入哈希表的实现
namespace bit
{
// unordered_map类模板，实现键值对的无序映射
template<class K, class V>
class unordered_map
{
// 仿函数类，用于从pair中提取key值
struct MapKeyOfT
{
// 重载()运算符，返回pair中的first成员(键值)
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
// 使用类型别名简化迭代器类型的书写
// 注意这里的模板参数：
// K: 键类型
// pair<K,V>: 实际存储的值类型(键值对)
// MapKeyOfT: 提取键的仿函数
typedef typename hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT>::iterator iterator;
// 返回容器的起始迭代器
iterator begin()
{
return _ht.begin();
}
// 返回容器的结束迭代器
iterator end()
{
return _ht.end();
}
// 插入键值对
// 参数kv: 要插入的键值对
// 返回值: 插入是否成功
bool insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
private:
// 底层哈希表对象
// K: 键类型
// pair<K,V>: 存储的值类型
// MapKeyOfT: 提取键的仿函数
hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT> _ht;
};
}
1.7 UnOrderedSet.h代码实现
UnOrderedSet.h
#pragma once // 防止头文件被重复包含
#include"HashTable.h" // 引入哈希表的实现
namespace bit
{
// unordered_set类模板，实现无序集合
// 特点：不重复、无序、只存储key
template<class K>
class unordered_set
{
// 仿函数类，用于返回key值本身
// 因为set只存储key，所以key和value是同一个值
struct SetKeyOfT
{
// 重载()运算符，直接返回key
const K& operator()(const K& key)
{
return key;
}
};
public:
// 使用类型别名简化迭代器类型的书写
// 注意这里的模板参数：
// K: 键类型
// K: 值类型(与键相同)
// SetKeyOfT: 提取键的仿函数
typedef typename hash_bucket::HashTable<K, K, SetKeyOfT>::iterator iterator;
// 返回容器的起始迭代器
iterator begin()
{
return _ht.begin();
}
// 返回容器的结束迭代器
iterator end()
{
return _ht.end();
}
// 插入元素
// 参数key: 要插入的值
// 返回值: 插入是否成功（如果元素已存在则返回false）
bool insert(const K& key)
{
return _ht.Insert(key);
}
private:
// 底层哈希表对象
// K: 键类型
// K: 值类型(与键相同)
// SetKeyOfT: 提取键的仿函数
hash_bucket::HashTable<K, K, SetKeyOfT> _ht;
};
}
