gopikrishna000's blog

By gopikrishna000, history, 2 months ago, In English

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}

	void update(T key, U newval) {
		U oldval = kv[key];
		auto pos = vk.find({oldval, key});
		if (pos != vk.end()) {
		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()) {
/* 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.vk = {{2,5},{4,3}}

	return 0;

PS: I m curious to know If there any better approach than using set and map

  • Vote: I like it
  • +20
  • Vote: I do not like it

2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by gopikrishna000 (previous revision, new revision, compare).

2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It would be better if it could be written as a template class type!