How can I make find() work with a set of structs?

Question

I am using a set to hold structs which contain several strings. I want to be able to use the find() functionality of sets. However, since the set is holding structs, it doesn't work. I want find() to look only at one of the strings in the struct. How can this be done?

Here's the code that I tried to use. It works fine except for the part where find() is used:

#include <iostream>
#include <string>
#include <set>
using namespace std;

struct test
{
    string key;
    string data;
};

bool operator<(const test & l, const test & r)
{
    return l.key < r.key;
}

bool operator==(const test & l, const test & r)
{
    return l.key == r.key;
}

set<test> s;

int main()
{
    test newmember;
    newmember.key = "key";
    newmember.data = "data";
    s.insert(newmember);
    s.find("key");
}

Here are the error messages that I get when I try to compile it:

test.cpp:30:7: error: no matching member function for call to 'find'
    s.find("key");
    ~~^~~~
In file included from test.cpp:3:
In file included from /usr/include/c++/4.2.1/set:65:
/usr/include/c++/4.2.1/bits/stl_set.h:429:7: note: candidate function not viable: no known conversion from 'const char [4]' to 'const key_type' (aka 'const test') for 1st argument
      find(const key_type& __x)
      ^
/usr/include/c++/4.2.1/bits/stl_set.h:433:7: note: candidate function not viable: no known conversion from 'const char [4]' to 'const key_type' (aka 'const test') for 1st argument
      find(const key_type& __x) const
      ^
1 error generated.

Answer 1

I suggest you operator< and operator== to your struct instead of overloading the global operator, I find it much cleaner; example:

struct test
{
  string key;
  string data;

  bool operator<(const test& rhs) const
  {
    return key < rhs.key;
  }

  bool operator==(const test& rhs) const
  {
    return key == rhs.key;
  }
};

Now on to your real problem - your are passing a string to the find() function, but it only accepts structs of type test. In order to do so, add a constructor for automatic conversion, so the final struct would look like this:

struct test
{      
  string key;
  string data;

  test(const std::string& strKey = "", const std::string& strData = "")
  : key(strKey),
    data(strData) {}

  bool operator<(const test& rhs) const
  {
    return key < rhs.key;
  }

  bool operator==(const test& rhs) const
  {
    return key == rhs.key;
  }
};

Then passing a string to find() would automatically call the constructor and create a temporary test struct containing only the relevant key. Note that in this special case, the constructor must not be declared explicit.

Answer 2

To be able to put your structs into set you have to specify operator< for your struct. You can make the operator< return result from comparing corresponding string members.

To be able to use find you can specify operator== for your struct to return true if corresponding string members are equal.

Sample:

    // code from your question used here

    int main()

{
    test newmember;
    newmember.key = "key";
    newmember.data = "data";

    test findMember;
    findMember.key = "key";
    // as operator== and operator< doesn't care about data field we can left it be
    // initialized by default constructor

    s.insert(newmember);
    s.find(findMember);
}

If you want to call find() with string parameter you can provide an implicit constructor from string for your test struct for example like this:

struct test {
//...
  test(const string &in_key) : key(in_key) {}
//...
};

But usage of implicit constructors isn't a good technique, because it can lead to some unpredictable conversions somewhere further in your code.

Answer 3

First and foremost, in order to make std::set::find() work with your struct, you don't need to specify operator==, as explained for std::set:

[...] two objects a and b are considered equivalent if neither compares less than the other: !comp(a, b) && !comp(b, a).

However, your actual problem is, that you can't search for parts of your struct by using find() prior to C++14. Prior to C++14, find() expects an element as argument, whose type matches the type of elements stored in the set. For your case, this means that you have to provide an instance of test. However, as your operator< compares only the key variables, you can use a dummy value for the data variable, for example, as follows:

test newmember;
newmember.key = "key";
newmember.data = "data";
s.insert(newmember);

auto it = s.find(test{ "key", "" });  // "" is the dummy variable.
std::cout << it->key << ", " << it->data << std::endl;

Output:

key, data

Please be aware that your operator< which compares only the key variables has a side effect: Two instances of test can only be stored in the set if their key variables are different, even if their data variables are different. For example, if you append the following code to the code above, then newmember will not be inserted (again):

newmember.data = "otherdata";
s.insert(newmember);  // Insertion fails!
for (auto const& t : s) {
    std::cout << t.key << ", " << t.data << std::endl;
}

Output:

key, data

Consequently, if you want to store multiple elements with the same key, then you might have to choose a different container.

Anyway, if a set of struct is fine for you and you can make use of C++11, then you can also use a lambda expression instead of defining operator< for your struct:

auto comp = [](const test& t1, const test& t2) { return t1.key < t2.key; };
std::set<test, decltype(comp)> s(comp);

Code on Ideone

---

C++14

Since C++14, you can use find() to do a "transparent comparison" as explained on std::set::find(). This means, that you can find an element that compares equivalent to the given argument. In detail this means, that you have to define operator< and your set as follows:

bool operator<(const test& t, const std::string& str) { return t.key < str; }
bool operator<(const std::string& str, const test& t) { return str < t.key; }
bool operator<(const test& t1, const test& t2) { return t1.key < t2.key; }
std::set<test, std::less<>> s;

Then you can perform your find() operation as you would have expected it to work:

test newmember;
newmember.key = "key";
newmember.data = "data";
s.insert(newmember);

auto it = s.find("key");
std::cout << it->key << ", " << it->data << std::endl;

Output:

key, data

Code on Ideone

Answer 4

Only you have to override operator<() function to enhance find function. In your case simply replace operator<() function as..

bool operator<(const offer& t1) const {
    if(this->key< t1.key)
        return true;
    else if(this->key == t1.key){
         if(this->data < t1.data)
             return true;
         else
             return false;
    }
    else
        return false;
}