Map with sorting bases on frequency(value)

Revision en1, by beyondpluto, 2023-01-29 12:37:42

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
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)