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

CKTIS / C++

std::merge — fusion stable de plages triées

std::merge, défini dans <algorithm>, copie deux plages triées dans une plage de sortie distincte. Il conserve les doublons et la stabilité, et renvoie un itérateur situé juste après le dernier élément écrit.

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

Syntaxe

#include <algorithm>
std::merge(first1, last1, first2, last2, result);
std::merge(first1, last1, first2, last2, result, comp);

std::merge fusionne [first1, last1) et [first2, last2), en écrivant tous les éléments à partir de result. Les deux entrées doivent déjà être triées selon le même ordre : croissant par défaut, ou selon l’ordre défini par comp. Le comparateur doit définir un ordre strict faible. Des entrées non triées ne respectent pas les préconditions de l’algorithme ; la fonction ne commence pas par trier les entrées.

La fusion est stable : elle préserve l’ordre des éléments dans chaque entrée, et les éléments de clés équivalentes de la première plage précèdent ceux de la seconde. L’équivalence signifie que ni comp(a, b) ni comp(b, a) n’est vrai. Les doublons sont conservés dans la sortie.

La plage de sortie ne doit chevaucher aucune des plages d’entrée. Prévoyez un espace correspondant à la somme de leurs longueurs, ou utilisez un itérateur d’insertion approprié. Appeler uniquement reserve() sur un vecteur ne crée pas d’éléments dans lesquels écrire via begin(). L’itérateur renvoyé pointe juste après le dernier élément écrit.

Pour les surcharges présentées ici, sans politique d’exécution, le travail est linéaire par rapport au nombre total d’éléments N, avec au plus N - 1 comparaisons lorsque N > 0. Ne confondez pas cette fonction avec std::inplace_merge, qui fusionne deux sous-plages triées adjacentes au sein de la même plage. L’exemple utilise une syntaxe compatible avec C++23 ; le projet de norme cité est mis à jour et peut également inclure des extensions ultérieures.

Exemples

#include <algorithm>
#include <array>
#include <iostream>

int main() {
    const std::array<int, 3> a{1, 3, 5};
    const std::array<int, 3> b{2, 3, 6};
    std::array<int, 6> result{};

    const auto end = std::merge(a.begin(), a.end(),
                                b.begin(), b.end(), result.begin());

    for (auto it = result.begin(); it != end; ++it) {
        if (it != result.begin()) {
            std::cout << ' ';
        }
        std::cout << *it;
    }
    std::cout << '\n';
}

Résultat

1 2 3 3 5 6

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