Find elements of std::set by custom comparison with value of different type

Question

Consider the following toy example of an std::set with a custom comparator:

#include <set>

struct A {
  A() : a(cnt++) {}
  const int a;
  static int cnt;
};

int A::cnt = 0;

struct comp {
  bool operator()(const A& left, const A& right)
  {
    return left.a < right.a;
  }
};

int main()
{
  std::set<A, comp> sa;
  for (int i = 0; i < 10; ++i) sa.insert(A());
  return 0;
}

Note that A cannot simply be created from an integer.

I would like to look for an A with a given value of A::a in sa, without constructing a temporary object of type A, i.e. I am searching for something like

sa.find(4)

with a custom comparator that allows for direct comparison of integers with objects of type A. Is that possible?

Warp

"The constant initialization of A::a is carried out in order to underline that it should not be possible to simply create objects of type A from integers." it does not work this way – Entrench

Use std::find_if – Medullated

Use the UnaryPredicate version of std::find_if – Anagram

Changed the example a bit to reflect the comments and make my point clearer. – Warp

@FrançoisAndrieux see ‘transparent comparators’ – Erne

Answer 1

With C++14 you can utilize "transparent" comparator:

#include <iostream>
#include <set>
#include <type_traits>

class A
{
    public: explicit A() : a{cnt++} {}
    private: explicit A(int) = delete;
    public: const int a;
    private: static int cnt;
};

int A::cnt{};

class Comparator
{
    // this member is required to let container be aware that 
    // comparator is capable of dealing with types other than key
    public: using is_transparent = std::true_type;

    public: bool operator()(const int & left, const A& right) const
    {
        return left < right.a;
    }

    public: bool operator()(const A & left, const int& right) const
    {
        return left.a < right;
    }

    public: bool operator()(const A& left, const A& right) const
    {
        return left.a < right.a;
    }
};

int main()
{
    std::set<A, Comparator> sa{};
    for (int i{}; i < 10; ++i)
    {
        sa.emplace();
    }
    std::cout << sa.find(3)->a << std::endl;
    return 0;
}

online compiler

Before C++14 heterogenous lookup was available in ::boost::intrusive::set:

#include <boost/intrusive/set.hpp>
#include <iostream>

namespace bi = ::boost::intrusive;

// hook contains set node data, supports various options, can be a member
class A: public bi::set_base_hook
<
    bi::link_mode<bi::link_mode_type::safe_link>
>
{
    public: explicit A() : a{cnt++} {}
    private: explicit A(int) = delete;
    public: const int a;
    private: static int cnt;
};

int A::cnt{};

class Comparator
{
    public: bool operator()(const int & left, const A& right) const
    {
        return left < right.a;
    }

    public: bool operator()(const A & left, const int& right) const
    {
        return left.a < right;
    }

    public: bool operator()(const A& left, const A& right) const
    {
        return left.a < right.a;
    }
};

int main()
{
    bi::set<A, bi::compare<Comparator>> sa{Comparator{}};
    for (int i{0}; i < 10; ++i)
    {
        sa.insert(*new A{}); // typically user manages object creation
    }
    // comparators may vary
    std::cout << sa.find(3, Comparator{})->a << std::endl;
    return 0;
}

online compiler

Aubine

Thanks, this solved the problem. Is there a particular reason for using public and private before every single member? – Warp

@Warp This allows to group members based of their usage and relations, improves readability (no need to scroll upwards to check the visibility of particular member), simplifies refactoring (no need to move code around). Most of the newer languages (java, c#, D) require access specifier for each member since such approach proved to be better. – Aubine

I couldn't find documentation about that is_transparent magic incantation. Why would I need to use it? Why is the default behavior for find not to work with custom comparators involving a type that's not the set's storage type? – Vladimir

@Vladimir See What are transparent comparators? – Aubine

Answer 2

This post was very helpful. Thank You

// this template requires the class to contain 
// a member of type <COMPARE_TYPE> named <COMPARE_MEMBER>
template <class SET_OBJECT, class COMPARE_TYPE, COMPARE_TYPE SET_OBJECT::*MEMBER> class SIMPLE_SET_COMPARATOR
{
public:
    using is_transparent = std::true_type;
    bool operator()(const COMPARE_TYPE& left, const SET_OBJECT& right) const { return left < right.*MEMBER; }
    bool operator()(const SET_OBJECT& left, const COMPARE_TYPE& right) const { return left.*MEMBER < right; }
    bool operator()(const SET_OBJECT& left, const SET_OBJECT& right)   const { return left.*MEMBER < right.*MEMBER; }
};

//Usage
class cMyClass{
    private: int a;
    public: cMyClass(int _a):a(_a) {};
}
std::set<cMyCLass, SIMPLE_SET_COMPARATOR<cMyClass, int, &cMyClass::a> > mySet;
for(int i = 100; i; i--)
    mySet.emplace( cMyClass(i) );
mySet.equal_range( 0 );

Illiterate