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 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 rule 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 . (See Meyers01 §21 for examples.)

...

[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 non-compliant example, the IntSetLE type defines a set with less_equal specified as the ordering rule. Less than or equal is not a valid ordering rule because it violates the requirement to provide a "strict weak ordering" over the objects compared. In particular, this ordering rule 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 equal equivalent values. As a result, the iterator pair returned by the equal_range() method is inverted and the subsequent loop fails to terminatebehavior 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
typedef set<int, less_equal<int > > IntSetLE;

IntSetLE::const_iterator sleIter;
IntSetLE sle;

sle.insert(5);
sle.insert(10);
sle.insert(20);

pair<IntSetLE::const_iterator, IntSetLE::const_iterator> psle;

psle = sle.equal_range(10);

for (sleIter = psle r.first; sleIter != psler.second; ++sleIterr.first) {
    cout << "Set contains: "std::cout << *sleIterr.first << std::endl;
  }
}

Compliant Solution

Provide an ordering rule that defines a strict weak orderingThis 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
typedef set<int, less<int> > IntSetLess;

IntSetLess::const_iterator islIter;
IntSetLess isl;

isl.insert(5);
isl.insert(10);
isl.insert(20);

pair<IntSetLess::const_iterator, IntSetLess::const_iterator> pisl;

pisl = isl.equal_range(10);

for (islIter = pisl r.first; islIter \!= pislr.second; \++islIterr.first) {
  cout << "Set contains: " std::cout << \*islIterr.first << std::endl;
  }
}

...

Noncompliant Code Example

In this non-compliant noncompliant code example, the IntPtrSet type defines a set of int pointers using the default comparison operator as the ordering rule. Unfortunately the default comparison operator will compare the pointer address values, not the values of the ints referenced by the pointers. As a result, the integers will be ordered consistently, but their order will appear to be scrambledobjects 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>
typedef set<int*> IntPtrSet;

IntPtrSet::const_iterator sIter;
IntPtrSet s;

int i[3] = {10, 20, 5};
s.insert(&i[2]);
s.insert(&i[1]);
s.insert(&i[0]);

cout << "Set contains ";
for (sIter = s.begin(); sIter != s.end(); ++sIter) cout << **sIter << ' ';
cout << endl;

TRhis code outputs:

Set contains 10 20 5

because the integers are stored in pointer order, which happens to be the order in which they are stored in the array.

Compliant Solution

To store pointers in a proper order, you should use the {{DereferenceLess}} template, as described in 
\[[Meyers 01|AA. C++ References#Meyers 01]\] Item 20:

struct DereferenceLess {
  template <typename PtrType>
  bool operator()(PtrType pl1, PtrType pl2) const {
    return *pl1 < *pl2;
  }
};

Now if we use this template when declaring the set:

typedef set<int*, DereferenceLess> IntPtrSet;

the rest of the program behaves as we expect:

Set contains 5 10 20

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

Other Languages

...

Automated Detection

Related Vulnerabilities

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

Related Guidelines

...

...

References

\[[Meyers 01|AA. C++ References#Meyers 01]\] Item 21: Always have comparison functions return false for equal values.
\[[Sutter 05|AA. C++ References#Sutter 05]\] Item 83: Use a checked STL implementation.
\[[ISO/IEC 14882-2003|AA. C++ References#ISO/IEC 14882-2003]\] Section 24: Iterators Library.

Bibliography

...

Image Added Image Added Image Added STL31-CPP. Use Valid Iterator Ranges      14. Templates and the STL (STL)      49. Miscellaneous (MSC)