gnu/gcc/6fc5746a5e809e4f22f343eb51bb963cd151ee7e libstdc++: make trees hetero equal_range O(lg n) [PR118851]
As shipped, the heterogeneous-key members equal_range of rbtree
containers map, multimap, set, and multiset walk the entire range
calling the predicate, in violation of the requirement for
logarithmic complexity. This patch revises them to match the
behavior of the non-heterogeneous multimap and multiset members,
and provides tests to verify it.
libstdc++-v3/Changelog:
PR libstdc++/118851
* include/bits/stl_tree.h (_M_equal_range_tr): Rewrite to match
non-heterogeneous equal_range implementation.
* testsuite/23_containers/map/operations/hetero/equal_range.cc:
New test.
* testsuite/23_containers/multimap/operations/hetero/equal_range.cc:
Same.
* testsuite/23_containers/multiset/operations/hetero/equal_range.cc:
Same.
* testsuite/23_containers/set/operations/hetero/equal_range.cc: Same.
5 files changed