Difference between revisions of "cpp/algorithm/reverse"

Latest revision as of 18:58, 27 March 2024

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

1) Reverses the order of the elements in the range [first, last).

Behaves as if applying std::iter_swap to every pair of iterators first + i and (last - i) - 1 for each integer i in [0, std::distance(first, last) / 2).

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)

If *first is not Swappable(until C++20)BidirIt is not ValueSwappable(since C++20), the behavior is undefined.

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>
constexpr // since C++20
void reverse(BidirIt first, BidirIt last)
{
    using iter_cat = typename std::iterator_traits<BidirIt>::iterator_category;
 
    // Tag dispatch, e.g. calling reverse_impl(first, last, iter_cat()),
    // can be used in C++14 and earlier modes.
    if constexpr (std::is_base_of_v<std::random_access_iterator_tag, iter_cat>)
    {
        if (first == last)
            return;
 
        for (--last; first < last; (void)++first, --last)
            std::iter_swap(first, last);
    }
    else
        while (first != last && first != --last)
            std::iter_swap(first++, last);
}

[edit] Notes

Implementations (e.g. MSVC STL) may enable vectorization when the iterator type satisfies LegacyContiguousIterator and swapping its value type calls neither non-trivial special member function nor ADL-found swap.

[edit] Example

Run this code

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
void println(auto rem, auto const& v)
{
    for (std::cout << rem; auto e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}
 
int main()
{
    std::vector<int> v {1, 2, 3};
    std::reverse(v.begin(), v.end());
    println("after reverse, v = ", v);
 
    int a[] = {4, 5, 6, 7};
    std::reverse(std::begin(a), std::end(a));
    println("after reverse, a = ", a);
}

Output:

after reverse, v = 3 2 1
after reverse, a = 7 6 5 4

[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 223	C++98	std::swap was applied to each pair of iterators	applies std::iter_swap instead
LWG 2039	C++98	std::iter_swap was also applied when i equals std::distance(first, last) / 2	not applied

[edit] See also

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

@@ Line 1: / Line 1: @@
 {{cpp/title|reverse}}
 {{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 BidirIt >
 void reverse( BidirIt first, BidirIt last );
 }}
-{{ddcl list end}}
+{{dcl|num=2|since=c++17|
+template< class ExecutionPolicy, class BidirIt >
+void reverse( ExecutionPolicy&& policy, BidirIt first, BidirIt last );
+}}
+{{dcl end}}
+@1@ Reverses the order of the elements in the range {{range|first|last}}.
+@@ Behaves as if applying {{lc|std::iter_swap}} to every pair of iterators {{c|first + i}} and {{c|(last - i) - 1}} for each integer {{c|i}} in {{range|0|std::distance(first, last) / 2}}.
+@2@ Same as {{v|1}}, but executed according to {{c|policy}}.
+@@ {{cpp/algorithm/parallel overload precondition}}
-Reverses the order of the elements in the range {{tt|[first, last)}}.
+If {{rev inl|until=c++20|{{c|*first}} is not {{named req|Swappable}}}}{{rev inl|since=c++20|{{tt|BidirIt}} is not {{named req|ValueSwappable}}}}, the behavior is undefined.
 ===Parameters===
-{{param list begin}}
+{{par begin}}
-{{param list item | first, last | the range of elements to reverse}}
+{{par|first, last|the range of elements to reverse}}
-{{param list end}}
+{{par exec pol}}
+{{par hreq}}
+{{par req named|BidirIt|BidirectionalIterator}}
+{{par end}}
-===Return value===
+===Complexity===
-(none)
+Exactly {{c|std::distance(first, last) / 2}} swaps.
+===Exceptions===
+{{cpp/algorithm/parallel exceptions reporting behavior|singular=yes}}
 ===Possible implementation===
-{{eq fun | 1=
+See also the implementations in [https://github.com/gcc-mirror/gcc/blob/14d8a5ae472ca5743016f37da2dd4770d83dea21/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1087-L1152 libstdc++], [https://github.com/llvm/llvm-project/blob/6adbc83ee9e46b476e0f75d5671c3a21f675a936/libcxx/include/__algorithm/reverse.h libc++], and [https://github.com/microsoft/STL/blob/472161105d596192194d4715ccad307c6c163b4a/stl/inc/xutility#L5335-L5370 MSVC STL].
+{{eq fun|1=
 template<class BidirIt>
+constexpr // since C++20
 void reverse(BidirIt first, BidirIt last)
 {
-     while ((first != last) && (first != --last)) {
+     using iter_cat = typename std::iterator_traits<BidirIt>::iterator_category;
-        std::swap(*first++, *last);
+    // Tag dispatch, e.g. calling reverse_impl(first, last, iter_cat()),
+    // can be used in C++14 and earlier modes.
+    if constexpr (std::is_base_of_v<std::random_access_iterator_tag, iter_cat>)
+    {
+        if (first == last)
+            return;
+        for (--last; first < last; (void)++first, --last)
+            std::iter_swap(first, last);
      }
+    else
+        while (first != last && first != --last)
+            std::iter_swap(first++, last);
 }
 }}
+===Notes===
+{{cpp/algorithm/notes swap vectorization}}
 ===Example===
 {{example
- |
+|
- | code=
+|code=
-#include <vector>
-#include <iostream>
 #include <algorithm>
+#include <iostream>
-int main(int argc, char** argv)
+#include <iterator>
+#include <vector>
+void println(auto rem, auto const& v)
 {
-     std::vector<int> v({1,2,3});
+     for (std::cout << rem; auto e : v)
-    std::reverse(std::begin(v), std::end(v));
+        std::cout << e << ' ';
-     std::cout << v[0] << v[1] << v[2] << '\n';
+     std::cout << '\n';
+}
+int main()
+{
+    std::vector<int> v {1, 2, 3};
+    std::reverse(v.begin(), v.end());
+    println("after reverse, v = ", v);
      int a[] = {4, 5, 6, 7};
-     std::reverse(&a[0], &a[4]);
+     std::reverse(std::begin(a), std::end(a));
-     std::cout << a[0] << a[1] << a[2] << a[3] << '\n';
+     println("after reverse, a = ", a);
 }
- | output=
+|output=
+after reverse, v = 3 2 1
+after reverse, a = 7 6 5 4
 }}
-===Complexity===
+===Defect reports===
+{{dr list begin}}
-linear in the distance between {{tt|first}} and {{tt|last}}
+{{dr list item|wg=lwg|dr=223|std=C++98|before={{lc|std::swap}} was applied to each pair of iterators|after=applies {{lc|std::iter_swap}} instead}}
+{{dr list item|wg=lwg|dr=2039|std=C++98|before={{lc|std::iter_swap}} was also applied when {{c|i}}<br>equals {{c|std::distance(first, last) / 2}}|after=not applied}}
+{{dr list end}}
 ===See also===
-{{dcl list begin}}
+{{dsc begin}}
-{{dcl list template | cpp/algorithm/dcl list reverse_copy}}
+{{dsc inc|cpp/algorithm/dsc reverse_copy}}
-{{dcl list end}}
+{{dsc inc|cpp/algorithm/ranges/dsc reverse}}
+{{dsc end}}
-[[es:cpp/algorithm/reverse]]
+{{langlinks|de|es|fr|it|ja|pt|ru|zh}}
-[[ru:cpp/algorithm/reverse]]

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

first, last	-	the range of elements to reverse
policy	-	the execution policy to use. See execution policy for details.
Type requirements
- `BidirIt` must meet the requirements of LegacyBidirectionalIterator.

cppreference.com

Namespaces

Variants

Views

Actions

Difference between revisions of "cpp/algorithm/reverse"

Latest revision as of 18:58, 27 March 2024

Contents

[edit] Parameters

[edit] Complexity

[edit] Exceptions

[edit] Possible implementation

[edit] Notes

[edit] Example

[edit] Defect reports

[edit] See also

Navigation

Toolbox