How to write custom comparator for std::set<std::pair<int,int>> where first element of pair must be unique

Question

I am having trouble writing a strict weak ordering comparator for std::set<std::pair<int,int>> such that the first element of an inserted pair must be unique in the set, and the second elements of the pairs must be in descending order.

Here is my implementation:

#include <set>
#include <iostream>

struct Comparator {
    bool operator()(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) {
        if (lhs.first == rhs.first) {
            return false;
        }
        
        return lhs.second > rhs.second;
    }
};


int main() {
    std::set<std::pair<int, int>, Comparator> s;
    
    s.emplace(1, 1);
    s.emplace(2, 0);
    s.emplace(2, 2);

    for (auto e : s) {
        std::cout << e.first << " " << e.second << std::endl;
    }

    return 0;
};

Expected output:

1 1
2 0

Actual output:

2 2
1 1
2 0

How do I enforce uniqueness of the first element of the pair?

Answer 1

std::set assumes that the keys are ordered based off a set of axioms known as strict weak ordering. On cppreference they give a programmer-friendly set of rules.

It requires:

Irreflexitive:

!( a < a )

Transitive:

(a < b) and (b < c) means (a < c)

then, define weak_equivalent(a,b) to mean !(a<b) and !(b<a) -- ie, neither element is less than each other, so under < we are "equivalent". Then this equivalence relation is transitive (and obviously reflexitive):

weak_equivalent(a,b) and weak_equivalent(b,c) means weak_equivalent(a,c)

ie, weak_equivalent describes a bundle of elements that are all equal to each other.

In your case, you appear to want all elements (x,_) to be equivalent under your <.

And you want it to otherwise be ordered by the second element (backwards, but that isn't important to me).

But (1,5) < (2,3) and (2,3) < (1,1), which means (1,5) < (1,1) by the transitive requirement.

That disagrees with your requirement that (1,5) and (1,1) is equivalent.

So std::set cannot support this ordering.

In general, sorting when you aren't at least a strict weak ordering is difficult, because there isn't a consistent order to your elements.

In your case, you should probably stop using a std::set directly.

struct my_special_container {
  std::map<int, int> m_s;

  void emplace_if_not_exist( int a, int b ) {
    auto it = m_s.find(b);
    if (it != m_s.end()) {
      m_s[b] = a;
    }
  }
};

now you just have to write an iterator that returns the elements; the map iterator does it backwards compared to your requirements.