CODEWITHSUNDEEP
c++performancedictionarystlcomparator
nappyfalcon
nappyfalcon

Reputation: 939

How can I search an std::map using a key of a different type

If I have std::map<X, Blah>, what is the best way of looking up a matching item in the map using an instance of Y?

Assume the information in Y is enough to uniquely find an X, but for performance reasons I don't want to create an instance of X by copying Y values.

I realize I can do this by creating a common base class or interface for X and Y and making that the map key, but is there any other way? e.g. creating some sort of comparator object?

Here is the sample code for clarity:

class X
{
public:
    int id;
    int subId;
};

std::map<X, Details> detailsMap;

class Y
{
public:
    int getId();
    int getSubId();
    int someOtherUnrelatedThings1;
    int someOtherUnrelatedThings2;
};

Now, if I have an instance of Y, in principle I should be able to find matching items in my map, given I can get an id and subId pair. But can I do it without creating an instance of X and copying over the id and subId?

Upvotes: 13

Views: 3166

Answers (2)

Michał G&#243;ral
Michał G&#243;ral

Reputation: 1517

With C++14 you can use heterogeneous lookup.

If you'd like to find an element with key that compares equivalent to the argument of std::map::find, you should provide a Comparator as a third template parameter which should have Comparator::is_transparent denoted as a type. It should also contain bool operator() comparing your map key with any other type you'd like.

Funny description aside, here's an example:

struct X
{
    int id;
    int subid;
};

struct Details {};

struct Comparator
{
    using is_transparent = std::true_type;

    // standard comparison (between two instances of X)
    bool operator()(const X& lhs, const X& rhs) const { return lhs.id < rhs.id; }

    // comparison via id (compares X with integer)
    bool operator()(const X& lhs, int rhs) const { return lhs.id < rhs; }
    bool operator()(int lhs, const X& rhs) const { return lhs < rhs.id; }

    // Same thing with Y
    bool operator()(const X& lhs, const Y& rhs) const { return lhs.id < rhs.getId(); }
    bool operator()(const Y& lhs, const X& rhs) const { return lhs.getId() < rhs.id; }
};

int main()
{
    std::map<X, Details, Comparator> detailsMap = {
        { X{1, 2}, Details{} }, 
        { X{3, 4}, Details{} },
        { X{5, 6}, Details{} }
    };

    // it1 and it2 point to the same element.
    auto it1 = detailsMap.find(X{1, 2});
    auto it2 = detailsMap.find(1);

    std::cout << detailsMap.size() << std::endl;
    std::cout << std::boolalpha << (it1 == detailsMap.end()) << std::endl; // false
    std::cout << std::boolalpha << (it1 == it2) << std::endl; // true
}

Note however that GCC didin't implement it until revision 219888.

Upvotes: 12

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275966

C++14 added is_transparent support to map orderings.

struct compare_helper {
  X const* px = nullptr;
  Y const* py = nullptr;
  compare_helper(compare_helper&&)=default;
  compare_helper(X const& x):px(&x) {}
  compare_helper(Y const& y):py(&y) {}
  explicit operator bool()const{return px&&py;}
  friend bool operator<(compare_helper&& lhs, compare_helper&& rhs) {
    if (!lhs || !rhs) {
      return !rhs < !lhs;
    }
    // TODO: compare lhs and rhs based off px and py
  }
};
struct ordering_helper {
  using is_transparent=std::true_type;
  bool operator()(compare_helper lhs, compare_helper rhs)const{
    return std::move(lhs)<std::move(rhs);
  }
};

now redefine your std::map:

std::map<X, Details, ordering_helper> detailsMap;

and you are done. You can now pass an Y const& to detailsMap.find or whatever.

Now // TODO: compare lhs and rhs based off px and py is a bit annoying.

But it should be writable.

If you need many different classes to be able to compare against X, and you either need a large compare_helper class with each saved, or you need to type-erase the operation somehow.

Basically, compare_helper needs to store a pointer-to-X, or a std::function< int(X const&) > which tells you if the X is less than, equal to, or greater than the other parameter. (you'll note this fails when comparing a Y against a Y or a Z against a Y -- in that case, returning false should be safe, as you'll only ever see one non-X in a given map search).

We can decouple this from the definition of compare_helper with some ADL:

struct compare_helper {
  X const* px = nullptr;
  using f_helper = std::function< int(X const&) >;
  f_helper not_X;
  compare_helper(compare_helper&&)=default;
  compare_helper(X const& x):px(std::addressof(x)) {}
  template<class NotX,
    class=std::enable_if_t< std::is_convertible<
      decltype(compare_with_X( std::forward<NotX>(notx) ))
      , f_helper
    >{}
  >
  compare_helper( NotX&& notx ):
    not_X( compare_with_X( std::forward<NotX>(notx) ) )
  {}
  explicit operator bool()const{return px&&not_X;}
  friend bool operator<(compare_helper&& lhs, compare_helper&& rhs) {
    if (!lhs || !rhs) {
      return !rhs < !lhs;
    }
    if (lhs.px && rhs.px) { return *lhs.px < *rhs.px; }
    if (lhs.px && rhs.not_X) { return rhs.not_X(*lhs.px) < 0; }
    if (lhs.not_X && rhs.px) { return lhs.not_X(*rhs.px) > 0; }
    else return false;
  }
};

now the end-user simply has to override the free function compare_with_X in the namespace of the type you want to compare with X to return a std::function<int(X const&)>, and the above map allows lookup from your non-X type.

Upvotes: 1

Related Questions