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 1: / Line 1: @@
 {{cpp/title|reverse_copy}}
-{{cpp/algorithm/sidebar}}
+{{cpp/algorithm/navbar}}
-{{ddcl list begin}}
+{{dcl begin}}
-{{ddcl list header | algorithm}}
+{{dcl header|algorithm}}
-{{ddcl list item |
+{{dcl|num=1|notes={{mark constexpr since c++20}}|
-template< class BidirectionalIterator, class OutputIterator >
+template< class BidirIt, class OutputIt >
-OutputIterator reverse_copy( BidirectionalIterator first, BidirectionalIterator last, OutputIterator d_first );
+OutputIt reverse_copy( BidirIt first, BidirIt last,
+                       OutputIt d_first );
 }}
-{{ddcl list end}}
+{{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 );
+}}
+{{dcl end}}
+@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.
-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.
+@2@ Same as {{v|1}}, but executed according to {{c|policy}}.
+@@ {{cpp/algorithm/parallel overload precondition}}
-<!-- ======== -->
 ===Parameters===
-{{param list begin}}
+{{par begin}}
-{{param list item | first, last | the range of elements to copy}}
+{{par|first, last|the range of elements to copy}}
-{{param list item | d_first | the beginning of the destination range}}
+{{par|d_first|the beginning of the destination range}}
-{{param list end}}
+{{par hreq}}
+{{par req named|BidirIt|BidirectionalIterator}}
+{{par req named|OutputIt|OutputIterator}}
+{{par req named|ForwardIt|ForwardIterator}}
+{{par end}}
-<!-- ======== -->
 ===Return value===
+Output iterator to the element past the last element copied.
-output iterator to the element past the last element copied.
+===Complexity===
+Exactly {{mathjax-or|\(\scriptsize N\)|N}} assignments.
-<!-- ======== -->
+===Exceptions===
-===Equivalent function===
+{{cpp/algorithm/parallel exceptions reporting behavior|singular=yes}}
-{{eq fun cpp | 1=
+===Possible implementation===
+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=
+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;
+}
 }}
-<!-- ======== -->
+===Notes===
-===Example===
+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 cpp
- |
- | code=
- | output=
+===Example===
+{{example
+|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=
+2 3
+2 1
+2 3
 }}
-<!-- ======== -->
+===Defect reports===
-===Complexity===
+{{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/>
-linear in the distance between {{tt|first}} and {{tt|last}}
-<!-- ======== -->
 ===See also===
-{{dcl list begin}}
+{{dsc begin}}
-{{dcl list template | cpp/algorithm/dcl list reverse}}
+{{dsc inc|cpp/algorithm/dsc reverse}}
-{{dcl list end}}
+{{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