c++ - 为什么 == 运算符用于字符串比较的线性时间(看似)相对于任一字符串长度?
问题描述
#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" == "bbbbbbbbbbbbb..."(长度 ~250)平均需要 >50% 的时间。
为什么会这样?在看到第一个字符不相等(或字符串的长度不相等)后,字符串比较函数不应该立即中断吗?
许多参考文献还提到字符串比较是两个输入字符串长度的线性复杂性(例如https://en.cppreference.com/w/cpp/string/basic_string/operator_cmp)。我不明白为什么会这样。非常感谢任何帮助。
解决方案
字符串== 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;
}
如您所见,在比较长度之前,它首先调用 this traits_type::compare()
,基本上是memcmp()
:
static int
compare(const char_type* __s1, const char_type* __s2, size_t __n)
{ return __builtin_memcmp(__s1, __s2, __n); }
因此,如果我没记错的话,比较将是你提到的线性时间。
推荐阅读
- c# - 有没有办法跳过 MediatR 管道?
- typescript - ReactJs Typescript,Emotion Js 使用主题类型
- javascript - 如何使用 java 脚本中的示例 json 对象将 aa 数组转换为 JSON
- java - 使用 https 将 jhipster (spring boot+angular) 应用程序连接到 keycloak
- javascript - 如何从flutter查询到node js
- javascript - 如何在 JavaScript 中过滤数组时过滤嵌套数组
- css - 光滑的滑块点和箭头不显示
- windows - 确定文本文件是否为空或显示的信息不正确
- python - 如何复制dataframe1中的行数以匹配pandas中dataframe 2中的n行
- javascript - 如何将 MySQL 值存储在网页中以供以后使用