This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of WP status.

3521. Overly strict requirements on qsort and bsearch

Section: 27.12 [alg.c.library] Status: WP Submitter: Richard Smith Opened: 2021-02-02 Last modified: 2021-06-07

Priority: Not Prioritized

View all other issues in [alg.c.library].

View all issues with WP status.

Discussion:

Per 27.12 [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.

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

[2021-03-12; Reflector poll]

Set status to Tentatively Ready after five votes in favour during reflector poll.

[2021-06-07 Approved at June 2021 virtual plenary. Status changed: Voting → WP.]

Proposed resolution:

This wording is relative to N4878.

  1. Modify 27.12 [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.