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
| Level | required |
|---|---|
| Target | implementation |
| Enforcement | non-automated |
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¶
This rule shares the following common options: confidence, exclude_in_macros, exclude_messages_in_system_headers, excludes, extend_exclude_to_macro_invocations, includes, justification_checker, languages, post_processing, provider, report_at, severity
The following places define options that affect this rule: Stylechecks, Analysis-GlobalOptions
compare_template_positions¶
compare_template_positions
Positions (zero based) of key comparison predicate template argument.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 }