Is it possible to use a structure as the key of a map?! If it is, then how can I do this? thanks in advance.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | adamant | 157 |
6 | awoo | 157 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | djm03178 | 153 |
Is it possible to use a structure as the key of a map?! If it is, then how can I do this? thanks in advance.
Name |
---|
Yes, but you have to implement the Boolean comparison operator '<' that the map class uses to order the entries.
For example:
Got it.. Thanks man.. Using this just solve today's CF round D2 E.. :)
With pleasure.
The Boolean comparison operator< is also used by the sort() function to sort an array of structure items, and by other containers such as a set or a list when it is required to order a set or a list of structure items.
For example,
This method helps in solving many CF problems as well.
Thanks for your kind information :)
Suppose I have a vector of a structure. It is sorted by the operator overloading method. Now, can I apply upper_bound and lower_bound operations on this vector ? how ?
Yes, as long as the vector has been sorted using the Boolean operator<.
Example:
Output:
1 2
3 4
5 6
3 4
5 6
The following is the previous example augmented with
struct myvector
wrapper forvector< mystruct >
:And that is not a valid comparison operator. Please read http://en.cppreference.com/w/cpp/concept/Compare .
Thanks for your comment.
A C++11 solution for problem 869E - Неприглядная античность has successfully used this operator to order points and rectangles in a 2D grid, please read 31224413.
Can you briefly explain the reason that this operator is invalid?
Thanks in advance.
The equivalence established by operator isn't transitive. For pairs a=(1, 5), b=(3,1), c=(4, 2) a=b a=c and b<c. It might work if if input is guaranteed not to contain such input or were simply lucky that with given inputs and STL implementation details output was suitable to rest of your code.
So on cppreference page it says that transitivity for
equiv
function should be fullfilled whereequiv(a,b)
=!comp(a,b) && !comp(b,a)
wherecomp
is your comparison function.In your case it is not fullfilled. For example:
What implications it may have during sort:
For example: (3,2), (1,3), (2,1) is technically valid sorted sequence even though (2,1) < (3,2). If during our sort we compare only neighbour values then our sort would stop without any changes because sequence is already observably sorted.
As for why it worked for the task — I don't know, it probably requires some additional investigation. But you better avoid using such operators since result is undefined.
Thanks for the clarification.
In the statement of the aforementioned problem, it is guaranteed that no two rectangle boundaries intersect.
The solution uses a rectangle_tree class whose root node is the entire 2500 x 2500 area. The children of each node (u) in the rectangle_tree are the largest non-intersecting rectangles contained in (u). Insertions and deletions update the tree according to inserted/deleted rectangles. A walk query returns "Yes" if and only if the smallest rectangles containing the source and the target cells are the same.
The Boolean operator are used to compare the corresponding upper-left and lower-right of rectangle pairs preserving the order of the corner cells, and to compare query points to those corner cells. Therefore, there is on luck in the success of the solution.
It is just the case that those counterexamples mentioned in your clarification are guaranteed to never take place.
The Boolean operator< is NOT used to sort an array of 2D points. It is just used to update the rectangle tree when a rectangle is inserted or deleted.
Best Regards.
I thought we were talking about comparator for STL functions. The requirements are what STL expects. If you only use it yourself it can do whatever you want even multipliciation. That doesn't mean it's always a good idea even more so if you give it as example of how to use it with map. Abusing operator overloading can easily cause misunderstandings like this when it is not obvious what operator X does for structure Y or it doesn't match conventions.
Thanks for your precious comments.
I agree with you that giving that example for sorting an array of structures was not a good choice; my apologies for the inconvenience, and my appreciation for your effort to clarify what confused you.
If you check the submitted solution, you will find that the operators
are called from the rectangle_tree methods:
The former
contains()
function returns true when the rectangle object contains rectangle (r), and the lattercontains()
function returns true when the rectangle object contains the query point given by the cell (r).The base class pair< cell, cell > is used to hold the upper-left and lower-right corners of the rectangle.
The example for implementing bool operator< has been updated to comply with STL requirements.
A word of gratitude is due to KarlisS and predelnik for their fruitful comments and efforts to elaborate the problem with the previous example.
If x and y in the previous example are known to be positive integers <= 4294967295U (UINT_MAX), then it is possible to concatenate the two 32-bit unsigned integers into one 64-bit unsigned integer using c++ union as follows:
The Boolean operator< compares the corresponding 64-bit numbers directly.