Adaptateurs de conteneurs et conteneurs spéciaux

Découvrez stack, queue, priority_queue et les types vocabulaire modernes comme span, string_view et optional. Comprenez quand les adaptateurs simplifient votre code.

Que sont les adaptateurs de conteneurs ?

Les adaptateurs de conteneurs sont des wrappers autour de conteneurs existants qui fournissent une interface restreinte. Ils imposent un mode d'accès spécifique en masquant l'API complète du conteneur :

- std::stack — LIFO (Last In, First Out), basé sur deque par défaut
- std::queue — FIFO (First In, First Out), basé sur deque par défaut
- std::priority_queue — tas max (max-heap), basé sur vector par défaut

Les adaptateurs ne fournissent pas d'itérateurs — vous ne pouvez accéder qu'à l'élément du sommet/de tête. Cette restriction est intentionnelle : elle rend l'intention du code plus claire et empêche les utilisations accidentelles incorrectes.

Stack et Queue en action

Les piles et files sont des structures de données fondamentales utilisées dans l'analyse syntaxique, le BFS/DFS, les systèmes d'annulation et l'ordonnancement de tâches.

stack_queue.cpp

#include <stack>
#include <queue>
#include <string>
#include <iostream>

// Check if parentheses are balanced using a stack
bool is_balanced(const std::string& expr) {
    std::stack<char> stk;
    for (char c : expr) {
        if (c == '(' || c == '[' || c == '{') {
            stk.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (stk.empty()) return false;
            char top = stk.top();
            stk.pop();
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) {
                return false;
            }
        }
    }
    return stk.empty();
}

int main() {
    std::cout << std::boolalpha;
    std::cout << is_balanced("({[]})") << '\n';   // true
    std::cout << is_balanced("({[}])") << '\n';   // false

    // Queue — BFS-style task processing
    std::queue<std::string> tasks;
    tasks.push("compile");
    tasks.push("link");
    tasks.push("run tests");

    while (!tasks.empty()) {
        std::cout << "Processing: " << tasks.front() << '\n';
        tasks.pop();   // removes from front
    }
}

File de priorité (tas)

std::priority_queue est un tas max par défaut — top() retourne le plus grand élément. Pour un tas min, utilisez std::greater comme comparateur.

priority_queue.cpp

#include <queue>
#include <vector>
#include <functional>
#include <iostream>
#include <string>

struct Task {
    int priority;
    std::string name;
};

int main() {
    // Max-heap (default) — largest first
    std::priority_queue<int> max_heap;
    max_heap.push(30);
    max_heap.push(10);
    max_heap.push(50);
    max_heap.push(20);

    while (!max_heap.empty()) {
        std::cout << max_heap.top() << ' ';  // 50 30 20 10
        max_heap.pop();
    }
    std::cout << '\n';

    // Min-heap — smallest first
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
    min_heap.push(30);
    min_heap.push(10);
    min_heap.push(50);
    std::cout << "Min: " << min_heap.top() << '\n';  // 10

    // Custom comparator with lambda
    auto cmp = [](const Task& a, const Task& b) {
        return a.priority < b.priority;  // higher priority first
    };
    std::priority_queue<Task, std::vector<Task>, decltype(cmp)> task_queue(cmp);
    task_queue.push({3, "low priority"});
    task_queue.push({10, "critical"});
    task_queue.push({7, "medium"});

    while (!task_queue.empty()) {
        auto& t = task_queue.top();
        std::cout << "[" << t.priority << "] " << t.name << '\n';
        task_queue.pop();
    }
}

std::span — Vue non propriétaire de données contiguës (C++20)

std::span est une vue légère et non propriétaire sur une séquence contiguë d'éléments. Il remplace le schéma sujet aux erreurs consistant à passer des paires (pointeur, taille).

span_example.cpp

#include <span>
#include <vector>
#include <array>
#include <iostream>
#include <numeric>

// span accepts vector, array, C-array — anything contiguous
void print_stats(std::span<const int> data) {
    if (data.empty()) return;
    std::cout << "Size: " << data.size() << '\n';
    std::cout << "First: " << data.front() << '\n';
    std::cout << "Last:  " << data.back() << '\n';

    int sum = std::accumulate(data.begin(), data.end(), 0);
    std::cout << "Sum:   " << sum << '\n';

    // Subviews
    auto first3 = data.first(3);   // first 3 elements
    auto last2  = data.last(2);    // last 2 elements
    auto mid    = data.subspan(1, 3);  // 3 elements starting at index 1
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    std::array<int, 5> arr = {10, 20, 30, 40, 50};
    int c_arr[] = {100, 200, 300, 400, 500};

    print_stats(vec);     // works with vector
    print_stats(arr);     // works with array
    print_stats(c_arr);   // works with C-array
}

string_view et optional

std::string_view (C++17) est une référence non propriétaire et en lecture seule vers une chaîne. Il évite le coût de copie ou d'allocation de std::string pour les fonctions qui n'ont besoin que de lire :

void greet(std::string_view name) {  // pas de copie, pas d'allocation
    std::cout << "Hello, " << name << '\n';
}
greet("world");               // fonctionne avec les littéraux de chaîne
greet(std::string{"world"});  // fonctionne avec std::string

std::optional (C++17) représente une valeur qui peut ou non être présente — un remplacement type-safe des « valeurs magiques » ou des pointeurs bruts pour indiquer l'absence :

std::optional<int> find_index(std::span<const int> data, int target) {
    for (int i = 0; i < data.size(); ++i)
        if (data[i] == target) return i;
    return std::nullopt;  // non trouvé
}
auto idx = find_index(vec, 42);
if (idx) std::cout << "Found at " << *idx << '\n';
std::cout << idx.value_or(-1) << '\n';  // -1 si vide

Piège

Puisque std::string_view et std::span sont non propriétaires, ils peuvent facilement devenir pendants si les données sous-jacentes sont détruites :

std::string_view bad() {
    std::string temp = "hello";
    return temp;  // PENDANT — temp détruit à la fin de la portée
}

Ne retournez jamais un string_view ou span vers une variable locale. Ils sont sûrs comme paramètres de fonction (les données de l'appelant survivent à l'appel), mais dangereux comme valeurs de retour sauf si vous pouvez garantir que la source survit à la vue.

Le même principe s'applique à std::span — c'est juste un pointeur et une taille en interne, sans sémantique de propriété.

Bonne pratique

Utilisez les adaptateurs de conteneurs lorsque vous voulez imposer une discipline sur la façon dont les éléments sont accédés :

- Utilisez std::stack au lieu d'un deque ou vector brut lorsque seul l'accès LIFO a du sens. Cela rend l'intention évidente et empêche l'accès aléatoire accidentel.
- Utilisez std::queue pour le traitement FIFO (files de tâches, BFS).
- Utilisez std::priority_queue pour l'ordonnancement, l'algorithme de Dijkstra ou tout scénario où vous voulez toujours l'élément extrême.

Si vous avez besoin d'itération, de requêtes de taille à des points arbitraires ou d'un accès au milieu de la séquence, utilisez directement le conteneur sous-jacent.

Points clés

Les adaptateurs de conteneurs (stack, queue, priority_queue) restreignent l'interface pour imposer une discipline d'utilisation
std::priority_queue est un tas max par défaut — utilisez std::greater pour un tas min
std::span (C++20) fournit une vue non propriétaire sur des données contiguës, remplaçant les paires (pointeur, taille)
std::string_view (C++17) évite la copie des chaînes pour un usage en lecture seule — mais attention aux références pendantes
std::optional (C++17) est la façon type-safe de représenter « peut-être pas de valeur » sans valeurs sentinelles magiques
Les vues non propriétaires (span, string_view) ne doivent jamais survivre aux données qu'elles référencent

Quiz — Testez vos connaissances

(15 XP)

1. Quel adaptateur de conteneur fournit un comportement FIFO (First In, First Out) ?

2. Quel type `std::priority_queue<int>` retourne-t-il par défaut depuis `top()` ?

3. Pourquoi est-il dangereux de retourner un `std::string_view` vers une `std::string` locale ?

Conteneurs associatifs : map, set, unordered_map

Les itérateurs : le ciment de la STL