Skip to content

Latest commit

 

History

History
488 lines (346 loc) · 17.7 KB

File metadata and controls

488 lines (346 loc) · 17.7 KB

🔝 Retour au Sommaire

15.6.1 — Views et lazy evaluation

Chapitre 15 — Algorithmes de la STL


Introduction

Les views sont le composant le plus transformateur de la bibliothèque Ranges. Une view est un adaptateur léger et paresseux qui décrit une opération sur une séquence — filtrage, transformation, troncature, inversion — sans l'exécuter. Aucune donnée n'est copiée, aucun conteneur intermédiaire n'est alloué. Le calcul n'a lieu que lorsqu'on itère sur la view, élément par élément, à la demande.

Ce modèle d'évaluation paresseuse (lazy evaluation) est familier aux développeurs Python (générateurs), Rust (itérateurs paresseux) ou Java (streams). En C++, il était possible avant C++20 via des librairies tierces (Range-v3, Boost.Range), mais la standardisation l'a rendu accessible sans dépendance externe.

#include <ranges>
#include <vector>
#include <string>

Toutes les views se trouvent dans le namespace std::views (alias de std::ranges::views).


Principe fondamental : décrire, pas exécuter

Comparons l'approche classique (eager) avec l'approche views (lazy) pour filtrer les nombres pairs d'un vector :

std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// Approche eager (classique) : allocation + copie
std::vector<int> evens;  
std::copy_if(v.begin(), v.end(), std::back_inserter(evens),  
    [](int x) { return x % 2 == 0; });
// evens est un NOUVEAU vector contenant {2, 4, 6, 8, 10}
// Coût : allocation mémoire + copie de 5 éléments

// Approche lazy (view) : zéro allocation
auto evens_view = std::views::filter(v, [](int x) { return x % 2 == 0; });
// evens_view ne contient AUCUNE donnée
// C'est un objet léger qui sait comment filtrer v à la demande

La view evens_view est un petit objet (typiquement quelques pointeurs et la lambda) qui stocke une référence vers v et le prédicat de filtrage. Aucun élément n'a été examiné, aucun filtrage n'a eu lieu. Le travail se fait uniquement quand on itère :

for (int x : evens_view) {
    std::print("{} ", x);
}
// Affiche : 2 4 6 8 10
// Chaque élément est filtré à la volée pendant l'itération

À chaque avancement de l'itérateur, la view consulte l'élément suivant de v, applique le prédicat, et saute les éléments qui ne passent pas le filtre. Le coût est exactement le même qu'une boucle for écrite à la main avec un if — mais avec une abstraction composable.


Propriétés des views

Toutes les views partagent un ensemble de propriétés garanties par le standard :

Coût de construction O(1) — Créer une view est une opération à temps constant. Pas de parcours, pas de copie, pas d'allocation. La view stocke uniquement des références et des paramètres.

Pas de propriété des données — Une view ne possède pas les données qu'elle décrit. Elle référence un range sous-jacent (le conteneur original ou une autre view). La durée de vie du range source doit dépasser celle de la view.

Copiable et déplaçable en O(1) — Copier une view copie quelques pointeurs et paramètres, pas les données.

Itérable — Chaque view fournit begin() et end(), ce qui la rend utilisable dans une range-based for loop et compatible avec tous les algorithmes std::ranges.

Non-propriétaire signifie non-invalidant — Une view ne modifie pas le conteneur source. Mais si le conteneur source est modifié (insertion, suppression), les itérateurs de la view sont invalidés, tout comme le seraient les itérateurs du conteneur lui-même.


Le catalogue des views standard

std::views::filter — Garder selon un prédicat

Produit les éléments pour lesquels le prédicat renvoie true :

std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

auto positives_odd = std::views::filter(v, [](int x) {
    return x % 2 != 0;
});

for (int x : positives_odd) {
    std::print("{} ", x);
}
// 1 3 5 7 9

La catégorie d'itérateur de la view filtrée est au mieux bidirectional (même si le range source est random-access), car le filtre rend impossible le saut en O(1) à une position arbitraire — on ne sait pas combien d'éléments seront sautés sans les parcourir.

Un détail important : filter_view met en cache le résultat de begin() après le premier appel. Cela signifie qu'un premier parcours calcule où commence la séquence filtrée, et les parcours suivants démarrent directement. Cela a une conséquence : si le range source est modifié entre deux itérations, le cache peut devenir incorrect. En pratique, il ne faut pas modifier le conteneur source tant qu'une filter_view est active.

std::views::transform — Projeter chaque élément

Applique une fonction à chaque élément, produisant une séquence de valeurs transformées :

std::vector<int> v = {1, 2, 3, 4, 5};

auto squared = std::views::transform(v, [](int x) { return x * x; });

for (int x : squared) {
    std::print("{} ", x);
}
// 1 4 9 16 25

Contrairement à std::transform (l'algorithme), la view ne produit aucun conteneur de sortie. Les valeurs transformées sont calculées à la volée et n'existent que le temps du déréférencement de l'itérateur.

La transformation peut changer le type :

struct Employee {
    std::string name;
    double salary;
};

std::vector<Employee> team = {
    {"Alice", 75000.0}, {"Bob", 62000.0}, {"Carol", 88000.0}
};

auto names = std::views::transform(team, &Employee::name);

for (const auto& name : names) {
    std::print("{}\n", name);
}
// Alice
// Bob
// Carol

std::views::take — Garder les N premiers

std::vector<int> v = {10, 20, 30, 40, 50, 60, 70};

auto first_three = std::views::take(v, 3);

for (int x : first_three) {
    std::print("{} ", x);
}
// 10 20 30

Si le range source contient moins de N éléments, take produit tous les éléments disponibles sans erreur.

std::views::take_while — Garder tant qu'un prédicat est vrai

std::vector<int> v = {2, 4, 6, 7, 8, 10};

auto leading_evens = std::views::take_while(v, [](int x) {
    return x % 2 == 0;
});

for (int x : leading_evens) {
    std::print("{} ", x);
}
// 2 4 6
// S'arrête dès que 7 (impair) est rencontré

std::views::drop — Ignorer les N premiers

std::vector<int> v = {10, 20, 30, 40, 50, 60, 70};

auto after_three = std::views::drop(v, 3);

for (int x : after_three) {
    std::print("{} ", x);
}
// 40 50 60 70

std::views::drop_while — Ignorer tant qu'un prédicat est vrai

std::vector<int> v = {1, 3, 5, 6, 7, 8};

auto from_first_even = std::views::drop_while(v, [](int x) {
    return x % 2 != 0;
});

for (int x : from_first_even) {
    std::print("{} ", x);
}
// 6 7 8

std::views::reverse — Inverser l'ordre

std::vector<int> v = {1, 2, 3, 4, 5};

for (int x : std::views::reverse(v)) {
    std::print("{} ", x);
}
// 5 4 3 2 1
// v n'est PAS modifié

Requiert un range bidirectional. Contrairement à std::reverse (l'algorithme), la view n'inverse rien en mémoire — elle parcourt simplement les éléments dans l'ordre inverse.

std::views::keys et std::views::values — Accéder aux composants de paires

Pour les ranges de paires (comme std::map) :

std::map<std::string, int> scores = {
    {"Alice", 95}, {"Bob", 82}, {"Carol", 91}
};

for (const auto& name : std::views::keys(scores)) {
    std::print("{} ", name);
}
// Alice Bob Carol

for (int score : std::views::values(scores)) {
    std::print("{} ", score);
}
// 95 82 91

std::views::elements — Accéder au N-ième élément de tuples

Généralisation de keys (index 0) et values (index 1) pour les tuples :

std::vector<std::tuple<std::string, int, double>> data = {
    {"web-01", 72, 4.5},
    {"db-01", 91, 12.3},
    {"cache-01", 23, 1.8}
};

// Extraire les noms (index 0)
for (const auto& name : std::views::elements<0>(data)) {
    std::print("{} ", name);
}
// web-01 db-01 cache-01

std::views::iota — Générer une séquence numérique

std::views::iota est une range factory — elle ne transforme pas un range existant mais en crée un à partir de rien :

// Séquence infinie : 0, 1, 2, 3, ...
for (int x : std::views::iota(0) | std::views::take(5)) {
    std::print("{} ", x);
}
// 0 1 2 3 4

// Séquence bornée : 1, 2, 3, ..., 10
for (int x : std::views::iota(1, 11)) {
    std::print("{} ", x);
}
// 1 2 3 4 5 6 7 8 9 10

iota avec un seul argument produit une séquence infinie. Combinée avec take ou take_while, elle remplace les boucles for (int i = 0; i < n; ++i) par une expression déclarative.

std::views::enumerate (C++23) — Index + valeur

Ajouté en C++23, enumerate produit des paires (index, valeur), comme enumerate() en Python :

std::vector<std::string> names = {"Alice", "Bob", "Carol"};

for (auto [i, name] : std::views::enumerate(names)) {
    std::print("[{}] {}\n", i, name);
}
// [0] Alice
// [1] Bob
// [2] Carol

std::views::zip (C++23) — Combiner plusieurs ranges

zip combine N ranges en un range de tuples, élément par élément :

std::vector<std::string> names = {"Alice", "Bob", "Carol"};  
std::vector<int> scores = {95, 82, 91};  

for (auto [name, score] : std::views::zip(names, scores)) {
    std::print("{}: {}\n", name, score);
}
// Alice: 95
// Bob: 82
// Carol: 91

La séquence s'arrête au plus court des ranges zippés.

std::views::split et std::views::join — Découper et aplatir

split découpe un range selon un délimiteur :

std::string csv = "Alice,Bob,Carol,Dave";

for (auto word : std::views::split(csv, ',')) {
    // word est un sous-range de caractères
    std::print("{}\n", std::string_view(word.begin(), word.end()));
}
// Alice
// Bob
// Carol
// Dave

join fait l'inverse : il aplatit un range de ranges en un seul range :

std::vector<std::vector<int>> matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

for (int x : std::views::join(matrix)) {
    std::print("{} ", x);
}
// 1 2 3 4 5 6 7 8 9

std::views::common — Compatibilité avec le code classique

Certaines views produisent des types d'itérateur et de sentinelle différents (le mécanisme de sentinelle vu en 15.6). Les algorithmes classiques (pré-C++20) exigent que begin et end soient du même type. common_view convertit un range avec sentinelle en un range « classique » compatible :

auto view = std::views::iota(0, 10)
          | std::views::filter([](int x) { return x % 2 == 0; });

// std::accumulate est un algorithme classique, pas un std::ranges::
// Il exige begin() et end() du même type
auto common = std::views::common(view);  
int sum = std::accumulate(common.begin(), common.end(), 0);  
// sum == 20

Matérialiser une view dans un conteneur

Les views sont paresseuses et ne stockent rien. Parfois, on a besoin de matérialiser le résultat dans un vrai conteneur — pour le stocker, le passer à une API qui attend un vector, ou simplement pour figer les données.

Avant C++23 : construction manuelle

auto view = std::views::iota(1, 6)
          | std::views::transform([](int x) { return x * x; });

// Matérialiser dans un vector
std::vector<int> result(view.begin(), view.end());
// result == {1, 4, 9, 16, 25}

// Alternative avec ranges::copy
std::vector<int> result2;  
std::ranges::copy(view, std::back_inserter(result2));  

C++23 : std::ranges::to

C++23 introduit std::ranges::to, une solution élégante et directe :

auto result = std::views::iota(1, 6)
            | std::views::transform([](int x) { return x * x; })
            | std::ranges::to<std::vector>();
// result est un std::vector<int> == {1, 4, 9, 16, 25}

// Fonctionne avec n'importe quel conteneur
auto as_set = std::views::iota(1, 6)
            | std::ranges::to<std::set>();
// as_set == {1, 2, 3, 4, 5}

std::ranges::to est le chaînon manquant qui rend les pipelines de views véritablement fluides de bout en bout.


Views sur des données mutables

Par défaut, transform_view renvoie des valeurs (pas des références). Les éléments ne sont pas modifiables via la view. Mais filter_view renvoie des références vers les éléments originaux — on peut modifier les éléments filtrés :

std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

// Doubler uniquement les nombres pairs, in-place
for (int& x : std::views::filter(v, [](int x) { return x % 2 == 0; })) {
    x *= 2;
}
// v == {1, 4, 3, 8, 5, 12, 7, 16, 9, 20}

C'est une technique puissante pour appliquer des modifications ciblées sans boucle explicite ni indices.


Durée de vie et dangling references

Les views ne possèdent pas les données — elles référencent un range source. Si ce range est détruit avant la view, tout accès produit un comportement indéfini :

// ⚠️ DANGEREUX — le vector temporaire est détruit immédiatement
auto bad_view = std::views::filter(
    std::vector<int>{1, 2, 3, 4, 5},  // temporaire détruit ici
    [](int x) { return x > 2; }
);
// bad_view référence un vector qui n'existe plus

// ✅ CORRECT — le vector survit à la view
std::vector<int> v = {1, 2, 3, 4, 5};  
auto good_view = std::views::filter(v, [](int x) { return x > 2; });  

Certaines views comme std::views::iota ou std::views::single sont des owning views — elles génèrent leurs propres données et n'ont pas ce problème. Mais la majorité des views de transformation/filtrage sont non-propriétaires. La règle : s'assurer que le range source a une durée de vie au moins aussi longue que la view.

Notons que std::ranges::to (C++23) résout implicitement le problème en matérialisant le résultat : une fois converti en vector, le résultat est autonome et ne dépend plus d'aucun range source.


Performance des views

Les views ajoutent-elles un surcoût par rapport à du code écrit à la main ? Dans la grande majorité des cas, non. Le compilateur optimise les views en un code équivalent à une boucle écrite manuellement. Les couches d'abstraction (objets view, itérateurs adaptés) sont éliminées par l'inlining et les optimisations du compilateur.

Un pipeline comme :

auto result = v | std::views::filter([](int x) { return x % 2 == 0; })
                | std::views::transform([](int x) { return x * x; });

produit typiquement un assembleur identique à :

for (int x : v) {
    if (x % 2 == 0) {
        int sq = x * x;
        // utiliser sq
    }
}

Le surcoût potentiel apparaît dans des cas spécifiques : des chaînes très longues de views imbriquées peuvent augmenter la taille des types d'itérateurs (chaque couche de view enveloppe l'itérateur précédent), ce qui peut impacter la taille du code généré et la pression sur le cache d'instructions. En pratique, des chaînes de 3 à 5 views ne posent aucun problème mesurable.

La vraie économie des views est mémoire : là où l'approche eager alloue un conteneur intermédiaire pour chaque étape, les views n'allouent rien. Sur de grands volumes de données, cette différence est significative — non pas en cycles CPU, mais en empreinte mémoire et en pression sur l'allocateur.


Tableau récapitulatif des views

View Namespace Description Catégorie résultante
filter std::views Garder selon prédicat ≤ Bidirectional
transform std::views Projeter chaque élément Préservée
take std::views N premiers éléments Préservée
take_while std::views Tant que prédicat vrai ≤ Bidirectional
drop std::views Ignorer N premiers Préservée
drop_while std::views Ignorer tant que prédicat vrai Préservée
reverse std::views Ordre inversé Bidirectional requis
keys std::views Premier élément des paires Préservée
values std::views Second élément des paires Préservée
elements<N> std::views N-ième élément des tuples Préservée
iota std::views Séquence numérique (factory) Random Access
single std::views Range d'un seul élément (factory) Contiguous
empty std::views Range vide (factory) Contiguous
split std::views Découper selon délimiteur Forward
join std::views Aplatir un range de ranges ≤ Bidirectional
common std::views Uniformiser begin/end Préservée
counted std::views Range depuis itérateur + taille Préservée
enumerate std::views Index + valeur (C++23) Préservée
zip std::views Combiner N ranges (C++23) ≤ Min des sources
chunk std::views Grouper par N (C++23) ≤ Forward
stride std::views Un élément sur N (C++23) Préservée

La colonne « Catégorie résultante » indique la catégorie d'itérateur de la view produite. « Préservée » signifie que la view conserve la catégorie du range source. Certaines views, comme filter, dégradent la catégorie car elles ne peuvent pas garantir l'accès en O(1).


Synthèse

Les views sont des descriptions paresseuses d'opérations sur des séquences. Elles ne possèdent pas de données, ne font aucune allocation, et ne calculent les résultats que quand on itère. C'est un changement de paradigme par rapport à l'approche « eager » de la STL classique : au lieu de matérialiser chaque étape dans un conteneur intermédiaire, on compose des views qui s'empilent et s'exécutent en une seule passe sur les données. Le compilateur optimise ces couches d'abstraction en code équivalent à une boucle écrite à la main. La sous-section suivante (15.6.2) montre comment l'opérateur | rend cette composition naturelle et lisible en permettant d'écrire des pipelines de gauche à droite.

⏭️ Pipelines avec l'opérateur |