Algoritmos
Os algoritmos são uma parte fundamental de biblioteca padrão do modelo. Os algoritmos não funcionam com contêineres próprios mas em vez com iteradores. Em virtude disso, o mesmo algoritmo pode ser usado pela maioria se nem todos os contêineres STL. Esta seção discute as convenções e a terminologia dos algoritmos STL.
Comentários
As descrições das funções de modelo do algoritmo empregam diversas sentenças de taquigrafia:
A frase “no intervalo [A, B)” significa a sequência os valores de zero ou mais discretos que começam com Ao até mas não incluindo o. B. Um intervalo só será válido se é possível acessar B de A; você pode armazenar A em um objeto N (N = A), incrementar o objeto zero ou mais vezes (++N), e fazer com que o objeto seja comparado igual a B depois de um número finito de incrementos (N == B*).*
A frase “cada N no intervalo [A, B)” significa que Em começa com o valor Para e será incrementado zero ou mais vezes até que é igual ao valor B. == B de casos Em 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 No intervalo [A, *B)*de modo 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 um repositório ocorre, a função substitui o valor final de N, B, que é igual ao valor de K. Para um iterador bidirecional ou de acesso aleatório, no entanto, também pode significar que começa Em com o valor mais alto no intervalo e é decrementado sobre o intervalo até que a condição X seja atendida.
Expressões como X - Y, onde X e Y iteradores podem ser diferentes dos iteradores de acesso aleatório, destina-se no sentido matemático. A função avalia não necessariamente o operador- se deve determinar esse valor. O mesmo é válido para expressões também como + X Em e X - N, onde N é do tipo inteiro.
Vários algoritmos utilizam um predicado que executa em pares uma comparação, como com operator==, para gerar um resultado de bool . A função **operator==**do predicado, ou nenhuma substituição para ela, não devem ser alterados nenhum de seus operandos. Deve ser o mesmo resultado de bool cada vez que é avaliado, e deve ser o mesmo resultado se uma cópia de um ou outro operando for substituída para o operando.
Vários algoritmos utilizam um predicado que deve impor a ordenação fraco restrito em pares de elementos de uma sequência. Para o predicado pr(X, Y):
Restrito significa que pr(X, *X)*será false.
Fraco significa que X e Y têm ordenar equivalente se !pr(X, Y) && !pr(Y, X) (X == Y não precisa ser definido).
Ordenação significa que pr(X, *Y) &&*pr(Y, Z) sugere pr(X, Z).
Alguns desses algoritmos implicitamente usam o predicado X < Y. Outros predicados que satisfazem normalmente o requisito de ordenação fraco estrito são X > , Yless(X, Y), e greater(X, Y). Observe, entretanto, que os predicados como = X < e Y = X > Y não satisfazem esse requisito.
Uma sequência de elementos designados por iteradores no intervalo [First, Last) é uma sequência ordenada pelo operador**<** se, para cada N no intervalo de [0, Last - First) e M para cada no intervalo (Em, Last - First) o predicado! (*First + ( M) <* ( N)primeiro +) é true. (Observe que os elementos são classificados em ordem crescente.) A função **operator<**do predicado, ou nenhuma substituição para ela, não devem ser alterados nenhum de seus operandos. Deve ser o mesmo resultado de bool cada vez que é avaliado, e deve ser o mesmo resultado se uma cópia de um ou outro operando for substituída para o operando. Além disso, deve impor a ordenação fraco restrito em que compara operandos.
Uma sequência de elementos designados por iteradores no intervalo [First, Last) é um heap ordenado por operator< se, para cada N no intervalo de [1, Last - First) o predicado! (*First < * ( *N)*First +) é true. (O primeiro elemento é o maior.) Sua estrutura interna é conhecida de outra forma somente a funções make_heap, pop_heap, e push_heapdo modelo. Como com uma sequência ordenada, a função **operator<**do predicado, ou nenhuma substituição para ela, não devem ser alterados nenhum de seus operandos, e deve impor a ordenação fraco restrito em que compara operandos. Deve ser o mesmo resultado de bool cada vez que é avaliado, e deve ser o mesmo resultado se uma cópia de um ou outro operando for substituída para o operando.
Os algoritmos STL estão nos arquivos de cabeçalho de <algorithm> e de <numeric> .