9

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?

piripiri
  • 1,925
  • 2
  • 18
  • 35

1 Answers1

15

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

user7860670
  • 35,849
  • 4
  • 58
  • 84
  • Thanks, this solved the problem. Is there a particular reason for using `public` and `private` before every single member? – piripiri Jan 11 '18 at 11:21
  • 1
    @piripiri 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. – user7860670 Jan 11 '18 at 11:35
  • 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? – Gabriel Apr 22 '19 at 20:35
  • 1
    @Gabriel See [What are transparent comparators?](https://stackoverflow.com/questions/20317413/what-are-transparent-comparators) – user7860670 Apr 22 '19 at 20:51