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&lt;iostream&gt;
#include&lt;fstream&gt;
#include&lt;vector&gt;
#include&lt;algorithm&gt;

using namespace std;

// Load a dictionary file (line-separated strings) into a vector&lt;string&gt; and return the vector.
vector&lt;string&gt; loadFromDic(string filename)
{
  ifstream file;
  vector&lt;string&gt; 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&lt;string&gt; strings = loadFromDic("english_dic.txt");

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

  vector&lt;string&gt; ok_strings; // Will hold the strings which passed the test.
  string aux;
  vector&lt;string&gt;::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)-&gt;bool
    {
      if(a.size() == b.size())
    return a &lt; b;
      return a.size() &lt; b.size();
    }
  );  

  // Display the strings which passed the test.
  for(it = ok_strings.begin() ; it != ok_strings.end() ; it++)
  {
    cout &lt;&lt; *it &lt;&lt; endl;
  }

  return 0;
}


The dictionary file I'm using is inside this .zip (renamed the US.dic -> english_dic.txt)
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 &lt;iostream&gt;
#include &lt;unordered_set&gt;
#include &lt;string&gt;
#include &lt;iterator&gt;
#include &lt;fstream&gt;
#include &lt;algorithm&gt;

template &lt;class InIt, class OutIt, class F, class P&gt;
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&lt;std::string&gt; words{
        std::istream_iterator&lt;std::string&gt;(in), 
        std::istream_iterator&lt;std::string&gt;()};

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

    std::sort(reversed.begin(), reversed.end(),
        [](std::string const &amp;a, std::string const &amp;b) {
            if (a.length() &lt; b.length())
                return true;
            return a &lt; b;
        });
    for (auto const &amp;s : reversed)
        std::cout &lt;&lt; s &lt;&lt; "\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.