This removes the indirect functors from <bits/predefined_ops.h> that are
used by our STL algorithms. Currently we wrap all predicates and values
into callables which accept iterator arguments, and automatically
dereference the iterators. With this change we no longer do that
dereferencing and so all predicates are passed values not iterators, and
the algorithms that invoke those predicates must dereference the
iterators.
This avoids wrapping user-provided predicates into another predicate
that does the dereferencing. User-provided predicates are now passed
unchanged to our internal algos like __search_n. For the overloads that
take a value instead of a predicate, we still need to create a predicate
that does comparison to the value, but we can now use std::less<void>
and std::equal_to<void> as the base predicate and bind the value to
those base predicates.
Because the "transparent operators" std::less<void> and
std::equal_to<void> were not added until C++14, this change defines
those explicit specializations unconditionally for C++98 and C++11 too
(but the default template arguments that make std::less<> and
std::equal_to<> refer to those specializations are still only present
for C++14 and later, because we don't need to rely on those default
template arguments for our internal uses).
When binding a predicate and a value into a new call wrapper, we now
decide whether to store the predicate by value when it's an empty type
or a scalar (such as a function pointer). This avoids a
double-indirection through function pointers, and avoids storing and
invoking stateless empty functors through a reference. For C++11 and
later we also use [[no_unique_address]] to avoid wasted storage for
empty predicates (which includes all standard relational ops, such as
std::less).
The call wrappers in bits/predefined_ops.h all have non-const operator()
because we can't be sure that the predicates they wrap are
const-invocable. The requirements in [algorithms.requirements] for
Predicate and BinaryPredicate template arguments require pred(*i) to be
valid, but do not require that std::to_const(pred)(*i) has to be valid,
and similarly for binary_pred.
libstdc++-v3/ChangeLog:
* include/bits/predefined_ops.h (equal_to, less): Define aliases
for std::equal_to<void> and std::less<void>.
(bind1st, bind2nd, not1, __equal_to): New object generator
functions for adapting predicates.
(__iter_less_iter, __iter_less_val, __iter_comp_val)
(__val_less_iter, __val_comp_iter, __iter_equal_to_iter)
(__iter_equal_to_val, __iter_comp_iter, __negate): Remove all
object generator functions and the class templates they return.
* include/bits/stl_algo.h (__move_median_to_first, __find_if_not)
(__find_if_not_n, __search_n_aux, find_end, find_if_not)
(__remove_copy_if, remove_copy, remove_copy_if, remove)
(remove_if, __adjacent_find, __unique, unique, __unique_copy)
(__unique_copy_1, __stable_partition_adaptive, stable_partition)
(__heap_select, __partial_sort_copy, partial_sort_copy)
(__unguarded_linear_insert, __insertion_sort)
(__unguarded_insertion_sort, __unguarded_partition)
(lower_bound, __upper_bound, upper_bound, __equal_range)
(equal_range, binary_search, __move_merge_adaptive)
(__move_merge_adaptive_backward, __merge_adaptive_resize)
(__merge_without_buffer, inplace_merge, __move_merge)
(__includes, includes, __next_permutation, next_permutation)
(__prev_permutation, prev_permutation, __replace_copy_if)
(replace_copy, replace_copy_if, __is_sorted_until)
(is_sorted_until, __minmax_element, minmax_element, minmax)
(is_permutation, __is_permutation, find, find_if, adjacent_find)
(count, count_if, search, search_n, unique_copy, partial_sort)
(nth_element, sort, __merge, merge, stable_sort, __set_union)
(set_union, __set_intersection, set_intersection)
(__set_difference, set_difference, __set_symmetric_difference)
(set_symmetric_difference, __min_element, min_element)
(__max_element, max_element, min, max): Use direct predicates
instead of __iter_equal_to_iter, __iter_comp_iter, and
__iter_less_iter, __negate etc. Dereference iterators when
invoking predicates.
* include/bits/stl_algobase.h (__lexicographical_compare_impl)
(__lexicographical_compare::__lc, __lower_bound, lower_bound)
(lexicographical_compare, __mismatch, mismatch, __find_if)
(__count_if, __remove_if, __search, __is_permutation)
(is_permutation, search): Likewise.
* include/bits/stl_function.h (equal_to<void>, less<void>):
Define transparent comparison functions for C++98 and C++11.
* include/bits/stl_heap.h (__is_heap_until, __is_heap)
(__push_heap, push_heap, __adjust_heap, pop_heap, make_heap)
(sort_heap, is_heap_until, is_heap): Likewise.
* include/std/deque (erase_if): Remove call to __pred_iter.
(erase): Replace __iter_equals_val with __equal_to.
* include/std/inplace_vector (erase_if, erase): Likewise.
* include/std/string (erase_if, erase): Likewise.
* include/std/vector (erase_if, erase): Likewise.
Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>
Reviewed-by: François Dumont <frs.dumont@gmail.com>
This adds missing includes to internal library headers which get
included from more than one other header, so that they can be compiled
as a stand-alone header unit.
For existing use cases these includes are no-ops because they're already
done by the header that includes these files. For compiling them as a
header unit, this ensures that they include what they use.
libstdc++-v3/ChangeLog:
PR libstdc++/99413
* include/bits/align.h: Include debug/assertions.h.
* include/bits/codecvt.h: Include bits/c++config.h.
* include/bits/enable_special_members.h: Likewise.
* include/bits/erase_if.h: Likewise.
* include/bits/functional_hash.h: Include <type_traits>.
* include/bits/invoke.h: Include bits/move.h.
* include/bits/ostream_insert.h: Include bits/exception_defines.h.
* include/bits/parse_numbers.h: Include <type_traits>.
* include/bits/predefined_ops.h: Include bits/c++config.h.
* include/bits/range_access.h: Include bits/stl_iterator.h.
* include/bits/stl_bvector.h: Do not include bits/stl_vector.h.
* include/bits/stl_iterator.h: Include bits/stl_iterator_base_types.h.
* include/bits/stl_uninitialized.h: Include bits/stl_algobase.h.
* include/bits/uniform_int_dist.h: Include bits/concept_check.h.
* include/bits/unique_lock.h: Include bits/std_mutex.h.
* include/debug/assertions.h: Include bits/c++config.h.
PR libstdc++/78346
* include/bits/predefined_ops.h (_Iter_equals_iter): Store iterator
not its referent.
(_Iter_comp_to_iter): Likewise.
* testsuite/25_algorithms/search/78346.cc: New test.
From-SVN: r245090
Jakub Jelinek