find() for std::set

Question

I have a question on how the objects stored in set are compared.

class A
{
public:  
char * name;
};

I am storing objects of A in a set. I am provide a comparator class which provides implementation of operator() ( A &ob1, A & ob2 ). Here I compare ob1.name & ob2.name and return true when ob1.name is lesser than ob2.name.

Will I be able to search for an object using the find() of set ? I have provided implementation only for operator(). Will this be sufficient ? Could someone explain how find() works in this case ?

Thanks in advance

Answer 1

Will I be able to search for an object using the find() of set ? I have provided implementation only for operator(). Will this be sufficient ?

Yes, it will be sufficient to provide only comparator class with implementation for operator ()(A&,A&) only. See default comparator std::less<>.

Could someone explain how find() works in this case ?

Very simple speaking: std::set<T,comparator>::find(k) returns iterator it if and only if both comparison fails:

1. false == comparator(k,*it)
2. false == comparator(*it, k)

Otherwise it returns std::set<>::end()...

---

Speaking in mathematical sense - std::set define equality by its weak ordering by this formula:

  a == b  <==>  !(a < b) && !(b < a)

Answer 2

The function that will be used in std::set::find() is an instance of the Comparator class that you declared as a template parameter of your set.

template < class Key, class Compare = less<Key>,
           class Allocator = allocator<Key> > class set;

Concretely, the comparator instance will be passed to Key objects and should return true if the first is located before the second. So yes, your implementation is fine.

Now, to dig further: if you want to convince yourself, you can dig into the source code of gcc’s implementation of the standard library, and you’ll find:

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue,
              _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    find(const _Key& __k)
    {
      iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
      return (__j == end()
          || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
    }

You can see that _M_key_compare (which is an instance of the _Compare class you provided), is called with __k as a first parameter (one of your Key) and the return value of _S_key(...) which is a key. The return value of _M_key_compare is used in a ternary expression, so it should be a boolean.