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, int> m;
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?

 

[Rolf Magnus]

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, int> m;
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.

 

[Jae]

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, int> m;
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..

 

[David Harmon]

On Sat, 21 Oct 2006 11:33:11 -0700 in comp.lang.c++, "Jae"

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;

 

[Salt_Peter]

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, int> m;
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.

 

[Jae]

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, int> m;
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?

 

[Daniel T.]

Hi

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

For example, I have a map m

map<int, int> m;
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, int> MyMap;

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';
}
}

 

[Daniel T.]

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, int> m;
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.

 

[LR]

Hi

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

For example, I have a map m

map<int, int> m;
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,int> NormalMap;
typedef std::map< std:air<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

 

[Salt_Peter]

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, int> m;
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, value> where
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.