Title
Overly strict requirements on qsort and bsearch
Status
new
Section
[alg.c.library]
Submitter
Richard Smith

Created on 2021-02-02.00:00:00 last changed 1 week ago

Messages

Date: 2021-02-23.17:20:05

Proposed resolution:

This wording is relative to N4878.

  1. Modify [alg.c.library] as indicated:

    void* bsearch(const void* key, const void* base, size_t nmemb, size_t size,
                 c-compare-pred* compar);
    void* bsearch(const void* key, const void* base, size_t nmemb, size_t size,
                  compare-pred* compar);
    void qsort(void* base, size_t nmemb, size_t size, c-compare-pred* compar);
    void qsort(void* base, size_t nmemb, size_t size, compare-pred* compar);
    

    -2- Preconditions: For qsort, tThe objects in the array pointed to by base are of trivialtrivially copyable type.

Date: 2021-02-15.00:00:00

[ 2021-02-23; Casey Carter provides concrete wording ]

Date: 2021-02-02.00:00:00

Per [alg.c.library]/2, for qsort and bsearch, we have:

Preconditions: The objects in the array pointed to by base are of trivial type.

This seems like an unnecessarily strict requirement. qsort only needs the objects to be of a trivially-copyable type (because it will use memcpy or equivalent to relocate them), and bsearch doesn't need any particular properties of the array element type. Presumably it would be in improvement to specify the more-precise requirements instead.

We should also reconsider the other uses of the notion of a trivial type. It's really not a useful or meaningful type property by itself, because it doesn't actually require that any operations on the type are valid (due to the possibility of them being ambiguous or only some of them being available) and the places that consider it very likely actually mean is_trivially_copyable plus is_trivially_default_constructible instead, or perhaps is_trivially_copy_constructible and is_trivially_move_constructible and so on.

Other than qsort and bsearch, the only uses of this type property in the standard are to constrain max_align_t, aligned_storage, aligned_union, and the element type of basic_string (and in the definition of the deprecated is_pod trait), all of which (other than is_pod) I think really mean "is trivially default constructible", not "has at least one eligible default constructor and all eligible default constructors are trivial". And in fact I think the alignment types are underspecified — we don't want to require merely that they be trivially-copyable, since that doesn't require any particular operation on them to actually be valid — we also want to require that they actually model semiregular.

History
Date User Action Args
2021-02-23 17:20:05adminsetmessages: + msg11696
2021-02-23 17:20:05adminsetmessages: + msg11695
2021-02-02 00:00:00admincreate