C++ 使用unordered

C++ 使用unordered_set去重

我是不想秃头的Carl
专注于嵌入式软件开发

拥有5年以上路由器、CPE开发经验

概述

在进行WiFi sta搜索ap信息时，遇到有重复ap的情况，使用循环嵌套去重遇到了一些问题，所以改用std::unordered_set。

在处理需要去重的数据集合时，std::unordered_set 是一个高效的工具。它基于哈希表实现，能够快速完成查找和插入操作，适用于需要高性能的场景。

`std::unordered_set` 的详细介绍

定义

std::unordered_set 是 C++ 标准模板库（STL）中的一个容器类，用于存储唯一元素的集合，底层基于 哈希表 实现。

主要特点

元素唯一性：集合中的每个元素都是唯一的，重复元素会被自动忽略。
无序性：元素的存储顺序不固定（由哈希函数决定）。
高效性：查找、插入、删除的平均时间复杂度为 O(1)。
动态大小：集合会根据元素数量动态调整底层哈希表的大小。

常用操作

以下是 std::unordered_set 的常用方法：

方法	描述
`insert(const T& value)`	向集合中插入元素，返回一个 `pair`，指示插入是否成功。
`find(const T& value)`	查找元素，返回指向该元素的迭代器；如果未找到，则返回 `end()`。
`erase(iterator)` / `erase(value)`	删除指定迭代器或值的元素。
`size()`	返回集合中元素的数量。
`clear()`	清空集合中的所有元素。
`empty()`	判断集合是否为空。
`count(const T& value)`	返回集合中某元素的数量（对于 `unordered_set`，结果只能是 0 或 1）。

使用示例

基本用法

#include <iostream>
#include <unordered_set>
using namespace std;int main() {unordered_set<int> mySet;// 插入元素mySet.insert(10);mySet.insert(20);mySet.insert(30);// 重复插入auto result = mySet.insert(10); // 插入失败if (!result.second) {cout << "Element 10 already exists!" << endl;}// 查找元素if (mySet.find(20) != mySet.end()) {cout << "Element 20 found!" << endl;}// 删除元素mySet.erase(20);// 遍历集合for (const auto& elem : mySet) {cout << "Element: " << elem << endl;}return 0;
}

输出

Element 10 already exists!
Element 20 found!
Element: 10
Element: 30

性能分析

时间复杂度：基于哈希表，std::unordered_set 在插入、查找、删除操作上的平均时间复杂度是 O(1)。
适合场景：特别适合需要快速判断元素是否存在（如去重）的场景。
局限性：对于需要元素按顺序排列的场景，可以考虑使用 std::set。

示例场景：WiFi 去重

假设我们有一组 WiFi 扫描结果，每个 AP 信息包含 MAC 地址 和 SSID，需要删除 MAC 地址重复的记录。

实现代码

AP 信息结构体

struct APInfo {string mac;string ssid;
};

改进前的去重方法

void removeDuplicatesOld(list<APInfo>& ap_list) {if (ap_list.size() > 1) {for (auto item = ap_list.begin(); item != prev(ap_list.end(), 1); ++item) {auto it = next(item, 1);while (it != ap_list.end()) {if (it->mac == item->mac) {it = ap_list.erase(it);} else {++it;}}}}
}

改进后的去重方法

#include <unordered_set>void removeDuplicatesNew(list<APInfo>& ap_list) {if (ap_list.size() <= 1) {return;}unordered_set<string> seen_macs;auto it = ap_list.begin();while (it != ap_list.end()) {if (seen_macs.insert(it->mac).second) {++it;} else {it = ap_list.erase(it);}}
}

测试代码

#include <iostream>
#include <list>
#include <string>
#include <chrono>
using namespace std;void testRemoveDuplicates() {list<APInfo> ap_list = {{"00:11:22:33:44:55", "WiFi_1"},{"66:77:88:99:AA:BB", "WiFi_2"},{"00:11:22:33:44:55", "WiFi_1_Duplicate"},{"88:99:AA:BB:CC:DD", "WiFi_3"},{"66:77:88:99:AA:BB", "WiFi_2_Duplicate"}};list<APInfo> ap_list_old = ap_list;list<APInfo> ap_list_new = ap_list;// 测量旧方法时间auto start_old = chrono::high_resolution_clock::now();removeDuplicatesOld(ap_list_old);auto end_old = chrono::high_resolution_clock::now();auto duration_old = chrono::duration_cast<chrono::microseconds>(end_old - start_old);// 测量新方法时间auto start_new = chrono::high_resolution_clock::now();removeDuplicatesNew(ap_list_new);auto end_new = chrono::high_resolution_clock::now();auto duration_new = chrono::duration_cast<chrono::microseconds>(end_new - start_new);// 输出执行时间cout << "Execution time (Old method): " << duration_old.count() << " microseconds" << endl;cout << "Execution time (New method): " << duration_new.count() << " microseconds" << endl;
}void testLargeDataset() {// 构造大规模测试数据list<APInfo> ap_list;for (int i = 0; i < 10000; ++i) {string mac = "00:11:22:33:44:" + to_string(i % 100); // 模拟重复 MACstring ssid = "WiFi_" + to_string(i);ap_list.push_back({mac, ssid});}list<APInfo> ap_list_old = ap_list;list<APInfo> ap_list_new = ap_list;// 测量旧方法时间auto start_old = chrono::high_resolution_clock::now();removeDuplicatesOld(ap_list_old);auto end_old = chrono::high_resolution_clock::now();auto duration_old = chrono::duration_cast<chrono::microseconds>(end_old - start_old);// 测量新方法时间auto start_new = chrono::high_resolution_clock::now();removeDuplicatesNew(ap_list_new);auto end_new = chrono::high_resolution_clock::now();auto duration_new = chrono::duration_cast<chrono::microseconds>(end_new - start_new);// 输出执行时间cout << "Execution time (Old method): " << duration_old.count() << " microseconds" << endl;cout << "Execution time (New method): " << duration_new.count() << " microseconds" << endl;
}

输出

testRemoveDuplicates

Execution time (Old method): 4 microseconds
Execution time (New method): 3 microsecondsAfter removing duplicates (Old method):
MAC: 00:11:22:33:44:55, SSID: WiFi_1
MAC: 66:77:88:99:AA:BB, SSID: WiFi_2
MAC: 88:99:AA:BB:CC:DD, SSID: WiFi_3After removing duplicates (New method):
MAC: 00:11:22:33:44:55, SSID: WiFi_1
MAC: 66:77:88:99:AA:BB, SSID: WiFi_2
MAC: 88:99:AA:BB:CC:DD, SSID: WiFi_3

testLargeDataset

Execution time (Old method): 11109 microseconds
Execution time (New method): 1837 microseconds

性能对比

方法	时间复杂度	特点
旧方法	O(n^2)	逻辑复杂，性能随数据量线性下降
新方法	O(n)	使用哈希表，去重效率显著提升