std::map sorts based on key. But what if we want the comparison to be based on value instead!
May be many people encountered this problem many times, and solved it using set< pair > and map< int >
So do I!
I have implemented a simple structure using above logic, so that one can fastly(in terms of typing) use it as template for such problem.
//Same complexity as map, with some constant factor
//sort based on value, and access based on key
template<typename T,typename U>
struct vmp { //value based map
set<pair<U, T>> vk; // {val,key}
map<T, U> kv; //{key,val}
vmp(){}
void update(T key, U newval) {
U oldval = kv[key];
auto pos = vk.find({oldval, key});
if (pos != vk.end()) {
vk.erase(pos);
}
vk.insert({newval, key});
kv[key] = newval;
}
U val(T key) {
return kv[key];
}
pair<T, U> first() {
pair<U, T> p = *vk.begin();
return {p.second, p.first};
}
void pop() {
if (!vk.empty()) {
vk.erase(vk.begin());
}
}
};
/* Extras:
* if need lower bound value, do it on vk
* if need index based acess, use ordered_pii for vk
*/
int32_t main() {
vmp<int,int> m;
m.update(3, 4); m.update(5, 2); m.update(6, -3);
// m.first() = {6,-3} //{key,val} with lowest val (if multiple same val, then based on key)
m.pop();
// m.vk = {{2,5},{4,3}}
return 0;
}
PS: I m curious to know If there any better approach than using set and map
