Reference¶

Each public entity of xstd-bits is specified here the way the standard specifies the library: a synopsis per header, then for each entity the elements of [structure.specifications] that apply. The library compiles as C++23, but its interfaces are measured against the current working draft, and every clause cited here is the draft's. A name with no namespace is in std.

The synopses leave out [[nodiscard]], as the standard's own have since P2422R1, which made it a recommended practice rather than part of a library's specification. The code carries it on every function that returns a value, but for a reference returned for chaining, as operator&= returns one, and for a by-product a caller may ignore: postfix ++ and --, insert, insert_range, emplace, emplace_hint, erase, the free erase and erase_if, the reference push_back and emplace_back return, and the try_ and unchecked_ doors. It carries it on every constructor but basic_bit_array's from an initializer_list.

The library's own terms are used throughout:

A block is an unsigned integer holding bits. Position i is bit i % D of block i / D, where D is the block's numeric_limits<Block>::digits.
The storage holds the blocks: fixed, the width the type's; inplace, a run-time width within a capacity the type carries, the blocks held inline; or dynamic, on the heap. Each has a standard backend: array, inplace_vector and vector. Any other container is a bit_storage argument; the aliases over other libraries' containers, such as Boost's small_vector, are under ext/ and are not related here.
An owner holds its storage, and a view refers to storage another object holds.
A reading is what the bits mean: a sequence of bool, a set of keys, or a valarray, the sequence read elementwise.

Each container answers a standard counterpart's synopsis, and is specified as that counterpart with what the packing changes. Members named adaptor_type, adapted_type, derived_type, reads_as, owns_storage, is_windowed and static_extent answer the library's own traits and are not specified here.

Each umbrella has a page of its own, with its synopsis and its headers, and each header a page beneath it:

Relation to the standard library¶

Each entity is one of five kinds, as across the xstd libraries: - Copied: the standard's own exposition-only wording, word for word, under a name users can spell. - Extends: a standard facility under its own name, giving the standard's answer wherever the standard gives one, with overloads or specializations for more types. - Generalizes: the job of a standard facility, done for more types through an interface of its own. - Spells: a portable spelling of a standard attribute or macro. - Proposed or new: no counterpart in the standard. A proposed entity follows a WG21 paper; a new one follows none.

Nothing here is copied or spelled: the containers, views and algorithms generalize, the specializations of standard templates extend, and the templates that choose a container's block type, storage and allocator, like what the standard has no word for, are new.

The Counterpart column leads with the clause of the working draft each entity answers, then says how it extends or generalizes what that clause specifies. The rows follow the draft's order of those clauses, and the names within a row the draft's order of their counterparts. A row with no counterpart sits beside its nearest kin, citing the kin's clause where one is shared.

Entity	Kind	Counterpart
`indeterminate` `indeterminate_array` `indeterminate_t`	New	[dcl.attr.indet] as a constructor tag: a fixed set's blocks left unwritten, as the attribute leaves a variable's storage
`bit_flag_set`	Generalizes	[bitmask.types] as the set of a bitmask type's one-bit values
`bit_enum_set`	New	none: the standard has no set of an enumeration's values
`least_block_t` `fast_block_t`	Generalizes	[cstdint.syn] chosen by a width rather than named by one
`bit_blocks` `bit_constructible_from` `bit_convertible_to` `bit_index_mapping` `bit_mask_mapping` `sized_bit_index_mapping`	New	none
`bit_align` `bit_blocks_extent_v` `bit_fast` `bit_least` `bit_underlying` `underlying_block_t`	New	none
`bit_storage_rebind`	New	[allocator.traits.types] as `rebind_alloc` rebinds an allocator, for a storage's block and its count of blocks
`bit_compare_three_way` `bit_equal_to` `bit_not_equal_to` `bit_greater` `bit_less` `bit_greater_equal` `bit_less_equal`	Generalizes	[comparisons.three.way] [range.cmp] across block types and storages
`hash`	Extends	[unord.hash] specializations for every owner but the valarrays, and for the set view
`bit_hash`	Generalizes	[unord.hash] of the packed bits rather than the model's value, under a Boost.Hash2 algorithm the caller names
`bit_hash_append`	New	none in the standard: a Boost.Hash2 `hash_append`, after N3980
`bit_digest`	Proposed	N3980's `uhash`, returning the algorithm's whole result
`is_range` `is_tuple_like`	New	none in the standard: specializations of Boost.ContainerHash's traits
`bit_convert`	Generalizes	[bit.cast] from P0476R2: position for position across widths and readings, rather than byte for byte at one size
`bit_convert` with `boost::dynamic_bitset`	New	none in the standard: conversion to and from Boost.DynamicBitset
`shl` `shr`	Proposed	P3793R2's total shifts, beside [bit.rotate]: a set's keys moved by any count, where the set's own `<<` and `>>` take a count below a static width as their precondition
`bit_array`	Generalizes	[array] of `bool`, packed
`basic_bit_array`	New	[array] customizing the block type
`to_bit_array`	Generalizes	[array.creation] returning a `bit_array`
`tuple_size` `tuple_element` `get`	Extends	[array.tuple] specializations and an overload for `basic_bit_array`
`erase` `erase_if`	Generalizes	[vector.erasure] [inplace.vector.erasure] [set.erasure] for the packed sequences and sets
`bit_vector`	Generalizes	[vector.bool] packed into blocks, which `vector<bool>` leaves to the implementation
`basic_bit_vector`	New	[vector.bool] customizing the storage, and with it the block type and the allocator, and capping the width
`bit_inplace_vector`	Generalizes	[inplace.vector] of `bool`, packed
`basic_bit_inplace_vector`	New	[inplace.vector] customizing the block type, as `basic_bit_vector` over inline blocks
`bit_set`	Generalizes	[set] of positions, one bit per possible key, packed into blocks
`basic_bit_set` `basic_bit_fixed_set` `basic_bit_inplace_set` `bit_fixed_set` `bit_inplace_set`	New	[set] customizing the key mapping and the storage, and with it the block type and the allocator: at a fixed width or within an inline capacity
`bit_set_view`	New	none: no standard view reads a range as a set
`bit_find_mapping` `bit_flag_mapping` `bit_key_mapping` `bit_range_mapping` `enum_traits`	New	none; `bit_key_mapping` is specialized per key as `char_traits` is, [char.traits]
`bit_storage`	New	[flat.set.overview] as `flat_set` constrains its `KeyContainer`, for the blocks an owner keeps
`bit_span`	Generalizes	[views.span] over blocks read as a sequence of `bool`
`bit_subspan`	Generalizes	[span.sub] at any bit offset
`bit_advance` `bit_distance` `bit_next` `bit_prev`	Generalizes	[range.iter.ops] a block at a time over a set
`from_blocks_t` `from_blocks`	Generalizes	[ranges.syn] from P1206R7: reading an argument's blocks as bits, where `from_range` reads its elements as values
`bit_all_of` `bit_any_of` `bit_none_of` `bit_for_each` `bit_find` `bit_find_last` `bit_count` `bit_mismatch` `bit_equal`	Generalizes	[alg.nonmodifying] a block at a time, without the projections and predicates a range of bits has no use for
`bit_copy` `bit_copy_backward` `bit_move` `bit_swap_ranges` `bit_transform` `bit_fill` `bit_reverse` `bit_reverse_copy` `bit_rotate` `bit_rotate_copy` `bit_shift_left` `bit_shift_right`	Generalizes	[alg.modifying.operations] a block at a time, without the projections a range of bits has no use for
`bit_sort` `bit_is_sorted` `bit_is_partitioned` `bit_partition` `bit_partition_point`	Generalizes	[alg.sorting] a block at a time, without the projections, predicates and comparators a range of bits has no use for
`bit_includes` `bit_set_union` `bit_set_intersection` `bit_set_difference` `bit_set_symmetric_difference`	Generalizes	[alg.set.operations] returning a set where the standard writes through an output iterator
`bit_intersects` `bit_disjoint`	New	[alg.set.operations] none: the standard has no test of whether two sets share an element
`bit_lexicographical_compare_three_way`	Proposed	[alg.three.way] over two ranges, as P2022R3 proposes `ranges::lexicographical_compare_three_way`
`bit_valarray` `bit_slice` `bit_slice_array` `bit_gslice` `bit_gslice_array` `bit_mask_array` `bit_indirect_array`	Generalizes	[numarray] of `bool`, packed, with the slices and helper arrays that select from it
`basic_bit_valarray` `basic_bit_fixed_valarray` `basic_bit_inplace_valarray` `bit_fixed_valarray` `bit_inplace_valarray`	New	[numarray] customizing the storage, and with it the block type and the allocator: at a fixed width or within an inline capacity
`bit_rebind` `bit_resize`	Generalizes	[simd.traits] from P1928R15, for owners rather than `simd` types

Prior work¶

What each entity builds on in C++, and, for an entity that introduces a name or a concept of its own, its counterpart in another language where that counterpart shares its purpose. A container that generalizes bitset or vector<bool> cites no other language. Papers are linked through wg21.link.

The containers, and bitset:
- Chuck Allison's N0075 (1991) and N0128 (1992), the proposals that became bitset, which named both of its readings, an array of bits and a set of integers.
- P0125R0, std::bitset inclusion test methods (Vittorio Romeo), the subset test bit_includes answers.
- P0161R0, Bitset Iterators, Masks, and Container Operations (Nathan Myers), which iterates a bitset as the sets iterate their keys.
- P2417R2, A more constexpr bitset (Daniil Goncharov), and P3103R2, More bitset operations (Jan Schultke).
bit_vector, and vector<bool>: the SGI STL's bit_vector, a class of its own for want of partial specialization, and N1847, vector: More Problems, Better Solutions (Herb Sutter).
The dynamic storage, and the containers under ext/:
- boost::dynamic_bitset, and N2050, Proposal to Add a Dynamically Sizeable Bitset to the Standard Library Technical Report Revision 1 (J. Allsop, A. Meredith, G. Prota), which proposed it for the standard.
- LLVM's BitVector and SmallBitVector, EASTL's bitvector and Qt's QBitArray.
- Boost.Container's small_vector, which ext/boost/'s small aliases adopt, and static_vector, which holds the inplace storage below C++26.
bit_inplace_vector, bit_inplace_set, bit_inplace_valarray: P0843R14, inplace_vector (Gonzalo Brito Gadeschi, Timur Doumler, Nevin Liber, David Sankel).
bit_span, bit_subspan and the proxies:
- P0237R10, Wording for fundamental bit manipulation utilities (Vincent Reverdy, Robert J. Brunner), whose bit_reference and bit_iterator address a bit at any offset.
- itsy_bitsy's bit_view and bit_sequence, a view and a container of bits over a range of words.
- P0122R7, span: bounds-safe views for sequences of objects (Neil MacIntosh, Stephan T. Lavavej).
bit_flag_set, bit_enum_set and the key mappings:
- C++: N3110, Problems with bitmask types in the library (Jonathan Wakely); N4202, Strongly Typed Bitset (Matthew Fioravante); and P4313R1, Bitmask operations for enums (Iliya Guterman, Anthony Williams), whose operators bit_flag_set takes as they are. Mozilla's EnumSet, whose default word is bit_underlying's, Chromium's EnumSet, type_safe's flag_set and Qt's QFlags.
- Java's EnumSet is bit_enum_set's counterpart: a set of one enumeration's values, represented internally as a bit vector.
The algorithms and iterator operations:
- P2022R3, Rangified version of lexicographical_compare_three_way (Ran Regev, Alex Dathskovsky), whose signature bit_lexicographical_compare_three_way takes.
- range-v3's set views, which return their result as the four set operations here do rather than writing it through an output iterator.
- SDSL's rank_support_v and select_support_mcl, the rank and select that bit_distance and bit_advance compute over a set a block at a time.
bit_rebind, bit_resize: P1928R15, std::simd - Merge data-parallel types from the Parallelism TS 2 (Matthias Kretz), whose rebind_t and resize_t they mirror.
bit_hash, bit_hash_append, bit_digest: N3980, Types Don't Know # (Howard Hinnant, Vinnie Falco, John Bytheway), Boost.Hash2 and Boost.ContainerHash.
from_blocks: P1206R7, Conversions from ranges to containers (Corentin Jabot, Eric Niebler, Casey Carter), whose from_range tag it mirrors. itsy_bitsy's bit_sequence takes its storage through std::in_place instead.
indeterminate: P2795R5, Erroneous behaviour for uninitialized reads (Thomas Köppe), whose [[indeterminate]] the tag mirrors; P1020R1, Smart pointer creation with default initialization (Glen Fernandes, Peter Dimov), the standard's for_overwrite; and Boost.Container's default_init_t.
bit_convert: P0476R2, Bit-casting object representations (JF Bastien).