Main Content

AUTOSAR C++14 Rule A25-4-1

Ordering predicates used with associative containers and STL sorting and related algorithms shall adhere to a strict weak ordering relation

Since R2022a

expand all in page

Description

Rule Definition

Ordering predicates used with associative containers and STL sorting and related algorithms shall adhere to a strict weak ordering relation.

Rationale

Algorithms and containers of the standard template library (STL) 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:

  • Irreflexivity: For all x, comparing x to itself must always evaluate to false.

  • Assymetry: For all x, y: if comparing x to y evaluates to true, then comparing y to x must evaluate to false.

  • Transitivity: For all x, y, z: if comparing x to y and y to z both evaluate to true, then comparing x to z must also evaluate to true.

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

  • std::less_equal

  • std::greater_equal

  • std::equal_to

  • std::not_equal_to

  • std::logical_or

  • std::logical_and

Using the preceding functions as ordering predicates for algorithms and containers from the STL might result in infinite loops, erratic behavior, and bugs that are difficult to diagnose. Instead, use functions that adhere to the strict weak ordering relation. For instance, use functions such as std::less or std::greater.

Polyspace Implementation

Polyspace® raises a violation of this rule when you use one of these compare types as predicates in standard library algorithms and containers:

  • std::less_equal

  • std::greater_equal

  • std::equal_to

  • std::not_equal_to

  • std::logical_or

  • std::logical_and

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.

Troubleshooting

If you expect a rule violation but Polyspace does not report it, see Diagnose Why Coding Standard Violations Do Not Appear as Expected.

Examples

expand all

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

  • The predicate greater_equal does not return false when comparing the same objects, violating the irreflexivity requirement.

  • The predicate less_equal does not return false when comparing the same objects, violating the irreflexivity requirement.

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.

Check Information

Group: Algorithms library
Category: Required, Non-automated

Version History

Introduced in R2022a

See Also

Topics