Searching for pseudo-palindromes ("semordnilaps")

I was interested to know which words of the English language, when spelled backwards, are still valid words (e.g. "drawer", which when spelled backwards is "reward"), so I wrote a small program to go through a dictionary text file to search for them.

I don't know if there's a word to describe them, but because of the similarity to palindromes, I decided to call them pseudo-palindromes.

So, I wanted to know:

• Is there a more efficient way to search for pseudo-palindromes? I believe my approach has \$O(n*log(n))\$ complexity. Is that right?

• Are there ways to make my code more readable and/or maintainable?

• Are there any other tips to enhance the performance or style?

```
#include
#include
#include
#include

using namespace std;

// Load a dictionary file (line-separated strings) into a vector and return the vector.
vector loadFromDic(string filename)
{
ifstream file;
vector strings;
string aux;

file.open(filename.c_str());
while(!file.eof())
{
getline(file,aux);
strings.push_back(aux);
}

return strings;
}

int main()
{
// Load the dictionary from memory.
vector strings = loadFromDic("english_dic.txt");

// Sort it alphabetically.
sort(strings.begin(),strings.end());

vector ok_strings; // Will hold the strings which passed the test.
string aux;
vector::iterator it;

// For each string:
for(it = strings.begin() ; it != strings.end() ; it++)
{
// Reverse the string.
aux = *it;
reverse(aux.begin(),aux.end());

// If the reversed string is a word contained in the dictionary, add it to the list.
if(binary_search(strings.begin() , strings.end() , aux))
{
ok_strings.push_back(*it);
}
}

// Sort ok_strings based on string length first and then alphabetically.
sort
(ok_strings.begin() , ok_strings.end() ,
[](string a, string b)->bool
{
if(a.size() == b.size())
return a < b;
return a.size() < b.size();
}
);

// Display the strings which passed t

I'd try to break some habits, and make others in their places.

-
One habit to break is using while (!file.eof()) -- it's nearly always a problem (including this time).

-
In its place, I'd consider initializing the array of input strings from a pair of std::istream_iterators.

-
I'd try to form the habit of creating fstream objects initialized with the name of the name of the file you want to read/write, rather than creating an uninitialized object, then using open open the file afterwards.

-
I'd also try to get in the habit of using better/more efficient data structures when possible. As pointed out below, in this case it doesn't make a big difference, but it does help a little, and it actually simplifies the code--a clear win.

-
Finally, get in the habit of using standard algorithms where they apply. In this case, I think a non-standard algorithm really makes more sense--a transform_if, which I end up using quite a bit, as a matter of fact.

Putting these together, we could end up with something on this order:

#include 
#include 
#include 
#include 
#include 
#include 

template 
void transform_if(InIt b, InIt e, OutIt o, P p, F f) { 
    while (b != e) { 
        auto v = f(*b);
        if (p(v))
            *o++ = v;
        ++b;
    }
}

int main(){ 
    std::ifstream in("us.dic");
    std::unordered_set words{
        std::istream_iterator(in), 
        std::istream_iterator()};

    std::vector reversed;
    transform_if(words.begin(), words.end(), 
        std::back_inserter(reversed),
        [&](std::string const &s) { return words.find(s) != words.end(); },
        [](std::string const &s) { return std::string(s.rbegin(), s.rend()); });

    std::sort(reversed.begin(), reversed.end(),
        [](std::string const &a, std::string const &b) {
            if (a.length() < b.length())
                return true;
            return a < b;
        });
    for (auto const &s : reversed)
        std::cout << s << "\n";
}

I haven't tried to move much out of main, because in this case we've already reduced main to only 6 statements (though, admittedly, some of those are fairly long).

A few other miscellaneous points:

• I'd prefer to see #include directives formatted with a space before the header name (as I've done in my code above).

• Using an unordered_set helps the run time somewhat, but not drastically--on my machine, the CPU time is reduced from ~.35 seconds to ~.24 seconds. That's clearly faster, but not immensely so.

• Another possibility to consider would be to put the inputs into a sorted vector, but use an interpolation search instead of a binary search to find the pseudo-palindromes.

StackExchange Code Review Q#52678, answer score: 13