Pages

Selecting the longest lines

We have in input a few strings, we want to output a given number of them, ordered by their size.

This is such a simple problem that I couldn't think of any interesting test case about. You can find it in the CodeEval open challenge under the name Longest Lines.

At its core, the solution to this problem is nothing more than a couple of C++ statements.

Assuming the number of lines we want to output is stored in an int variable named nr, and the vector of strings named lines keep the data, it is just a matter of sort the vector by lines size and return its first nr elements:
std::sort(lines.begin(), lines.end(), StringSizeCmp());
for(int i = 0; i < nr; ++i)
  std::cout << lines[i] << std::endl;
Right. But I forgot to tell you who is that StringSizeCmp guy. It is a simple functor that defines how sort() should decide which element comes first:
struct StringSizeCmp : public std::binary_function<std::string, std::string, bool>
{
  bool operator()(const std::string& lhs, const std::string& rhs) const
  {
    return lhs.size() > rhs.size();
  }
};
As clearly stated by inheritance, StringSizeCmp is a binary function that gets a couple of strings in and gives a boolean out. The comparison is here solved accordingly to the input sizes.

C++11 makes it even simpler, by means of lambda function. We could combine the predicate definition and its usage in a single line:
std::sort(lines.begin(), lines.end(),
    [](const std::string& lhs, const std::string& rhs) {
  return lhs.size() > rhs.size();
});

No comments:

Post a Comment