我试图编写一个函数,返回字符串中第一个不重复的字符。我做的算法是:
- 断言字符串为非空
- 遍历字符串并将所有不重复的字符添加到集合中
- 断言集合为非空
- 再次遍历字符串并返回集合中的第一个字符
- 添加一个无用的返回语句,让编译器感到高兴。(任意返回"F")
显然,我的算法非常"暴力",可以改进。无论如何,它都能运行。我想知道是否有更好的方法可以做到这一点,也想知道无用的返回语句的惯例是什么。不要害怕严厉批评我。我正在努力成为一个C++爱好者
#include <iostream>
#include <string>
#include <set>
char first_nonrepeating_char(const std::string&);
int main() {
std::string S = "yodawgIheardyoulike";
std::cout << first_nonrepeating_char(S);
}
// Finds that first non-repeated character in the string
char first_nonrepeating_char(const std::string& str) {
assert (str.size() > 0);
std::set<char> nonRepChars;
std::string::const_iterator it = str.begin();
while (it != str.end()) {
if (nonRepChars.count(*it) == 0) {
nonRepChars.insert(*it);
} else {
nonRepChars.erase(*it);
}
++it;
}
assert (nonRepChars.size() != 0);
it = str.begin();
while (it != str.end()) {
if (nonRepChars.count(*it) == 1) return (*it);
++it;
}
return ('F'); // NEVER HAPPENS
}
主要问题只是消除警告。
理想情况下,你应该能够说
assert( false ); // Should never get here
但不幸的是,并没有消除我最常用的编译器的所有警告,即Visual C++和g++。
相反,我这样做:
xassert_should_never_get_here();
其中xassert_should_never_get_here
是
通过编译器特定的方式声明为"noreturn",例如Visual C++的
__declspec
、有一个
assert(false)
来处理调试构建,然后抛出CCD_ 4。
最后两点由宏XASSERT
完成(它在我的代码中的实际名称是CPPX_XASSERT
,最好为宏名称使用前缀,以降低名称冲突的概率)。
当然,不应该结束的断言相当于参数字符串至少包含一个不重复字符的断言,因此这是函数(其合同的一部分)的先决条件,我认为应该用注释来记录。:-)
当你没有这个前提条件时,有三种主要的"现代C++"编码方式,即
选择一个
char
值表示"没有这样的",例如' '
或在没有异常或的情况下抛出异常
返回一个逻辑上可以为"空"的装箱结果,例如Barton和Nackmann的
Fallible
对应的Boost类。
关于算法:当您没有在中集成第一个不重复的
char
时,您可以通过保持每个字符的计数来避免重新扫描字符串,例如使用map<char, int>
而不是set<char>
。有一种更简单、"更干净"的方法,但在计算上并不比"暴力"快。
使用一个统计输入字符串中每个字符出现次数的表。
然后再次遍历输入字符串,并返回计数为1的第一个字符。
char GetFirstNonRepeatedChar(const char* s)
{
int table[256] = {0};
for (int i=0; s[i]!=0; i++)
table[s[i]]++;
for (int i=0; s[i]!=0; i++)
if (table[s[i]] == 1)
return s[i];
return 0;
}
注意:以上内容适用于ASCII字符串。
如果使用不同的格式,则需要更改256
(当然还有char
)。