为什么==运算符用于字符串比较的时间(似乎)相对于任何一个字符串的长度都是线性的？

Question

#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“==”bbbbbbbbbbbbbbbbb...“(长度约250)平均多花50%以上的时间。

为什么会这样呢？在发现第一个字符不相等(或字符串的长度不相等)后，字符串比较函数不应该立即中断吗？

许多参考文献还提到，字符串比较在两个输入字符串的长度上都是线性复杂度(例如https://en.cppreference.com/w/cpp/string/basic_string/operator_cmp)。我不明白为什么会这样。任何帮助都是非常感谢的。

Answer 1

字符串== operator依赖于compare()方法。查看我的TDMGCC上可用的实现，我发现了以下内容：

// 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); }

因此，如果我没有错，比较将是您提到的线性时间。

Answer 2

这里要注意的第一件事是，正如前面提到的here，operator==()在内部使用compare()方法。

正如here和here所提到的，compare()方法的许多实现都依赖于memcmp。(或某些等效函数)您可以在this C实现中看到，memcmp使用的算法具有线性时间复杂度。下面给出了这个特定的实现。

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()方法的这种内部实现以及涉及的优化，您可能需要更大的字符串大小才能观察该方法执行所需时间的线性趋势。