PR 90409 Deque fiil/copy/move/copy_backward/move_backward/equal overloads
François Dumont
frs.dumont@gmail.com
Fri Jul 26 05:07:00 GMT 2019
A new version with tests added at the right place, in 25_algorithms,
next to the existing basic ones.
Ok to commit ?
François
On 6/19/19 7:32 PM, François Dumont wrote:
> 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 --------------
A non-text attachment was scrubbed...
Name: deque_algos.patch
Type: text/x-patch
Size: 139762 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20190726/cfa443aa/attachment.bin>
-------------- 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/25_algorithms/copy/deque_iterators/11_neg.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/12_neg.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/2.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/21_neg.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/22_neg.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/31.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/32.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/33.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/41.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/42.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/43.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/51_neg.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/61_neg.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/71_neg.cc: New.
* testsuite/25_algorithms/copy/deque_iterators/72_neg.cc: New.
* testsuite/25_algorithms/copy_backward/deque_iterators/11_neg.cc: New.
* testsuite/25_algorithms/copy_backward/deque_iterators/12_neg.cc: New.
* testsuite/25_algorithms/copy_backward/deque_iterators/2.cc: New.
* testsuite/25_algorithms/copy_backward/deque_iterators/21_neg.cc: New.
* testsuite/25_algorithms/copy_backward/deque_iterators/22_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/1.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/10_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/11_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/12_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/13_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/14_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/15_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/16_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/1_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/2_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/3_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/4_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/5_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/6_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/7_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/8_neg.cc: New.
* testsuite/25_algorithms/equal/deque_iterators/9_neg.cc: New.
* testsuite/25_algorithms/fill/deque_iterators/1.cc: New.
* testsuite/25_algorithms/fill/deque_iterators/1_neg.cc: New.
* testsuite/25_algorithms/move/deque_iterators/11_neg.cc: New.
* testsuite/25_algorithms/move/deque_iterators/12_neg.cc: New.
* testsuite/25_algorithms/move/deque_iterators/2.cc: New.
* testsuite/25_algorithms/move/deque_iterators/21_neg.cc: New.
* testsuite/25_algorithms/move/deque_iterators/22_neg.cc: New.
* testsuite/25_algorithms/move_backward/deque_iterators/11_neg.cc: New.
* testsuite/25_algorithms/move_backward/deque_iterators/12_neg.cc: New.
* testsuite/25_algorithms/move_backward/deque_iterators/2.cc: New.
* testsuite/25_algorithms/move_backward/deque_iterators/21_neg.cc: New.
* testsuite/25_algorithms/move_backward/deque_iterators/22_neg.cc: New.
More information about the Libstdc++
mailing list