Algoritmos

Os algoritmos são uma parte fundamental da Biblioteca Padrão do C++. Os algoritmos não funcionam com contêineres em si, mas sim com iteradores. Portanto, o mesmo algoritmo pode ser usado pela maioria ou até por todos os contêineres da Biblioteca Padrão do C++. Esta seção discute as convenções e a terminologia dos algoritmos da Biblioteca Padrão do C++.

Comentários

As descrições dos modelos de função do algoritmo empregam várias frases abreviadas:

• A frase "no intervalo [A, B)" significa a sequência de zero ou mais valores discretos que começam com A até, mas não incluindo B. Um intervalo é válido somente se B for alcançável a partir de A, você pode armazenar A em um objeto N (N A), você pode incrementar o objeto zero ou mais vezes (++N) e fazer com que o objeto seja comparado igual a B após um número finito de incrementos (N = == B).

• A frase "cada N no intervalo [A, B)" significa que N começa com o valor A e é incrementado zero ou mais vezes até ser igual ao valor B. O caso N == B não está no intervalo.

• A frase "o valor mais baixo de N no intervalo [A, B), de modo que X" significa que a condição X é determinada para cada N no intervalo [A, B) até que a condição X seja atendida.

• A frase "o valor mais alto de N no intervalo [A, B) tal que X" significa que X é determinado para cada N no intervalo [A, B). A função armazena em K uma cópia de N cada vez que a condição X é atendida. Se ocorrer tal armazenamento, a função substituirá o valor final de N, que é igual a B, pelo valor de K. No entanto, para um iterador bidirecional ou de acesso aleatório isso também pode significar que N começa com o valor mais alto no intervalo e é decrementado no intervalo até que a condição X seja atendida.

• Expressões como X - Y, em que X e Y podem ser iteradores diferentes dos iteradores de acesso aleatório, são usadas no sentido matemático. A função não necessariamente avalia o operador - se ele deve determinar tal valor. O mesmo também vale para expressões como X + N e X - N, em que N é do tipo inteiro.

Vários algoritmos usam um predicado que executa uma comparação de pares, como com operator==, para produzir um resultado bool. A função de predicado operator== ou qualquer substituição dela, não deve alterar nenhum de seus operandos. Ele deve produzir o mesmo resultado toda vez que for avaliado, e deve produzir o mesmo bool resultado se uma cópia de qualquer operando for substituída pelo operando.

Vários algoritmos usam um predicado que deve impor uma ordenação fraca estrita aos pares de elementos de uma sequência. Para o predicado pred(X, Y):

• Estrito significa que pred(X, X) é falso.

• Fraco significa que X e Y têm uma ordem equivalente se !pred(X, Y) && !pred(Y, X) (X == Y não precisa ser definido).

• Ordenação significa que pred(X, Y) && pred(Y, Z) implica pred(X, Z).

Alguns desses algoritmos usam o predicado X<Y implicitamente. Outros predicados que normalmente atendem ao requisito estrito de ordenação fraca são X>Y, less(X, Y), e greater(X, Y). Note, no entanto, que predicados como X= Y e X><= Y não satisfazem esse requisito.

Uma sequência de elementos designada por iteradores no intervalo [First, Last) é uma sequência ordenada pelo operador < se, para cada N no intervalo [0, Last - First) e para cada M no intervalo (N, Last - First) o predicado !(*(First + M) < *(First + N)) é verdadeiro. (Observe que os elementos são classificados em ordem crescente). A função de predicado operator<, ou qualquer substituição para ela, não deve alterar nenhum de seus operandos. Ele deve produzir o mesmo resultado toda vez que for avaliado, e deve produzir o mesmo bool resultado se uma cópia de qualquer operando for substituída pelo operando. Além disso, ela deve impor uma ordenação fraca estrita aos operandos que compara.

Uma sequência de elementos designada por iteradores no intervalo [First, Last) é um heap ordenado por operator< se, para cada N no intervalo [1, Last - First) o predicado !(*Primeiro< *(First + N)) é verdadeiro. (O primeiro elemento é o maio). Sua estrutura interna é conhecida apenas pelas funções de modelo make_heap, pop_heap e push_heap. Assim como acontece com uma sequência ordenada, a função predicado operator<, ou qualquer substituição para ela, não deve alterar nenhum de seus operandos, e deve impor uma ordenação fraca estrita aos operandos que compara. Ele deve produzir o mesmo resultado toda vez que for avaliado, e deve produzir o mesmo bool resultado se uma cópia de qualquer operando for substituída pelo operando.

Os algoritmos da Biblioteca Padrão C++ estão localizados nos arquivos de cabeçalho <algorithm> e <numeric>.

Confira também

Referência da biblioteca padrão C++
Acesso Thread-Safe na Biblioteca Padrão C++