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.
| Code Block | ||
|---|---|---|
| ||
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.
| Code Block | ||
|---|---|---|
| ||
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;
}
|
Risk Assessment
Using an invalid ordering rule can lead to erratic behavior or infinite loops.
Rule | Severity | Likelihood | Remediation Cost | Priority | Level |
|---|---|---|---|---|---|
STL32-CPP | 1 (low) | 2 (probable) | 1 (high) | P2 | L3 |
References
| Wiki Markup |
|---|
\[[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. |
STL31-CPP. Use Valid Iterator Ranges 14. Templates and the STL (TPL) 49. Miscellaneous (MSC)