Longest words in dictionary that can be constructed from a list of letters The problem is to find the longest words in a dictionary of legal words that can be constructed from a given list of letters.

For example:


$ ./scrabble dictionary.txt i g h l p r a
argil glair grail graph hilar laigh phial pilar ralph



More details here.

I've already solved this problem in Python (see this).

To brush up my C++ I decided to reproduce the exact same algorithm in C++. I learned C++ as "C with classes" and never learned to use the STL properly, so I usually end up writing more code than necessary to accomplish simple things.

This is what I came up with for this problem:

#include &lt;algorithm&gt;
#include &lt;fstream&gt;
#include &lt;iostream&gt;
#include &lt;vector&gt;

using namespace std;

bool can_make(string word, vector&lt;char&gt; letters);
int get_max_len(vector&lt;string&gt; words);


int main(int argc, char* argv[])
{
    // Grab the dictionary.
    fstream dict_file(argv[1]);
    string in;
    vector&lt;string&gt; dict_words;
    while(getline(dict_file, in)) dict_words.push_back(in);
    dict_file.close();

    // Get the list of input letters.
    vector&lt;char&gt; letters;
    for (int i = 2; i &lt; argc; i++)
        letters.push_back(argv[i][0]);

    // Get all words.
    vector&lt;string&gt; all_words;
    vector&lt;string&gt;::iterator it;
    for (it = dict_words.begin(); it &lt; dict_words.end(); it++)
        if (can_make(*it, letters))
            all_words.push_back(*it);

    // Get longest words.
    int max_len = get_max_len(all_words);
    vector&lt;string&gt; longest_words;
    for (it = all_words.begin(); it &lt; all_words.end(); it++)
        if ((*it).length() == max_len)
            longest_words.push_back(*it);

    // Print the result.
    for (it = longest_words.begin(); it &lt; longest_words.end(); it++)
        cout &lt;&lt; *it &lt;&lt; " ";
    cout &lt;&lt; endl;

    return 0;
}


bool can_make(string word, vector&lt;char&gt; letters)
{
    /*
        Return true if the word &lt;word&gt; can be generated by all letters in &lt;letters&gt;
        and only the letters in &lt;letters&gt;.
    */

    if (word.length() &gt; letters.size()) return false;

    vector&lt;char&gt; l(letters);
    vector&lt;char&gt; word_letters(word.c_str(), word.c_str()+word.length());
    vector&lt;char&gt;::iterator it, loc;

    // Iterate through &lt;word_letters&gt;. If a letter in &lt;word_letters&gt; also
    // appears in &lt;letters&gt;, remove it. Otherwise, return false.
    for (it = word_letters.begin(); it &lt; word_letters.end(); it++) {
        loc = find(letters.begin(), letters.end(), *it);
        if (loc == letters.end()) return false;
        letters.erase(loc);
    }

    return true;
}


int get_max_len(vector&lt;string&gt; words)
{
    /*
        Return the length of the longest word(s) in &lt;words&gt;.
    */

    int max_len = 0;
    vector&lt;string&gt;::iterator it;
    for (it = words.begin(); it &lt; words.end(); it++)
        if ((*it).length() &gt; max_len)
            max_len = (*it).length();

    return max_len;
}



Is this idiomatic C++?
How can I make this code more concise?
How can I make it more correct?
What C++11 features can I use here to make the code even shorter?
What features have I used here that I should avoid?
Preface

I am not sure the algorithm you have chosen is the best one. Sorting the letters, or using a frequency table of the letters, are obvious alternatives. However, this is code review, and not algorithm review.

So here we go:

Iterators

Don't use &lt; on iterators, use != on iterators. &lt; only works on bidirectional iterators, != works on all iterators. std::list&lt;&gt; is an example where &lt; won't work.

Use ++it instead of it++. Theoretically, the latter has to return a temporary copy of the original, which is additional overhead when the iterator is a class. Practically, it won't make much of a difference (if any) as most compilers will inline and optimize. Still, it's one of the best signals whether someone is a true C++ expert or a converted C-programmer :P .

So

for (it = dict_words.begin(); it &lt; dict_words.end(); it++)


Will become:

for (it = dict_words.begin(); it != dict_words.end(); ++it)


Predefined algorithms

Many of your one-line loops can be replaced with algorithms from &lt;algorithm&gt;.

In this small case, I wouldn't bother as it wouldn't help to make your code more clear or shorter.

On the other hand, experimenting with them in this case will make you more comfortable with them. With the introduction of lambdas in C++11, those algorithms will become much more common in new code!

C++11

Due to the fact that C++11 hasn't been around long yet (and compilers don't fully implement it yet), idiomatic C++11 will change over the next couple years. So take this section with a grain of salt.

That being said, use auto for the type of it. That part of C++11 has become idiomatic already.

E.g.:

vector&lt;string&gt;::iterator it;
for (it = dict_words.begin(); it != dict_words.end(); ++it)


will become:

for (auto it = dict_words.begin(); it != dict_words.end(); ++it)


EDIT: oops, forgot about the range-based for in C++11. See other answers for that. I'm not that well versed in C++11 yet, but I believe it would look like this:

for (auto it : dict_words)


More functions

Most of your code is in one long function, called main. Try to split it up.

Once you start inserting empty lines and comment headings to clarify what the block does, it's usually a good candidate to turn into a separate function.

E.g. this block of code (limited by empty lines, with a comment):

// Grab the dictionary.
fstream dict_file(argv[1]);
string in;
vector&lt;string&gt; dict_words;
while(getline(dict_file, in)) dict_words.push_back(in);
dict_file.close();


Can be replaced with this function:

void grab_dictionary(const char* filename, vector&lt;string&gt;&amp; dict_words)
{
    fstream dict_file(filename);
    string in;
    while(getline(dict_file, in))
       dict_words.push_back(in);
}


Usage from main:

vector&lt;string&gt; dict_words;
grab_dictionary(argv[1], dict_words);


Additional benefit:


The comment is no longer needed - usually it has become the name of the function!
There is no need for dict_file.close() as the destructor will close the file at the right time.