473,219 Members | 1,473 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,219 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 5798
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

8
by: Kin Pang | last post by:
Hi, I have a routine where I'm using a std::map from a pair of ints to double for caching evaluation results. The cache depth could be upto say 1000 in depth. However, my application needs to...
26
by: Pieter Thysebaert | last post by:
Hello, I've got a question conerning erasing key-value pairs from a std::map while iterating over it. According to the STL docs, erasing an element in a map invalidates all iterators pointing...
7
by: Kevin W. | last post by:
How do I sort a map by the value, rather than the key? (either automatically or with the sort function.) -- Kevin W :-) Opera/CSS/webdev blog: http://www.exclipy.com/ Using Opera:...
5
by: Peter Jansson | last post by:
Hello, I have the following code: std::map<int,std::set<std::string> > k; k="1234567890"; k="2345678901"; //... std::set<std::string> myMethod(std::map<int,std::set<std::string> > k)...
3
by: vertigo | last post by:
Hello I have std::map object and i want to have randomly sorted objects in it. I tried to: std::map<int,RandomCompare> myobject; and: struct RandomCompare{ bool operator(int i1, int i2){
13
by: kamaraj80 | last post by:
Hi I am using the std:: map as following. typedef struct _SeatRowCols { long nSeatRow; unsigned char ucSeatLetter; }SeatRowCols; typedef struct _NetData
10
by: desktop | last post by:
If I have: std::map<int,intm; where I have: m.insert(std::make_pair(1,2)); how do I update the value to 7 associated with key = 1?
8
by: mveygman | last post by:
Hi, I am writing code that is using std::map and having a bit of an issue with its performance. It appears that the std::map is significantly slower searching for an element then a sequential...
6
by: Juha Nieminen | last post by:
joseph cook wrote: Not always. By default, yes, but you can specify other comparators, eg: std::map<int, int, std::greaterreversedMap;
1
isladogs
by: isladogs | last post by:
The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, Mike...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
0
by: jianzs | last post by:
Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
by: jimatqsi | last post by:
The boss wants the word "CONFIDENTIAL" overlaying certain reports. He wants it large, slanted across the page, on every page, very light gray, outlined letters, not block letters. I thought Word Art...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

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.