Transparent comparator code minimization

Question

Let's say we store a struct with a string key and we want to find it by that string in a container like std::set, so common implementation would look like this:

struct Foo {
    std::string id;
};

struct FooComp {
    using is_transparent = std::true_type;

    bool operator()( const Foo &foo, const std::string &str ) const
    {
        return foo.id < str;
    }

    bool operator()( const std::string &str, const Foo &foo ) const
    {
        return str < foo.id;
    }

    bool operator()( const Foo &foo1, const Foo &foo2 ) const
    {
        return foo1.id < foo2.id;
    }
};

 std::set<Foo,FooComp> foo_set;
 ...

This works fine, but writing three methods for FooComp that do prety match the same (logically) is monotonic and error prone. Is there a way to minimize that code?

Answer 1

You may do as following:

struct Foo {
    std::string id;
};

struct FooComp {
    using is_transparent = std::true_type;

    template <typename LHS, typename RHS>
    bool operator()(const LHS& lhs, const RHS& rhs) const
    {
        return ProjectAsId(lhs) < ProjectAsId(rhs);
    }

private:
    const std::string& ProjectAsId(const std::string& s) const { return s; }
    const std::string& ProjectAsId(const Foo& foo) const { return foo.id; }
};

You write comparison once, but you have to write the projection for each type.

In C++17, it can even be

template <auto f> struct ProjLess
{
    using is_transparent = std::true_type;

    template <typename LHS, typename RHS>
    bool operator()(const LHS& lhs, const RHS& rhs) const
    {
        return project(lhs) < project(rhs);
    }

private:
    template <typename T>
    using f_t = decltype(std::invoke(f, std::declval<const T&>()));

    template <typename T>
    using is_f_callable = is_detected<f_t, T>;

    template <typename T, std::enable_if_t<is_f_callable<T>::value>* = nullptr>
    decltype(auto) project(const T& t) const { return std::invoke(f, t); }

    template <typename T, std::enable_if_t<!is_f_callable<T>::value>* = nullptr>
    const T& project(const T& t) const { return t; }
};

And usage:

std::set<Foo, ProjLess<&Foo::id>> s;

Demo with C++17

Answer 2

My solution is all in the class:

struct FooComp {
  using is_transparent = std::true_type;
  struct FooProj {
    std::string const& str;
    FooProj( std::string const& sin ):str(sin) {}
    FooProj( const Foo& foo ):str(foo.id) {}
    FooProj( FooProj const& ) = default;
    friend bool operator<(FooProj lhs, FooProj rhs) {
      return lhs.str < rhs.str;
    }
  };
  bool operator()( FooProj lhs, FooProj rhs ) const
  {
    return lhs<rhs;
  }
};

This doesn't support types that can convert to std::string.

However, when doing a projection-based comparison, I do this:

template<class F, class After=std::less<>>
auto order_by( F&& f, After&& after={} ) {
  return
    [f=std::forward<F>(f), after=std::forward<After>(after)]
    (auto&& rhs, auto&&lhs)->bool {
      return after( f(decltype(lhs)(lhs)), f(decltype(rhs)(rhs)) );
    };
}

which takes a projection and generates a comparison function for it. We make it transparent with:

template<class F>
struct as_transparent_t {
  F f;
  using is_transparent=std::true_type;
  template<class Lhs, class Rhs>
  bool operator(Lhs const& lhs, Rhs const& rhs)const{ return f(lhs, rhs); }
};
template<class F>
as_transparent_f<std::decay_t<F>>
as_transparent( F&& f ) { return {std::forward<F>(f)}; }

so we can project and be transparent via:

as_transparent( order_by( some_projection ) );

which only leaves the projection.

In C++14 we just do a

std::string const& foo_proj_f( std::string const& str ) { return str; }
std::string const& foo_proj_f( Foo const& foo ) { return foo.id; }
auto foo_proj = [](auto const& x)->decltype(auto){ return foo_proj_f(x); };
auto foo_order = as_transparent( order_by( foo_proj ) );

which breaks things down into modular chunks.

In C++17 we can use if constexpr:

auto foo_proj = [](auto const& x)->std::string const& {
  if constexpr( std::is_same<decltype(x), std::string const&>{} ) {
    return x;
  }
  if constexpr( std::is_same<decltype(x), Foo const&>{} ) {
    return x.id;
  }
};
auto foo_order = as_transparent( order_by( foo_proj ) );

or

template<class...Ts>
struct overloaded:Ts...{
  using Ts::operator()...;
  overloaded(Ts...ts):Ts(std::move(ts)...){}
};
template<class...Ts> overloaded -> overloaded<Ts...>;

which permits

auto foo_proj = overloaded{
  [](std::string const& s)->decltype(auto){return s;},
  [](Foo const& f)->decltype(auto){return f.id;}
};

which may be easier to read than the if constexpr version. (This version can also be adapted to c++14 or c++11).