 ##### Page tree
Go to start of banner

# CTR57-CPP. Provide a valid ordering predicate

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

## Automated Detection

Tool

Version

Checker

Description

Parasoft C/C++test

10.4.2

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.

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

## 1 Comment

1. The list of requirements at the top do not correctly specify a strict weak ordering. In fact, these only specify a strict partial ordering (note that asymetry is already implied by irreflexivity and transitivity). One also needs transitivity of incomparability.

The explanation for the second non-compliant example is also wrong. The relation is assymetric but fails the transitivity of incomparability. Consider P = (0, 2), Q = (2, 0) and R = (1, 3). Observe that P and Q are incomparable (neither P < Q nor Q < P), and Q and R are incomparable. However, P < R and hence, P and R are comparable.