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

CKTIS / C++

std::inplace_merge : fusion stable de séries adjacentes

std::inplace_merge fusionne de façon stable deux sous-plages consécutives déjà triées dans la même plage.

Version : C++23

Syntaxe

template<class BidirectionalIt>
void std::inplace_merge(BidirectionalIt first, BidirectionalIt middle, BidirectionalIt last);

template<class BidirectionalIt, class Compare>
void std::inplace_merge(BidirectionalIt first, BidirectionalIt middle, BidirectionalIt last, Compare comp);

std::inplace_merge(first,middle,last) fusionne [first,middle) et [middle,last) avec std::less ; une surcharge reçoit comp. Les deux doivent être valides et triées séparément selon le même ordre. Le résultat occupe [first,last) et reste stable : les équivalents de la première série précèdent ceux de la seconde.

L’exemple contient 1,4,7 et 2,3,8 ; il affiche ensuite 1 2 3 4 7 8. middle marque la frontière d’entrée, pas une position conservée.

Violer le prérequis de tri est un comportement indéfini. Il faut des itérateurs bidirectionnels et des valeurs déplaçables et échangeables. Sans policy, assez de mémoire donne exactement N−1 comparaisons ; l’absence de tampon sélectionne la méthode sans tampon jusqu’à O(N log N), tandis que les autres exceptions se propagent. Avec une policy standard, une exception d’élément non capturée appelle std::terminate ; le manque de mémoire temporaire pour l’exécution parallèle peut lever std::bad_alloc.

Exemples

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

int main() {
    std::vector<int> values{1, 4, 7, 2, 3, 8};
    std::inplace_merge(values.begin(), values.begin() + 3, values.end());
    for (int value : values) std::cout << value << ' ';
    std::cout << '\n';
}

Résultat

1 2 3 4 7 8 

std::inplace_merge → 1 2 3 4 7 8

Sources