Cross-post from SO- Palindrome finding function

Question

I didn't know this site existed before now... awesome!

I just made a thread here: https://stackoverflow.com/questions/8511620/c-palindrome-finder-optimization

#include <iostream>
#include <ostream>
#include <vector>
#include <fstream>
#include <algorithm>
using namespace std;

bool isPal(string);

int main()
{
    vector<string> sVec;
    vector<string> sWords;
    vector<string> sTwoWords1;
    vector<string> sTwoWords2;
    char myfile[256]="/home/Damien/Test.txt";
    ifstream fin;
    string str;
    fin.open(myfile);
    if(!fin){
        cout << "fin failed";
        return 0;
    } 
    while(fin){
        fin >> str;
        sWords.push_back(str);
        if(!fin){
            break;
        }
        if(isPal(str)){
            sVec.push_back(str);
        }
        else{
            getline(fin, str);
        }
    }
    reverse(sVec.begin(), sVec.end());
    for(int i =0; i < sVec.size(); i++){ 
        cout << sVec[i] << " is a Palindrome " <<endl;
    } 

    // Test 2 
    for(int i=0; i<sWords.size(); i++)
    {                                         
        for(int j=(i+1); j<sWords.size(); j++){ 
            str = sWords[i]+sWords[j];
            if(isPal(str)){
                sTwoWords1.push_back(sWords[i]);
                sTwoWords2.push_back(sWords[j]);
            }
        }
    }
    fin.close();
    for(int i=0; i<sTwoWords1.size();i++){ 
        cout << sTwoWords1[i] << " and " << sTwoWords2[i] << " are palindromic. \n";
    } 
    return 0;
}
bool isPal(string& testing) {
    return std::equal(testing.begin(), testing.begin() + testing.size() / 2, testing.rbegin());
}

About optimizing some code, assuming that I take the revision to my isPal function, what else can I do to optimize the hell out of my code?

Thanks a lot for any / all recommendations!

Wordfile: http://www.filedropper.com/ospd3

Loki Astari · Accepted Answer · 2011-12-14 22:04:35Z

Reading a file:

while(fin){ 

    fin >> str; 
    sWords.push_back(str); 
    if(!fin){ 
        break; 
    }

You push the value str before checking it worked. It should be:

while(fin)
{ 
    fin >> str; 
    if(!fin){ 
        break; 
    } 
    sWords.push_back(str);

Or even better would be:

while(fin >> str)
{    
    sWords.push_back(str);

Why are you doing this:

    else{
        getline(fin, str);
    }

Mixing operator >> and getline() makes the code hard to read.
Either use all operator >> or use getline() to get a line at a time then parse the line internally.

Note:: operator>> will ignore the '\n' at the end of the line and work. So if your file is a list of words one per line there is no need to use getline(). If on the other hand your file is a lot of text and you only want the first word on each line then you need to use getline().

Method 1: Use operator>>

 // If your input file has one word per line (or you want to use all words)
 while(file >> word)
 {
      // Do stuff
 }

Method 1: Use getline()

 // If your input file contains lots of words
 // But you only want to use the first word on each line
 while(std::getline(file, line))
 {
     std::stringstream  linestream(line);
     linestream >> word;

     // Do stuff
 }

You seem to reversing the line just to print it:

reverse(sVec.begin(), sVec.end());                          
for(int i =0; i < sVec.size(); i++){                                
    cout << sVec[i] << " is a Palindrome " <<endl;                                  
}

Rather than reversing the array, just iterate it in reverse order:

for(std::vector<std::string>::const_iterator& loop = sVec.rbegin(); loop != sVec.rend(); ++ loop)
{                               
    cout << (*loop) << " is a Palindrome " <<endl;                                  
}

Note on efficiency:

Using push_back() on an vector can be in-effecient if you are pushing a lot of data. As evertime the vector runs out of space it must allocate more memory and copy the string to the new buffer. You help by pre-allocting space.

sVec.reserve(1000); // Guess at the size
                    // Note when the vector runs out of space it will approximately
                    // double its internal buffer.

Whoops, I actually parsed two different revisions of my code, thank you very much for bringing this to my attention. I was actually using getline(fin, str) as my while statement but then I changed it to fin >> for a different test I was running. Thank you so much for pointing those errors out. — HunderingThooves
– HunderingThooves, Commented Dec 14, 2011 at 21:49

Sjoerd · Accepted Answer · 2011-12-15 00:50:25Z

#include <iostream>
#include <ostream>
#include <vector>
#include <fstream>
#include <algorithm>

You forgot to #include <string>.

using namespace std;

Although this might be acceptable in books and on this site to shorten lines, don't use using namespace std in real code.

    vector<string> sVec;
    vector<string> sWords;
    vector<string> sTwoWords1;
    vector<string> sTwoWords2;
    char myfile[256]="/home/Damien/Test.txt";
    ifstream fin;
    string str;

This is an outdated style. Even in C, your variabled don't have to be declared at the top anymore. Declare each variable on the line it's initialized.

    char myfile[256]="/home/Damien/Test.txt";

Don't use char arrays, use std::string (or in rare cases: std::vector<char>).

    ifstream fin;
    fin.open(myfile);

Why two lines where one would be enough, and why using open()? Replace it with:

    std::ifstream fin(myfile.c_str());

As myfile should be a std::string.

    while(fin){
        fin >> str;
        sWords.push_back(str);

The other answer has already corrected the bug in this statement.

    reverse(sVec.begin(), sVec.end());
    for(int i =0; i < sVec.size(); i++){

Use iterators to loop over a container. In this case, use reverse iterators and you won't even need to call reverse().

    fin.close();

The destructor will close it anyway. Is there any reason to explicitly close it at this point? If there was any, just make sure that the life-time of fin ends at this point, e.g. by making a separate function of reading all input. Your main() is way too long anyway.

            str = sWords[i]+sWords[j];
            if(isPal(str)){

Bug! "aab" and "aa" will turn out to be a palindrome pair, as "aabaa" is a palindrome.

bool isPal(string& testing) {

That should be a const reference.

bool isPal(string);
....
bool isPal(string& testing) {

Those don't match.

    return std::equal(testing.begin(), testing.begin() + testing.size() / 2, testing.rbegin());

Cool! Finally some real C++ code! Even the std:: is present!

\$\begingroup\$ Ouch, brutal answer. \$\endgroup\$

HunderingThooves
– HunderingThooves

2011-12-15 10:22:27 +00:00
Commented Dec 15, 2011 at 10:22 — HunderingThooves
– HunderingThooves, Commented Dec 15, 2011 at 10:22

Stack Exchange Network

Cross-post from SO- Palindrome finding function

2 Answers 2

Reading a file:

Why are you doing this:

Method 1: Use operator>>

Method 1: Use getline()

You seem to reversing the line just to print it:

Note on efficiency:

You must log in to answer this question.

Hot Network Questions

Cross-post from SO- Palindrome finding function

2 Answers 2

Reading a file:

Why are you doing this:

Method 1: Use operator>>

Method 1: Use getline()

You seem to reversing the line just to print it:

Note on efficiency:

You must log in to answer this question.

Related

Hot Network Questions