Find longest lines from a file This is a challenge question from codeeval.com:




  Write a program which reads a file and prints to stdout the specified
  number of the longest lines that are sorted based on their length in
  descending order. Input sample:
  
  Your program should accept a path to a file as its first argument. The
  file contains multiple lines. The first line indicates the number of
  lines you should output, the other lines are of different length and
  are presented randomly. You may assume that the input file is
  formatted correctly and the number in the first line is a valid
  positive integer. 
  
  For Example:

2 
Hello World
CodeEval 
Quick Fox
A
San Francisco

  
  Output sample:
  
  Print out the longest lines limited by specified number and sorted by
  their length in descending order.
  
  For example:

San Francisco 
Hello World



Please let me know how I can improve this implementation.



#include&lt;iostream&gt;
#include&lt;map&gt;
#include&lt;fstream&gt;
#include&lt;string&gt;
#include&lt;chrono&gt;

class fixed_hash{
public:
        fixed_hash( int pSize )
        {
            size = pSize;
        }
        void push( std::string &amp; record )
        {

            if( hash_table.size() &lt; size )
            {
                hash_table.emplace( std::make_pair( record.size(), record ) );
            }
            else if( record.size() &gt; hash_table.rbegin()-&gt;second.size() )
            {
                hash_table.erase( hash_table.begin() );
                hash_table.emplace( std::make_pair( record.size(), record ) );
            }
        }
        void print()
        {
            auto end = std::rend(hash_table);
            for( auto it = std::rbegin( hash_table ); it != end ; ++it )
            {
                std::cout &lt;&lt; it-&gt;second &lt;&lt; "\n";
            }
        }

 private:
        std::map&lt;int,std::string&gt; hash_table;
        int size;
};

void readInputFile( std::string fileName )
{
    std::ifstream infile( fileName );
    std::string record;
    int output_nbr = 0;
    infile &gt;&gt; output_nbr;
    fixed_hash output_string_list( output_nbr );
    while( std::getline( infile, record ) )
    {
        output_string_list.push( record );
    }

    output_string_list.print();
    infile.close();
}

int main( int argc, char* argv[] )
{
    auto start = std::chrono::steady_clock::now();
    if( argc &lt; 2 )
    {
        std::cout &lt;&lt; "Error: input file is missing " &lt;&lt; "\n";
        exit( 0 );
    }

    std::ios_base::sync_with_stdio( false );
    readInputFile( argv[ 1 ]);

    auto end      = std::chrono::steady_clock::now();
    auto duration = std::chrono::duration_cast&lt;std::chrono::microseconds&gt;(end-start);
    std::cout&lt;&lt; duration.count() &lt;&lt; "\n";
    return 0;
}
This is a bug:

else if( record.size() &gt; hash_table.rbegin()-&gt;second.size() )


As implemented, insertion stops once your program encounters the longest line in the file.

For example, suppose the input contains:




2
abcdefghijklmop
a
ab
abc
abcd



Your program will output:


abcdefghijklmop
a



The fix is simple: Change rbegin to begin.



Another potential issue is your use of a std::map as opposed to some other container. Your concept is fine, but not necessarily for "I'm the best hacker!" type sites that place strong emphasis on execution time. A vector-based solution could be faster. With the red-black tree-based hash, search, insertion, and delete are \$O(log n)\$ (but with large constants). With a vector-based solution, search would be \$O(log n)\$ (but potentially much faster than a red-black search), deleting the tail is \$O(1)\$ (which is a big win), but insertion is \$O(n)\$ (which is of course a big loss). However, for small enough values of n, a fast \$O(n)\$ algorithm can and will beat a slow \$O(log n)\$ algorithm.

One last remark: Rather than your void print() member, a stream insertion operator would be more C++-like:



class fixed_hash
{
    ...
    friend std::ostream&amp; operator&lt;&lt;(std::ostream&amp; os, const fixed_hash&amp; hash);
    ...
};

std::ostream&amp; operator&lt;&lt;(std::ostream&amp; os, const fixed_hash&amp; hash)
{
    auto end = std::rend(hash.hash_table);
    for( auto it = std::rbegin(hash.hash_table); it != end ; ++it )
    {
        os &lt;&lt; it-&gt;second &lt;&lt; "\n";
    }
    return os;
}