5 ms·

std::sorting floats is perfectly well defined in C++ as long as you respect the precondition that there are no NaNs in your range. In other words the subset of

std::sorting floats is perfectly well defined in C++ as long as you respect the precondition that there are no NaNs in your range. In other words the subset of floats without NaNs respects strict weak ordering. edit: when using the default comparison. With a custom comparator you can do whatever you want, including using std::weak_order to sort NaNs.

tialaramex 3y ago
std::sort is defined in terms of a semantic requirement Compare - a constraint on types - which forbids types which don't have Equivalence. Specifically, our type needs to have some equivalence predicate equiv(A, B) such that equiv(A, A) is true, and the provided comparisons for floating point types in C++ do not meet this requirement. I would be astonished if you're not correct at runtime in practice of course, but "It works in my environment" and "This is correct by the standard" are two different things.
- gpderetta 3y ago
  std::sort has a semantic requirement on the type of Compare, but Compare itself only has a constraint on the values it is comparing. From the 27.8.1.3 [1]: "comp shall induce a strict weak ordering on the values." It is not terribly clear what "values" is referring to, but form context it must be all values that are being sorted, as opposed to all possible values of T. The only explicit constrain on T is that it must be Move Assignable and Constructible. [1] https://eel.is/c++draft/alg.sorting.general#4 https://eel.is/c++draft/alg.sorting.general#4
  - tialaramex 3y ago
    I see what you're saying about defining "values" as specifically only the values which, at runtime, we happen to be using Compare on, which is an idea I hadn't considered before - but I'm not sure how to square that with the way the rest of the language is defined. Maybe one day the proposed "Appendix" of all UB and IFNDR will actually explain clearly what the intended rules are. Corentin Jabot's "UB? In My Lexer?" showed that the ISO document is still very uh, unpolished after decades of effort.
- LegionMammal978 3y ago
  From [structure.requirements]/4 (at [0]): > Requirements are stated in terms of well-defined expressions that define valid terms of the types that meet the requirements. I'd read this as separating the values of a type into valid and invalid terms, where the valid terms can be any arbitrary set of values that's closed under the required operations. (This is explicitly clarified for concepts in [structure.requirements]/8, saying that the functions and conditions don't have to be total over all values of the type.) In this case, NaN would be considered an invalid term for std::sort(), so the compiler could break the program at a point only if it could statically guarantee that a NaN will inevitably make its way into std::sort(). [0] https://eel.is/c++draft/structure.requirements#4 https://eel.is/c++draft/structure.requirements#4
  - tialaramex 3y ago
    Staring at that text just gives me a headache, in particular "This does not affect whether a type models the concept". I'm sure that everybody proposing and voting on this text was sure they agreed with it, however I'm doubtful that they all had the same meaning in mind, and I have no idea which one the author intended. What is "this" here? The example, of a type which clearly doesn't model the concept it syntactically conforms to? The requirement? All of the preceding text ?
    - LegionMammal978 3y ago
      > What is "this" here? The example, of a type which clearly doesn't model the concept it syntactically conforms to? The requirement? All of the preceding text ? Generally, pronouns in the standard are scoped to the paragraph they're in. In this case, I read it as saying that the type (e.g., float) can still model a concept even if the semantic requirements are violated for some particular values. (That is, "this" is "whether the required operation is partial or total".) To support this reading, we can see from [res.on.requirements]/1 ([0]) that 'modeling' a concept is defined as meeting its associated semantic requirements: > A sequence Args of template arguments is said to model a concept C if Args satisfies C ([temp.constr.decl]) and meets all semantic requirements (if any) given in the specification of C. And 'meeting a semantic requirement' is mediated by [structure.requirements]/4, which I read to say that semantic requirements aren't universal rules for all values of a type, but necessary preconditions for values to be valid terms that can be passed into standard-library APIs. By that logic, even though an operation might not "meet the semantic requirements of [a] concept when operating on NaNs", it doesn't kill the entire type, it just rules out NaNs from being valid terms. I think the weirdness here is that the set of valid terms of any type is up in flux, to be defined by the ultimate user. But even if the operations don't meet the semantics over that entire set, the compiler has no way to prove that the program is ill-formed until the user actually generates one of the offending values, asserting that it truly is a valid term. [0] https://eel.is/c++draft/res.on.requirements#1 https://eel.is/c++draft/res.on.requirements#1

tialaramex 3y ago

std::sort is defined in terms of a semantic requirement Compare - a constraint on types - which forbids types which don't have Equivalence. Specifically, our type needs to have some equivalence predicate equiv(A, B) such that equiv(A, A) is true, and the provided comparisons for floating point types in C++ do not meet this requirement. I would be astonished if you're not correct at runtime in practice of course, but "It works in my environment" and "This is correct by the standard" are two different things.

gpderetta 3y ago
std::sort has a semantic requirement on the type of Compare, but Compare itself only has a constraint on the values it is comparing. From the 27.8.1.3 [1]: "comp shall induce a strict weak ordering on the values." It is not terribly clear what "values" is referring to, but form context it must be all values that are being sorted, as opposed to all possible values of T. The only explicit constrain on T is that it must be Move Assignable and Constructible. [1] https://eel.is/c++draft/alg.sorting.general#4 https://eel.is/c++draft/alg.sorting.general#4
- tialaramex 3y ago
  I see what you're saying about defining "values" as specifically only the values which, at runtime, we happen to be using Compare on, which is an idea I hadn't considered before - but I'm not sure how to square that with the way the rest of the language is defined. Maybe one day the proposed "Appendix" of all UB and IFNDR will actually explain clearly what the intended rules are. Corentin Jabot's "UB? In My Lexer?" showed that the ISO document is still very uh, unpolished after decades of effort.
LegionMammal978 3y ago
From [structure.requirements]/4 (at [0]): > Requirements are stated in terms of well-defined expressions that define valid terms of the types that meet the requirements. I'd read this as separating the values of a type into valid and invalid terms, where the valid terms can be any arbitrary set of values that's closed under the required operations. (This is explicitly clarified for concepts in [structure.requirements]/8, saying that the functions and conditions don't have to be total over all values of the type.) In this case, NaN would be considered an invalid term for std::sort(), so the compiler could break the program at a point only if it could statically guarantee that a NaN will inevitably make its way into std::sort(). [0] https://eel.is/c++draft/structure.requirements#4 https://eel.is/c++draft/structure.requirements#4
- tialaramex 3y ago
  Staring at that text just gives me a headache, in particular "This does not affect whether a type models the concept". I'm sure that everybody proposing and voting on this text was sure they agreed with it, however I'm doubtful that they all had the same meaning in mind, and I have no idea which one the author intended. What is "this" here? The example, of a type which clearly doesn't model the concept it syntactically conforms to? The requirement? All of the preceding text ?
  - LegionMammal978 3y ago
    > What is "this" here? The example, of a type which clearly doesn't model the concept it syntactically conforms to? The requirement? All of the preceding text ? Generally, pronouns in the standard are scoped to the paragraph they're in. In this case, I read it as saying that the type (e.g., float) can still model a concept even if the semantic requirements are violated for some particular values. (That is, "this" is "whether the required operation is partial or total".) To support this reading, we can see from [res.on.requirements]/1 ([0]) that 'modeling' a concept is defined as meeting its associated semantic requirements: > A sequence Args of template arguments is said to model a concept C if Args satisfies C ([temp.constr.decl]) and meets all semantic requirements (if any) given in the specification of C. And 'meeting a semantic requirement' is mediated by [structure.requirements]/4, which I read to say that semantic requirements aren't universal rules for all values of a type, but necessary preconditions for values to be valid terms that can be passed into standard-library APIs. By that logic, even though an operation might not "meet the semantic requirements of [a] concept when operating on NaNs", it doesn't kill the entire type, it just rules out NaNs from being valid terms. I think the weirdness here is that the set of valid terms of any type is up in flux, to be defined by the ultimate user. But even if the operations don't meet the semantics over that entire set, the compiler has no way to prove that the program is ill-formed until the user actually generates one of the offending values, asserting that it truly is a valid term. [0] https://eel.is/c++draft/res.on.requirements#1 https://eel.is/c++draft/res.on.requirements#1