Map with sorting basesd on frequency(value)
Difference between en1 and en2, changed 2 character(s)
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;↵
}↵


```

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English beyondpluto 2023-01-30 19:09:22 117
en3 English beyondpluto 2023-01-29 12:41:15 81
en2 English beyondpluto 2023-01-29 12:38:02 2
en1 English beyondpluto 2023-01-29 12:37:42 1384 Initial revision (published)