Have std::map sorted by value

[Matthias Pfeifer]

Hi there,

a std::map is build from std:air 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

 

[Reetesh Mukul]

Hi there,

a std::map is build from std:air 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:air<T,U> based map, such that the
map is sorted on the basis of U (and not on the basis of T) ?
Regards,
RM

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

Hi there,

a std::map is build from std:air 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.

 

[Matthias Pfeifer]

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:perator[].

What do you want? Do you want std:air<T,U> based 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:air<typeA, typeB> mytype;
std::map<mytype> mymap;

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

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

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:perator[].

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:air<T,U> based 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:air<typeA, typeB> mytype;
std::map<mytype> mymap;

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<mytype> and 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).

 

[Jeff F]

Hi there,

a std::map is build from std:air 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

 

[Reetesh Mukul]

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:air<T,U> PAIR_;
typedef std::map<PAIR_> MAP_;
typedef MAP::iterator Iter;
typedef std:air<U,Iter> PAIR2_;
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/mcape/oss/projects/mc_projects/boost_projects/boost_bimap.html

Regards,
RM

 

[Jeff F]

Hi,

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

typedef std:air<T,U> PAIR_;
typedef std::map<PAIR_> MAP_;
typedef MAP::iterator Iter;
typedef std:air<U,Iter> PAIR2_;
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/mcape/oss/projects/mc_projects/boost_projects/boost_bimap.html

Yes, stick with well designed and tested facilities which provide full
container semantics.

Jeff