Custom Comparators (Behind the scene)

Revision en6, by Electron, 2021-03-17 08:48:06

Ofcourse there are a lot of blogs about custom comparators on internet but what I find is most of them don't talk about the precautions which one must take while using them in solving questions. I encountered quite a bit difficulty in using it to solve this problem. Do give it a try!!

Syntax

So lets start with the very basic syntax of writing a custom comparator:

struct cmp {
    bool operator() (const datatype& a, const datatype& b) const {
        return return_value;
    }
}

Do check this link for other syntax as well.

So lets talk about what this comparator actually do. Whenever you insert, find or erase any particular element the container will work according to the definition in the comparator. This is quite obvious but lets look at some detail.

Set deleting non-equal elements

Lets look at this situation, where we are considering a structure.

struct example {
    int compare_element, b, c;
}

and use this comparator

struct cmp {
    bool operator() (const example& a, const example& b) const {
        return a.compare_element < b.compare_element;
    }
};

Now, in our cmp (comparator), we will compare 2 elements just by using 'compare_element' of 'example' structure. Lets consider a set container, and insert {1, 2, 3} and {1, 5, 6}. Well these elements are unique so the set must have size 2 after these operations. Check this link for the output. But, the size of the set is 1, with element {1, 2, 3}. This is because set always store unique elements but what made those two elements same, obviously the comparator. As I said the comparator is used in every operation, whether it is insert or erase for finding the element. So in the comparator we are only comparing 'compare_element' which in both the elements is same, so set regards them as equal, whatever may be there other elements, and simply omits the insertions of {1, 5, 6}.

Points to remember

So, you must remember these points:

  • After declaring the comparator, the container always work according to the definition in the comparator. It is even possible that the comparator will find that two elements are equal even if they are not just because of what you have written in the comparator.
  • To be on a safer side always handle equality in your comparator.

multiset find operation giving wrong output

You must be thinking that, then you can use a multiset, but keep in mind that your comparator will be used even when you are using 'find' operation.

So, to demonstrate this, in the above example lets consider a multiset in which after insert operations we are finding {1, 5, 6}. Check this link for the output. Again we got some weird output, where we were finding {1, 5, 6} but got {1, 2, 3} as our result. Before proceeding one must remember that multiset 'find' operation returns the very first element it finds equal to the element searched. So as already discussed, according to our comparator definition all the containers will regard {1, 2, 3} and {1, 5, 6} as equal, and that's what happened in this case. Even, if you try to find {1, 88, 36}), in the above multiset, which does not even exits, just because of the comparator, you will be able to get an output instead of nothing(which ideally should be the answer). Such weird things can happen in contests, if you are not aware what is actually happening behind the scene.

Please consider giving feedback on any error which I may have committed. Thankyou.

Tags #multiset, #set

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en7 English Electron 2021-03-17 08:50:43 19
en6 English Electron 2021-03-17 08:48:06 19
en5 English Electron 2021-03-17 08:25:39 215 Tiny change: ' answer)** Such weir' -> ' answer)**. Such weir'
en4 English Electron 2021-03-17 08:13:54 7 (published)
en3 English Electron 2021-03-17 08:12:15 44
en2 English Electron 2021-03-17 08:07:16 3059
en1 English Electron 2021-03-17 07:14:55 514 Initial revision (saved to drafts)