Difference between revisions of "cpp/algorithm/reverse copy"

Latest revision as of 19:19, 27 March 2024

Defined in header `<algorithm>`
template< class BidirIt, class OutputIt > OutputIt reverse_copy( BidirIt first, BidirIt last, OutputIt d_first );	(1)	(constexpr since C++20)
template< class ExecutionPolicy, class BidirIt, class ForwardIt > ForwardIt reverse_copy( ExecutionPolicy&& policy, BidirIt first, BidirIt last, ForwardIt d_first );	(2)	(since C++17)

1) Given

N

as std::distance(first, last). Copies the elements from the range [first, last) (source range) to another range of

N

elements beginning at d_first (destination range) in such a way that the elements in the destination range are in reverse order.

Behaves as if by executing the assignment *(d_first + N - 1 - i) = *(first + i)^[1] once for each integer i in [0, N).

If source and destination ranges overlap, the behavior is undefined.

2) Same as (1), but executed according to policy.

This overload participates in overload resolution only if

std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> is true.	(until C++20)
std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> is true.	(since C++20)

first, last	-	the range of elements to copy
d_first	-	the beginning of the destination range
Type requirements
- `BidirIt` must meet the requirements of LegacyBidirectionalIterator.
- `OutputIt` must meet the requirements of LegacyOutputIterator.
- `ForwardIt` must meet the requirements of LegacyForwardIterator.

[edit] Return value

Output iterator to the element past the last element copied.

[edit] Complexity

Exactly $\scriptsize N$ $N$ assignments.

[edit] Exceptions

The overload with a template parameter named ExecutionPolicy reports errors as follows:

If execution of a function invoked as part of the algorithm throws an exception and ExecutionPolicy is one of the standard policies, std::terminate is called. For any other ExecutionPolicy, the behavior is implementation-defined.
If the algorithm fails to allocate memory, std::bad_alloc is thrown.

[edit] Possible implementation

See also the implementations in libstdc++, libc++, and MSVC STL.

template<class BidirIt, class OutputIt>
constexpr // since C++20
OutputIt reverse_copy(BidirIt first, BidirIt last, OutputIt d_first)
{
    for (; first != last; ++d_first)
        *d_first = *(--last);
    return d_first;
}

[edit] Notes

Implementations (e.g. MSVC STL) may enable vectorization when the both iterator types satisfy LegacyContiguousIterator and have the same value type, and the value type is TriviallyCopyable.

[edit] Example

Run this code

#include <algorithm>
#include <iostream>
#include <vector>
 
int main()
{
    auto print = [](const std::vector<int>& v)
    {
        for (const auto& value : v)
            std::cout << value << ' ';
        std::cout << '\n';
    };
 
    std::vector<int> v{1, 2, 3};
    print(v);
 
    std::vector<int> destination(3);
    std::reverse_copy(std::begin(v), std::end(v), std::begin(destination));
    print(destination);
 
    std::reverse_copy(std::rbegin(v), std::rend(v), std::begin(destination));
    print(destination);
}

Output:

1 2 3 
3 2 1 
1 2 3

[edit] Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR	Applied to	Behavior as published	Correct behavior
LWG 2074	C++98	for each i, the assignment was (d_first + N - i) = (first + i)^[1]	corrected to (d_first + N - 1 - i) = (first + i)^[1]
LWG 2150	C++98	only one element was required to be assigned	corrected the requirement

↑ ^1.0 ^1.1 ^1.2 LegacyOutputIterator is not required to support binary + and -. The usages of + and - here are exposition-only: the actual computation does not need to use them.

[edit] See also

reverse	reverses the order of elements in a range (function template) [edit]
ranges::reverse_copy (C++20)	creates a copy of a range that is reversed (niebloid)[edit]

[plusminus-1] 1.0 ^1.1 ^1.2 LegacyOutputIterator is not required to support binary + and -. The usages of + and - here are exposition-only: the actual computation does not need to use them.

[1]

@@ Line 2: / Line 2: @@
 {{cpp/algorithm/navbar}}
 {{dcl begin}}
-{{dcl header | algorithm}}
+{{dcl header|algorithm}}
-{{dcl rev multi | num=1 | since1= | until1=c++20 |dcl1=
+{{dcl|num=1|notes={{mark constexpr since c++20}}|
 template< class BidirIt, class OutputIt >
-OutputIt reverse_copy( BidirIt first, BidirIt last, OutputIt d_first );
+OutputIt reverse_copy( BidirIt first, BidirIt last,
-|dcl2=
+                       OutputIt d_first );
-template< class BidirIt, class OutputIt >
-constexpr OutputIt reverse_copy( BidirIt first, BidirIt last, OutputIt d_first );
 }}
-{{dcl | since=c++17 | until= | num=2 |1=
+{{dcl|num=2|since=c++17|
 template< class ExecutionPolicy, class BidirIt, class ForwardIt >
-ForwardIt reverse_copy( ExecutionPolicy&& policy, BidirIt first, BidirIt last, ForwardIt d_first );
+ForwardIt reverse_copy( ExecutionPolicy&& policy,
+                        BidirIt first, BidirIt last,
+                        ForwardIt d_first );
 }}
 {{dcl end}}
-@1@ Copies the elements from the range {{tt|[first, last)}} to another range beginning at {{tt|d_first}} in such a way that the elements in the new range are in reverse order.
+@1@ Given {{mathjax-or|\(\scriptsize N\)|N}} as {{c|std::distance(first, last)}}. Copies the elements from the range {{range|first|last}} (source range) to another range of {{mathjax-or|\(\scriptsize N\)|N}} elements beginning at {{c|d_first}} (destination range) in such a way that the elements in the destination range are in reverse order.
+@@ Behaves as if by executing the assignment {{c|1=*(d_first + N - 1 - i) = *(first + i)}}<ref name="plusminus">{{named req|OutputIterator}} is not required to support binary {{tt|+}} and {{tt|-}}. The usages of {{tt|+}} and {{tt|-}} here are exposition-only: the actual computation does not need to use them.</ref> once for each integer {{c|i}} in {{range|0|N}}.
+@@ If source and destination ranges overlap, the behavior is undefined.
-@@Behaves as if by executing the assignment {{c|*(d_first + (last - first) - 1 - i) {{=}} *(first + i)}} once for each non-negative {{tt|i < (last - first)}}
+@2@ Same as {{v|1}}, but executed according to {{c|policy}}.
+@@ {{cpp/algorithm/parallel overload precondition}}
-@@If the source and destination ranges (that is, {{tt|[first, last)}} and {{tt|[d_first, d_first+(last-first))}} respectively) overlap, the behavior is undefined.
-@2@ Same as {{v|1}}, but executed according to {{tt|policy}}. {{cpp/algorithm/parallel overload precondition}}
 ===Parameters===
 {{par begin}}
-{{par | first, last | the range of elements to copy}}
+{{par|first, last|the range of elements to copy}}
-{{par | d_first | the beginning of the destination range}}
+{{par|d_first|the beginning of the destination range}}
 {{par hreq}}
-{{par req named | BidirIt | BidirectionalIterator}}
+{{par req named|BidirIt|BidirectionalIterator}}
-{{par req named | OutputIt | OutputIterator}}
+{{par req named|OutputIt|OutputIterator}}
-{{par req named | ForwardIt | ForwardIterator}}
+{{par req named|ForwardIt|ForwardIterator}}
 {{par end}}
@@ Line 37: / Line 37: @@
 ===Complexity===
-Exactly {{tt|last - first}} assignments.
+Exactly {{mathjax-or|\(\scriptsize N\)|N}} assignments.
 ===Exceptions===
-{{cpp/algorithm/parallel_exceptions_reporting_behavior|singular=yes}}
+{{cpp/algorithm/parallel exceptions reporting behavior|singular=yes}}
 ===Possible implementation===
-See also the implementations in [https://github.com/gcc-mirror/gcc/blob/d9375e490072d1aae73a93949aa158fcd2a27018/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1207 libstdc++] and [https://github.com/llvm-mirror/libcxx/blob/a12cb9d211019d99b5875b6d8034617cbc24c2cc/include/algorithm#L2298 libc++].
+See also the implementations in [https://github.com/gcc-mirror/gcc/blob/14d8a5ae472ca5743016f37da2dd4770d83dea21/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1170-L1190 libstdc++], [https://github.com/llvm/llvm-project/tree/134723edd5bf06ff6ec8aca7b87c56e5bd70ccae/libcxx/include/__algorithm/reverse_copy.h libc++], and [https://github.com/microsoft/STL/blob/472161105d596192194d4715ccad307c6c163b4a/stl/inc/algorithm#L4184-L4229 MSVC STL].
-{{eq fun | 1=
+{{eq fun|1=
 template<class BidirIt, class OutputIt>
+constexpr // since C++20
 OutputIt reverse_copy(BidirIt first, BidirIt last, OutputIt d_first)
 {
-     while (first != last) {
+     for (; first != last; ++d_first)
-         *(d_first++) = *(--last);
+         *d_first = *(--last);
-    }
      return d_first;
 }
 }}
+===Notes===
+Implementations (e.g. [https://github.com/microsoft/STL/blob/main/stl/src/vector_algorithms.cpp MSVC STL]) may enable vectorization when the both iterator types satisfy {{named req|ContiguousIterator}} and have the same value type, and the value type is {{named req|TriviallyCopyable}}.
 ===Example===
 {{example
- |
+|code=
- | code=
+#include <algorithm>
+#include <iostream>
 #include <vector>
-#include <iostream>
-#include <algorithm>
 int main()
 {
-     std::vector<int> v({1,2,3});
+     auto print = [](const std::vector<int>& v)
-     for (const auto& value : v) {
+     {
-        std::cout << value << " ";
+        for (const auto& value : v)
-    }
+            std::cout << value << ' ';
-    std::cout << '\n';
+        std::cout << '\n';
+    };
+    std::vector<int> v{1, 2, 3};
+    print(v);
      std::vector<int> destination(3);
      std::reverse_copy(std::begin(v), std::end(v), std::begin(destination));
-     for (const auto& value : destination) {
+     print(destination);
-        std::cout << value << " ";
-     }
+     std::reverse_copy(std::rbegin(v), std::rend(v), std::begin(destination));
-     std::cout << '\n';
+    print(destination);
 }
+|output=
- | output=
 2 3
 2 1
+2 3
 }}
+===Defect reports===
+{{dr list begin}}
+{{dr list item|wg=lwg|dr=2074|std=C++98|before=for each {{c|i}}, the assignment was<br>{{c|1=*(d_first + N - i) = *(first + i)}}<ref name="plusminus" />|after=corrected to<br>{{c|1=*(d_first + N - 1 - i) = *(first + i)}}<ref name="plusminus" />}}
+{{dr list item|wg=lwg|dr=2150|std=C++98|before=only one element was required to be assigned|after=corrected the requirement}}
+{{dr list end}}
+<references/>
 ===See also===
 {{dsc begin}}
-{{dsc inc | cpp/algorithm/dsc reverse}}
+{{dsc inc|cpp/algorithm/dsc reverse}}
+{{dsc inc|cpp/algorithm/ranges/dsc reverse_copy}}
 {{dsc end}}
 {{langlinks|de|es|fr|it|ja|pt|ru|zh}}

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros (C++20)
Language support library
Concepts library (C++20)
Metaprogramming library (C++11)
Diagnostics library
General utilities library
Strings library
Containers library
Iterators library
Ranges library (C++20)
Algorithms library
Numerics library
Localizations library
Input/output library
Filesystem library (C++17)
Regular expressions library (C++11)
Concurrency support library (C++11)
Execution support library (C++26)
Technical specifications
Symbols index
External libraries

cppreference.com

Namespaces

Variants

Views

Actions