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 #include #include void f() { std::set> 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 #include void f() { std::set 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 #include 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 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 #include #include   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 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.

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