CertC++-CTR57

Provide a valid ordering predicate

Required inputs: IR

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 all  x:  x < x == false (irreflexivity)
  • for all  x, y: if  x < y then !(y < x) (asymmetry)
  • 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 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>> s{5, 10, 20};
  for (auto r = s.equal_range(10); r.first != r.second; ++r.first) {
    std::cout << *r.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> s{5, 10, 20};
  for (auto r = s.equal_range(10); r.first != r.second; ++r.first) {
    std::cout << *r.first << std::endl;
  }
}
Noncompliant Code Example

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

#include <iostream>
#include <set>

class S {
  int i, j;

public:
  S(int i, int j) : i(i), j(j) {}

  friend bool operator<(const S &lhs, const S &rhs) {
    return lhs.i < rhs.i && lhs.j < rhs.j;
  }

  friend std::ostream &operator<<(std::ostream &os, const S& o) {
    os << "i: " << o.i << ", j: " << o.j;
    return os;
  }
};

void f() {
  std::set<S> t{S(1, 1), S(1, 2), S(2, 1)};
  for (auto v : t) {
    std::cout << v << std::endl;
  }
}
Compliant Solution

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

#include <iostream>
#include <set>
#include <tuple>
 
class S {
  int i, j;
 
public:
  S(int i, int j) : i(i), j(j) {}

  friend bool operator<(const S &lhs, const S &rhs) {
    return std::tie(lhs.i, lhs.j) < std::tie(rhs.i, rhs.j);
  }

  friend std::ostream &operator<<(std::ostream &os, const S& o) {
    os << "i: " << o.i << ", j: " << o.j;
    return os;
  }
};

void f() {
  std::set<S> t{S(1, 1), S(1, 2), S(2, 1)};
  for (auto v : t) {
    std::cout << v << std::endl;
  }
}
Risk Assessment

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

Rule Severity Likelihood Remediation Cost Priority Level
CTR57-CPP Low Probable High P2 L3
Related Guidelines
SEI CERT Oracle Coding Standard for Java  MET10-J. Follow the general contract when implementing the compareTo() method
Bibliography
[ ISO/IEC 14882-2014] Subclause 23.2.4, "Associative Containers"
[ Meyers 2001] Item 21, "Always Have Comparison Functions Return False for Equal Values"
[ Sutter 2004] Item 83, "Use a Checked STL Implementation"
Excerpt from SEI CERT C++ Coding Standard [https://cmu-sei.github.io/secure-coding-standards/sei-cert-cpp-coding-standard/rules/containers-ctr/ctr57-cpp], Copyright (C) 1995-2026 Carnegie Mellon University. See section 9.4. "3rd-Party Licenses" in the documentation for full details.

Possible Messages

Key

Text

Severity

Disabled

valid_ordering_irreflexivity

‘{}’ does not provide strict weak order: Irreflexivity violation: comparator returns true for equal elements.

None

False

valid_ordering_transivity

‘{}’ does not provide strict weak order: Transitivity violation: Field ‘{}’ is compared if field ‘{}’ is {}, but not if ‘{}’ is {}.

None

False

Options

compare_template_positions

compare_template_positions

Type: dict[bauhaus.analysis.config.QualifiedName, int]

Default:

{
   'std::binary_search': 2,
   'std::equal_range': 2,
   'std::includes': 2,
   'std::inplace_merge': 1,
   'std::is_heap': 1,
   'std::is_heap_until': 1,
   'std::is_sorted': 1,
   'std::is_sorted_until': 2,
   'std::lexicographical_compare': 2,
   'std::lower_bound': 2,
   'std::make_heap': 1,
   'std::map': 2,
   'std::max': 1,
   'std::max_element': 1,
   'std::merge': 3,
   'std::min': 1,
   'std::min_element': 1,
   'std::minmax': 1,
   'std::minmax_element': 1,
   'std::multimap': 2,
   'std::multiset': 1,
   'std::next_permutation': 1,
   'std::nth_element': 1,
   'std::partial_sort': 1,
   'std::partial_sort_copy': 2,
   'std::pop_heap': 1,
   'std::prev_permutation': 1,
   'std::priority_queue': 2,
   'std::push_heap': 1,
   'std::set': 1,
   'std::set_difference': 3,
   'std::set_intersection': 3,
   'std::set_symmetric_difference': 3,
   'std::set_union': 3,
   'std::sort': 1,
   'std::sort_heap': 1,
   'std::stable_sort': 1,
   'std::upper_bound': 2
}
Positions (zero based) of key comparison predicate template argument.