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

CKTIS / C++

Tri, comparaisons et plages de recherche

Un tri correct exige un comparateur qui définit un ordre strict faible. La recherche binaire exige une plage partitionnée selon la condition concernée ; trier toute la plage suffit, mais n’est pas toujours nécessaire.

Version : C++23; repository compiler flag, production runtime not attested

Syntaxe

std::sort(first, last, comp);
std::lower_bound(first, last, value, comp);

std::sort de <algorithm> ordonne la plage semi-ouverte [first, last) selon comp : aucun élément situé plus loin ne précède un élément antérieur. Il exige des itérateurs à accès aléatoire et des éléments satisfaisant aux exigences de déplacement et d’échange. Il effectue O(N log N) comparaisons. Il ne garantit pas le maintien de l’ordre des éléments équivalents ; utilisez std::stable_sort pour cela.

Le comparateur doit définir un ordre strict faible. comp(a, b) signifie que a précède b, et comp(a, a) doit être faux. La relation doit être transitive. L’équivalence définie par !comp(a, b) && !comp(b, a) doit également être transitive et ne doit pas nécessairement correspondre à operator==. N’utilisez pas <= : il enfreint l’exigence pour des arguments identiques. Si les exigences imposées au comparateur ne sont pas respectées, les garanties de l’algorithme ne s’appliquent pas.

L’ordre strict faible et la partition des plages de recherche sont des exigences liées, mais distinctes. Dans une plage partitionnée selon un prédicat, tous les éléments donnant true précèdent ceux donnant false ; l’une ou l’autre partie peut être vide. Pour std::lower_bound(first, last, value, comp), le prédicat est comp(e, value). La fonction renvoie la frontière : le premier élément donnant false, ou last. Cela ne prouve pas que la valeur recherchée est présente ; ne déréférencez pas last.

Un tri selon le même ordre garantit cette partition pour chaque clé. Pour une seule clé, la partition suffit : [2, 1, 4, 3] satisfait la précondition de std::lower_bound pour value = 3 et la comparaison <, bien que la plage ne soit pas triée. Les autres fonctions de recherche binaire ont leurs propres exigences de partition. std::lower_bound effectue O(log N) comparaisons, mais sans itérateurs à accès aléatoire, il peut nécessiter un nombre linéaire de déplacements d’itérateur.

L’exemple trie des entiers, puis réutilise le même comp pour obtenir l’indice 3. Le contenu vise C++23 ; la référence fournie pointe vers un projet évolutif, et non vers une publication C++23 figée. La prise en charge par le compilateur et l’environnement d’exécution de production n’est pas attestée.

Exemples

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{4, 1, 3, 1, 2};
    const auto comp = [](int a, int b) { return a < b; };

    std::sort(values.begin(), values.end(), comp);
    for (std::size_t i = 0; i < values.size(); ++i) {
        if (i != 0) std::cout << ' ';
        std::cout << values[i];
    }
    std::cout << '\n';

    const auto it = std::lower_bound(values.begin(), values.end(), 3, comp);
    std::cout << "index=" << (it - values.begin()) << '\n';
}

Résultat

1 1 2 3 4
index=3

Le code affiché et le résultat déclaré ont été vérifiés dans un environnement isolé selon la méthode consignée dans la preuve de vérification de cette version exacte.

Sources