std::unordered_set 是检测第一个重复字符最直接高效的方法:遍历字符串,用 insert() 返回值判断是否已存在,首次返回 false 即得第一个重复字符,时间复杂度 O(n),空间 O(min(m,n))。

用 std::unordered_set 检测第一个重复字符最直接
如果目标是快速找出字符串中**第一个出现的重复字符**(比如 "abccba" 返回 'c'),std::unordered_set 是最常用且高效的选择。它平均 O(1) 插入和查找,整体时间复杂度 O(n),空间 O(min(m, n)),其中 m 是字符集大小。
常见错误是用 std::set 替代 —— 它带排序开销,纯属浪费;或者遍历时用 find() 后再 insert(),其实 insert() 的返回值就能直接判断是否已存在:
char firstRepeatingChar(const std::string& s) {
std::unordered_set<char> seen;
for (char c : s) {
if (!seen.insert(c).second) { // insert() 返回 pair<iterator bool>,second 为 false 表示已存在
return c;
}
}
return '\0'; // 无重复
}</iterator></char>
注意:该方法对大小写敏感,'A' 和 'a' 被视为不同字符;若需忽略大小写,插入前统一转小写(如 std::tolower(static_cast)。
检测所有重复字符并统计次数用 std::unordered_map
当需要知道哪些字符重复、各重复几次(例如生成频次表),std::unordered_map 是自然选择。比手动维护两个容器或反复扫描更清晰、更不易出错。
容易踩的坑包括:
- 忘记初始化计数器(应直接用
++count[c],map 会自动初始化为 0) - 误用
count.find(c) != count.end()再取值 —— 多一次哈希查找,不如直接count[c] - 遍历 map 时假设键有序(
unordered_map不保证顺序;如需按字符 ASCII 排序输出,得额外拷贝到std::map或std::vector后排序)
简例:
std::unordered_map<char int> getCharCounts(const std::string& s) {
std::unordered_map<char int> count;
for (char c : s) {
++count[c]; // 自动初始化 +1
}
return count;
}</char></char>
ASCII 字符串可用布尔数组替代哈希容器提升性能
如果确定输入只含 ASCII 字符(0–127),且关注极致性能或嵌入式环境内存受限,用长度为 128 的 std::array 或 bool seen[128]{} 比 unordered_set 更快、更省内存 —— 避免哈希计算和动态分配。
关键点:
- 必须确保字符值非负,
char可能是signed,所以访问前强制转unsigned char:seen[static_cast(c)] - 不能用于 Unicode(UTF-8 多字节)或宽字符(
wchar_t)场景 - 初始化必须清零(用
{}或= {}),否则未初始化的栈数组内容是随机的
示例:
char firstRepeatASCII(const std::string& s) {
std::array<bool> seen = {}; // 全初始化为 false
for (char c : s) {
unsigned char uc = static_cast<unsigned char>(c);
if (seen[uc]) return c;
seen[uc] = true;
}
return '\0';
}</unsigned></bool>
遇到中文或 UTF-8 字符串怎么办
C++ 标准库的 std::string 本身不识别 UTF-8,一个汉字在 UTF-8 中占 3 字节,直接按 char 遍历会把汉字拆成多个无效字节,导致误判重复。
正确做法不是“用 std::wstring”,因为 Windows 和 Linux 下 wchar_t 宽度不同(Windows 是 16-bit,Linux 是 32-bit),且 UTF-8 文件读入后仍是 std::string。
实用方案只有两个:
- 用成熟 UTF-8 库(如
utf8cpp)先解码为std::vector(即 Unicode 码点),再对码点做重复检测 - 若只需处理常见中文(GB2312/GBK),且环境可控,可改用
std::string+ 双字节判定逻辑(但兼容性差,不推荐)
没有银弹:只要涉及多字节编码,就必须先完成字符边界识别,跳过字节级操作。这点极易被忽略,尤其在测试数据全为英文时表现正常,一上真实中文数据就崩。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











