std::ranges::fold_right_last
Von de.cppreference.net
| Definiert in Header <algorithm>
|
||
| Aufrufsignatur |
||
template< std::bidirectional_iterator I, std::sentinel_for<I> S,
/*indirectly-binary-right-foldable*/<std::iter_value_t<I>, I> F >
requires std::constructible_from<
std::iter_value_t<I>, std::iter_reference_t<I>>
constexpr auto
fold_right_last( I first, S last, F f );
|
(1) | (seit C++23) |
template< ranges::bidirectional_range R,
/*indirectly-binary-right-foldable*/<
ranges::range_value_t<R>, ranges::iterator_t<R>> F >
requires std::constructible_from<
ranges::range_value_t<R>, ranges::range_reference_t<R>>
constexpr auto
fold_right_last( R&& r, F f );
|
(2) | (seit C++23) |
| Helferkonzepte |
||
template< class F, class T, class I >
concept /*indirectly-binary-left-foldable*/ = /* see description */;
|
(3) | (nur zur Veranschaulichung*) |
template< class F, class T, class I >
concept /*indirectly-binary-right-foldable*/ = /* see description */;
|
(4) | (nur zur Veranschaulichung*) |
Rechts-faltung der Elemente des gegebenen Bereichs, d. h. gibt das Ergebnis der Auswertung des Kettenausdrucks zurück:f(x1, f(x2, ...f(xn-1, xn))), wobei x1, x2, ..., xn Elemente des Bereichs sind.
Informell verhält sich ranges::fold_right_last wie ranges::fold_left(views::reverse(r), *--last, /*flipped*/(f)) (unter der Annahme, dass der Bereich nicht leer ist).
Das Verhalten ist undefiniert, wenn [first, last) kein gültiger Bereich ist.
1) Der Bereich ist
[first, last). Gegeben U als decltype(ranges::fold_right(first, last, std::iter_value_t<I>(*first), f)), äquivalent zu:
if (first == last)
return std::optional<U>();
I tail = ranges::prev(ranges::next(first, std::move(last)));
return std::optional<U>(std::in_place, ranges::fold_right(std::move(first), tail,
std::iter_value_t<I>(*tail), std::move(f)));
2) Gleich wie (1), außer dass
r als Bereich verwendet wird, als ob ranges::begin(r) als first und ranges::end(r) als last verwendet würde.3) Äquivalent zu:
| Helferkonzepte |
||
template< class F, class T, class I, class U >
concept /*indirectly-binary-left-foldable-impl*/ =
std::movable<T> &&
std::movable<U> &&
std::convertible_to<T, U> &&
std::invocable<F&, U, std::iter_reference_t<I>> &&
std::assignable_from<U&,
std::invoke_result_t<F&, U, std::iter_reference_t<I>>>;
|
(3A) | (nur zur Veranschaulichung*) |
template< class F, class T, class I >
concept /*indirectly-binary-left-foldable*/ =
std::copy_constructible<F> &&
std::indirectly_readable<I> &&
std::invocable<F&, T, std::iter_reference_t<I>> &&
std::convertible_to<std::invoke_result_t<F&, T, std::iter_reference_t<I>>,
std::decay_t<std::invoke_result_t<F&, T, std::iter_reference_t<I>>>> &&
/*indirectly-binary-left-foldable-impl*/<F, T, I,
std::decay_t<std::invoke_result_t<F&, T, std::iter_reference_t<I>>>>;
|
(3B) | (nur zur Veranschaulichung*) |
4) Äquivalent zu:
| Helferkonzepte |
||
template< class F, class T, class I >
concept /*indirectly-binary-right-foldable*/ =
/*indirectly-binary-left-foldable*/</*flipped*/<F>, T, I>;
|
(4A) | (nur zur Veranschaulichung*) |
| Helfer-Klassenvorlagen |
||
template< class F >
class /*flipped*/
{
F f; // exposition only
public:
template< class T, class U >
requires std::invocable<F&, U, T>
std::invoke_result_t<F&, U, T> operator()( T&&, U&& );
};
|
(4B) | (nur zur Veranschaulichung*) |
Die auf dieser Seite beschriebenen funktionsähnlichen Entitäten sind Algorithmus-Funktionsobjekte (informell als Niebloide bezeichnet), d. h.:
- Beim Aufruf eines von ihnen können keine expliziten Vorlagenargumentlisten angegeben werden.
- Keines von ihnen ist für argumentabhängige Namenssuche sichtbar.
- Wenn eines von ihnen durch normale unqualifizierte Namenssuche als Name links vom Funktionsaufrufoperator gefunden wird, wird argumentabhängige Namenssuche unterdrückt.
Parameter
| first, last | - | das Iterator-Sentinel-Paar, das den Bereich der zu faltenden Elemente definiert |
| r | - | der Bereich der zu faltenden Elemente |
| f | - | das binäre Funktionsobjekt |
Rückgabewert
Ein Objekt vom Typ std::optional<U>, das das Ergebnis der Rechts-faltung des gegebenen Bereichs über f enthält.
Wenn der Bereich leer ist, wird std::optional<U>() zurückgegeben.
Mögliche Implementierungen
struct fold_right_last_fn
{
template<std::bidirectional_iterator I, std::sentinel_for<I> S,
/*indirectly-binary-right-foldable*/<std::iter_value_t<I>, I> F>
requires
std::constructible_from<std::iter_value_t<I>, std::iter_reference_t<I>>
constexpr auto operator()(I first, S last, F f) const
{
using U = decltype(
ranges::fold_right(first, last, std::iter_value_t<I>(*first), f));
if (first == last)
return std::optional<U>();
I tail = ranges::prev(ranges::next(first, std::move(last)));
return std::optional<U>(std::in_place,
ranges::fold_right(std::move(first), tail, std::iter_value_t<I>(*tail),
std::move(f)));
}
template<ranges::bidirectional_range R,
/*indirectly_binary_right_foldable*/<
ranges::range_value_t<R>, ranges::iterator_t<R>> F>
requires
std::constructible_from<ranges::range_value_t<R>, ranges::range_reference_t<R>>
constexpr auto operator()(R&& r, F f) const
{
return (*this)(ranges::begin(r), ranges::end(r), std::ref(f));
}
};
inline constexpr fold_right_last_fn fold_right_last;
|
Komplexität
Genau ranges::distance(first, last) Anwendungen des Funktionsobjekts f.
Hinweise
Die folgende Tabelle vergleicht alle eingeschränkten Faltalgorithmen:
| Faltfunktionsvorlage | Startet bei | Anfangswert | Rückgabetyp |
|---|---|---|---|
ranges::fold_left |
links | init |
U
|
ranges::fold_left_first |
links | erstes Element | std::optional<U>
|
ranges::fold_right |
rechts | init |
U
|
ranges::fold_right_last |
rechts | letztes Element | std::optional<U>
|
ranges::fold_left_with_iter |
links | init |
(1) (2) wobei |
ranges::fold_left_first_with_iter |
links | erstes Element |
(1) (2) wobei |
| Feature-Test-Makro | Wert | Std | Feature |
|---|---|---|---|
__cpp_lib_ranges_fold |
202207L |
(C++23) | std::ranges Faltalgorithmen
|
Beispiel
Dieses Programm ausführen
#include <algorithm>
#include <functional>
#include <iostream>
#include <ranges>
#include <utility>
#include <vector>
int main()
{
auto v = {1, 2, 3, 4, 5, 6, 7, 8};
std::vector<std::string> vs {"A", "B", "C", "D"};
auto r1 = std::ranges::fold_right_last(v.begin(), v.end(), std::plus<>()); // (1)
std::cout << "*r1: " << *r1 << '\n';
auto r2 = std::ranges::fold_right_last(vs, std::plus<>()); // (2)
std::cout << "*r2: " << *r2 << '\n';
// Use a program defined function object (lambda-expression):
auto r3 = std::ranges::fold_right_last(v, [](int x, int y) { return x + y + 99; });
std::cout << "*r3: " << *r3 << '\n';
// Get the product of the std::pair::second of all pairs in the vector:
std::vector<std::pair<char, float>> data {{'A', 3.f}, {'B', 3.5f}, {'C', 4.f}};
auto r4 = std::ranges::fold_right_last
(
data | std::ranges::views::values, std::multiplies<>()
);
std::cout << "*r4: " << *r4 << '\n';
}
Ausgabe:
*r1: 36
*r2: ABCD
*r3: 729
*r4: 42
Referenzen
- C++23-Standard (ISO/IEC 14882:2024):
- 27.6.18 Fold [alg.fold]
Siehe auch
(C++23) |
faltet einen Bereich von Elementen von rechts (Algorithmus-Funktionsobjekt) |
(C++23) |
faltet einen Bereich von Elementen von links (Algorithmus-Funktionsobjekt) |
(C++23) |
faltet einen Bereich von Elementen von links unter Verwendung des ersten Elements als Anfangswert (Algorithmus-Funktionsobjekt) |
(C++23) |
faltet einen Bereich von Elementen von links und gibt ein pair (Iterator, Wert) zurück (Algorithmus-Funktionsobjekt) |
| faltet einen Bereich von Elementen von links unter Verwendung des ersten Elements als Anfangswert und gibt ein pair (Iterator, optional) zurück (Algorithmus-Funktionsobjekt) | |
| summiert oder faltet einen Bereich von Elementen (Funktionsvorlage) | |
(C++17) |
ähnlich std::accumulate, außer in beliebiger Reihenfolge (Funktionsvorlage) |