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

CKTIS / C++

std::stable_sort — ordenação estável

std::stable_sort ordena um intervalo preservando a ordem relativa dos elementos equivalentes segundo a comparação. Permite ordenar registos por uma chave sem alterar a ordem anterior dos registos com a mesma chave.

Versão: C++23; repository compiler flag, production runtime not attested

Sintaxe

#include <algorithm>

std::stable_sort(first, last);
std::stable_sort(first, last, comp);

std::stable_sort, declarado em <algorithm>, reorganiza os elementos de [first, last) e devolve void. A sobrecarga sem comp ordena por ordem crescente usando a comparação predefinida; a sobrecarga com comp usa o comparador fornecido. Ao contrário de std::sort, garante a preservação da ordem relativa dos elementos equivalentes.

Equivalência significa !comp(a, b) && !comp(b, a), não necessariamente a == b. O comparador tem de definir uma ordem estrita fraca: em particular, comp(x, x) tem de ser falso, e tanto a ordem como a equivalência que dela resulta têm de ser transitivas. Não uses <= em vez de < nem modifiques os elementos comparados.

São necessários iteradores de acesso aleatório, e os elementos têm de suportar troca, construção por movimento e atribuição por movimento. Para N = last - first, o número de comparações é O(N log N) quando existe memória adicional suficiente; caso contrário, é, no máximo, O(N log² N). A ordenação modifica a entrada, mas não garante um uso constante de memória auxiliar.

O exemplo compara apenas key: B mantém-se antes de D, e A antes de C. Destina-se a ser executado com uma opção de compilador C++23. O código apresentado foi executado sem alterações num ambiente isolado e o resultado obtido coincidiu com o indicado. Esta verificação não atesta a compatibilidade com o ambiente de execução em produção. O projeto de norma atual associado pode incluir extensões posteriores a C++23; as chamadas apresentadas não precisam delas.

Exemplos

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

struct Item {
    int key;
    char id;
};

int main() {
    std::vector<Item> items{{2, 'A'}, {1, 'B'}, {2, 'C'}, {1, 'D'}};

    std::stable_sort(items.begin(), items.end(),
        [](const Item& a, const Item& b) {
            return a.key < b.key;
        });

    for (const Item& item : items) {
        std::cout << item.key << ' ' << item.id << '\n';
    }
}

Resultado

1 B
1 D
2 A
2 C

O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.

Fontes