C-String与C++字符串的效率

Question

C++ Primer说

对于大多数应用程序,除了更安全之外,使用库字符串而不是C样式字符串也更有效

安全是理解的.为什么C++字符串库更有效？毕竟,在它下面,是不是字符串仍然表示为字符数组？

为了澄清,作者是否谈论程序员效率(理解)或处理效率？

Answer 1

C字符串通常更快,因为它们不调用malloc/new.但有些情况std::string会更快.函数strlen()是O(N),但是std::string::size()是O(1).

此外,当您搜索子字符串时,您需要'\0'在每个周期检查C字符串中std::string- 您没有.在一个天真的子串搜索算法中它并不重要,因为而不是检查'\0'你需要检查i<s.size().但现代高性能子串搜索算法以多字节步骤遍历字符串.并且需要'\0'检查每个字节会减慢它们的速度.这就是GLIBC memmem快了x2倍的原因strstr.我做了很多子串算法的基准测试.

这不仅适用于子串搜索算法.对于零终止字符串,许多其他字符串处理算法较慢.

Answer 2

为什么C++字符串库更有效？毕竟,在它下面,是不是字符串仍然表示为字符数组？

因为如果不仔细写,使用char*或char[]更可能无效的代码.例如,你看过这样的循环:

char *get_data();

char const *s = get_data(); 

for(size_t i = 0 ; i < strlen(s) ; ++i) //Is it efficent loop? No.
{
   //do something
}

这有效吗？不是.时间复杂度strlen()是O(N),并且在上面的代码中,在每次迭代中计算它.

现在你可以说"如果我strlen()只召唤一次,我可以提高效率." .当然可以.但是你必须自己和有意识地做所有那种优化.如果你遗漏了什么,你错过了CPU周期.但是std::string,许多这样的优化是由类本身完成的.所以你可以这样写:

std::string get_data();

std::string const & s = get_data(); //avoid copy if you don't need  it

for(size_t i = 0 ; i < s.size() ; ++i) //Is it efficent loop? Yes.
{
   //do something
}

这有效吗？是.时间复杂度size()是O(1).无需手动优化它,这通常会使代码看起来丑陋且难以阅读.与之std::string相比,生成的代码几乎总是整洁干净char*.

另请注意,std::string这不仅可以使您的代码在CPU周期方面有所作为,而且还可以提高程序员的工作效率!

Answer 3

这里有一些情况,其中一个std::string可能击败char[].例如,C风格的字符串通常没有传递明确的长度 - 而是NUL终结符隐式定义长度.

这意味着一个连续strcat进入a 的循环char[]实际上正在执行O(n²)工作,因为每个循环strcat都必须处理整个字符串以确定插入点.相比之下,std::string需要执行以连接到字符串末尾的唯一工作是复制新字符(并可能重新分配存储 - 但为了比较公平,您必须事先知道最大大小和reserve()它) .

Answer 4

A std::string知道它的长度,这使得许多操作更快.

例如,给定:

const char* c1 = "Hello, world!";
const char* c2 = "Hello, world plus dog!";
std::string s1 = c1;
std::string s2 = c2;

strlen(c1)比...慢s1.length().对于比较,strcmp(c1, c2)必须比较几个字符以确定字符串不相等,但s1 == s2可以告诉长度不一样并立即返回false.

其他操作也受益于提前知道长度,例如strcat(buf, c1)必须找到空终止符buf以查找附加数据的位置,但是s1 += s2知道s1已经的长度并且可以立即将新字符附加到正确的位置.

在内存管理方面,std::string每次增长时都会分配额外的空间,这意味着未来的附加操作不需要重新分配.