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 3: / Line 3: @@
 {{dcl begin}}
 {{dcl header|algorithm}}
-{{dcl rev multi|num=1
+{{dcl|num=1|notes={{mark constexpr since c++20}}|
-|dcl1=
 template< class BidirIt, class OutputIt >
-OutputIt reverse_copy( BidirIt first, BidirIt last, OutputIt d_first );
+OutputIt reverse_copy( BidirIt first, BidirIt last,
-|since2=c++20|dcl2=
+                       OutputIt d_first );
-template< class BidirIt, class OutputIt >
-constexpr OutputIt reverse_copy( BidirIt first, BidirIt last, OutputIt d_first );
 }}
 {{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 );
+                         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|1=*(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===
@@ Line 40: / 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}}
-===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}}.
 ===Possible implementation===
@@ Line 60: / Line 54: @@
 }
 }}
+===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===
@@ Line 70: / Line 67: @@
 int main()
 {
-     auto print = [](std::vector<int> const& v)
+     auto print = [](const std::vector<int>& v)
      {
          for (const auto& value : v)
              std::cout << value << ' ';
-         std::cout << '\t';
+         std::cout << '\n';
      };
-     std::vector<int> v({1,2,3});
+     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));
@@ Line 87: / Line 84: @@
      print(destination);
 }
-|output=1 2 3   3 2 1   1 2 3
+|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===

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