Find in a set containing self defined type

Question

I have a set storing self defined data, and I'd like to search it by key value.

Here is a simple example:

struct Data {
  Data(int x, int y):x(x), y(y){}
  int x;
  int y;
};

struct Compare {
  bool operator() (const Data& lhs, const Data& rhs) {
    return lhs.x < rhs.x;
  }
};

int main()
{
  set<Data, Compare> s;
  s.insert(Data(2, 77));
  s.insert(Data(3, 15));
  s.insert(Data(1, 36));
  for (auto i:s)
    cout<<i.x<<" "<<i.y<<endl;

  auto i = s.find(3);  // <-- Not working
  auto i = s.find(Node(3, 0));
  if (i != s.end())
    cout<<"found"<<endl;
  else
    cout<<"not found"<<endl;
}

This set is sorted only by x, but I have to create a temp object to search in the set: s.find(Node(3, 0))

Is it possible to search by key only? i.e. s.find(3)?

You may want to look at `std::map`. – n. m. could be an AI Sep 18 '15 at 13:58 — n. m. could be an AI, Sep 18 '15 at 13:58
@n.m. nice one, will think about it – Deqing Sep 19 '15 at 03:17 — Deqing, Sep 19 '15 at 03:17

score 0 · Answer 1 · answered Sep 18 '15 at 14:04

0

Why don't you write something like this?

Data myFind(const set<Data, Compare>& s, int x) {
   auto it = s.find(Node(x, 0));
   return *it;
}

answered Sep 18 '15 at 14:04

c.bear

1,197
8
21

score 0 · Answer 2 · edited May 23 '17 at 10:26

Your code has a bug. std::set is a unique container, meaning that it expects not to contain two values which are equal to each other. However, by giving the set a comparison function which only uses x, you've made it so two values with the same x component will be considered equal by the set, regardless of whether their y's match. This will prevent you from inserting more than one value for an x. (That may be what you want... if so, ignore this part.) A better comparison would break ties in x by looking at y (this is known as a "lexicographic" comparison:

struct Compare {
  bool operator() (const Data& lhs, const Data& rhs) {
    if(lhs.x != rhs.x) return lhs.x < rhs.x;
    return lhs.y < rhs.y;
  }
};

Now, as for searching by something that doesn't have the same type as the keys. This became possible in C++14 due to some new overloads in the associative containers' search function. See the first answer to Raw pointer lookup for sets of unique_ptrs for more information. Basically, you give your comparator an "is_transparent" member to flag it, and you make it able to compare Datas with whatever type you intend to search by.

score 0 · Accepted Answer · answered Sep 18 '15 at 17:20

In c++14, you can make use of is_transparent:

Finds an element with key that compares equivalent to the value x. This overload only participates in overload resolution if the qualified-id Compare::is_transparent is valid and denotes a type. It allows calling this function without constructing an instance of Key

struct Compare {
  using is_transparent = std::true_type;
  bool operator() (const Data& lhs, const Data& rhs) const {
    return lhs.x < rhs.x;
  }
  bool operator() (const Data& lhs, const int & rhsx) const {
    return lhs.x < rhsx;
  }
  bool operator() (const int & lhsx, const Data& rhs) const {
    return lhsx < rhs.x;
  }
};

Now your code is valid.

Find in a set containing self defined type

3 Answers3