468,463 Members | 2,121 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,463 developers. It's quick & easy.

STL map--> sort by value?

Jae
Hi

I wonder how can I implement the STL map sorting by value.

For example, I have a map m

map<int, intm;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1

and then.. I'd like to sort that with the m's value.
So, if I print the map, I'd like to get the result like

m[6] = 1
m[2] = 5
m[4] = 6
m[1] = 10

this.

How can I sort like this way?
Is there any way that I can deal with the key and value with sorted values?


Oct 21 '06 #1
9 16453
Jae wrote:
Hi

I wonder how can I implement the STL map sorting by value.
Maps are always sorted by key. That's a requirement of the algorithm that
makes maps so fast for searching by key.
For example, I have a map m

map<int, intm;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1

and then.. I'd like to sort that with the m's value.
So, if I print the map, I'd like to get the result like

m[6] = 1
m[2] = 5
m[4] = 6
m[1] = 10

this.

How can I sort like this way?
Is there any way that I can deal with the key and value with sorted
values?
Well, why don't you swap the key with the value? Then the map is sorted just
like you want it.

Oct 21 '06 #2
Jae
"Rolf Magnus" <ra******@t-online.dewrote in message
news:eh*************@news.t-online.com...
Jae wrote:
>Hi

I wonder how can I implement the STL map sorting by value.

Maps are always sorted by key. That's a requirement of the algorithm that
makes maps so fast for searching by key.
>For example, I have a map m

map<int, intm;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1

and then.. I'd like to sort that with the m's value.
So, if I print the map, I'd like to get the result like

m[6] = 1
m[2] = 5
m[4] = 6
m[1] = 10

this.

How can I sort like this way?
Is there any way that I can deal with the key and value with sorted
values?

Well, why don't you swap the key with the value? Then the map is sorted
just
like you want it.
Well. Because I have a case that

m[1] = 10;
m[3] = 10;

like this. If I swap it, then m[10] cannot store the m[1] and m[3] both.
That's the problem..
Oct 21 '06 #3
On Sat, 21 Oct 2006 11:33:11 -0700 in comp.lang.c++, "Jae"
<su*****@stanford.eduwrote,
>Well. Because I have a case that

m[1] = 10;
m[3] = 10;

like this. If I swap it, then m[10] cannot store the m[1] and m[3] both.
Then you would need std::multimap;
Oct 21 '06 #4

Jae wrote:
"Rolf Magnus" <ra******@t-online.dewrote in message
news:eh*************@news.t-online.com...
Jae wrote:
Hi

I wonder how can I implement the STL map sorting by value.
Maps are always sorted by key. That's a requirement of the algorithm that
makes maps so fast for searching by key.
For example, I have a map m

map<int, intm;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1

and then.. I'd like to sort that with the m's value.
So, if I print the map, I'd like to get the result like

m[6] = 1
m[2] = 5
m[4] = 6
m[1] = 10

this.

How can I sort like this way?
Is there any way that I can deal with the key and value with sorted
values?
Well, why don't you swap the key with the value? Then the map is sorted
just
like you want it.

Well. Because I have a case that

m[1] = 10;
m[3] = 10;

like this. If I swap it, then m[10] cannot store the m[1] and m[3] both.
That's the problem..
Then obviously you can't use a map. Try a multimap perhaps.

Oct 21 '06 #5
Jae

"Salt_Peter" <pj*****@yahoo.comwrote in message
news:11**********************@f16g2000cwb.googlegr oups.com...
>
Jae wrote:
>"Rolf Magnus" <ra******@t-online.dewrote in message
news:eh*************@news.t-online.com...
Jae wrote:

Hi

I wonder how can I implement the STL map sorting by value.

Maps are always sorted by key. That's a requirement of the algorithm
that
makes maps so fast for searching by key.

For example, I have a map m

map<int, intm;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1

and then.. I'd like to sort that with the m's value.
So, if I print the map, I'd like to get the result like

m[6] = 1
m[2] = 5
m[4] = 6
m[1] = 10

this.

How can I sort like this way?
Is there any way that I can deal with the key and value with sorted
values?

Well, why don't you swap the key with the value? Then the map is sorted
just
like you want it.

Well. Because I have a case that

m[1] = 10;
m[3] = 10;

like this. If I swap it, then m[10] cannot store the m[1] and m[3] both.
That's the problem..

Then obviously you can't use a map. Try a multimap perhaps.
Can I sort the multimap's value?
Oct 21 '06 #6
"Jae" <su*****@stanford.eduwrote:
Hi

I wonder how can I implement the STL map sorting by value.

For example, I have a map m

map<int, intm;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1

and then.. I'd like to sort that with the m's value.
So, if I print the map, I'd like to get the result like

m[6] = 1
m[2] = 5
m[4] = 6
m[1] = 10

this.

How can I sort like this way?
Is there any way that I can deal with the key and value with sorted values?
The easiest way is to put them in a set.

typedef map<int, intMyMap;

struct LessRight
{
bool operator()( const MyMap::value_type& lhs,
const MyMap::value_type& rhs ) const
{
return lhs.second < rhs.second;
}
};

typedef set< MyMap::value_type, LessRight MySet;

ostream& operator<<( ostream& os, const MySet::value_type& v ) {
return os << "m[" << v.first << "] = " << v.second;
}

int main() {
MyMap m;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1;

MySet s( m.begin(), m.end() );
MySet::iterator it = s.begin();
while ( it != s.end() ) {
cout << *it++ << '\n';
}
}

--
There are two things that simply cannot be doubted, logic and perception.
Doubt those, and you no longer*have anyone to discuss your doubts with,
nor any ability to discuss them.
Oct 21 '06 #7
Rolf Magnus <ra******@t-online.dewrote:
Jae wrote:
Hi

I wonder how can I implement the STL map sorting by value.

Maps are always sorted by key. That's a requirement of the algorithm that
makes maps so fast for searching by key.
For example, I have a map m

map<int, intm;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1

and then.. I'd like to sort that with the m's value.
So, if I print the map, I'd like to get the result like

m[6] = 1
m[2] = 5
m[4] = 6
m[1] = 10

this.

How can I sort like this way?
Is there any way that I can deal with the key and value with sorted
values?

Well, why don't you swap the key with the value? Then the map is sorted just
like you want it.
You might have to use a multimap in that case.

--
There are two things that simply cannot be doubted, logic and perception.
Doubt those, and you no longer have anyone to discuss your doubts with,
nor any ability to discuss them.
Oct 21 '06 #8
LR
Jae wrote:
Hi

I wonder how can I implement the STL map sorting by value.

For example, I have a map m

map<int, intm;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1

and then.. I'd like to sort that with the m's value.
So, if I print the map, I'd like to get the result like

m[6] = 1
m[2] = 5
m[4] = 6
m[1] = 10

this.

How can I sort like this way?
I'm not 100% certain I understand what you mean by sort in this context.

Is there any way that I can deal with the key and value with sorted values?
What kind of container do you want to sort them in?

Could this possibly be what you're looking for?

-------------------------------------------------------------------
#include <iostream>
#include <map>
#include <utility>

typedef std::map<int,intNormalMap;
typedef std::map< std::pair<int,int>, NormalMap::const_iterator >
ReverseMap;

int main() {
NormalMap m;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1;
m[11] = 10;
// note second '10' value,
// but all keys are still unique

// if the NormalMap is going to change
// often in the code, then this might
// be better in a function
ReverseMap n;
for(NormalMap::const_iterator i=m.begin(); i!=m.end(); i++) {
// note that key,value has become
// value, key here
// each of these pairs will be
// unique, because the key
// from the NormalMap is
// unique
n[ std::make_pair(i->second,i->first) ] = i;
}

// the ReverseMap is ordered by the value,key from the
// NormalMap, and its mapped_type is a const_iterator
// to the NormalMap
for(ReverseMap::const_iterator i=n.begin(); i!=n.end(); i++) {
NormalMap::const_iterator j = i->second;
std::cout << "m[" << j->first
<< "] = " << j->second << ";"
<< std::endl;
}
}
--------------------------------------------------

And the output was:

-----------------------------
m[6] = 1;
m[2] = 5;
m[4] = 6;
m[1] = 10;
m[11] = 10;
------------------------------

You could also put the data from the NormalMap into a std::set,
reversing the key and value.

LR
Oct 21 '06 #9

Jae wrote:
"Salt_Peter" <pj*****@yahoo.comwrote in message
news:11**********************@f16g2000cwb.googlegr oups.com...

Jae wrote:
"Rolf Magnus" <ra******@t-online.dewrote in message
news:eh*************@news.t-online.com...
Jae wrote:

Hi

I wonder how can I implement the STL map sorting by value.

Maps are always sorted by key. That's a requirement of the algorithm
that
makes maps so fast for searching by key.

For example, I have a map m

map<int, intm;
m[1] = 10;
m[2] = 5;
m[4] = 6;
m[6] = 1

and then.. I'd like to sort that with the m's value.
So, if I print the map, I'd like to get the result like

m[6] = 1
m[2] = 5
m[4] = 6
m[1] = 10

this.

How can I sort like this way?
Is there any way that I can deal with the key and value with sorted
values?

Well, why don't you swap the key with the value? Then the map is sorted
just
like you want it.


Well. Because I have a case that

m[1] = 10;
m[3] = 10;

like this. If I swap it, then m[10] cannot store the m[1] and m[3] both.
That's the problem..
Then obviously you can't use a map. Try a multimap perhaps.

Can I sort the multimap's value?
no, unless the value itself (or a component thereof), is the key. A
multimap, like most associative containers, use a key to sort its
elements at insertion based on a predicate. In other words, its
impossible to have an associative container that is not sorted. The
question is: how is it sorted?
Answer: a key + a predicate. What the key is and how the predicate
sorts those keys is completely programmeable.

So if a map is a sorted container of element-pairs <key, valuewhere
all the keys are unique but some values may have duplicates, and you
need to sort by values (with duplicates), you'ld swap the map with a
multimap in order to allow for the duplicate keys. The map's value
becomes the multimap's key. Of course, swapping a map-element's value
to become a multimap-element's key is something you'll need to do
programatically, but thats a minor issue.

Note that even the multimap's duplicate keys themselves can be sorted
if that predicate is appropriately written.

Oct 22 '06 #10

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

17 posts views Thread by parvus | last post: by
2 posts views Thread by keys4worship | last post: by
48 posts views Thread by Alex Chudnovsky | last post: by
15 posts views Thread by bcochofel | last post: by
1 post views Thread by VanZandt | last post: by
reply views Thread by NPC403 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.