Using pair (x,y) in Multiset and sort according to y value.

[shawn]

Hi all!,
I am relatively new to C++. I want to have a multiset and
not multimap, which is collection of pair,(x,y) where x may be pointer
pointing to some object and y is a value. Now I want to sort the set
accoring to y value. How can I do this, Please help..


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Mark Van Peteghem]

Post by shawn
Hi all!,
I am relatively new to C++. I want to have a multiset and
not multimap, which is collection of pair,(x,y) where x may be pointer
pointing to some object and y is a value. Now I want to sort the set
accoring to y value. How can I do this, Please help..

Create a struct to act as a function object, i.e. with method
bool operator()(std::pair &p1, std::pair &p2), and give that as an
extra template argument to your multiset. The method should return
true if the first argument is to be considered smaller than the
second, and false if equal or greater.

Example:

struct SortPair
{
bool operator()(const std::pair<int*, int> &p1,
const std::pair<int*, int> &p2) const
{
return p1.second < p2.second;
}
};

std::multiset< std::pair<int*, int>, SortPair> mySet;

[Antoun Kanawati]

Post by Mark Van Peteghem

Post by shawn
Hi all!,
I am relatively new to C++. I want to have a multiset and
not multimap, which is collection of pair,(x,y) where x may be pointer
pointing to some object and y is a value. Now I want to sort the set
accoring to y value. How can I do this, Please help..

struct SortPair
{
bool operator()(const std::pair<int*, int> &p1,
const std::pair<int*, int> &p2) const
{
return p1.second < p2.second;
}
};
std::multiset< std::pair<int*, int>, SortPair> mySet;

Doens't work; the multimap comparator sees only the key
type.

[Mark Van Peteghem]

Post by Antoun Kanawati

Post by Mark Van Peteghem

Post by shawn
Hi all!,
I am relatively new to C++. I want to have a multiset and
not multimap, which is collection of pair,(x,y) where x may be pointer
pointing to some object and y is a value. Now I want to sort the set
accoring to y value. How can I do this, Please help..

struct SortPair
{
bool operator()(const std::pair<int*, int> &p1,
const std::pair<int*, int> &p2) const
{
return p1.second < p2.second;
}
};
std::multiset< std::pair<int*, int>, SortPair> mySet;

Doens't work; the multimap comparator sees only the key
type.

Please read carefully what the OP wrote:
"I want to have a multiset and not multimap"
If I understand his question correctly, he wants a multiset
with std::pair as elements, sorted by the second part of the pairs.
Which is exactly what my solution does.

--
Mark dot Van dot Peteghem at q-mentum dot com
http://www.q-mentum.com -- easier and more powerful unit testing

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Antoun Kanawati]

Post by Mark Van Peteghem

.... [wrong answer] ...

"I want to have a multiset and not multimap"
If I understand his question correctly, he wants a multiset
with std::pair as elements, sorted by the second part of the pairs.
Which is exactly what my solution does.

Apologies for the rushed answer.

[Gerhard Menzl]

Post by Antoun Kanawati

Post by Mark Van Peteghem
struct SortPair
{
bool operator()(const std::pair<int*, int> &p1,
const std::pair<int*, int> &p2) const
{
return p1.second < p2.second;
}
};
std::multiset< std::pair<int*, int>, SortPair> mySet;

Doens't work; the multimap comparator sees only the key
type.

Is this a typo or an oversight? std::multimap doesn't come into play
here; we have a std::multiset with std::pair<int*, int> as key type.
--
Gerhard Menzl

#dogma int main ()

Humans may reply by replacing the thermal post part of my e-mail address
with "kapsch" and the top level domain part with "net".

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Antoun Kanawati]

Post by Gerhard Menzl

[bad answer]

Is this a typo or an oversight? std::multimap doesn't come into play
here; we have a std::multiset with std::pair<int*, int> as key type.

It was an error on my part, I was seeing 'map' where the OP has typed
'set'.
--
A. Kanawati
***@comcast.net

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Antoun Kanawati]

Post by shawn
Hi all!,
I am relatively new to C++. I want to have a multiset and
not multimap, which is collection of pair,(x,y) where x may be pointer
pointing to some object and y is a value. Now I want to sort the set
accoring to y value. How can I do this, Please help..

Using the same pair type, you can't re-sort the multimap since map
comparators are called to compare only the keys, and never get to
see the 'second', or y, part of the pair. There are other problems
with this interpretation of the problem statement, like: redefining the
comparison function.

If we reinterpret the statement to mean "another ordering of the same
pairs" in a different container, we can solve the problem as follows:

typedef std::multimap<int *, int> mmtype;
typedef std::mmtype::const_iterator elt_type;

inline bool less_than(const elt_type& a, const elt_type &b)
{ return a->second < b->second; }

/* another ordering of the SAME pairs */
typedef std::multiset<elt_type, less_than> mm_by_y_type;

void make_second_ordering(const mmtype &mm, mm_by_y_type &ms)
{
for(elt_type i = mm.begin(); i != mm.end(); ++i)
ms.insert(i);
}

[Seungbeom Kim]

Post by Antoun Kanawati

Post by shawn
Hi all!,
I am relatively new to C++. I want to have a multiset and
not multimap, which is collection of pair,(x,y) where x may be pointer
pointing to some object and y is a value. Now I want to sort the set
accoring to y value. How can I do this, Please help..

Using the same pair type, you can't re-sort the multimap since map
comparators are called to compare only the keys, and never get to
see the 'second', or y, part of the pair. There are other problems
with this interpretation of the problem statement, like: redefining the
comparison function.

The OP has explicitly stated that he wanted a multiset and not a multimap.
Your explanation is irrelevant to the OP's situation.

--
Seungbeom Kim

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Eric B]

Post by Antoun Kanawati

Post by shawn
Hi all!,
I am relatively new to C++. I want to have a multiset and
not multimap, which is collection of pair,(x,y) where x may be pointer
pointing to some object and y is a value. Now I want to sort the set
accoring to y value. How can I do this, Please help..

Using the same pair type, you can't re-sort the multimap since map
comparators are called to compare only the keys, and never get to
see the 'second', or y, part of the pair. There are other problems
with this interpretation of the problem statement, like: redefining the
comparison function.
If we reinterpret the statement to mean "another ordering of the same
typedef std::multimap<int *, int> mmtype;
typedef std::mmtype::const_iterator elt_type;
inline bool less_than(const elt_type& a, const elt_type &b)
{ return a->second < b->second; }
/* another ordering of the SAME pairs */
typedef std::multiset<elt_type, less_than> mm_by_y_type;
void make_second_ordering(const mmtype &mm, mm_by_y_type &ms)
{
for(elt_type i = mm.begin(); i != mm.end(); ++i)
ms.insert(i);
}

My question about this is OT, but how would you adapt this to a class.
say class A has the mmtype typedef and member of that type. What is the
best design to implement a "sorted view" object in relation to the
original map object?

Eric B


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Andrew Koenig]

Post by shawn
I am relatively new to C++. I want to have a multiset and
not multimap, which is collection of pair,(x,y) where x may be pointer
pointing to some object and y is a value. Now I want to sort the set
accoring to y value. How can I do this, Please help..

The easiest way is probably to use pair<y,x> as your element type instead of
pair<x,y>. If you do that, the multiset will automatically be sorted by y
value, and then by x value within groups of equal y values.


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[shawn]

The multiset and multimap would sort automatically for (y,x) , but
what is needed is a multiset(x,y) as this is the most fundamental way
of representing a pair.


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[k***@gabi-soft.fr]

Post by Andrew Koenig

Post by shawn
I am relatively new to C++. I want to have a
multiset and not multimap, which is collection of pair,(x,y)
where x may be pointer pointing to some object and y is a
value. Now I want to sort the set accoring to y value. How
can I do this, Please help..

The easiest way is probably to use pair<y,x> as your element
type instead of pair<x,y>. If you do that, the multiset will
automatically be sorted by y value, and then by x value within
groups of equal y values.

Wouldn't this have an effect on find? If the comparison
function only takes y into account, I would expect the following
code to visit all of the elements with the equivalent y:

multiset< pair< X, Y > >::iterator i
= m.find( pair<X,Y>( x,y ) ) ;
while ( i != m.end() && i->second == y ) {
// ...
}

If the x value is also part of the sort criterium, this will not
be the case.

Or have I misunderstood something. I wasn't able to find the
guarantee that find return an iterator to the first equal
element in the standard. But if it isn't guaranteed, how do you
visit all equal elements?

--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, [phone]


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[John Potter]

Post by k***@gabi-soft.fr
If the comparison
function only takes y into account, I would expect the following
multiset< pair< X, Y > >::iterator i
= m.find( pair<X,Y>( x,y ) ) ;
while ( i != m.end() && i->second == y ) {
// ...
}
Or have I misunderstood something. I wasn't able to find the
guarantee that find return an iterator to the first equal
element in the standard. But if it isn't guaranteed, how do you
visit all equal elements?

By using m.equal_range( pair<X,Y>( x,y ) ) for the range.

John

[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]