471,319 Members | 1,585 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,319 software developers and data experts.

Have std::map sorted by value

Hi there,

a std::map is build from std::pair elements where for a pair p p.first
is called the key and p.second the value. Is there a way to keep the map
sorted by the values? Ie is there a std::key_compare in the stl that
offeres this functionality? It's ok if this would make finding a key
more expensive. Writing my own would be possible, but why do it if it's
already there...

matthias
Aug 27 '07 #1
7 5654
On Aug 27, 1:54 pm, Matthias Pfeifer <pfe...@web.dewrote:
Hi there,

a std::map is build from std::pair elements where for a pair p p.first
is called the key and p.second the value. Is there a way to keep the map
sorted by the values? Ie is there a std::key_compare in the stl that
offeres this functionality? It's ok if this would make finding a key
more expensive. Writing my own would be possible, but why do it if it's
already there...

matthias
What do you want? Do you want std::pair<T,Ubased map, such that the
map is sorted on the basis of U (and not on the basis of T) ?
Regards,
RM

Aug 27 '07 #2
On 2007-08-27 10:54, Matthias Pfeifer wrote:
Hi there,

a std::map is build from std::pair elements where for a pair p p.first
is called the key and p.second the value. Is there a way to keep the map
sorted by the values? Ie is there a std::key_compare in the stl that
offeres this functionality? It's ok if this would make finding a key
more expensive. Writing my own would be possible, but why do it if it's
already there...
Use a multiset and store value-key pairs.

--
Erik Wikström
Aug 27 '07 #3
Hi Reetesh, Hi Erik

thanks for your answers. Apperently using multimap and exchange the
value and key is not possible, since we don't see way to still index the
(now) std::multimap using std::(multi)map::operator[].
What do you want? Do you want std::pair<T,Ubased map, such that the
map is sorted on the basis of U (and not on the basis of T) ?
To clarify. We have a

typedef std::pair<typeA, typeBmytype;
std::map<mytypemymap;

we want to have

std::for_each(it=mymap.begin(), mymap.end(, some_fun)

iterate over mymap beginning with smallest typeB and in the same way
still want to be able to index mymap using typeA like in

mymap[typeA()]

The question may be simplified to wether we can feed anything suitable
from inside "namespace std" into the

std::map::map( const key_compare& cmp );

constructor of std::map.

matthias
Aug 27 '07 #4
On 2007-08-27 13:00, Matthias Pfeifer wrote:
Hi Reetesh, Hi Erik

thanks for your answers. Apperently using multimap and exchange the
value and key is not possible, since we don't see way to still index the
(now) std::multimap using std::(multi)map::operator[].
Of course not, since a multimap can't guarantee that there's only one
value per key, which means that there would be an ambiguity of which of
the values to return.

If you can guarantee that the values will be unique as well as a key you
can use a normal map where you switch places between key and value.
>What do you want? Do you want std::pair<T,Ubased map, such that the
map is sorted on the basis of U (and not on the basis of T) ?

To clarify. We have a

typedef std::pair<typeA, typeBmytype;
std::map<mytypemymap;

we want to have

std::for_each(it=mymap.begin(), mymap.end(, some_fun)

iterate over mymap beginning with smallest typeB and in the same way
still want to be able to index mymap using typeA like in

mymap[typeA()]
What you want is a data structure sorted by both key and value, there is
no such thing in the standard library.
The question may be simplified to wether we can feed anything suitable
from inside "namespace std" into the

std::map::map( const key_compare& cmp );

constructor of std::map.
You could copy all the values to a vector or such and then sort the
vector and perform the operations on those, or use pointers to the
values stored in the map.

Another alternative, if you can sacrifice the efficiency of getting an
element by key, is to use std::vector<mytypeand sort it by typeB. To
find an element given a certain key would then be O(n), while finding an
element by value O(log n).

--
Erik Wikström
Aug 27 '07 #5

"Matthias Pfeifer" <pf****@web.dewrote in message
news:5j*************@mid.dfncis.de...
Hi there,

a std::map is build from std::pair elements where for a pair p p.first
is called the key and p.second the value. Is there a way to keep the map
sorted by the values? Ie is there a std::key_compare in the stl that
offeres this functionality? It's ok if this would make finding a key
more expensive. Writing my own would be possible, but why do it if it's
already there...
See http://www.boost.org/libs/multi_index/doc/index.html which has an
example of a bi-directional map. In fact a specific bi-map has been recently
reviewed and accepted into boost as well.

Jeff Flinn
Aug 28 '07 #6
On Aug 28, 5:55 am, "Jeff F" <norepl...@please.comwrote:
"Matthias Pfeifer" <pfe...@web.dewrote in message

news:5j*************@mid.dfncis.de...
Hi there,
a std::map is build from std::pair elements where for a pair p p.first
is called the key and p.second the value. Is there a way to keep the map
sorted by the values? Ie is there a std::key_compare in the stl that
offeres this functionality? It's ok if this would make finding a key
more expensive. Writing my own would be possible, but why do it if it's
already there...

Seehttp://www.boost.org/libs/multi_index/doc/index.htmlwhich has an
example of a bi-directional map. In fact a specific bi-map has been recently
reviewed and accepted into boost as well.

Jeff Flinn
Hi,

You can use this ad hoc solution by using an additional multimap, as
such,

typedef std::pair<T,UPAIR_;
typedef std::map<PAIR_MAP_;
typedef MAP::iterator Iter;
typedef std::pair<U,IterPAIR2_;
typedef std::multimap<PAIR2_MMAP_;

MAP_ A;
MMAP_ Key;
T t_;
U u_;
A[t_] = u_;
Key[u_] = A.find(t_);

Now you can iterate over Key...

Using insert can be a better option. This is an optimized solution and
I will recommend you using boost::mutlti_index as Jeff has told.
Another easier interface is boost::bimap ---
http://cablemodem.fibertel.com.ar/mc...ost_bimap.html

Regards,
RM
Aug 28 '07 #7

"Reetesh Mukul" <re***********@gmail.comwrote in message
news:11*********************@e9g2000prf.googlegrou ps.com...
On Aug 28, 5:55 am, "Jeff F" <norepl...@please.comwrote:
>"Matthias Pfeifer" <pfe...@web.dewrote in message

news:5j*************@mid.dfncis.de...
Hi there,
a std::map is build from std::pair elements where for a pair p p.first
is called the key and p.second the value. Is there a way to keep the
map
sorted by the values? Ie is there a std::key_compare in the stl that
offeres this functionality? It's ok if this would make finding a key
more expensive. Writing my own would be possible, but why do it if it's
already there...

Seehttp://www.boost.org/libs/multi_index/doc/index.htmlwhich has an
example of a bi-directional map. In fact a specific bi-map has been
recently
reviewed and accepted into boost as well.

Jeff Flinn

Hi,

You can use this ad hoc solution by using an additional multimap, as
such,

typedef std::pair<T,UPAIR_;
typedef std::map<PAIR_MAP_;
typedef MAP::iterator Iter;
typedef std::pair<U,IterPAIR2_;
typedef std::multimap<PAIR2_MMAP_;
Except most of these typedefs won't even compile even with T and U defined,
and the obvious missing '_'.
MAP_ A;
MMAP_ Key;
T t_;
U u_;
A[t_] = u_;
Key[u_] = A.find(t_);

Now you can iterate over Key...
To what end?
Using insert can be a better option. This is an optimized solution and
I will recommend you using boost::mutlti_index as Jeff has told.
Another easier interface is boost::bimap ---
http://cablemodem.fibertel.com.ar/mc...ost_bimap.html
Yes, stick with well designed and tested facilities which provide full
container semantics.

Jeff
Aug 29 '07 #8

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

8 posts views Thread by Kin Pang | last post: by
26 posts views Thread by Pieter Thysebaert | last post: by
7 posts views Thread by Kevin W. | last post: by
3 posts views Thread by vertigo | last post: by
13 posts views Thread by kamaraj80 | last post: by
10 posts views Thread by desktop | last post: by
8 posts views Thread by mveygman | last post: by
6 posts views Thread by Juha Nieminen | last post: by
reply views Thread by rosydwin | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.