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.

Noncompliant Code Example

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:.

#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:.

#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.

#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:.

#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;
  }
}

Risk Assessment

Using an invalid ordering rule can lead to erratic behavior or infinite loops.

Automated Detection

Related Vulnerabilities

Search for vulnerabilities resulting from the violation of this rule on the CERT website.

Related Guidelines

Bibliography

...

Image Added Image Added CTR39-CPP. Do not use pointer arithmetic on polymorphic objects      006. Containers (CTR)      Image Modified