Code snippet: easy lexicographical ordering

The C++ standard library provides the std::lexicographical_compare function which takes two iterator ranges and returns a boolean, indicating which of the ranges is smaller. But what if we have a data structure like this:

struct foo
{
  int a;
  std::string b;
  char c;

  bool operator<(foo const &) const;
};

for which we want to write an operator< which does a lexicographical comparison of a, b and c. We end up with the following:

bool foo::operator<(foo const &r) const
{
  if (a < r.a)
    return true;
  if (r.a < a)
    return false;
  if (b < r.b)
    return true;
  if (r.b < b)
    return false;
  return c < r.c;
}

In case you’re wondering, I’m assuming we work on types which only have an operator<, which is why I cannot use operator> and operator!=.

Now, this is tedious to write and error prone. And it can be solved more elegantly. You might know that std::pair has an operator< which does lexicographical comparison. So I checked if boost::tuple has this feature, too. As it turns out, it does! So the above code can be reduced to:

bool foo::operator<(foo const &r) const
{
  return boost::make_tuple(a,b,c) < boost::make_tuple(r.a,r.b,r.c);
}

Note that you need the tuple/tuple_comparison.hpp header for this to work. I checked the latest C++0x draft and it confirms that this feature is ported to C++0x, too. And if you’re lucky, all of the tuple stuff in the above code will be optimized away, so the handwritten code from above is left.

Advertisements
This entry was posted in Uncategorized and tagged , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s