Page History

Associative containers place a strict weak ordering requirement on their key comparison predicates [ISO/IEC 14882-2014]. A strict weak ordering has the following properties:

For for all x: x < x == false (irreflexivity)
For for all x, y: if x < y y then != (y < x) (asymmetry)
For for all x, y, z: if x < y && y < z == then x < z (transitivity)

Providing an invalid ordering predicate for an associative container (e.g., sets, maps, multisets, and multimaps), or as a comparison criterion with the sorting algorithms, can result in erratic behavior or infinite loops [Meyers 01]. When an ordering predicate is required for an associative container or a generic STL standard template library algorithm, the predicate must meet the requirements for inducing a strict weak ordering.

...

In this noncompliant code example, the std::set object is created with a comparator that does not adhere to the strict weak ordering requirement. Specifically, it fails to return false for equivalent values. As a result, the behavior of iterating over the results from std::set::equal_range results in unspecified behavior:.

Code Block

bgColor	#FFcccc
lang	cpp

#include <functional>
#include <iostream>
#include <set>

void f() {
  std::set<int, std::less_equal<int>> Ss{5, 10, 20};  
  for (auto Rr = Ss.equal_range(10); Rr.first != Rr.second; ++Rr.first) {
    std::cout << *Rr.first << std::endl;
  }
}

Compliant Solution

This compliant solution uses the default comparator with std::set instead of providing an invalid one:.

Code Block

bgColor	#ccccff
lang	cpp

#include <iostream>
#include <set>

void f() {
  std::set<int> Ss{5, 10, 20};  
  for (auto Rr = Ss.equal_range(10); Rr.first != Rr.second; ++Rr.first) {
    std::cout << *Rr.first << std::endl;
  }
}

Noncompliant Code Example

In this noncompliant code example, the objects stored in the stdthe std::set have an overloaded operator< overloaded operator< implementation, allowing the objects to be compared with stdwith std::less. However, the comparison operation does not provide a strict weak ordering. Specifically, the values 1, N and 1, M can , two sets, x and y, whose i values are both 1, but have differing j values can result in a situation where compwhere comp(x, y) == and comp(y, x) are both false, failing the asymmetry requirements.

Code Block

bgColor	#FFcccc
lang	cpp

#include <iostream>
#include <set>

class S {
  int Ii, Jj;

public:
  S(int Ii, int Jj) : Ii(Ii), Jj(Jj) {}
  
  friend bool operator<(const S &LHSlhs, const S &RHSrhs) {
    return LHSlhs.Ii < RHSrhs.Ii && LHSlhs.Jj < RHSrhs.Jj;
  }
  
  friend std::ostream &operator<<(std::ostream &OSos, const S& Oo) {
    OSos << "Ii: " << Oo.Ii << ", Jj: " << Oo.Jj;
    return OSos;
  }
};

void f() {
  std::set<S> Tt{S(1, 1), S(1, 2), S(2, 1)};
  for (auto Vv : Tt) {
    std::cout << Vv << std::endl;
  }
}

Compliant Solution

This compliant solution uses stduses std::tie() to properly implement the strict weak ordering operator< ordering operator< predicate:.

Code Block

bgColor	#ccccff
lang	cpp

#include <iostream>
#include <set>
#include <tuple>
 
class S {
  int Ii, Jj;
 
public:
  S(int Ii, int Jj) : Ii(Ii), Jj(Jj) {}
  
  friend bool operator<(const S &LHSlhs, const S &RHSrhs) {
    return std::tie(LHSlhs.Ii, LHSlhs.Jj) < std::tie(RHSrhs.Ii, RHSrhs.Jj);
  }
  
  friend std::ostream &operator<<(std::ostream &OSos, const S& Oo) {
    OSos << "Ii: " << Oo.Ii << ", Jj: " << Oo.Jj;
    return OSos;
  }
};

void f() {
  std::set<S> Tt{S(1, 1), S(1, 2), S(2, 1)};  
  for (auto Vv : Tt) {
    std::cout << Vv << std::endl;
  }
}