CODEWITHSUNDEEP
c++sortingsetstdicomparable
milennalim
milennalim

Reputation: 309

C++: Why does a functor for set order which returns false only lets one element be added to the set?

I wrote the following functor, with the expectation that all the elements in the set will be added in reverse order of their insertion:

struct cmp {
  bool operator () (int a, int b) {
    return false;
  }
};

and when I tested it as below, the only value added to the set is 1.

int main() {
  set<int, cmp > combos;

  combos.insert(1);
  combos.insert(4);
  combos.insert(7);
  combos.insert(5);
  combos.insert(9);
  combos.insert(1);

  for (int a : combos) {
    cout << a << endl;
  }
  return 0;
}

However, when I changed the functor to return true each time, all the values get added to the set in the order they were inserted [1, 4, 7, 5, 9, 1]. I thought that when the functor comparator returns true, it is treated as if the first element is smaller than the second element, and false means that the first element is treated as grater than the second element? It seems to be the case when I did return (a < b); and return (a > b); in the operator function.

Upvotes: 2

Views: 107

Answers (2)

LogicStuff
LogicStuff

Reputation: 19607

In this case, std::set uses !(a < b) && !(b < a) to determine equality of two elements: a and b.

!(false) && !(false) will be yielding true everytime, when checking for duplicates, thus not allowing std::set to contain more than one element. This is a mistreatment of std::set.

Upvotes: 2

Dietmar K&#252;hl
Dietmar K&#252;hl

Reputation: 153840

The comparision function needs to define a strict weak order on the elements. That is, these three conditions need to hold for all elements, a, b, c:

  1. a < a is false (irreflexitivity)
  2. a < b being true implies b < a is false (asymmetry)
  3. a < b and b < c both true implies a < c is also true (transitivity)

When using a comparator object cmp the conditions above need to apply with x < y replaced with cmp(x, y).

Your first comparison function (always returning false) is actually a strict weak order, however, one which implies that all elements are equivalent. There is no way to distinguish between two elements. In particular, neither a < b nor b < a yields true. If both of these conditions are false the two objects clearly are equivalent. As a result, only one element is in the set.

The second comparison function (always return true) is not a strict weak order as it violates the first condition (irreflexitity). Whatever happens in the set is undefined behavior.

Upvotes: 7

Related Questions