Adapters are type constructors that provide a different behavior and/or different interface than the given type.

instrumented takes an type and provides a global counting mechanism that stores the number of default constructions, copy constructions, copy assignments, move constructions, move assignments, destructions, equality comparisons, and less than comparisons on objects. The static member array counts stores the counts. counter_names contains names of the counters, and initialize resets them to 0. It takes an optional count that is stored in counts[0] and can be used for labelling.

cursor takes a Cursor and provides the minimal interface required.

forward_cursor takes a Forward_cursor and provides the minimal interface required.

counted_cursor takes a Cursor and optionally an offset of the Difference_type of the cursor, constructing a cursor type that can be compared against a limit that is Equality_comparable_with the offset. increment increments both the cursor and the offset, decrement decrements both the cursor and the offset.

loadable_cursor takes a Loadable Cursor and provides the minimal interface required.

reverse_cursor takes a Bidirectional_cursor and implements a Bidirectional_cursor where increment decrements and decrement increments. Loading and storing is done from the predecessor of the original cursor. It is used for traversing ranges in reverse.

filter_cursor takes a Storable Cursor and a unary Predicate, constructing a cursor type that stores and increments when store is called, if the predicate is true for the current element. filter_sink takes a unary Predicate, constructing an Invocable type that returns a filter_cursor when invoked with a Storable Cursor.

insert_cursor takes a Storable Cursor, constructing a cursor type that applies the function insert on the current element when store is called. insert_sink in an Invocable type that returns an insert_cursor when invoked with a Storable Cursor.

map_cursor takes a Storable Cursor and a unary Invocable, constructing a cursor type that applies the function on the current element when store is called. map_sink takes a unary Invocable, constructing an Invocable type that returns a map_cursor when invoked with a Storable Cursor.

power_left_associated takes a left-associative binary Operation or Accumulation_procedure, a value of its Return_type, and positive Integer. It raises the value to the power of the integer. power_right_associated takes a right-associative binary Operation or Accumulation_procedure, a value of its Return_type, and positive Integer. It raises the value to the power of the integer. power_semigroup takes a Semigroup operation or Semigroup_accumulator, a value of its Return type, and a positive Integer. It raises the value to the power of the integer. power_monoid takes a Monoid operation or Monoid_accumulator, a value of its Return type, and a non-negative Integer. It raises the value to the power of the integer, returning the Identity_element of the operation if the integer is zero. power_group takes a Group operation or Group_accumulator, a value of its Return type, and an Integer. It raises the value to the power of the integer.

abs returns the absolute value of a member of an Ordered_group, with respect to its inverse operation. It defaults to using negation, the inverse operation of add.

cancel performs cancellation (i.e. partial subtraction) on a member of a Cancellable_monoid.

quotient returns the quotient of a member of a Halvable_monoid with respect to another member and a given operation.

remainder returns the remainder of a member of a Halvable_monoid with respect to another member and a given operation.

quotient_remainder returns the quotient and remainder of a member of an Archimedean_monoid with respect to another member and a given operation. The default operation is add. If the members satisfy an Archimedean_group, it uses the inverse_operation instead of cancel. If called with multiply it calculates logarithm and remainder.

gcd returns the greatest common divisor of two members of an Euclidean_semimodule.

choose selects the n choose k binomial coefficent.

quadrance gives the quadrance between two points. It is a quadratic measure of the separation between two points.

The functions in ordering.h implement order selection algorithms, as described in StepanovMcJones, Chapter 4.3. They are all stable, i.e. equivalent objects are ordered with respect to the order in which they are passed as arguments.

select_0_2 takes a weak ordering and two values of its domain, and returns the minimum value. min uses lt as the weak ordering. select_1_2 takes a weak ordering and two values of its domain, and returns the maximum value. max uses lt as the weak ordering. select_0_3 takes a weak ordering and three values, returning the minimum. min uses lt as the weak ordering. select_2_3 takes a weak ordering and three values, returning the maximum. max uses lt as the weak ordering. select_1_3_ab takes a weak ordering and three values, where the first two are in increasing order, returning the median. select_1_3_ac takes a weak ordering and three values, where the first and the last are in increasing order, returning the median. clamp uses ltas the weak ordering. select_1_3 takes a weak ordering and three values, returning the median. median uses lt as the weak ordering. select_2_3 takes a weak ordering and three values, returning the maximum. max uses lt as the weak ordering. select_0_4 takes a weak ordering and four values, returning the minimum. min uses lt as the weak ordering. select_1_4 takes a weak ordering and four values, returning the second minimum. select_1_4_ab takes a weak ordering and four values, where the first two are in increasing order, returning the second minimum. select_1_4_ab_cd takes a weak ordering and four values, where the first two and the last two are in increasing order, returning the second minimum. select_2_4 takes a weak ordering and four values, returning the second maximum. select_2_4_cd takes a weak ordering and four values, where the last two are in increasing order, returning the second maximum. select_2_4_ab_cd takes a weak ordering and four values, where the first two and the last two are in increasing order, returning the second maximum. select_3_4 takes a weak ordering and four values, returning the maximum. max uses lt as the weak ordering.

equivalent_lexicographical takes two loadable ranges and an equivalence relation, comparing them for equivalence. equal_lexicographical uses eq as the equivalence relation.

compare_lexicographical takes two loadable ranges and a weak ordering, comparing them for lexicographical ordering. less_lexicographical uses lt as the ordering.

equal_range takes two Ranges, comparing them for equality. less_range takes two Ranges, comparing them for lt lexicographical ordering.

fill takes a writable range and a value, filling the range with that value. Alternatively, it takes a range, a value and a binary sink function, invoking the sink function with each cursor in the range and the given value.

count_if takes a loadable range, a unary predicate, and optionally an initial count. It counts the number of values in the range that satisfy the predicate. count_if_not takes a loadable range, a unary predicate, and optionally an initial count. It counts the number of values in the range that do not satisfy the predicate. count takes a loadable range, a value, and optionally an initial count. It counts the number of values in the range that equal the value. count_not takes a loadable range, a value, and optionally an initial count. It counts the number of values in the range that do not equal the value.

copy takes a loadable range as source and a storable cursor as destination. It performs copying from the first to the last element of the source. The range starting at the destination cursor can overlap with the source range, as long as no source cursor is read after an aliased destination cursor. The range starting at the destination cursor must be at least as long as the source range. copy may also take a loadable range as source and a storable range as destination. Then it performs copying from the first element of the source until either the source range or the destination range reaches its last element.

copy_n takes a loadable position and a count as source and a storable cursor as destination. It performs copying of n elements from the source. The range starting at the destination cursor can overlap with the source range, as long as no source cursor is read after an aliased destination cursor.

copy_select takes a loadable range as source, a storable cursor as destination, and a unary Predicate to determine which of the elements from the source that should be copied to the destination.

copy_if takes a loadable range as source, a storable cursor as destination, and a unary Predicate to determine which of the elements from the source that should be copied to the destination. The predicate is tested on the elements at the source cursors.

copy_if_not takes a loadable range as source, a storable cursor as destination, and a unary Predicate to determine which of the elements from the source that should not be copied to the destination. The predicate is tested on the elements at the source cursors.

The first version of map takes a loadable range as source, a storable cursor as destination, and a unary function to apply to every element in the source range, storing the result in the range starting at the destination cursor. It applies the function from the first to the last element of the source, which implies that the range starting at the destination cursor can overlap with the source cursor, as long as no source cursor is read after an aliased destination cursor.

The second version of map takes a loadable range and a loadable cursor as sources, a storable cursor as destination, and a binary function to apply to every corresponding pair of elements in the source ranges, storing the result in the range starting at the destination cursor. It applies the function from the first to the last element of the sources, which implies that the range starting at the destination cursor can overlap with any of the source cursors, as long as no source cursor is read after an aliased destination cursor.

reduce takes a loadable range, a binary operation, optionally a unary function, and a zero value. It starts with the zero value as the result, and, for each element in the range, applies the binary operation on the result and the return value of the unary function applied on the element. The default function is load.

reduce_nonempty takes a nonempty loadable range, a binary operation, and optionally a unary function. It starts with the result of applying the unary function on the first element of the range as the result, and, for each element in the rest of the range, applies the binary operation on the result and the return value of the unary function applied on the element. The default function is load.

reduce_nonzeroes takes a loadable range, a binary operation, optionally a unary function, and a zero value. It works the same as reduce except that the binary function is not applied when the function applied on an element of the range returns the zero value. The default function is load.

reduce_balanced takes a loadable range, a binary operation, optionally a unary function, and a zero value. It performs balanced reduction, storing intermediate reductions in a binary_counter. The default function is load. This algorithm minimizes the cost of applying the operation if the size of a reduced object is the sum of the sizes of the original objects and the complexity of applying the reduction operation grows linearly with the sizes of its arguments.

flat_map takes a loadable range as source and a unary function that returns a Sequence. It applies the function on every element in the source range, returning a Sequence of the concatenated sequences that the unary function returns.

is_partitioned takes a loadable range and a unary predicate. It checks if the range is partitioned according to the predicate, with all elements not satisfying the predicate preceding the elements satisfying the predicate.

is_partitioned_n takes a forward cursor, a distance, and a unary predicate. It checks if the range is partitioned according to the predicate, with all elements not satisfying the predicate preceding the elements satisfying the predicate.

partition_point takes a loadable forward range and a unary predicate, assuming that the range is partitioned according to the predicate. Using bisection, it returns a cursor pointing to the first element satisfying the predicate.

partition_point_n takes a forward cursor, a distance, and a unary predicate, assuming that the range from the cursor to the cursor + distance is partitioned according to the predicate. Using bisection, it returns a cursor pointing to the first element satisfying the predicate.

partition_semistable takes a mutable forward range and a unary prediate. It partitions the range such that all elements not satisfying the predicate precede the elements satisfying the predicate. It preserves the relative ordering of the elements not satisfying the predicate, but not the relative ordering of the elements satisfying the predicate. It returns the partition point, i.e. a cursor pointing to the first element satisfying the predicate.

partition_stable_with_buffer takes a mutable forward range, a cursor pointing to the first element of a mutable buffer with a size not less than the size of the forward range, and a unary prediate. It partitions the range such that all elements not satisfying the predicate precede the elements satisfying the predicate. It preserves the relative ordering of the elements on both sides of the partition point. It returns the partition point.

partition_stable_with_buffer takes a mutable forward range, a cursor pointing to the first element of a mutable buffer with a size not less than the size of the forward range, and a unary prediate. It partitions the range such that all elements not satisfying the predicate precede the elements satisfying the predicate. It preserves the relative ordering of the elements on both sides of the partition point. It returns the partition point.

partition_stable takes a mutable forward range and a unary predicate. It partitions the range such that all elements not satisfying the predicate precede the elements satisfying the predicate. It preserves the relative ordering of the elements on both sides of the partition point. It returns the partition point.

partition_unstable takes a mutable bidirectional range and a unary prediate. It partitions the range such that all elements not satisfying the predicate precede the elements satisfying the predicate. It returns the partition point.

gather_stable_with_buffer takes a mutable forward range, a cursor within the range, a cursor pointing to the first element of a mutable buffer with a size not less than the size of the forward range, and a unary predicate. It gathers all elements satisfying the predicate around the given cursor. It preserves the relative ordering of both elements satisfying the range and elements not satisfying the range. It returns the bounded_range of satisfying elements.

gather_stable takes a mutable bidirectional range, a cursor within the range, and a unary predicate. It gathers all elements satisfying the predicate around the given cursor. It preserves the relative ordering of both elements satisfying the range and elements not satisfying the range. It returns the bounded_range of satisfying elements.

gather_unstable takes a mutable forward range and a unary predicate. It gathers all elements satisfying the predicate around the given cursor. It returns the bounded_range of satisfying elements.

The functions in search_binary.h implement algorithms based on binary search, as described in Knuth3, Chapter 6.2.

search_binary_lower takes a loadable forward range and a relation defaulting to lt, assuming that the range is ordered in accordance with the relation. It returns a cursor pointing to the first element satisfying the relation.

search_binary_lower_n takes a loadable forward cursor, a count, and a relation defaulting to lt, assuming that the range is ordered in accordance with the relation. It returns a cursor pointing to the first element satisfying the relation.

search_binary_upper takes a loadable forward range and a relation defaulting to lt, assuming that the range is ordered in accordance with the relation. It returns the successor of a cursor pointing to the last element satisfying the relation.

search_binary_upper_n takes a loadable forward cursor, a count, and a relation defaulting to lt, assuming that the range is ordered in accordance with the relation. It returns the successor of a cursor pointing to the last element satisfying the relation.

search_binary takes a loadable forward range and a relation defaulting to lt, assuming that the range is ordered in accordance with the relation. It finds the bounded_range of elements satisfying the relation.

search_binary_n takes a loadable forward cursor, a count, and a relation defaulting to lt, assuming that the range is ordered in accordance with the relation. It finds the bounded_range of elements satisfying the relation.

The functions in search.h implement algorithms based on linear search, as described in Knuth3, Chapter 6.1, and KnuthMorrisPratt.

search and search_not take a loadable range and a value that is equality-comparable with the elements of the range, stopping at the position of the first matching element, or at the limit of the range if no matching element is found. For search, a match is defined as the first element y in the range for which the given element x equals y. For search_not, a match is defined as the first element y in the range for which the given element x differs from y.

search_n and search_not_n take a weak range instead of a loadable range. They return a pair of the cursor and the count so that a search can be resumed.

search_if and search_if_not take a unary predicate instead of an element. For search_if, a match is defined as the first element x for which the given predicate is true. For search_if_not, a match is defined as the first element y for which the given predicate is false.

search_if_n and search_if_not_n take a weak range instead of a loadable range. They return a pair of the cursor and the count so that a search can be resumed.

search_backward, search_backward_not, search_backward_if, and search_backward_if_not are variations of the functions above that search backward through the loadable range. They require a bidirectional range.

search_backward_n, search_backward_not_n, search_backward_if_n, and search_backward_if_not_n take a weak range instead of a loadable range. They return a pair of the cursor and the remaining count so that a search can be resumed.

search_unguarded, search_not_unguarded, search_if_unguarded, and search_if_not_unguarded are variations of the functions above that assum_ope an element satisfying the applied predicate is known to exist in the given range (which necessarily is nonempty). They take a cursor pointing to the first element to be tested instead of a range as they don't need to check for the limit of the range at each iteration. Iteration is faster because the end of the range doesn't need to be checked.

search_guarded, search_not_guarded, search_if_guarded, and search_if_not_guarded are variations of the functions above that temporarily put a sentinel value at the last position of the range, to enable search nearly as fast as for the unguarded variations. They require the range to be Mutable and take a cursor pointing to the last element of the range instead of its limit. search_not_guarded, search_if_guarded, and search_if_not_guarded also take a sentinel value to be used to ensure termination.

assum_ope an element satisfying the applied predicate is known to exist in the given range. They take a cursor pointing to the first element to be tested instead of a range as they don't need to check for the limit of the range at each iteration.

search_match and search_mismatch take two loadable ranges and an optional relation, simultaneously traversing the ranges and stopping at the first positions where a match or a mismatching element is found, respectively. The default relation is eq. If the second range is not shorter than the first, or if a match is known to exist before the end of the second range, the algorithm can be called with only a cursor to the first element of the second range.

search_match_n and search_mismatch_n are variants of the functions above that take a weak range and a cursor. They return a pair of a cursor pair and the remaining count so that a search can be resumed.

search_adjacent_match and search_adjacent_mismatch take a loadable range and a relation, stopping at the first position where an element and its successor satisfy the relation, or does not satisfy the relation, respectively. The default relation is eq.

search_adcacent_match_n and search_adjacent_mismatch_n are variants of the functions above that take a weak range and a cursor. They return a pair of a cursor and the remaining count so that a search can be resumed.

search_subsequence takes two loadable ranges, a cursor pointing to the first element of a mutable buffer of the Difference_type of the range cursor, with a size not less than the size of the second range, and an optional relation. The default relation is eq It will return a cursor pointing to the first subsequence in the first range that matches the second range, or the limit of the first range if no subsequence matching the second range is found.

reverse takes a mutable range and reverses the elements in the range.

rotate takes a mutable range and a cursor in the range, swapping elements such that the element at the given cursor's position becomes the first element in the range, and the element preceding it becomes the last element.

for_each takes a loadable range and a procedure of arity 1. It applies the procedure on each value in the range, returning a pair containing a cursor and the procedure. The cursor points at the position where the iteration has stopped (which may not be reachable a second time), and the procedure is returned as it could have accumulated information during the traversal.

for_each_n takes a loadable cursor, a count, and a range and a procedure of arity 1. It applies the procedure on each value in the range, returning a pair containing a cursor and the procedure. The cursor points at the position where the iteration has stopped (which may not be reachable a second time), and the procedure is returned as it could have accumulated information during the traversal.

each_of takes a loadable range and a unary predicate. It checks if each value in the range satisfy the predicate. any_not_of takes a loadable range and a unary predicate. It checks if any value in the range does not satisfy the predicate. none_of takes a loadable range and a unary predicate. It checks if none of the values in the range satisfies the predicate. any_of takes a loadable range and a unary predicate. It checks if any value in the range satisfies the predicate.

each_of_n, any_not_of, none_of_n, and any_of_n are variants of the functions above that take a weak range instead of a loadable range.

power_unary takes a Transformation or Action, a starting value of its Return_type, and a non-negative Integer. It invokes the Transformation or Action as many times as given by the Integer. distance takes a Transformation or Action and two values of the its Return_type, where the second value is reachable from the first. It returns the number of invocations of the transformation it takes to go from the first to the second value. collision_point takes a Transformation or Action, a starting value of its Return_type, and a unary Predicate. It returns the terminal point (if the transformation is terminating) or the collision point of the transformation (if the transformation is non-terminating). The collision point is the value where the transformation (starting with the given starting value) applied n times equals the transformation applied 2n + 1 times. The predicate guards against going outside of the transformation's definition space. collision_point_nonterminating_orbit takes a Transformation or Action and a starting value of its Return_type. The transformation has to be total or nonterminating for the given value. is_terminating takes a Transformation or Action, a starting value of its Return_type, and a unary Predicate. It determines if the given transformation is terminating. is_circular takes a Transformation or Action, a starting value of its Return_type, and a unary Predicate. It determines if the given transformation is circular. is_circular_nonterminating_orbit takes a Transformation or Action and a starting value of its Return_type. The transformation has to be total or nonterminating for the given value. It determines if the given transformation is circular. connection_point takes a Transformation or Action, a starting value of its Return_type, and a unary Predicate. It returns the connection point of the transformation, i.e. the point where a cycle starts, or the terminal element for a terminating transformation. connection_point_nonterminating_orbit takes a Transformation or Action and a starting value of its Return_type. It returns the connection point of the transformation, i.e. the point where a cycle starts, or the terminal element for a terminating transformation. orbit_structure takes a Transformation or Action, a starting value of its Return_type, and a unary Predicate. It returns a structure that measures all orbit sizes. orbit_structure_nonterminating_orbit takes a Transformation or Action and a starting value of its Return_type. It returns a structure that measures all orbit sizes.

zip takes two loadable ranges as sources and a storable cursor as destination. It performs copying from the first to the last element of the sources, starting with the first source and alternating between the sources for every element. If one of the source ranges is longer than the other, its remaining elements are appended at the end.

unzip takes one loadable range as source and two storable cursors as destinations. It performs copying from the first to the last element of the source, alternating between the destinations for each element.

is_dag takes a Bidirectional_bicursor with no predecessor and checks if it forms a directed acyclic graph (DAG).

The following algorithms assume that the given Bicursors traverse binary trees.

is_reachable takes two Bidirectional_bicursors of a binary tree. It checks if the second can be reached from the first.

tree_weight takes a Bicursor and calculates the number of tree nodes reachable from it. If the given bicursor is not a Bidirectional_bicursor but is a Linked_bicursor to non-constant tree nodes, it uses link rotation and avoids recursion. Otherwise recursion is used, which may be an issue with unbalanced trees.

tree_height takes a Bicursor and calculates the height of the tree with the bicursor as its root. If the given bicursor is not a Bidirectional_bicursor recursion is used, which may be an issue with unbalanced trees.

tree_traverse takes a Bicursor and a binary Invocable procedure where the first argument is a df_visit and the second argument is of the bicursor type. It traverses the tree in depth-first order, invoking the given procedure three times for each node visit, passing in the order of the visit (preorder, inorder, postorder) of the call along with a copy of the cursor for each node visit.

tree_traverse_rotating takes a Linked_bicursor and a unary Invocable procedure where the argument is of the bicursor type. It traverses the tree in depth-first order, visiting each node three times with no information about the order of the visit.

tree_traverse_phased_rotating takes a Linked_bicursor, a phase between 0 and 3 and a unary Invocable procedure where the argument is of the bicursor type. It traverses the tree in depth-first order, visiting each node three times but invoking the procedure only once per node.

tree_isomorphic takes two Bicursors, comparing two trees for isomorphism (i.e. if they have the same shape).

tree_equivalent takes two Loadable Bicursors and an equivalence relation, comparing two trees for equivalence. Trees that are not isomorphic are not equivalent. tree_equal uses eq as the equivalence relation.

tree_compare takes two Loadable Bicursors and a weak ordering, comparing them for lexicographical ordering. A missing left or right successor for otherwise equivalent trees during traversal makes that tree less than the other. tree_less uses lt as the ordering. tree_shape_less uses a relation that is always false, and can be used for sorting trees by shape.

bit implements a type supporting the algebra of Boole and propositional logic. It is a Commutative_semiring, with addition represented by "xor" and multiplication represented by "and". The 16 possible logical operations on two bits are implemented over this semiring by the following named functions, in binary counting order: contradiction, conjunction, nonimplication, projection_left, converse_nonimplication, projection_right, nonequivalence, disjunction, nondisjunction, equivalence, nonprojection_right, converse_implication, nonprojection_left, implication, nonconjunction, tautology.

vector implements an affine vector type for use in linear algebra. It is a Semimodule over a Semiring, and a Mutable_range. It is customizable by an Engine_type, which handles element storage, and an operation traits type, which allows customization of vector operations. matrix_operation_t implements default operations for linear algebra. static_vector implements a fixed-size vector type where the engine uses array_k for storage and matrix_operation_t for operations. dynamic_vector implements a variable-size vector type where the engine uses array for storage and matrix_operation_t for operations.

point implements an affine point type for use in linear algebra. It is an Affine_space over a Vector_space. By default it uses array_k for storage of the coordinates.

rational implements a rational number type, forming a Field over any Integral_domain.

polynomial implements a polynomial type, forming an Integral_domain over any Ring. degree returns the degree of the polynomial, where an empty polynomial has degree -1. evaluate evaluates the polynomial at a given value, and subderivative calculates the k:th subderivate of a given polynomial and value k.

binary counter implements a binary counter of k elements, using a given binary operation and identity element. When calling it with an object, if the object is not equal to the identity element of the counter, it will be reduced with the existing elements in the counter, resetting each element to the identity element until either an identity element is found or the end of the elements are reached. If an identity element is found, the reduced value replaces it. If the end of the elements are reached, it is appended as the new last element.

memory implements a descriptor for a contiguous sequence of bytes, with a pointer to the first byte and the size of the sequence.

empty_allocator implements an Allocator that always fails. choice_allocator implements an Allocator that composes an Ownership_aware_allocator with an Allocator. When allocating, it tries the first allocator, and if it fails it tries the second. static_allocator implements a stateful Allocator that stores data in a locally allocated array. It can be queried with available for its remaining space. It only suppports deallocation of the last allocated memory. dynamic_allocator implements a stateless Allocator that allocates using allocate_dynamic. affix_allocator is an Allocator that stores another Allocator and adds the option to store a prefix and a postfix object to the allocated bytes. If any of the types are void no object is stored. By default no postfix is stored. prefix and postfix return a reference to the stored affix object. partition_allocator implements an Allocator that stores two Allocators and a Pseudopredicate. When allocating, it uses the first allocator if the pseudopredicate returns false and the second allocator if the pseudopredicate returns true.

A single instance default_allocator is defined. It can statically allocate up to 1KB and then dynamically allocates with suitable alignment for all built-in scalar types. To avoid exhausing the static buffer, deallocation needs to be done in reverse order of allocation. A function array_allocator that returns a reference to default_allocator is also defined. It is used as the default allocator for all array data structures.

bounded_range implements a Range consisting of two Loadable cursors.

pair implements a structure of two elements (that may differ in type) allocated on the stack. They can be accessed through the function get, either by cursor or by type. If the two elements are of the same type, pair also provides a functor interface through the member function .map.

array_k implements an array of k elements contiguously allocated on the stack, like built-in C++ arrays, but with regular semantics, lexicographic comparison operators, and supporting functions and type functions for iteration and element access. array_k is also a Monad.

In linked data structures, the elements are stored in nodes that are permanently placed. During the lifetime of a linked data structure its nodes never move.

Lists have regular semantics, lexicographic comparison operators, and supporting functions and type functions for iteration and element access. Lists are also Monads.

Singly-linked lists provide a Forward_cursor.

list_singly_linked_front implements a singly-linked list that supports constant-time insert and erase at the front or after a given cursor. The header and cursor type are the size of a single pointer.

list_singly_linked_front_back implements a singly-linked list that supports constant-time insert and erase at the front or after a given cursor, and constant-time insert at the back. The header is the size of two pointers and the cursor type is the size of a single pointer.

list_singly_linked_circular implements a circular singly-linked list that supports constant-time insert and erase at the front or after a given cursor, and constant-time insert at the back. The header is the size of a single pointer and the cursor type is the size of two pointers. Iteration is slower than for list_singly_linked_front and list_singly_linked_front_back because of special cases at the front and back of the list.

Doubly-linked lists support constant-time insert and erase at the front and back and constant-time insert before and after a given cursor.

list_doubly_linked_circular implements a circular doubly-linked list. It supports constant-time erase before and after a given cursor. The header is the size of a single pointer and the cursor type is the size of three pointers. Iteration is slower than for list_doubly_linked_front_backand list_doubly_linked_sentinel because of special cases at the front and back of the list. Construction of an empty list is cheaper than for list_doubly_linked_sentinel.

list_doubly_linked_front_back implements a doubly-linked list with both ends linked to its header. It supports constant-time erase at a given cursor. The header is the size of two pointers and the cursor type is the size of a single pointer. Construction of an empty list is cheaper than for list_doubly_linked_sentinel, but move construction, move assignment and swap is more expensive because of remote links to the header at the front and back of the list.

list_doubly_linked_sentinel implements a doubly-linked list with a sentinel node linked at both ends. It supports constant-time erase at a given cursor. The header and cursor type are the size of a single pointer. Iteration is faster than for list_doubly_linked_circular but construction of an empty list is more expensive as it requires allocation of the sentinel node.

In extent-based data structures, the elements are stored in one or more extents that are allocated and deallocated on demand. During the lifetime of an extent-based data structure its elements may move.

Arrays have regular semantics, lexicographic comparison operators, and supporting functions and type functions for iteration and element access. Arrays are also Monads.

array_single_ended implements an array of dynamically allocated elements. It stores a single pointer on the stack, keeping the array size and capacity in a header to the array elements. array_single_ended supports insertion at the back in amortized constant time using emplace and push. If the capacity is exceeded it reallocates and moves its elements.

array_double_ended implements an array of dynamically allocated elements. It stores a single pointer on the stack, keeping the array size and capacity in a header to the array elements. array_double_ended supports insertion at the back and the front in amortized constant time using emplace, push, emplace_first, and push_first. If the capacity is exceeded it reallocates and moves its elements.

array_circular implements an array of elements that are not necessarily contiguously allocated, as the elements are treated as if they may wrap around at the end of the reserved area. It stores a single pointer on the stack, keeping the array size and capacity in a header to the array elements. Cursors of array_circular elements are larger and element access is slower than for array_single_ended and array_double_ended. array_circular supports insertion at the back and the front in amortized constant time using emplace, push, emplace_first, and push_first. If the capacity is exceeded it reallocates and moves its elements.

array_segmented_single_ended implements a segmented array of elements, where elements are dynamically allocated in multiple contiguously allocated blocks of a fixed size k, managed by an index of pointers, also dynamically allocated. All blocks in the array are full, except possibly the last one. array_segmented_single_ended supports insertion at the back in amortized constant time using push. If the last block is full, a new block is allocated and appended to the index. Existing elements are never moved when new allocations occur. Erasure at the back using pop deallocates the last block if it becomes empty.

array_segmented_double_ended implements a segmented array of elements, where elements are dynamically allocated in multiple contiguously allocated blocks of a fixed size k, managed by an index of pointers, also dynamically allocated. All blocks in the array are full, except possibly the first and last one. array_segmented_double_ended supports insertion at the front and at back in amortized constant time using emplace, push, emplace_first, and push_first. If the last block is full, a new block is allocated and appended to the index. Existing elements are never moved when new allocations occur. Erasure at the front and back and front using pop_first or pop deallocates the first and last block if they become empty.

list_pool implements a pool of contiguously allocated singly linked elements. allocate inserts a new element after a given position and returns the position of the new element. free removes an element at a given position. free_pool removes all elements starting at a given position until the last reachable element.

tree_oriented implements a binary tree, optionally containing elements. Trees are constructed by supplying (optional) left and right subtrees. Tree nodes contain links to the left and right child nodes, supporting Bicursor traversal.

tree_bidirectional implements a binary tree, optionally containing elements. Trees are constructed by supplying (optional) left and right subtrees. Tree nodes contain links to the left and right child nodes, and a link to the parent node, supporting Bidirectional_bicursor traversal, which avoids recursion.

height returns the height of a binary tree. weight returns the weight of a binary tree.

traverse performs a depth-first traversal of a binary tree, invoking a binary procedure on each node at the preorder, inorder, and postorder visit. The first argument is a df_visit and the second argument is a Bicursor used to access the tree node. traverse_rotating performs a depth-first traversal of a binary tree, invoking a unary procedure once on each node. The argument is a Bicursor used to access the tree node. It uses traverse_phased_rotating, which implies that the tree must be mutable and the traversal much be completed to preserve the tree invariant.

result implements a type that carries either a value or an error. The presence of a value can be checked by boolean evaluation. An expected object is Mutable if its Value_type is. fail constructs a result carrying an error. result also provides a monadic interface through the member functions .map and .flat_map.

locked_stack implements a thread-safe stack on top of a single-ended dynamic sequence. try_push tries to push a value on the stack, failing if the stack is locked. push pushes a value on the stack, blocking until it succeeds. try_pop tries to pop a value off the stack, failing if the stack is locked or empty.

locked_queue implements a thread-safe queue on top of a double-ended dynamic sequence. try_push tries to push a value on the queue, failing if the queue is locked. push pushes a value on the queue, blocking until it succeeds. try_pop tries to pop a value off the queue, failing if the queue is locked or empty. pop waits until the queue is non-empty and then pops the value.

The concepts in this library are largely based on definitions in StepanovMcJones, with some name changes and adaptations to modern C++ features, such as move semantics.

Same_as describes a pair of types that are the same.

Convertible_to describes a pair of types where the first is implicitly and explicitly convertible to the second.

Boolean_testable describes a type that is implicitly and explicitly convertible to bool.

Equality_comparable describes a type with equality comparison operators. Equality_comparable_with describes two types with equality comparison operators defined between them.

Destructible describes a type with a destructor. Constructible describes a type with a constructor. Default_initializable describes a type for which the variable initialization T t is valid. Move_constructible describes a type with a move constructor. Copy_constructible describes a type with a copy constructor. Assignable describes a type with assignment operator. Movable describes a Move_constructible type with a move assignment operator. Copyable describes a Copy_constructible type with a copy assignment operator. Semiregular describes a type that is both Default_constructibleand Copyable. Regular describes a type that is Semiregular and Equality_comparable. axiom_Regular checks the concept for one given value. Totally_ordered describes a type where the relational operators provide the natural total ordering for the type. axiom_Totally_ordered checks the concept for two given values where the first must be less than the second.

Semigroup describes a Regular type together with an associative binary operation. Additive_semigroup describes a commutative Semigroup where the binary operation is operator+. axiom_Additive_semigroup checks the concept for three given values. Multiplicative_semigroup describes a Semigroup where the binary operation is operator*. axiom_Multiplicative_semigroup checks the concept for three given values.

Monoid describes a Semigroup with an identity element, returned by the type function Identity_element. Additive_monoid describes an Additive_semigroup with an identity element, returned by the type function Zero. axiom_Additive_monoid checks the concept for three given values. Multiplicative_monoid describes an Multiplicative_semigroup with an identity element, returned by the type function One. axiom_Multiplicative_monoid checks the concept for three given values.

Group describes a Monoid with a unary Operation inverse_operation that when invoked returns the inverse of an object. Additive_group describes an Additive_monoid where the inverse of an object is returned by the unary operator-, and subtraction is implemented by the binary operator-. axiom_Additive_group checks the concept for three given values. Multiplicative_group describes a Multiplicative_monoid where the inverse of an object is returned by inoking the unary Operation reciprocal, and division is implemented by operator/. axiom_Multiplicative_group checks the concept for three given values.

Semiring describes a type that is a Monoid in two operations Add_op and Mul_op, defaulted to the operators returned by the binary Operations add and multiply, which unless specialized invoke operator+ and operator*. Add_op is expected to be commutative, and Mul_op is expected to distribute over Add_op. axiom_Semiring checks the concept for three given values. Commutative_semiring descrivbes a Semiring where Mul_op is commutative.

Ring describes a Semiring where Add_op forms a Group. axiom_Ring checks the concept for three given values. Commutative_ring describes a Ring where Mul_op is commutative.

Integral_domain describes a Commutative_ring where there are no non-zero divisors.

Field describes an Integral_domain where Mul_op forms a group.

Left_semimodule describes a "vector" type that is a Monoid with a binary operation V_add_op defaulted to add_op, together with a "scalar" type that is a Commutative_semiring with two binary operations S_add_op and S_mul_op defaulted to addand multiply, and where an operator* with the scalar on the left side and the vector on the right side is defined, is commutative, distributive over V_add_op, compatible with S_mul_op and has an identity element One. Right_semimodule describes a similar structure where operator* has the vector on the left side and the scalar on the right side. Semimodule describes a pair of types that form both a Left_semimodule and a Right_semimodule.

Left_module describes a Left_semimodule where the "vector" type is a Group with V_add_op and where the "scalar" type is a Ring with S_add_op and S_mul_op. Right_module describes a similar structure based on a Right_semimodule. Module describes a pair of types that form both a Left_module and a Right_module.

Vector_space describes a Module where the "scalar" type is a Field and is defaulted to the Scalar_type of the "vector" type.

Affine_space describes a triple of types, representing a "point", a "vector", and a "scalar", where the vector and scalar form an Affine_space and the point is a Regular type where operator+ and operator- are defined such that addition and subtraction of point and vector yields a point, and subtraction of point and point yields a vector.

Functor describes a Movable type with a related type constructor functor_t, that supports the type function Constructor_type and the function fmap, returning a new Functor.

Monad describes a type that is constructible from one value of its Value_type with the function unit, and where a value of the type and a unary Invocable that takes a value of the Monad's Value_type can be composed with the function chain, returning an object of the same type.

Integral describes a built-in binary integer type.

Signed_integral describes a built-in binary integer type.

Unsigned_integral describes a built-in binary integer type.

Integer describes a Totally_ordered integral type represented like a built-in machine type, with all its standard operators.

Invocable describes a procedure that is not required to be equality-preserving. Regular_invocable describes an equality-preserving Invocable. Operation describes a Regular_invocable with arity > 0 and with the same domain and codomain. Predicate describes a Regular_invocable where the codomain is Boolean_testable. Pseudopedicate describes an Invocable where the codomain is Boolean_testable. Relation describes a Predicate of arity 2 which accepts its arguments in any order. Transformation describes a unary Operation with an Integer Distance_type. Action describes a unary function that takes an object by non-constant reference. It is equivalent with a corresponding Transformation that returns a modified copy of the argument. Accumulation_procedure describes a binary Invocable procedure that modifies its first argument, using itself and the second argument. It is equivalent with a corresponding binary Operation. Semigroup_accumulator describes an associative Accumulation_procedure. Monoid_accumulator describes a Semigroup_accumulator with an identity element, returned by the type function Identity_element. Group_accumulator descrives a Monoid_accumulator with a unary Operation inverse_operation that when invoked returns the inverse of an object.

Ordered_semigroup describes a Semigroup that is also Totally_ordered. Ordered_additive_semigroup describes an Additive_semigroup that is also Totally_ordered. Ordered_monoid describes a Monoid that is also Totally_ordered. Ordered_additive_monoid describes an Additive_monoid that is also Totally_ordered. Ordered_group describes a Group that is also Totally_ordered. Ordered_additive_group describes an Additive_group that is also Totally_ordered. Cancellable_monoid describes an Ordered_monoid that has a binary operation cancel that implements cancellation. Archimedean_monoid describes a Cancellable_monoid that has a Quotient_type that is an Integral_domain. Halvable_monoid describes a Archimedean_monoid that has a half function. Archimedean_group describes an Archimedean_monoid that is also a Group. Euclidean_semimodule describes a Semimodule that has a quotient and remainder function, and where Euclid's algorithm terminates. Ordered_ring describes a Ring that is also Totally_ordered. Ordered_integral_domain describes an Integral_domain that is also Totally_ordered.

Allocator describes a Semiregular type managing blocks of raw memory. A function allocate that takes a reference to an Allocator and a desired number of bytes will try to allocate a contiguous sequence of bytes and return a memory descriptor to it. The caller must keep the descriptor around for deallocation when supported. Ownership_aware_allocator describes an Allocator that supports the Predicate is_owner, which takes an Allocator and a memory block allocated from it, and checks if allocate was called with that Allocator to obtain it.

Cursors are types representing a point in a space, such as a number in a numeric type or a memory address to an element in a data structure. When defined, cursors may have accessible have successors and predecessors. If the cursor points to a point holding a value, it can often be accessed via the cursor using the functions load, store, and at.

Cursor describes a Movable object representing a point in a space, with a function increment that moves it to the next point. Points are not necessarily visitable more than once.

Forward_cursor describes a Regular Cursor type where points may be visited multiple times.

Bidirectional_cursor describes a Forward_cursor type with a function decrement that moves it to the previous point. It is an Affine_space over its Difference_type.

Linked_forward_cursor describes a Forward_cursor type with a function next_link that returns a reference to the next linked element.

Forward_linker describes a function object type that can be called with two Linked_forward_cursor objects and will link the first one to the second one.

Linked_bidirectional_cursor describes a Bidirectional_cursor type with functions next_link and prev_link that return a reference to the adjacent linked

Bidirectional_linker describes a function object type that can be called with two Linked_bidirectional_cursor objects and will link the first one to the second one.

Segmented_cursor describes a cursor in a segmented range, consisting of an index cursor and a segment cursor at the current index, both of which are Cursor types.

Bicursor describes an object representing the position of a node in a directed graph with up to two outgoing edges from each node, labelled left and right, with a function is_empty to check if no outgoing edges exist, functions has_left_successor and has_right_successor to check for outgoing edges, and functions increment_left and increment_right to move it to an existing outgoing edge.

Bidirectional_bicursor describes a Bicursor type with a function has_predecessor to check if an incoming edge exists, and a function decrement to move it to an existing incoming edge.

Linked_bicursor describes a Bicursor type with functions set_left_successor and set_right_successor that set the outgoing edges to link to a given bicursor. is_empty must also be defined on a default-constructed (empty) bicursor, and left_successor and right_successor must be defined and refer to empty bicursors when they don't refer to a node.

Loadable describes a type with a function load that returns a constant reference to its held object. For an object that represents the position of another object, load returns a reference to the other object. For other objects, load returns a reference to the object itself.

Storable describes a type with a function store that stores a given value at at a given position. If the given object does not represent a position, it stores the value at the position of the object itself.

Mutable describes a type that is both Loadable and Storable, and defines a function at that returns either a reference or a constant reference to its held object.

Limit describes a Cursor type together with a type that can be used to check if the limit of the range into which the cursor points has been reached. The check is done with the binary Predicate precedes.

Range describes a type with two functions first and limit, returning the half-open range of cursors describing it. Mutable_range describes a Range with a Mutable Cursor_type.

Sequence describes a Range that is Totally_ordered, and represents a composite object whose range of elements are its parts. It has functions is_empty. size and operator[] for element access. Dynamic_sequence describes a Sequence that can change size at runtime. It has functions insert and erase to change elements at the back or the front of the range.

Traversable describes a tree with a Bicursor type that can be used to visit every node from a starting/ending point given by root with a function traverse. The tree also features functions is_empty, height, and weight.

Remove_const is a type stripped of const and volatile qualifiers.

Remove_ref is a type stripped of reference qualifiers.

Decay is a type stripped of const, volatile, and reference qualifiers.

Underlying_type is the type describing the data storage of a given type.

Element_type is the type of an element in a pair with a given index.

Error_type is the type of the error that can be stored in a result.

Scalar_type is the associated scalar type of a Module-like object.

Zero is the additive identity element of a given type.

One is the multiplicative identity element of a given type.

Return_type is the return type of an Invocable type with a given list of argument types.

Distance_type is an Integer type large enough to count the number of invocations of a Transformation or Action that is necessary to go from any return value to another.

Value_type is either a type directly, or, in the case of a Cursor type or a Range type, the type it is parameterized on.

Pointer_type is the type of a pointer to an object of a given type.

Difference_type is a type capable of storing the (signed) difference between two cursors of the given type.

Cursor_type is the type of an object describing a cursor to the given type.

Size_type is the type used to describe the size of an object of a given type.

Size is the size of a given type (when known at compile time).

Index_cursor_type and Segment_cursor_type are the two Cursor types of a Segment_cursor.

Weight_type is a type capable of storing the weight of a graph.

Allocator_alignment returns the alignment of a given Allocator.

Signed_type returns a signed type of the same size as a given Integral type.

Unsigned_type returns an unsigned type of the same size as a given Integral type.

Concepts, types and functions in this library are named based on the following principles:

Consistency with the history and modern conventions of mathematics, in particular with computer science, is deemed more important than consistency with established names in popular programming languages. Consistency with popular programming languages is deemed more important than consistency with established names in C++.

Lexicographical ordering of names for closely related elements is deemed desirable, to facilitate searching. Multi-word names are separated by _. Concepts and type functions are named with a leading upper case letter, while functions and types are all lower case.

Short names are deemed desirable, but abbreviations are generally avoided.

instrumented

cursor forward_cursor counted_cursor loadable_cursor reverse_cursor

filter_cursor filter_sink insert_cursor insert_sink map_cursor map_sink

power_left_associated power_right_associated power_semigroup power_monoid power_group

abs cancel quotient remainder quotient_remainder gcd

choose

quadrance

select_0_2 min select_1_2 max select_0_3 select_2_3 select_1_3_ab select_1_3_ac clamp select_1_3 select_0_4 select_1_4 select_1_4_ab select_1_4_ab_cd select_2_4 select_2_4_cd select_2_4_ab_cd select_3_4 median equivalent_lexicographical equal_lexicographical compare_lexicographical less_lexicographical equal_range less_range

fill

count_if count_if_not count count_not

copy copy_n copy_select copy_if copy_if_not

map

reduce reduce_nonempty reduce_nonzeroes reduce_balanced

flat_map

is_relation_preserving is_partitioned is_partitioned_n partition_point partition_point_n partition_semistable partition_stable_with_buffer partition_stable partition_unstable

gather_stable_with_buffer gather_stable gather_unstable

search_binary_lower search_binary_upper search_binary

search search_not search_n search_not_n search_if search_if_not. search_if_n search_if_not_n

search_backward search_backward_not search_backward_if search_backward_if_not search_backward_n search_backward_not_n search_backward_if_n search_backward_if_not_n

search_unguarded, search_not_unguarded, search_if_unguarded search_if_not_unguarded

search_guarded, search_not_guarded, search_if_guarded search_if_not_guarded

search_match search_mismatch search_match_n search_mismatch_n

search_adjacent_match search_adjacent_mismatch search_adjacent_match_n search_adjacent_mismatch_n

reverse rotate

for_each for_each_n

each_of any_not_of none_of any_of each_of_n any_not_of_n none_of_n any_of_n

zip unzip

is_dag

is_reachable tree_weight tree_height tree_traverse tree_traverse_rotating tree_traverse_phased_rotating tree_isomorphic tree_equivalent tree_equal tree_compare tree_less tree_shape_less

distance collision_point collision_point_nonterminating_orbit is_terminating is_circular is_circular_nonterminating_orbit connection_point connection_point_nonterminating_orbit orbit_structure orbit_structure_nonterminating_orbit

contradiction conjunction nonimplication projection_left converse_nonimplication projection_right nonequivalence disjunction nondisjunction equivalence nonprojection_right converse_implication nonprojection_left implication nonconjunction tautology

bit vector static_vector dynamic_vector point rational polynomial

memory static_allocator dynamic_allocator affix_allocator partition_allocator

bounded_range

pair array_k

list_singly_linked_front list_singly_linked_front_back list_singly_linked_circular

list_doubly_linked_circular list_doubly_linked_front_back list_doubly_linked_sentinel

array_single_ended array_double_ended array_circular

array_segmented_single_ended array_segmented_double_ended

list_pool

tree_oriented tree_bidirectional

result

locked_stack locked_queue

Same_as Equality_comparable Equality_comparable_with Destructible Constructible Default_initializable Move_constructible Copy_constructible Assignable Movable Copyable Semiregular Regular Totally_ordered

Semigroup Additive_semigroup Multiplicative_semigroup Monoid Additive_monoid Multiplicative_monoid Group Additive_group Multiplicative_group Semiring Commutative_semiring Ring Commutative_ring Integral_domain Field Left_semimodule Right_semimodule Semimodule Left_module Right_module Module Vector_space Affine_space

Functor Monad

Integral Signed_integral Unsigned_integral

Invocable Regular_invocable Operation Predicate Relation Transformation Action Accumulation_procedure Semigroup_accumulator Monoid_accumulator Group_accumulator

Ordered_semigroup Ordered_additive_semigroup Ordered_monoid Ordered_additive_monoid Ordered_group Ordered_additive_group Cancellable_monoid Archimedean_monoid Halvable_monoid Archimedean_group Euclidean_semimodule Ordered_ring Ordered_integral_domain

Allocator Ownership_aware_allocator

Cursor Forward_cursor Bidirectional_cursor Linked_forward_cursor Forward_linker Linked_bidirectional_cursor Bidirectional_linker Segmented_cursor Bicursor Bidirectional_bicursor Linked_bicursor Loadable Storable Mutable Limit Range Mutable_range Sequence Dynamic_sequence Traversable

Remove_const Remove_ref Decay Underlying_type Element_type Error_type

Scalar_type Zero One

Return_type Distance_type

Value_type Pointer_type Difference_type Cursor_type Size_type Size Index_cursor_type Segment_cursor_type Weight_type

Allocator_alignment

Signed_type Unsigned_type

[Knuth3] "The Art of Computer Programming, Volume 3, Sorting and Searching, Second Edition", ISBN 0-20189685-0

[KnuthMorrisPratt] "Fast Pattern Matching in Strings, SIAM Journal on Computing, Volume 6, Issue 2, pp. 323-350"

[StepanovMcJones] "Elements of Programming", ISBN 0-321-63537-X