跳到主要内容C++ STL unordered_set/unordered_map 使用介绍 | 极客日志C++算法
C++ STL unordered_set/unordered_map 使用介绍
本文详细介绍了 C++ STL 中无序关联容器 unordered_set 和 unordered_map 的使用方法。内容包括容器的模板参数解析、常见构造方式、容量查询、元素访问与修改接口、哈希桶操作及负载因子策略。同时对比了 unordered_set/map 与有序容器 set/map 在底层实现、迭代器特性及时间复杂度上的核心差异，并通过百万级数据测试验证了哈希表在增删查操作中的平均 O(1) 性能优势。
路由之心1 浏览 前言
本文学习 C++ STL 中的无序关联容器 unordered_set 和 unordered_map。相比基于红黑树的有序容器，它们主打 O(1) 的平均时间复杂度，适合对性能要求高且不需要有序遍历的场景。
unordered_set
一、介绍
unordered_set 是 C++ STL 中的无序集合容器，底层基于哈希表实现。
template<class Key,
class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Alloc = allocator<Key>
class unordered_set;
模板参数说明：
- Key（键类型）：存储的键的类型。
- Hash（哈希函数）：默认
hash<Key>，计算键的哈希值。
- Pred（相等比较器）：默认
equal_to<Key>，判断两个键是否相等。
- Alloc（内存分配器）：默认
allocator<Key>，管理内存。
若需自定义内存管理或哈希规则，可传入自定义仿函数或分配器。
unordered_set 的功能主要分为成员函数和非成员函数重载两部分，涵盖构造销毁、容量查询、迭代器获取、元素查找修改、桶操作及哈希策略控制等。
二、接口
1. 常见的构造
#include <iostream>
#include <string>
#include <unordered_set>
template<class T>
T cmerge(T a, T b) {
T t(a);
t.insert(b.begin(), b.end());
return t;
}
{
std::unordered_set<std::string> first;
;
;
;
;
;
( std::string& x : sixth) {
std::cout << << x;
}
std::cout << std::endl;
;
}
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown 转 HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
- HTML 转 Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
int main()
std::unordered_set<std::string> second({"red", "green", "blue"})
std::unordered_set<std::string> third({"orange", "pink", "yellow"})
std::unordered_set<std::string> fourth(second)
std::unordered_set<std::string> fifth(cmerge(third, fourth))
std::unordered_set<std::string> sixth(fifth.begin(), fifth.end())
for
const
" "
return
0
2. 容量的操作
std::unordered_set::size
#include <iostream>
#include <string>
#include <unordered_set>
int main() {
std::unordered_set<std::string> myset;
std::cout << "0. size: " << myset.size() << std::endl;
myset = {"milk", "potatoes", "eggs"};
std::cout << "插入 3 个元素后 size: " << myset.size() << std::endl;
myset.insert("pineapple");
std::cout << "再插入 1 个元素后 size: " << myset.size() << std::endl;
myset.erase("milk");
std::cout << "删除 1 个元素后 size: " << myset.size() << std::endl;
return 0;
}
std::unordered_set::empty
#include <iostream>
#include <string>
#include <unordered_set>
int main() {
std::unordered_set<std::string> first;
std::unordered_set<std::string> second = {"alpha", "beta", "gamma"};
std::cout << "first " << (first.empty() ? "is empty" : "is not empty") << std::endl;
std::cout << "second " << (second.empty() ? "is empty" : "is not empty") << std::endl;
return 0;
}
3. 访问的操作
std::unordered_set::find
查找元素，返回指向该元素的迭代器，未找到返回 end()。
#include <iostream>
#include <string>
#include <unordered_set>
int main() {
std::unordered_set<std::string> myset = {"red", "green", "blue"};
std::string input;
std::cout << "color? ";
getline(std::cin, input);
auto got = myset.find(input);
if (got == myset.end()) {
std::cout << "未在 myset 容器中找到该元素";
} else {
std::cout << *got << "在 myset 容器中";
}
std::cout << std::endl;
return 0;
}
std::unordered_set::count
返回元素在容器中出现的次数（对于 set 类容器，只能是 0 或 1）。
#include <iostream>
#include <string>
#include <unordered_set>
int main() {
std::unordered_set<std::string> myset = {"hat", "umbrella", "suit"};
for (auto& x : {"hat", "sunglasses", "suit", "t-shirt"}) {
if (myset.count(x) > 0) {
std::cout << "myset has " << x << std::endl;
} else {
std::cout << "myset has no " << x << std::endl;
}
}
return 0;
}
4. 修改的操作
std::unordered_set::clear
#include <iostream>
#include <string>
#include <unordered_set>
int main() {
std::unordered_set<std::string> myset = {"chair", "table", "lamp", "sofa"};
for (const std::string& x : myset) {
std::cout << " " << x;
}
std::cout << std::endl;
myset.clear();
myset.insert("bed");
myset.insert("wardrobe");
myset.insert("nightstand");
for (const std::string& x : myset) {
std::cout << " " << x;
}
std::cout << std::endl;
return 0;
}
std::unordered_set::swap
#include <iostream>
#include <string>
#include <unordered_set>
int main() {
std::unordered_set<std::string> first = {"iron", "copper", "oil"};
std::unordered_set<std::string> second = {"wood", "corn", "milk"};
first.swap(second);
std::cout << "交换后 first 容器:";
for (const std::string& x : first) std::cout << " " << x;
std::cout << std::endl;
std::cout << "交换后 second 容器:";
for (const std::string& x : second) std::cout << " " << x;
std::cout << std::endl;
return 0;
}
std::unordered_set::insert
支持拷贝插入、移动插入、范围插入和初始化列表插入。
#include <iostream>
#include <string>
#include <array>
#include <unordered_set>
int main() {
std::unordered_set<std::string> myset = {"yellow", "green", "blue"};
std::array<std::string, 2> myarray = {"black", "white"};
std::string mystring = "red";
myset.insert(mystring);
myset.insert(mystring + "dish");
myset.insert(myarray.begin(), myarray.end());
myset.insert({"purple", "orange"});
for (const std::string& x : myset) {
std::cout << " " << x;
}
std::cout << std::endl;
return 0;
}
std::unordered_set::erase
#include <iostream>
#include <string>
#include <unordered_set>
int main() {
std::unordered_set<std::string> myset = {"Canada", "France", "UK", "China", "Japan", "Germany", "Italy"};
myset.erase(myset.begin());
myset.erase("France");
myset.erase(myset.find("Japan"), myset.end());
for (const std::string& x : myset) {
std::cout << " " << x;
}
std::cout << std::endl;
return 0;
}
std::unordered_set::emplace
#include <iostream>
#include <string>
#include <unordered_set>
int main() {
std::unordered_set<std::string> myset;
myset.emplace("potatoes");
myset.emplace("milk");
myset.emplace("flour");
for (const std::string& x : myset) {
std::cout << " " << x;
}
std::cout << std::endl;
return 0;
}
5. 哈希桶操作
std::unordered_set::bucket_count
#include <iostream>
#include <string>
#include <unordered_set>
int main() {
std::unordered_set<std::string> myset = {"Mercury", "Venus", "Earth", "Mars", "Jupiter", "Saturn", "Uranus", "Neptune"};
unsigned n = myset.bucket_count();
std::cout << "myset 容器中有" << n << "个哈希桶\n";
for (unsigned i = 0; i < n; ++i) {
std::cout << "bucket #" << i << " 中的内容是:";
for (auto it = myset.begin(i); it != myset.end(i); ++it) {
std::cout << " " << *it;
}
std::cout << "\n";
}
return 0;
}
std::unordered_set::bucket_size
#include <iostream>
#include <string>
#include <unordered_set>
int main() {
std::unordered_set<std::string> myset = {"red", "green", "blue", "yellow", "purple", "pink"};
unsigned nbuckets = myset.bucket_count();
std::cout << "myset 容器中有" << nbuckets << "个哈希桶\n";
for (unsigned i = 0; i < nbuckets; ++i) {
std::cout << "bucket #" << i << " 有 " << myset.bucket_size(i) << " 个元素\n";
}
return 0;
}
std::unordered_set::bucket
#include <iostream>
#include <string>
#include <unordered_set>
int main() {
std::unordered_set<std::string> myset = {"water", "sand", "ice", "foam"};
for (const std::string& x : myset) {
std::cout << x << " 是在哈希桶的 #" << myset.bucket(x) << std::endl;
}
return 0;
}
6. 哈希的策略
std::unordered_set::load_factor
获取当前负载因子（size / bucket_count），反映哈希表拥挤程度。
#include <iostream>
#include <unordered_set>
int main() {
std::unordered_set<int> myset;
std::cout << "size = " << myset.size() << std::endl;
std::cout << "bucket_count = " << myset.bucket_count() << std::endl;
std::cout << "load_factor = " << myset.load_factor() << std::endl;
std::cout << "max_load_factor = " << myset.max_load_factor() << std::endl;
return 0;
}
std::unordered_set::rehash
#include <iostream>
#include <string>
#include <unordered_set>
int main() {
std::unordered_set<std::string> myset;
myset.rehash(12);
myset.insert("office");
myset.insert("house");
myset.insert("gym");
myset.insert("parking");
myset.insert("highway");
std::cout << "现在的 bucket_count: " << myset.bucket_count() << std::endl;
return 0;
}
std::unordered_set::reserve
#include <iostream>
#include <string>
#include <unordered_set>
int main() {
std::unordered_set<std::string> myset;
myset.reserve(5);
myset.insert("office");
myset.insert("house");
myset.insert("gym");
myset.insert("parking");
myset.insert("highway");
for (const std::string& x : myset) {
std::cout << " " << x;
}
std::cout << std::endl;
return 0;
}
unordered_map
一、介绍
unordered_map 是 C++ STL 中的无序映射容器，底层基于哈希表实现，存储键值对。
template<class Key,
class T,
class Hash = hash<Key>,
class Pred = equal_to<Key>,
class Alloc = allocator<pair<const Key, T>>
class unordered_map;
- Key（键类型）：键的类型。
- T（映射值类型）：值的类型。
- Hash（哈希函数）：默认
hash<Key>。
- Pred（相等比较器）：默认
equal_to<Key>。
- Alloc（内存分配器）：默认
allocator<pair<const Key, T>>。
二、接口
1. 常用的构造
#include <iostream>
#include <string>
#include <unordered_map>
typedef std::unordered_map<std::string, std::string> stringmap;
stringmap merge(stringmap a, stringmap b) {
stringmap temp(a);
temp.insert(b.begin(), b.end());
return temp;
}
int main() {
stringmap first;
stringmap second = {{"apple", "red"}, {"lemon", "yellow"}};
stringmap third = {{"orange", "orange"}, {"strawberry", "red"}};
stringmap fourth(second);
stringmap fifth(merge(third, fourth));
stringmap sixth(fifth.begin(), fifth.end());
for (auto& x : sixth) {
std::cout << " " << x.first << ":" << x.second;
}
std::cout << std::endl;
return 0;
}
2. 容量的操作
std::unordered_map::size
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, double> mymap = {{"milk", 2.30}, {"potatoes", 1.90}, {"eggs", 0.40}};
std::cout << "mymap.size() is " << mymap.size() << std::endl;
for (const auto& pair : mymap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
return 0;
}
std::unordered_map::empty
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, int> first;
std::unordered_map<int, int> second = {{1, 10}, {2, 20}, {3, 30}};
std::cout << "first " << (first.empty() ? "is empty" : "is not empty") << std::endl;
std::cout << "second " << (second.empty() ? "is empty" : "is not empty") << std::endl;
return 0;
}
3. 访问的操作
std::unordered_map::operator[]
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, std::string> mymap;
mymap["Bakery"] = "Barbara";
mymap["Seafood"] = "Lisa";
mymap["Produce"] = "John";
std::string name = mymap["Bakery"];
mymap["Seafood"] = name;
mymap["Bakery"] = mymap["Produce"];
for (auto& x : mymap) {
std::cout << x.first << ": " << x.second << std::endl;
}
return 0;
}
std::unordered_map::at
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> mymap = {{"Mars", 3000}, {"Saturn", 60000}, {"Jupiter", 70000}};
mymap.at("Mars") = 3396;
mymap.at("Saturn") += 272;
mymap.at("Jupiter") = mymap.at("Saturn") + 9638;
for (auto& x : mymap) {
std::cout << x.first << ": " << x.second << std::endl;
}
return 0;
}
std::unordered_map::find
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, double> mymap = {{"mom", 5.4}, {"dad", 6.1}, {"bro", 5.9}};
std::string input;
std::cout << "who? ";
getline(std::cin, input);
auto got = mymap.find(input);
if (got == mymap.end()) {
std::cout << "没有找到";
} else {
std::cout << got->first << " 是 " << got->second;
}
std::cout << std::endl;
return 0;
}
std::unordered_map::count
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, double> mymap = {{"Burger", 2.99}, {"Fries", 1.99}, {"Soda", 1.50}};
for (auto& x : {"Burger", "Pizza", "Salad", "Soda"}) {
if (mymap.count(x) > 0) {
std::cout << "mymap 容器中有 " << x << std::endl;
} else {
std::cout << "mymap 容器中没有" << x << std::endl;
}
}
return 0;
}
4. 修改的操作
std::unordered_map::clear
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, std::string> mymap = {{"house", "房子"}, {"car", "汽车"}, {"grapefruit", "西柚"}};
for (auto& x : mymap) {
std::cout << " " << x.first << "=" << x.second;
}
std::cout << std::endl;
mymap.clear();
mymap["hello"] = "你好";
mymap["sun"] = "太阳";
for (auto& x : mymap) {
std::cout << " " << x.first << "=" << x.second;
}
std::cout << std::endl;
return 0;
}
std::unordered_map::swap
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, std::string> first = {{"Star Wars", "G. Lucas"}, {"Alien", "R. Scott"}, {"Terminator", "J. Cameron"}};
std::unordered_map<std::string, std::string> second = {{"Inception", "C. Nolan"}, {"Donnie Darko", "R. Kelly"}};
first.swap(second);
std::cout << "first: ";
for (auto& x : first) {
std::cout << x.first << " (" << x.second << "), ";
}
std::cout << std::endl;
std::cout << "second: ";
for (auto& x : second) {
std::cout << x.first << " (" << x.second << "), ";
}
std::cout << std::endl;
return 0;
}
std::unordered_map::insert
同 unordered_set，支持多种插入方式。
#include <iostream>
#include <string>
#include <array>
#include <unordered_map>
int main() {
std::unordered_map<std::string, std::string> mymap;
mymap.insert({{"A", "a"}, {"B", "b"}});
std::cout << mymap.size() << std::endl;
return 0;
}
std::unordered_map::erase
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, std::string> mymap;
mymap["U.S."] = "Washington";
mymap["U.K."] = "London";
mymap["France"] = "Paris";
mymap.erase(mymap.begin());
mymap.erase("France");
mymap.erase(mymap.find("Germany"), mymap.end());
for (auto& x : mymap) {
std::cout << x.first << ": " << x.second << std::endl;
}
return 0;
}
std::unordered_map::emplace
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, std::string> mymap;
mymap.emplace("NCC-1701", "J.T. Kirk");
mymap.emplace("NCC-1701-D", "J.L. Picard");
mymap.emplace("NCC-74656", "K. Janeway");
for (auto& x : mymap) {
std::cout << x.first << ": " << x.second << std::endl;
}
return 0;
}
5. 哈希桶操作
std::unordered_map::bucket_count
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, std::string> mymap = {{"house", "房子"}, {"apple", "苹果"}, {"tree", "树"}, {"book", "书"}, {"door", "门"}, {"grapefruit", "西柚"}};
unsigned n = mymap.bucket_count();
std::cout << "mymap 容器中有" << n << " 个哈希桶\n";
for (unsigned i = 0; i < n; ++i) {
std::cout << "bucket #" << i << " contains: ";
for (auto it = mymap.begin(i); it != mymap.end(i); ++it) {
std::cout << "[" << it->first << ":" << it->second << "] ";
}
std::cout << "\n";
}
return 0;
}
std::unordered_map::bucket_size
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, std::string> mymap = {{"house", "房子"}, {"apple", "苹果"}, {"tree", "树"}, {"book", "书"}, {"door", "门"}, {"grapefruit", "西柚"}};
unsigned nbuckets = mymap.bucket_count();
std::cout << "mymap 容器中有 " << nbuckets << "个哈希桶\n";
for (unsigned i = 0; i < nbuckets; ++i) {
std::cout << "bucket #" << i << " 有 " << mymap.bucket_size(i) << "个元素\n";
}
return 0;
}
std::unordered_map::bucket
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, std::string> mymap = {{"us", "United States"}, {"uk", "United Kingdom"}, {"fr", "France"}, {"cn", "China"}};
for (auto& x : mymap) {
std::cout << "元素 [" << x.first << ":" << x.second << "] 是在 bucket #" << mymap.bucket(x.first) << std::endl;
}
return 0;
}
6. 哈希的策略
std::unordered_map::load_factor
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, int> mymap;
std::cout << "size = " << mymap.size() << std::endl;
std::cout << "bucket_count = " << mymap.bucket_count() << std::endl;
std::cout << "load_factor = " << mymap.load_factor() << std::endl;
std::cout << "max_load_factor = " << mymap.max_load_factor() << std::endl;
return 0;
}
std::unordered_map::rehash
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, std::string> mymap;
mymap.rehash(12);
mymap.insert({{"office", "办公室"}, {"house", "房子"}, {"gym", "健身房"}, {"parking", "停车场"}, {"highway", "高速公路"}});
std::cout << "当前的 bucket_count: " << mymap.bucket_count() << std::endl;
return 0;
}
std::unordered_map::reserve
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, std::string> mymap;
mymap.reserve(6);
mymap["house"] = "房子";
mymap["apple"] = "苹果";
mymap["tree"] = "树";
mymap["book"] = "书";
mymap["door"] = "门";
mymap["grapefruit"] = "西柚";
for (auto& x : mymap) {
std::cout << x.first << ": " << x.second << std::endl;
}
return 0;
}
功能差异
一、unordered_set
1. unordered_set 模板参数的解析
unordered_set 对 Key 有三类核心需求：
- 哈希转换需求：要求
Key 能通过 hash<Key> 转换为整数哈希值。
- 相等比较需求：要求
Key 支持 == 比较。
- 内存分配需求：通过
allocator<Key> 申请内存。
2. unordered_set 与 set 的功能差异
- 对 Key 的约束差异：
set 要求 Key 支持小于比较（operator<），底层为红黑树；unordered_set 要求 Key 可哈希且可相等比较，底层为哈希表。
- 迭代器的差异：
set 迭代器为双向迭代器，遍历有序；unordered_set 迭代器为单向迭代器，遍历无序。
- 性能差异：
set 增删查复杂度为 O(log N)；unordered_set 平均复杂度为 O(1)。
二、unordered_map
1. unordered_map 模板参数的解析
unordered_map 存储 pair<const Key, T>，模板参数围绕键的哈希、相等比较和内存管理展开。
2. unordered_map 与 map 的功能差异
- 对 Key 的约束差异：
map 要求 Key 支持小于比较；unordered_map 要求 Key 可哈希且可相等比较。
- 迭代器的差异：
map 迭代器为双向迭代器，遍历有序；unordered_map 迭代器为单向迭代器，遍历无序。
- 性能差异：
map 增删查改复杂度为 O(log N)；unordered_map 平均复杂度为 O(1)，多数场景下效率更高。
性能对决
测试文件：Test.h
#include <iostream>
#include <set>
#include <unordered_set>
#include <vector>
#include <ctime>
using namespace std;
int test_set() {
const size_t N = 1000000;
srand(unsigned(int(time(0))));
set<int> rb_s;
unordered_set<int> ht_s;
vector<int> v;
v.reserve(N);
for (size_t i = 0; i < N; ++i) {
v.push_back(rand() + i);
}
cout << "------------插入性能对比------------" << endl;
size_t begin1 = clock();
for (auto it : v) {
rb_s.insert(it);
}
size_t end1 = clock();
cout << "set insert:" << end1 - begin1 << "ms" << endl;
size_t begin2 = clock();
ht_s.reserve(N);
for (auto it : v) {
ht_s.insert(it);
}
size_t end2 = clock();
cout << "unordered_set insert:" << end2 - begin2 << "ms" << endl;
cout << "插入数据个数：" << rb_s.size() << endl;
cout << "插入数据个数：" << ht_s.size() << endl << endl;
cout << "------------查找性能对比------------" << endl;
int m1 = 0;
size_t begin3 = clock();
for (auto it : v) {
auto ret = rb_s.find(it);
if (ret != rb_s.end()) {
++m1;
}
}
size_t end3 = clock();
cout << "set find:" << end3 - begin3 << "ms--->" << "查找的节点的数量是" << m1 << endl;
int m2 = 0;
size_t begin4 = clock();
for (auto e : v) {
auto ret = ht_s.find(e);
if (ret != ht_s.end()) {
++m2;
}
}
size_t end4 = clock();
cout << "unordered_set find:" << end4 - begin4 << "ms--->" << "查找的节点的数量是" << m2 << endl << endl;
cout << "------------删除性能对比------------" << endl;
size_t begin5 = clock();
for (auto it : v) {
rb_s.erase(it);
}
size_t end5 = clock();
cout << "set erase:" << end5 - begin5 << "ms" << endl;
size_t begin6 = clock();
for (auto it : v) {
ht_s.erase(it);
}
size_t end6 = clock();
cout << "unordered_set erase:" << end6 - begin6 << "ms" << endl << endl;
return 0;
}
int main() {
test_set();
return 0;
}
