std::map sorts based on key. But what if we want the comparison to be based on value instead! <br>↵
May be many people encountered this problem many times, and solved it using set< pair > and map< int > <br>↵
So do I!<br>↵
↵
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↵
struct vmp { //value based map↵
set<pair<int, int>> vk; // {val,key}↵
map<int, int> kv; //{key,val}↵
void update(int key, int newval) {↵
int oldval = kv[key];↵
auto pos = vk.find({oldval, key});↵
if (pos != vk.end()) {↵
vk.erase(pos);↵
}↵
vk.insert({newval, key});↵
kv[key] = newval;↵
}↵
int val(int key) {↵
return kv[key];↵
}↵
pair<int, int> first() {↵
pair<int, int> 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 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;↵
}↵
↵
↵
```
May be many people encountered this problem many times, and solved it using set< pair > and map< int > <br>↵
So do I!<br>↵
↵
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↵
struct vmp { //value based map↵
set<pair<int, int>> vk; // {val,key}↵
map<int, int> kv; //{key,val}↵
void update(int key, int newval) {↵
int oldval = kv[key];↵
auto pos = vk.find({oldval, key});↵
if (pos != vk.end()) {↵
vk.erase(pos);↵
}↵
vk.insert({newval, key});↵
kv[key] = newval;↵
}↵
int val(int key) {↵
return kv[key];↵
}↵
pair<int, int> first() {↵
pair<int, int> 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 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;↵
}↵
↵
↵
```
