C++萌新求快速对 std::vector<std::string>去重(string 是"数字")
csfreshman · 2022-10-25 23:59:13 +08:00 · 1945 次点击这是一个创建于 741 天前的主题，其中的信息可能已经有所发展或是发生改变。
遇到一个问题是需要遍历 std::vectorstd::string,string 内容可能重复，需要过滤，对每一个 string 执行一个处理逻辑，伪代码：
std::vector<std::string> vec;
for(auto str:vec)
{
if(xxxx.find(str) == xxxx.end())
{
//first match,handle
handle();
xxxx.insert(str);
} else {
//noting to do
}
}
我写了两个方案，晚上学习了 benchmark 写法，写了对比下，居然是先转成整数速度快一些？ https://quick-bench.com/q/MJ4zzU3S5LIhGHd8qlgwBNRAOEc String_dup_set 和 String_dup_atoi ，第一个写法可能再向 set 中插入的时候触发了构造？ 请教大家，有没有更优雅，更快速的方法，最好 c++14 支持（当前项目代码不支持 17 20 ）
 |
1
yuruizhe 2022-10-26 00:59:02 +08:00 via iPhone
先排序，再从尾部一个一个删元素？
|
 |
2
lanmiao 2022-10-26 01:02:42 +08:00
因为你的测试字符串，就是专门为 String_dup_atoi 准备的，set<int> 相比 set<string> 在 计算 hash 、相等判断当然快啦。
你改成随机字符串，String_dup_atoi 还能用？ |
 |
3
wevsty 2022-10-26 02:06:38 +08:00
std::unordered_set 默认使用 std::hash ，但 std::hash 某些编译器上的实现不够优良比较容易产生冲撞。建议是自己指定一个合适的 hash 算法，或者直接用 std::set 。
既然知道是 copy 产生了开销，那就尽量避免 copy 。 for(auto str:vec) 这里的 str 可能会产生复制，不如写成 for(auto &str:vec) 如果确定 string 内的内容一定是数字，那么先转换成 int 确实是更划算的选项，因为你每次 insert 都必然会复制对象，复制 int 毫无疑问比复制一个 std::string 更快 最后，代码风格上我个人不建议驼峰和下划线一起用，要么统一驼峰，要么统一下划线。 |
|
4
wevsty 2022-10-26 02:51:24 +08:00
|
 |
5
GeruzoniAnsasu 2022-10-26 04:12:10 +08:00
你这个 bench 也太不严谨了……
https://quick-bench.com/q/lbS2mpw9mSu7EbyfG_57FMsb9Iw 但其实 quick bench 本来也 bench 个寂寞，没有火焰图的 profiling 都是脑补空气，甚至瓶颈在算法本身呢还是内存分配呢，不知道的 |
 |
6
csfreshman OP @GeruzoniAnsasu 学习了，我明天看下，多谢
|
|
7
csfreshman OP @wevsty for(auto &str:vec) 这里现在线上跑的有优化，vec 的量这里我加监控统计，平均 1500 左右，明天研究下你写的那个 bench ，多谢
|
 |
8
whi147 2022-10-27 08:47:54 +08:00 via iPhone
转为 std::set 不行吗
|
|
9
whi147 2022-10-27 08:48:38 +08:00 via iPhone
利用 hash 特性去重
|
Select Language