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:

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

Automated Detection

Tool

Version

Checker

Description

Parasoft C/C++test

CERT_CPP-CTR57-a

For associative containers never use comparison function returning true for equal values

Related Vulnerabilities

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

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"