This proposal is part of a group of papers aimed at improving the state of freestanding.
At a high level, this proposal adds most of the facilities from <algorithm>, <numeric>, and <random> that don't require floating point or ExecutionPolicy.
Implementations of these often rely on facilities like memcpy, which is made freestanding by P2338 "Freestanding Library: Character primitives and the C library".
On hosted implementations, the included facilities don't directly require heap allocations, don't use system calls, and don't require exceptions. The facilities are generally useful. This combination keeps the burden low for standard library implementations to single source these facilities as both hosted and freestanding.
The execution policy overloads in <algorithm> and <numeric> are not required to be present in freestanding implementations.
An argument could be made to support sequential execution, but that provides very little value.
This matches precedent in <memory>, as the execution policy overloads in that header are not require to be present in freestanding implementations either.
The execution policy overloads are not marked as // freestanding-deleted.
// freestanding-deleted is typically useful for ensuring that overload resolution doesn't change when moving between freestanding and hosted environments.
The execution policy overloads are already constrained such that accidental selection of these overloads is highly unlikely, so an additional = delete would not provide much benefit.
Some algorithms (stable_sort, stable_partition, and inplace_merge) attempt to allocate temporary buffers as a way to reduce the time complexity of the algorithm.
Freestanding implementations are not required to have an operational ::operator new. As a result, these algorithms are not required to be present in freestanding implementations.
In theory, we could include these algorithms with the expectation that the fall-back, worse time complexity is used instead of the complexity that we get from the temporary buffer version of the algorithm. I did not take that approach, as I see it being a subtle performance break. I would much rather have a loud compiler error than a subtle performance break.
This paper makes the iostreams streaming requirements optional for random number engines [rand.req.eng] and random number distributions [rand.req.dist] on freestanding implementations. Freestanding doesn't require iostreams to be present, and won't require the random number iostreams operations to be present either. Streaming these objects allows users to save and restore the state of the object in a round-trippable manner. Common usages of the random number facilities that don't involve serialization still work without iostreams support.
In many kernel environments, loading, storing, or manipulating floating point values is not allowed in the general case. Using floating point in these areas ends up corrupting user mode floating point state. As a result, freestanding avoids requiring facilities that use floating point types.
The random number facilities in <random> are a mix of integer and floating point facilities.
All the distributions other than uniform_int_distribution rely on floating point math.
In addition, the shuffle_order_engine and its associated knuth_b typedef are specified and implemented in terms of floating point math. generate_canonical also deals directly with floating point numbers.
Implementing random_device in a useful way requires knowledge of the operating environment.
While a conforming implementation of random_device is allowed to return pseudo-random numbers, actually doing so is user hostile.
If users want random_device non-deterministic random numbers, and the system cannot supply them, then users would typically prefer a compiler error rather than getting incorrect, deterministic random results.
Due to this dependency on the operating environment, random_device is not required to be present in freestanding implementations.
seed_seq requires dynamic memory allocation.
Dynamic memory allocation is typically considered a facility provided by the operating environment.
As a result, seed_seq is not required to be present in freestanding implementations.
All of the standard library random engines have constructors taking a seed sequence.
Those constructors are templated on the seed sequence, and do not specifically require seed_seq.
These changes have been tested with the libc++ test suite in the Microsoft Windows 11 kernel with the MSVC STL.
The binaries produced were scanned for unexpected floating point usage.
Usage of exceptions, iostreams, and global ::operator new and ::operator delete cause linker errors on that platform.
The C++03 portions of the library have seen extensive field use in kernel drivers produced by NI (formerly National Instruments). Those drivers use a modified version of STLport in kernel drivers built for Microsoft Windows, Linux, and Apple MacOS, as well as for various real time operating systems.
Paul Bendixen has implemented P0829 in a libstdc++ fork. P0829 is (almost) a superset of the facilities in this paper.
An entity, deduction guide, or typedef-name is a freestanding item if it is:
- introduced by a declaration that is a freestanding item,
- a member of a freestanding item other than a namespace where the introducing declaration is not followed by a comment that includes hosted,
- an enumerator of a freestanding item,
- a deduction guide of a freestanding item,
- an enclosing namespace of a freestanding item,
- a friend of a freestanding item where the introducing declaration is not followed by a comment that includes hosted,
- denoted by a typedef-name that is a freestanding item, or
- denoted by an alias template that is a freestanding item.
<algorithm> and <numeric> are already freestanding headers.| Subclause | Header(s) | |
|---|---|---|
| […] | […] | […] |
| ?.? [rand] | Random number generation | <random> |
| […] | […] | […] |
Update the integer literal for the following macro:#define __cpp_lib_freestanding_numeric 20XXXXL // freestanding, also in <numeric> #define __cpp_lib_freestanding_random 20XXXXL // freestanding, also in <random>
__cpp_lib_freestanding_algorithm
Please insert a // mostly freestanding comment at the beginning of the [algorithm.syn] synopsis.
Please append a // hosted comment to each function template with an ExecutionPolicy parameter.
Please append a // hosted comment to all overloads of the following function templates:
stable_sortstable_partitioninplace_merge
Please remove the // freestanding comment from the following functions.
The markings are now redundant given the // mostly freestanding comment at the beginning of the synopsis.
fill_n(OutputIterator first, Size n, const T& value)swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
Please insert a // mostly freestanding comment at the beginning of the [numeric.ops.overview] synopsis.
Please append a // hosted comment to each function template with an ExecutionPolicy parameter.
Please remove the // freestanding comment from the following functions.
The markings are now redundant given the // mostly freestanding comment at the beginning of the synopsis.
add_satsub_satmul_satdiv_satsaturate_cast// freestanding comment to the following declarations:uniform_random_bit_generator minstd_rand0minstd_randmt19937mt19937_64ranlux24_baseranlux48_baseranlux24ranlux48knuth_b is intentional.// partially freestanding comment to the following declarations:linear_congruential_enginemersenne_twister_enginesubtract_with_carry_enginediscard_block_engineindependent_bits_engineuniform_int_distributionshuffle_order_engine is intentional.Table 96: Random number engine requirements [tab:rand.req.eng]
... ... ... ...
...Table 97: Random number distribution requirements [tab:rand.req.dist]
... ... ... ...
operator<< and operator>> overload in the linear_congruential_engine synopsis.operator<< and operator>> overload in the mersenne_twister_engine synopsis.operator<< and operator>> overload in the subtract_with_carry_engine synopsis.operator<< and operator>> overload in the discard_block_engine synopsis.operator<< and operator>> overload in the independent_bits_engine synopsis.operator<< and operator>> overload in the uniform_int_distribution synopsis.