提问人：vopsea 提问时间：2/8/2020 最后编辑：vopsea 更新时间：2/8/2020 访问量：363
为什么字符串比较的 == 运算符（似乎）相对于任一字符串长度是线性时间？
Why is == operator for string comparison linear time (seemingly) with respect to either strings length?
问：
#include <iostream>
#include <chrono>
#include <string>
using namespace std::chrono;
int main(int arc, char* argv[]) {
const std::string password = "a";
int correct = 1;
auto start = high_resolution_clock::now();
if(password != argv[1])
correct = 0;
auto end = high_resolution_clock::now();
auto elapsed = duration_cast<nanoseconds> (end-start).count();
std::cout << "time: " << elapsed << "\n";
return correct;
}
比较“a”==“b”和“a”==“bbb...”（长度~250）平均需要>50%的时间。
为什么会这样？字符串比较函数不应该在看到第一个字符不相等（或字符串的长度不相等）后立即中断吗？
许多参考文献还提到，字符串比较是两个输入字符串长度的线性复杂度（例如 https://en.cppreference.com/w/cpp/string/basic_string/operator_cmp）。我不明白为什么会这样.. 任何帮助都非常感谢。
答：
3赞
André Caceres
2/8/2020
#1
字符串依赖于该方法。
查看我的TDMGCC上可用的实现，我发现：== operatorcompare()
// This is the overloaded one called when you compare to argv[1]
template<typename _CharT, typename _Traits, typename _Alloc>
int
basic_string<_CharT, _Traits, _Alloc>::
compare(const _CharT* __s) const
{
__glibcxx_requires_string(__s);
const size_type __size = this->size();
const size_type __osize = traits_type::length(__s);
const size_type __len = std::min(__size, __osize);
int __r = traits_type::compare(_M_data(), __s, __len);
if (!__r)
__r = _S_compare(__size, __osize);
return __r;
}
正如你所看到的，在比较长度之前，它首先调用这个，这基本上是：traits_type::compare()memcmp()
static int
compare(const char_type* __s1, const char_type* __s2, size_t __n)
{ return __builtin_memcmp(__s1, __s2, __n); }
因此，如果我没记错的话，正如您提到的，比较将是线性时间。
评论
0赞
ChrisMM
3/12/2020
取决于实现。例如，MSVC 在调用之前检查长度（这更有意义）compare
1赞
ilim
2/8/2020
#2
这里首先要注意的是，内部使用方法，如此处所述。operator==()compare()
正如 here 和 here 所指出的，该方法的许多实现都依赖于 .（或一些等效函数）在此 C 实现中，您可以看到 by 使用的算法具有线性时间复杂度。下面给出了该特定实现。compare()memcmpmemcmp
int
memcmp (const PTR str1, const PTR str2, size_t count)
{
register const unsigned char *s1 = (const unsigned char*)str1;
register const unsigned char *s2 = (const unsigned char*)str2;
while (count-- > 0)
{
if (*s1++ != *s2++)
return s1[-1] < s2[-1] ? -1 : 1;
}
return 0;
}
由于该方法的这种内部实现以及所涉及的优化，您可能需要更大大小的字符串才能在执行方法所需的时间内观察线性趋势。compare()
评论
0赞
vopsea
2/8/2020
你知道这里有什么算数吗？是较长字符串的字节长度吗？您能对三元运算符的逻辑进行一些了解吗？我很难理解这里发生了什么。我们正在比较内存块，如果它们不相等，请检查前一个块 （？）
1赞
ilim
2/8/2020
实际上，在该特定实现中，是指要比较的字符数。当找到 和 的两个不同字符时，使用三元运算符。（见上述条件）它有助于确定要从哪个值返回。如果在词法上“较小”，则返回 -1，如果在词法上“较大”，则返回 1。counts1s2ifmemcmps1
评论