c++ - 关于效率的问题

Question

因此，在学习 Udemy over C++ 类(class)时，其中一个挑战是检查字符串是否为回文。我成功地完成了任务，但以与导师不同的方式去做。我知道有多种方法可以完成一项任务，但我想知道哪种方法更有效，为什么？在重新自学编码时想知道这一点似乎很愚蠢，但我觉得这是我应该牢记的。

//Instructors code//

# include<iostream>
using namespace std;

/*program for reverse a string and check a string is a palidrome

*/
int main()
{
    string str="MADAM";
    string rev="";
    int len=(int)str.length();
    rev.resize(len);
    for(int i=0, j=len-1; i<len; i++, j--)
    {
        rev[i]=str[j];
    }
    rev[len]='\0';  
    if(str.compare(rev)==0)
        cout<<"palindrome"<<endl;
    else
        cout<<"not a pallindrome"<<endl;
    return 0;
}

我的方法

#include <iostream>
using namespace std;

int main(){
    string str1="test";
//    cout << "Enter a string to check if it is a Palindrome: ";
//    getline(cin,str1);

    string str2;

    string::reverse_iterator it;
    for(it=str1.rbegin(); it!= str1.rend(); it++)
    {
        str2.push_back(*it);

    }
    if(!str1.compare(str2))
        cout << "\nPalindrome";
    else
        cout << "\nNot a Palindrome";
    return 0;
}

先感谢您。

Answer 1

从理论上讲，您的讲师提供的代码更有效，但是这两个示例都有问题。

对于您的讲师代码，主要问题是使用

int len=(int)str.length();

在这个例子中，这是可以的，因为我们知道字符串的大小将适合 int。 ，但如果您从外部来源获取字符串，这可能是个问题。一个 std::string使用无符号整数类型来存储字符串的大小，这意味着您可以拥有一个大小大于 int 的字符串。 .如果发生这种情况，那么代码将无法正常工作。

使用您的代码，您可以避免所有这些，这很好，但您也会在桌面上留下一些性能。理论上你的代码

for(it=str1.rbegin(); it!= str1.rend(); it++)
{
    str2.push_back(*it);

}

将导致str2随着新缓冲区的增长，分配多个缓冲区并从旧缓冲区复制到新缓冲区。这是您不需要做的大量额外工作，因为您已经知道需要分配多少空间。有

str2.reserve(str1.size() + 1);

在循环预先分配您需要的所有空间之前，这样您就不会受到那些潜在的性能影响。

然后我们发现您的两个示例都使用了第二个字符串。您不需要另一个字符串来检查回文。您可以做的只是检查第一个字符和最后一个字符是否相同，以及它们是否继续移动到第一个+1 和最后一个字符，依此类推，直到您到达中间或它们不匹配。您可以使用类似的构造来做到这一点

bool is_palindrome = true;
for (auto start = str.begin(), end = str.end() - 1; 
     start < end && is_palindrome; 
     ++start, --end)
{
    if (*start != *end)
        is_palindrom = false
}
if (is_palindrome)
    std::cout << "palindrome\n";
else
    std::cout << "not a pallindrome\n";