Transparent Comparators C++

The associative container lookup functions (find, lower_bound, upper_bound, equal_range) only take an argument of key_type, requiring users to construct (either implicitly or explicitly) an object of the key_type to do the lookup. This may be expensive, e.g. constructing a large object to search in a set when the comparator function only looks at one field of the object. There is strong desire among users to be able to search using other types which are comparable with the key_type.

Consider the below structure Book

struct Book
{
  std::string title;
  Book(const std::string &str):title(str){}
};

Now, suppose we are making a library that will store our books in std::set, and to compare books we will use the title of Book.

int main()
{
  std::set<Book> library;
  library.insert(Book("The Alchemist"));
  auto search = library.find("The Alchemist");
  std::cout << (search != library.end()? "Found":"Not Found") << std::endl;
}

❌ Error: no matching function for call to ‘std::set<Book>::find(const char [5])’
17 | auto search = library.find("The Alchemist");

This does not work because library.find expects us to pass a Book object instead of string.
To overcome this, we can do library.find(Book("The Alchemist")); instead, but this creates a temporary object which is passed to the .find function.

To avoid creating temporary objects, we can create a transparent functor (comparator class) by defining is_transparent inside the functor.

A “transparent functor” is one which accepts any argument types (which don’t have to be the same) and simply forwards those arguments to another operator.

struct Compare
{
  using is_transparent = void;
  bool operator()(const Book &lhs, const Book &rhs) const
  {
    return lhs.title < rhs.title;
  }
  bool operator()(const Book &lhs, const std::string &rhs) const
  {
    return lhs.title < rhs;
  }
  bool operator()(const std::string &lhs, const Book &rhs) const
  {
    return lhs < rhs.title;
  }
};

int main()
{
  std::set<Book, Compare> library;
  library.insert(Book("The Alchemist"));
  auto search = library.find("The Alchemist");
  std::cout << (search != library.end()? "Found":"Not Found") << std::endl;
}

Found

Although the above code works, there is still a hidden temporary object being created, i.e., char* "The Alchemist" to std::string on calling library.find("The Alchemist");. To solve this problem, we can overload the operator() to accept char*. A more elegant solution would be to use template.

Here’s the final code

#include<iostream>
#include<string>
#include<set>

struct Book
{
  std::string title;
  Book(const std::string &str):title(str){}
};

struct Compare
{
  using is_transparent = void;
  bool operator()(const Book &lhs, const Book &rhs) const
  {
    return lhs.title < rhs.title;
  }
  template<typename T>
  bool operator()(const Book &lhs, const T &rhs) const
  {
    return lhs.title < rhs;
  }
  template<typename T>
  bool operator()(const T &lhs, const Book &rhs) const
  {
    return lhs < rhs.title;
  }
};

int main()
{
  std::set<Book, Compare> library;
  library.insert(Book("Ross"));
  auto search = library.find("Ross");
  std::cout << (search != library.end()? "Found":"Not Found") << std::endl;
}

Now we can use char*, char[], std::string, std::string_view or any other object that can be compared with std::string for comparison.

ℹ️ Note: is_transparent was introduced in C++14, make sure to use C++14 or later while compiling

Additional Resources#

Additional Resources