[PATCH] Extend std::lexicographical_compare optimizations

[François Dumont]

Following:

https://gcc.gnu.org/ml/libstdc++/2019-12/msg00028.html

I've done the same kind of work on std::lexicographical_compare algo.

I had to make the internal lexicographical_compare functions return int 
rather than bool cause with bool you can't use a chunck based approach 
unless you double the number of comparison (once a < b and and another b 
< a).

 Â Â Â  * include/bits/stl_algobase.h
 Â Â Â  (__lexicographical_compare_impl): Return int.
 Â Â Â  (__lexicographical_compare::__lc): Likewise.
 Â Â Â  (__lexicographical_compare_aux1(_II1, _II1, _II2, _II2)): New.
 Â Â Â  (__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
 Â Â Â  _II2, _II2)): New.
 Â Â Â  (__lexicographical_compare_aux1(_II1, _II1,
 Â Â Â  _Deque_iterator<>, _Deque_iterator<>)): New.
 Â Â Â  (__lexicographical_compare_aux1(_Deque_iterator<>, _Deque_iterator<>,
 Â Â Â  _Deque_iterator<>, _Deque_iterator<>)): New.
 Â Â Â  (__lexicographical_compare_aux): Adapt, call later.
 Â Â Â  (__lexicographical_compare_aux(_Safe_iterator<>, _Safe_iterator<>,
 Â Â Â  _II2, _II2)): New.
 Â Â Â  (__lexicographical_compare_aux(_II1, _II1,
 Â Â Â  _Safe_iterator<>, _Safe_iterator<>)): New.
 Â Â Â  (__lexicographical_compare_aux(_Safe_iterator<>, _Safe_iterator<>,
 Â Â Â  _Safe_iterator<>, _Safe_iterator<>)): New.
 Â Â Â  (std::lexicographical_compare): Adapt, call later.
 Â Â Â  * include/bits/deque.tcc (__lex_cmp_dit): New.
 Â Â Â  (__lexicographical_compare_aux1): Add definitions.
 Â Â Â  * include/debug/safe_iterator.tcc (__lexicographical_compare_aux): New.
 Â Â Â  * testsuite/25_algorithms/lexicographical_compare/1.cc (test6, test7):
 Â Â Â  New.
 Â Â Â  * testsuite/25_algorithms/lexicographical_compare/deque_iterators/1.cc:
 Â Â Â  New.

Tested under Linux x86_64 normal and debug modes.

François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: lex_algo.patch
Type: text/x-patch
Size: 19459 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20191209/f42a29cf/attachment.bin>