Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

CKTIS / C++

Plage de recherche partitionnée

`std::lower_bound` n’exige pas un tri complet : pour la clé donnée, les éléments qui satisfont le test doivent tous précéder ceux qui ne le satisfont pas.

Version : ISO C++23; implementation support may vary

Syntaxe

#include <algorithm>

std::lower_bound(first, last, key);
std::lower_bound(first, last, key, comp);
std::ranges::lower_bound(first, last, key, comp, proj);
std::ranges::lower_bound(range, key, comp, proj);

// For this key, the predicate must be true for a prefix and false for the rest.
// Classic: bool(comp(element, key))
// Ranges:  bool(std::invoke(comp, std::invoke(proj, element), key))

Une plage [first, last) est partitionnée par rapport à la clé si bool(comp(element, key)) donne d’abord uniquement true, puis uniquement false. Chaque partie peut être vide et aucune ne doit être triée en interne. La version classique std::lower_bound, dans <algorithm>, renvoie le premier itérateur pour lequel le test est faux, ou last s’il n’y en a pas. L’élément renvoyé n’est pas nécessairement égal à la clé. Si la précondition de partitionnement n’est pas respectée, le comportement est indéfini.

La surcharge classique avec comparateur ne compare que dans le sens élément–clé. Elle accepte donc une lambda [](const Sale& row, int key) qui teste row.sales > key ; [] ne capture rien. std::ranges::lower_bound (depuis C++20) accepte une paire itérateur–sentinelle ou une plage. Son comparateur doit satisfaire indirect_strict_weak_order pour les éléments projetés et la clé ; &Sale::sales permet de comparer des entiers. Les deux versions demandent au moins des itérateurs avant et un nombre logarithmique de comparaisons, mais le nombre de déplacements peut être linéaire sans accès aléatoire. La surcharge sur une plage renvoie std::ranges::dangling si la plage temporaire n’est pas une borrowed_range. Ne déréférencez ni un itérateur de fin ni un itérateur invalidé.

std::nth_element et std::partial_sort exigent des itérateurs à accès aléatoire et un ordre faible strict : comp(x, x) doit être faux, et la comparaison comme l’équivalence définie par deux comparaisons fausses doivent être transitives. Pour des ventes entières, a.sales > b.sales respecte ces règles, contrairement à >=. nth_element place l’élément de rang choisi à sa position dans l’ordre de tri et sépare les deux parties sans garantir leur tri. partial_sort trie le préfixe demandé et laisse le reste dans un ordre non spécifié. Aucun des deux ne garantit le partitionnement de toute la plage pour une clé arbitraire. Pour des recherches répétées avec des clés variables, triez toute la plage selon le même ordre.

Exemples

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

struct Sale {
    int sales;
};

int main() {
    const std::vector<Sale> rows{{95}, {120}, {70}, {85}, {60}};
    const int key = 90;
    const auto before_key = [](const Sale& row, int key) {
        return row.sales > key;
    };

    const auto classic = std::lower_bound(rows.begin(), rows.end(), key, before_key);
    const auto ranged = std::ranges::lower_bound(rows, key, std::ranges::greater{}, &Sale::sales);

    if (classic != rows.end() && ranged != rows.end()) {
        std::cout << classic->sales << '\n' << ranged->sales << '\n';
    }
}

Résultat

70
70

Pour `90`, les deux appels affichent `70`, la première valeur qui ne dépasse pas le seuil, bien que la plage ne soit pas triée par ordre décroissant. Pour `100`, `95` donne `false` avant que `120` donne `true` : aucun des deux appels n’est valide avec `100` sur cette plage.

Leçons associées

  • C++ · Leçon 23 · Avancé · Version : 3

Sources