 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
shawn
Guest
|
 Posted: Mon Apr 18, 2005 9:03 am Post subject: Using pair (x,y) in Multiset and sort according to y value. |
 |
|
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! ]
|
|
| Back to top |
|
 |
Mark Van Peteghem
Guest
|
| Posted: Mon Apr 18, 2005 11:06 am Post subject: Re: Using pair (x,y) in Multiset and sort according to y val |
|
|
Shawn wrote:
| Quote: | 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 mySet;
--
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! ]
|
|
| Back to top |
|
|
Antoun Kanawati
Guest
|
| Posted: Mon Apr 18, 2005 3:13 pm Post subject: Re: Using pair (x,y) in Multiset and sort according to y val |
|
|
Mark Van Peteghem wrote:
| Quote: | Shawn wrote:
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 mySet;
|
Doens't work; the multimap comparator sees only the key
type.
--
A. Kanawati
[email]NO.antounk.SPAM (AT) comcast (DOT) net[/email]
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Antoun Kanawati
Guest
|
| Posted: Mon Apr 18, 2005 3:13 pm Post subject: Re: Using pair (x,y) in Multiset and sort according to y val |
|
|
shawn wrote:
| Quote: | 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);
}
--
A. Kanawati
[email]NO.antounk.SPAM (AT) comcast (DOT) net[/email]
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Mark Van Peteghem
Guest
|
| Posted: Tue Apr 19, 2005 9:46 pm Post subject: Re: Using pair (x,y) in Multiset and sort according to y val |
|
|
Antoun Kanawati wrote:
| Quote: | Mark Van Peteghem wrote:
Shawn wrote:
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 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! ]
|
|
| Back to top |
|
|
Seungbeom Kim
Guest
|
| Posted: Tue Apr 19, 2005 10:25 pm Post subject: Re: Using pair (x,y) in Multiset and sort according to y val |
|
|
Antoun Kanawati wrote:
| Quote: | shawn wrote:
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! ]
|
|
| Back to top |
|
|
Gerhard Menzl
Guest
|
| Posted: Wed Apr 20, 2005 9:13 am Post subject: Re: Using pair (x,y) in Multiset and sort according to y val |
|
|
Antoun Kanawati wrote:
| Quote: | 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 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! ]
|
|
| Back to top |
|
|
Andrew Koenig
Guest
|
| Posted: Wed Apr 20, 2005 9:33 am Post subject: Re: Using pair (x,y) in Multiset and sort according to y val |
|
|
| Quote: | 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! ]
|
|
| Back to top |
|
|
Antoun Kanawati
Guest
|
| Posted: Wed Apr 20, 2005 3:56 pm Post subject: Re: Using pair (x,y) in Multiset and sort according to y val |
|
|
Mark Van Peteghem wrote:
| Quote: | Antoun Kanawati wrote:
.... [wrong answer] ...
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.
|
Apologies for the rushed answer.
--
A. Kanawati
[email]NO.antounk.SPAM (AT) comcast (DOT) net[/email]
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
shawn
Guest
|
| Posted: Wed Apr 20, 2005 4:50 pm Post subject: Re: Using pair (x,y) in Multiset and sort according to y val |
|
|
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! ]
|
|
| Back to top |
|
|
Antoun Kanawati
Guest
|
| Posted: Wed Apr 20, 2005 8:56 pm Post subject: Re: Using pair (x,y) in Multiset and sort according to y val |
|
|
Gerhard Menzl wrote:
| Quote: | Antoun Kanawati wrote:
[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
[email]NO.antounk.SPAM (AT) comcast (DOT) net[/email]
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
kanze@gabi-soft.fr
Guest
|
| Posted: Thu Apr 21, 2005 12:12 pm Post subject: Re: Using pair (x,y) in Multiset and sort according to y val |
|
|
Andrew Koenig wrote:
| Quote: | 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, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Fri Apr 22, 2005 2:13 pm Post subject: Re: Using pair (x,y) in Multiset and sort according to y val |
|
|
On 21 Apr 2005 08:12:40 -0400, [email]kanze (AT) gabi-soft (DOT) fr[/email] wrote:
| Quote: | 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 ) {
// ...
}
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! ]
|
|
| Back to top |
|
|
Eric B
Guest
|
| Posted: Wed Apr 27, 2005 8:13 am Post subject: Re: Using pair (x,y) in Multiset and sort according to y val |
|
|
Antoun Kanawati wrote:
| Quote: | shawn wrote:
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);
}
|
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! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
