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<iostream>
#include<map>
#include<fstream>
#include<string>
#include<chrono>

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

            if( hash_table.size() < size )
            {
                hash_table.emplace( std::make_pair( record.size(), record ) );
            }
            else if( record.size() > hash_table.rbegin()->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 << it->second << "\n";
            }
        }

 private:
        std::map<int,std::string> hash_table;
        int size;
};

void readInputFile( std::string fileName )
{
    std::ifstream infile( fileName );
    std::string record;
    int output_nbr = 0;
    infile >> 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 < 2 )
    {
        std::cout << "Error: input file is missing " << "\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<std::chrono::microseconds>(end-start);
    std::cout<< duration.count() << "\n";
    return 0;
}
  • Note: C++ has a built in heap type: cplusplus.com/reference/algorithm/make_heap – Martin York Jul 12 '15 at 21:07
  • 2
    Also note that your hash_table is not a hash-table in the strict meaning of the word. std::map is a binary search tree. If you really care about using a true hash-table, then the correct container would be std::unordered_map. – glampert Jul 12 '15 at 21:08
  • 1
    @glampert - The name is a misnomer. Steephen is very much taking advantage of the fact that a std::map is ordered. – David Hammen Jul 12 '15 at 22:14
up vote 12 down vote accepted

This is a bug:

else if( record.size() > hash_table.rbegin()->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& operator<<(std::ostream& os, const fixed_hash& hash);
    ...
};

std::ostream& operator<<(std::ostream& os, const fixed_hash& hash)
{
    auto end = std::rend(hash.hash_table);
    for( auto it = std::rbegin(hash.hash_table); it != end ; ++it )
    {
        os << it->second << "\n";
    }
    return os;
}
  • Good catch on spotting the bug! Interesting that our reviews are largely complementary. It's yet more evidence that multiple reviews are more useful than any single one. – Edward Jul 12 '15 at 16:30

Here are some things that may help you improve your code, but with the caveat that "improve" could mean one of several things. In this review, I'm mostly going to comment on things that will make the code more readable, and not necessarily yield performance improvements.

Use better naming

The name readInputFile is a bit misleading, since it does much more than simply reading -- all of the processing, including output, is done there. Also, I tend to prefer CamelCase for class names, so I'd be inclined to name the class something else, perhaps FixedHash, although I'm not very fond of that name either.

Use std::size_t instead of int

A more appropriate type for your size in fixed_hash would be std::size_t instead of int.

Consider using a multiset instead

One could easily argue it either way, but I'd be inclined to use a std::multiset instead of a std::map. Your current code is more efficient in that it uses less memory and is probably faster, but an alternative would be to use a more-or-less plain multiset:

template <class T>
struct longer {
    bool operator()(const T &left, const T &right) const {
        return right.size() < left.size();
    }
};
std::multiset<std::string, longer<std::string>> lines;

Printing would then be:

for (auto line = lines.cbegin(); count && line != lines.cend(); ++line, --count) {
    std::cout << *line << std::endl;
}

If needed, you could adapt the multiset as you have for the map. It seems to me that the code might be slightly simpler.

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main.

  • I have to disagree. Not enough to downvote, but I disagree. (1) Better naming. Many people have come to the realization that CamelCaseWasABigUnreadableMistake. (2) size_t vs int. This is a problem on machines using an OS from Redmond. On other machines, are you going to find text files that are 2 billion lines long, lines that are 2 billion characters long? The answer is almost always no. (3) multiset vs set. This depends on ones interpretation of a key vague point in the challenge, how to treat lines of the same length. (4) Never omit return 0! Adding that shortcut was a travesty. – David Hammen Jul 12 '15 at 17:08
  • 1
    @DavidHammen: regarding CamelCase - it's a personal preference, which is why I stated it as such and not as a recommendation. Better, more descriptive naming is still advisable, regardless of the form it's expressed. For size_t vs. int -- it's a signed/unsigned rather than an OS-specific thing. I use Linux and gcc here; gcc correctly warns about a sign mismatch in the comparison. IMHO, it's best to address the potential problem during construction rather than have it fail in the distant future when someone does try it on 2 billion lines. – Edward Jul 12 '15 at 17:24
  • @DavidHammen: Have to disagree with all your points. 1) Most => not true. There are multiple arguments on all fronts. 2) Not true. MS machines use size_t fine. 3) What. 4) Omitting return 0 in main is pretty standard when there is no chance the application can fail (it is a way of documenting that the application does not fail). – Martin York Jul 13 '15 at 5:58

You may consider using std::multimap since there may be strings of equal length in the input. For example (C++11), change your input stream accordingly or use freopen with this code.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    multimap <size_t, string, greater<size_t>> map;
    string line;
    while (getline(cin, line)) 
        map.emplace(line.length(), line);
    for (auto i = map.begin(); i != map.end() && n--; ++i)
        cout << i->second << endl;
    return 0;
}

See it working here.


C++11 is not present on codeeval.com. A C++03 compatible version would look like this:

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char * argv[]) {
    int n;
    cin >> n;
    multimap <size_t, string, greater<size_t> > map;
    string line;
    while (getline(cin, line)) 
        map.insert(make_pair(line.length(), line));
    for (multimap<size_t, string>::iterator i = map.begin(); i != map.end() && n--; ++i)
        cout << i->second << endl;
    return 0;
}

In addition to all above answers, here are a few things that may improve your existing code:

In the push member function, it's not necessary to do the comparing and deleting and its algorithm there; it seems odd. It's better to make it for inserting a new elements that's quite regular, especially when std::map has template parameter comparators made for that purpose and the compare expression by default is std::less<T>. You can create your compare expression or use std::greater<T> which is defined in the <functional> header file.

std::map<std::size_t ,std::string, std::greater<int>> hash_table;

and push member function will be like this

    void push( std::string & record )
    {
        hash_table.emplace( std::make_pair( record.size(), record ) );
    }

In the print member function, try not use std::begin() std::end(). That would be really unnecessary for STL containers. It already has its own begin() and end().

    void print()
    {
        for( auto it = hash_table.begin(); it != hash_table.end() && size; ++it , --size )
        {
            std::cout << it->second <<"\n";
        }
    }

My suggestion is to pick the right container for this question. It's known that std::vector is a better choice for small data sizes and best for iterating data, but it has limitations in lookup, unlike std::map. This example really is a perfect reason to go with std::vector over std::map, especially because it asked for longer lines in a text file only.

My opinion is to create std::vector<std::string> and once all data is stored in the vector, it can be sorted and printed easily by using what STL offers to us as shown below:

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

int main(int argc, char* argv[])
{
    std::ifstream in(argv[1]);
    std::vector<std::string> vec;
    std::string line;
    while (std::getline(in, line))
    {       
        vec.push_back(line);
    }
    std::size_t n = atoi(vec.begin()->c_str());
    std::sort(vec.begin(), vec.end(), [](const std::string &left, const std::string &right){ return right.size() < left.size(); });
    std::copy(vec.begin(), vec.begin() + n, std::ostream_iterator<std::string>(std::cout, "\n"));
}

Following corrections are implemented:

  1. Reported bug is fixed

  2. Instead of std::map<> using std::multi_map<>

  3. Using size_t instead of wrong use of int as a type

//

#include<iostream>
#include<map>
#include<fstream>
#include<string>
#include<chrono>

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

            if( hash_table.size() < size )
            {
                hash_table.emplace( std::make_pair( record.size(), record ) );
            }
            else if( record.size() > hash_table.begin()->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 << it->second << "\n";
            }
        }

 private:
        std::multimap<int,std::string> hash_table;
        std::size_t size;
};

void readInputFile( std::string fileName )
{
    std::ifstream infile( fileName );
    std::string record;
    int output_nbr = 0;
    infile >> 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 < 2 )
    {
        std::cout << "Error: input file is missing " << "\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<std::chrono::microseconds>(end-start);
    std::cout<< duration.count() << "\n";
    return 0;
}

protected by Community Aug 17 '15 at 12:55

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.