AutosarC++18_03-A25.4.1

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

Required inputs: IR

Rationale

Ordering predicates that can be passed to associative containers or sorting STL algorithms and related operations must fulfill requirements for a strict weak ordering, e.g.:

  • irreflexivity: FOR ALL x: x < x == false
  • asymmetry: FOR ALL x, y: if x < y then !(y < x)
  • transitivity: FOR ALL x, y, z: if x < y && y < z then x < z

Ordering predicates not adhering to these requirements will result in these algorithms not working correctly, which may include infinite loops and other erratic behavior.

Example
//% $Id: A25-4-1.cpp 309738 2018-03-01 15:08:00Z michal.szczepankiewicz $

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

int main(void) {
  // non-compliant, given predicate does not return false
  // for equal values
  std::set<int, std::greater_equal<int>> s{2, 5, 8};
  auto r = s.equal_range(5);
  // returns 0
  std::cout << std::distance(r.first, r.second) << std::endl;

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

  return 0;
}
See Also
  • SEI CERT C++ Coding Standard [9]: CTR57-CPP: Provide a valid ordering predicate
  • cppreference.com [15]: C++ concepts: Compare

Possible Messages

Key

Text

Severity

Disabled

valid_ordering_irreflexivity

‘{}’ does not provide strict weak order: Irreflexivity violation: comparator returns true for equal elements.

None

False

valid_ordering_transivity

‘{}’ does not provide strict weak order: Transitivity violation: Field ‘{}’ is compared if field ‘{}’ is {}, but not if ‘{}’ is {}.

None

False

Options

compare_template_positions

compare_template_positions

Type: dict[bauhaus.analysis.config.QualifiedName, int]

Default:

{
   'std::binary_search': 2,
   'std::equal_range': 2,
   'std::includes': 2,
   'std::inplace_merge': 1,
   'std::is_heap': 1,
   'std::is_heap_until': 1,
   'std::is_sorted': 1,
   'std::is_sorted_until': 2,
   'std::lexicographical_compare': 2,
   'std::lower_bound': 2,
   'std::make_heap': 1,
   'std::map': 2,
   'std::max': 1,
   'std::max_element': 1,
   'std::merge': 3,
   'std::min': 1,
   'std::min_element': 1,
   'std::minmax': 1,
   'std::minmax_element': 1,
   'std::multimap': 2,
   'std::multiset': 1,
   'std::next_permutation': 1,
   'std::nth_element': 1,
   'std::partial_sort': 1,
   'std::partial_sort_copy': 2,
   'std::pop_heap': 1,
   'std::prev_permutation': 1,
   'std::priority_queue': 2,
   'std::push_heap': 1,
   'std::set': 1,
   'std::set_difference': 3,
   'std::set_intersection': 3,
   'std::set_symmetric_difference': 3,
   'std::set_union': 3,
   'std::sort': 1,
   'std::sort_heap': 1,
   'std::stable_sort': 1,
   'std::upper_bound': 2
}
Positions (zero based) of key comparison predicate template argument.