Find () for std :: set

Question

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

class A { public: char * name; }; 

I store objects A in a set. I provide a comparator class that provides an implementation of the () operator (A & ob1, A and ob2). Here I compare ob1.name and ob2.name and return true when ob1.name is less than ob2.name.

Will I search for an object using find ()? I have provided an implementation for operator () only. Would that be enough? Can someone explain how find () works in this case?

Thank you in advance

Answer 1

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; 

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

Now, to dig further: if you want to convince yourself, you can delve into the source code of the gccs implementation of the standard library, and you will 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 that you provided) is called with __k as the first parameter (one of your Key ) and the return value is _S_key(...) which is the key. The return value of _M_key_compare used in the _M_key_compare expression, so it should be logical.

Answer 2

Will I search for an object using find ()? I have provided an implementation for operator () only. Would that be enough?

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

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

A very simple expression: std::set<T,comparator>::find(k) returns the iterator it if and only if both comparisons fail:

• false == comparator (k, * it)
• false == comparator (* it, k)

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

---

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

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

Answer 3

I store objects A in a set. I provide a comparator class that provides an implementation of the () operator (A & ob1, A and ob2).

This is not true. The std::set container supports elements ordered by the comparator that is configured in the second argument of the template. To ensure that the invariant of order is not violated, the container stores the keys as constant objects, and this, in turn, means that the comparator must take const & keys.

In general, comparators should offer operator() , which takes two elements by const-reference, and the member function should be const itself:

 struct comparator : std::binary_function<A,A,bool> { bool operator()( A const& lhs, A const& rhs ) const; }; 

Answer 4

you can use set.find or set.count, set :: find () returns set :: end () if the element is not found, the count of the number is zero if the element is not found.

 set<Item*> itemSet; Item* item = new Item(); if (itemSet.count(item) == 0) { std::cout<<"not found" } //or if (itemSet.find(item) == itemSet.end()) { std::cout<<"not found" }