Base de conhecimentoCentro de Exames
PT · PTPortuguês (Portugal)
Escolher idioma13

CKTIS / C++

std::inplace_merge: junção estável de séries adjacentes

std::inplace_merge junta de forma estável dois subintervalos consecutivos já ordenados no mesmo intervalo.

Versão: C++23

Sintaxe

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) junta [first,middle) e [middle,last) com std::less; outro overload recebe comp. Ambos têm de ser válidos e ordenados pelo mesmo critério. O resultado ocupa [first,last) e é estável: equivalentes da primeira série ficam antes dos da segunda.

O exemplo contém 1,4,7 e 2,3,8; depois imprime 1 2 3 4 7 8. middle marca a fronteira de entrada, não uma posição preservada.

Violar a precondition de ordenação é undefined behavior. Requer iteradores bidirecionais e valores movíveis e trocáveis. Sem policy, memória suficiente dá exatamente N−1 comparações; sem buffer usa o algoritmo sem memória até O(N log N), enquanto outras exceções se propagam. Com policy standard, exceção de elemento não capturada chama std::terminate; falta de memória temporária para execução paralela pode lançar std::bad_alloc.

Exemplos

#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';
}

Resultado

1 2 3 4 7 8 

std::inplace_merge → 1 2 3 4 7 8

Fontes