Re: Have std::map sorted by value
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,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::pair<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).
--
Erik Wikstr?m