Deque fiil/copy/move/copy_backward/move_backward/equal overloads
François Dumont
frs.dumont@gmail.com
Wed Jun 19 17:32:00 GMT 2019
I wanted to implement Debug overloads for those already existing
overloads but then realized that those algos could be generalized. This
way we will benefit from the memmove replacement when operating with C
array or std::array or std::vector iterators.
I might do the same for lexicographical_compare one day.
The ChangeLog below is quite huge so I attached it. I wonder if I could
use deque::iterator and deque::const_iterator in place of the
_Deque_iterator<> to reduce it ?
Tested under Linux x86_64 normal and debug modes, ok to commit ?
François
-------------- next part --------------
* include/bits/stl_deque.h
(fill, copy, copy_backward, move, move_backward): Move overloads for
std::deque iterators in std namespace.
(copy<_Tp, _OI>(
_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _OI)): New.
(copy<_Tp, _OI>(_Deque_iterator<_Tp, _Tp&, _Tp*>,
_Deque_iterator<_Tp, _Tp&, _Tp*>, _OI)): New, use latter.
(copy<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)): New.
(copy_backward<_Tp, _OI>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _OI)): New.
(copy_backward<_Tp, _OI>(_Deque_iterator<_Tp, _Tp&, _Tp*>,
_Deque_iterator<_Tp, _Tp&, _Tp*>, _OI)): New, use latter.
(copy_backward<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)):
New.
(equal<_Tp, _II>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _II)): New.
(equal<_Tp, _II>(_Deque_iterator<_Tp, _Tp&, _Tp*>,
_Deque_iterator<_Tp, _Tp&, _Tp*>, _II)): New, use latter.
(equal<_Tp>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>)): New.
(equal<_Tp>(_Deque_iterator<_Tp, _Tp&, _Tp*>,
_Deque_iterator<_Tp, _Tp&, _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>)): New, use latter.
(equal<_Tp>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, _Tp&, _Tp*>)): Likewise.
(equal<_Tp>(_Deque_iterator<_Tp, _Tp&, _Tp*>,
_Deque_iterator<_Tp, _Tp&, _Tp*>, _Deque_iterator<_Tp, _Tp&, _Tp*>)):
Likewise.
(equal<_II, _Tp>(_II, _II,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>): New.
(equal<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>): New, use
latter.
(move<_Tp, _OI>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _OI)):
New.
(move<_Tp, _OI>(_Deque_iterator<_Tp, _Tp&, _Tp*>, _OI)): New, use
latter.
(move<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)): New.
(move_backward<_Tp, _OI>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_OI)): New.
(move_backward<_Tp, _OI>(_Deque_iterator<_Tp, _Tp&, _Tp*>, _OI)): New,
use latter.
(move_backward<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)):
New.
* include/bits/deque.tcc
(fill, copy, copy_backward, move, move_backward): Move overloads for
std::deque iterators in std namespace.
(fill): Move loop on nodes inside branch when first and last nodes are
different.
(std::__detail::__copy_from_dit): New.
(copy<_Tp>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, _Tp&, _Tp*>)): Adapt to use latter.
(copy<_Tp, _OI>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _OI)): New, likewise.
(std::__detail::__copy_to_dit): New.
(copy<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)): New, use
latter.
(std::__detail::__copy_backward_from_dit): New.
(copy_backward<_Tp>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, _Tp&, _Tp*>)): Adapt to use latter.
(copy_backward<_Tp, _OI>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _OI)): New, likewise.
(std::__detail::__copy_backward_to_dit): New.
(copy_backward<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)):
New, use latter.
(std::__detail::__equal_from_dit): New.
(equal<_Tp, _II>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>)): Use latter.
(equal<_Tp, _II>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _II)): New, likewise.
(std::__detail::__equal_to_dit): New.
(equal<_II, _Tp>(_II, _II,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>): New, use latter.
(std::__detail::__move_from_dit): New.
(move<_Tp>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, _Tp&, _Tp*>)): Adapt to use latter.
(move<_Tp, _OI>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _OI)): New, likewise.
(std::__detail::__move_to_dit): New.
(move<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)): New, use
latter.
(std::__detail::__move_backward_from_dit): New.
(move_backward<_Tp>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, _Tp&, _Tp*>)): Adapt to use latter.
(move_backward<_Tp, _OI>(_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
_Deque_iterator<_Tp, const _Tp&, const _Tp*>, _OI)): New, likewise.
(std::__detail::__move_backward_to_dit): New.
(move_backward<_II, _Tp>(_II, _II, _Deque_iterator<_Tp, _Tp&, _Tp*>)):
New, use latter.
* include/debug/deque
(fill<_Tp, _Alloc>(const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>
, __debug::deque<_Tp, _Alloc>>&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc>>&, const _Tp&)): New.
(copy<_Tp, _Alloc, _OI>(
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&, _OI)): New.
(copy<_Tp, _Alloc, _OI>(
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&, _OI)): New.
(copy<_Tp, _Alloc>(
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&)): New.
(copy<_Tp, _Alloc>(
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&)): New.
(copy<_II, _Tp, _Alloc>(_II, _II,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&)): New.
(copy_backward<_Tp, _Alloc, _OI>(
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&, _OI)): New.
(copy_backward<_Tp, _Alloc, _OI>(
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&, _OI)): New.
(copy_backward<_Tp, _Alloc>(
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&)): New.
(copy_backward<_Tp, _Alloc>(
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&)): New.
(copy_backward<_II, _Tp, _Alloc>(_II, _II,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&)): New.
(equal<_Tp, _Alloc, _II>(
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&, _II)): New.
(equal<_Tp, _Alloc, _II>(
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&, _II)): New.
(equal<_Tp, _Alloc1, _Alloc2>(
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc1> >&,
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc1> >&,
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc2> >&)): New.
(equal<_Tp, _Alloc1, _Alloc2>(
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc1> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc1> >&,
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc2> >&)): New.
(equal<_Tp, _Alloc1, _Alloc2>(
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc1> >&,
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc1> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc2> >&)): New.
(equal<_Tp, _Alloc1, _Alloc2>(
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc1> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc1> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc2> >&)): New.
(equal<_II, _Tp, _Alloc>(_II, _II,
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&)): New.
(equal<_II, _Tp, _Alloc>(_II, _II,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&)): New.
(move<_Tp, _Alloc, _OI>(
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&, _OI)): New.
(move<_Tp, _Alloc, _OI>(
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&, _OI)): New.
(move<_Tp, _Alloc>(
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&)): New.
(move<_Tp, _Alloc>(
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&)): New.
(move<_II, _Tp, _Alloc>(_II, _II,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&)): New.
(move_backward<_Tp, _Alloc, _OI>(
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&, _OI)): New.
(move_backward<_Tp, _Alloc, _OI>(
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&, _OI)): New.
(move_backward<_Tp, _Alloc>(
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, const _Tp&, const _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&)): New.
(move_backward<_Tp, _Alloc>(
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&)): New.
(move_backward<_II, _Tp, _Alloc>(_II, _II,
const _Safe_iterator<_Deque_iterator<_Tp, _Tp&, _Tp*>,
__debug::deque<_Tp, _Alloc> >&)): New.
* testsuite/23_containers/deque/copy.cc: New.
* testsuite/23_containers/deque/copy_backward.cc: New.
* testsuite/23_containers/deque/debug/copy11_neg.cc: New.
* testsuite/23_containers/deque/debug/copy12_neg.cc: New.
* testsuite/23_containers/deque/debug/copy21_neg.cc: New.
* testsuite/23_containers/deque/debug/copy22_neg.cc: New.
* testsuite/23_containers/deque/debug/copy31_neg.cc: New.
* testsuite/23_containers/deque/debug/copy32_neg.cc: New.
* testsuite/23_containers/deque/debug/copy33_neg.cc: New.
* testsuite/23_containers/deque/debug/copy41_neg.cc: New.
* testsuite/23_containers/deque/debug/copy42_neg.cc: New.
* testsuite/23_containers/deque/debug/copy43_neg.cc: New.
* testsuite/23_containers/deque/debug/copy51_neg.cc: New.
* testsuite/23_containers/deque/debug/copy61_neg.cc: New.
* testsuite/23_containers/deque/debug/copy71_neg.cc: New.
* testsuite/23_containers/deque/debug/copy72_neg.cc: New.
* testsuite/23_containers/deque/debug/copy_backward11_neg.cc: New.
* testsuite/23_containers/deque/debug/copy_backward12_neg.cc: New.
* testsuite/23_containers/deque/debug/copy_backward21_neg.cc: New.
* testsuite/23_containers/deque/debug/copy_backward22_neg.cc: New.
* testsuite/23_containers/deque/debug/fill_neg.cc: New.
* testsuite/23_containers/deque/debug/move11_neg.cc: New.
* testsuite/23_containers/deque/debug/move12_neg.cc: New.
* testsuite/23_containers/deque/debug/move21_neg.cc: New.
* testsuite/23_containers/deque/debug/move22_neg.cc: New.
* testsuite/23_containers/deque/debug/move_backward11_neg.cc: New.
* testsuite/23_containers/deque/debug/move_backward12_neg.cc: New.
* testsuite/23_containers/deque/debug/move_backward21_neg.cc: New.
* testsuite/23_containers/deque/debug/move_backward22_neg.cc: New.
* testsuite/23_containers/deque/fill.cc: New.
* testsuite/23_containers/deque/move.cc: New.
* testsuite/23_containers/deque/move_backward.cc: New.
* testsuite/25_algorithms/equal/debug/deque10_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque11_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque12_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque13_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque14_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque15_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque16_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque1_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque2_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque3_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque4_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque5_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque6_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque7_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque8_neg.cc: New.
* testsuite/25_algorithms/equal/debug/deque9_neg.cc: New.
* testsuite/25_algorithms/equal/deque/equal.cc: New.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: deque_algos.patch
Type: text/x-patch
Size: 138987 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20190619/4893fec3/attachment.bin>
More information about the Gcc-patches
mailing list