CERT C++: CTR57-CPP

Use of predicate lacking strict weak ordering occurs when you use one of these compare types as predicates in standard template library (STL) algorithms and containers:

For a list of standard library algorithms that expect a predicate with strict weak ordering, see Compare.

If you use a user-defined predicate function, Polyspace^® does not check if the custom predicate adheres to strict weak ordering.

Algorithms and containers of the standard template library use predicates to sort and compare their elements. The predicates must adhere to strict weak ordering. That is, the predicate must adhere to these requirements:

These compare type methods violate at least one of these requirements:

Using the preceding predicates with algorithms and containers from the standard library might result in infinite loops, erratic behavior, and bugs that are difficult to diagnose.

To resolve this defect, avoid using the preceding methods as predicates for algorithms and containers from the standard template library. Instead, use methods that adhere to strict weak ordering. For instance, use functions such as std::less or std::greater. The STL uses these functions or their equivalent operators as the default ordering predicate. Using the default predicate might be sufficient to resolve the defect.

#include <functional>
#include <iostream>
#include <set>
#include <map>

int main(void)
{
    // GE
    std::set<int, std::greater_equal<int>>//Noncompliant
		s1{2, 5, 8};   
    auto r = s1.equal_range(5);
    //returns 0
    std::cout << std::distance(r.first, r.second) << std::endl;

    //LE
    std::map<int, std::string, std::less_equal<int>>//Noncompliant 
		m1{{2, "AB"}, {5, "CD"}, {8, "EF"}}; 
    auto r3 = m1.equal_range(5);
    //returns 0
    std::cout << std::distance(r3.first, r3.second) << std::endl;
    
    return 0;
}

In this example, Polyspace flags the use of inappropriate predicates when declaring STL containers. For instance:

Polyspace flags the use of these function as predicates when declaring containers such as std::set or std::map.

By default, these containers use the function std::less as the ordering predicate. Because this function adheres to strict weak ordering relation, Polyspace does not raise a violation when you declare the containers by using the default predicate.

#include <functional>
#include <iostream>
#include <set>
#include <map>

int main(void)
{
    std::set<int> s2{2, 5, 8}; //Compliant
    auto r2 = s2.equal_range(5);
    //returns 1
    std::cout << std::distance(r2.first, r2.second) << std::endl;

    
    std::map<int, std::string> m2{{2, "AB"}, {5, "CD"}, {8, "EF"}}; //Compliant
    auto r4 = m2.equal_range(5);
    //returns 1
    std::cout << std::distance(r4.first, r4.second) << std::endl;

    return 0;
}