通过与不同类型的值进行自定义比较来查找 std::set 的元素

Question

考虑以下带有自定义比较器的

std::set

玩具示例：

#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;
}

请注意，

A

不能简单地从整数创建。

我想在

A

中寻找给定值为

A::a

的

sa

，无需构造

A

类型的临时对象，即我正在寻找类似的东西

sa.find(4)

带有自定义比较器，允许直接比较整数与

A

类型的对象。这可能吗？

Answer 1

使用 C++14，您可以使用“透明”比较器：

#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;
}

在线编译器

在 C++14 异构查找可用之前

::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;
}

在线编译器

Answer 2

这篇文章非常有帮助。 谢谢你

// 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 );