CTR40-CPP. Use a valid ordering rule

Providing an invalid ordering rule for an associative container or as a comparison criterion with the sorting algorithms can result in erratic behavior or infinite loops. (See Meyers01 §21 for examples.)

Non-Compliant 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 fails to return false for equal values. As a result, the iterator pair returned by the equal_range() method is inverted and the subsequent loop fails to terminate.

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.first; sleIter != psle.second; ++sleIter){
    cout << "Set contains: " << *sleIter << endl;
}

Compliant Solution

Provide an ordering rule that defines a strict weak ordering.

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.first; islIter != pisl.second; ++islIter) {
  cout << "Set contains: " << *islIter << endl;
}

Non-Compliant Code Example

In this non-compliant 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 scrambled.

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;

This 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] 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

Risk Assessment

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

Other Languages

This rule appears in the Java Secure Coding Standard as MET10-J. Follow the general contract when implementing the compareTo() method.

Bibliography

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

CTR39-CPP. Do not use pointer arithmetic on polymorphic objects      06. Containers (CTR)      CTR41-CPP. A container's allocator should never have a data field that is not static