algorithms stl
Um estudo explícito de algoritmos e seus tipos em STL.
é uma chave de rede igual a uma senha
STL suporta vários algoritmos que atuam em contêineres por meio de iteradores. Como esses algoritmos atuam em iteradores e não diretamente em contêineres, eles podem ser usados em qualquer tipo de iterador.
Os algoritmos STL são integrados e, portanto, economizam muito tempo e também são mais confiáveis. Eles também aumentam a capacidade de reutilização do código. Normalmente, esses algoritmos são apenas uma chamada de função e não precisamos escrever um código exaustivo para implementá-los.
=> Procure toda a série de treinamento C ++ aqui.
O que você aprenderá:
Tipos de algoritmos STL
STL suporta os seguintes tipos de algoritmos
- Algoritmos de busca
- Algoritmos de classificação
- Algoritmos numéricos
- Algoritmos não transformadores / modificadores
- Algoritmos de transformação / modificação
- Operações mínimas e máximas
Discutiremos cada um desses tipos em detalhes nos parágrafos a seguir.
Algoritmos de pesquisa e classificação
O algoritmo de pesquisa proeminente em STL é uma pesquisa binária. O algoritmo de pesquisa binária opera em uma matriz classificada e procura o elemento dividindo a matriz pela metade.
Isso é feito comparando primeiro o elemento a ser pesquisado com o elemento do meio da matriz e, em seguida, limitando a pesquisa a 1stmetade ou 2WLmetade da matriz dependendo se o elemento a ser pesquisado é menor ou maior que o elemento do meio.
A pesquisa binária é o algoritmo de pesquisa mais amplamente usado.
Sua sintaxe geral é:
binary_search(startaddr, endaddr, key)
Onde,
startaddr: endereço do primeiro elemento da matriz.
endaddr: endereço do último elemento da matriz.
chave: o elemento a ser pesquisado.
O STL nos fornece um algoritmo de “classificação” que é usado para organizar os elementos em um contêiner em uma ordem específica.
A sintaxe geral do algoritmo de classificação é:
sort(startAddr, endAddr);
Onde,
startAddr: endereço inicial do array a ser classificado.
endAddr: endereço final do array a ser classificado.
Internamente, o STL usa o algoritmo Quicksort para classificar a matriz.
Vejamos um exemplo para demonstrar a busca binária e o algoritmo de classificação:
#include #include using namespace std; int main() { int testAry[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 }; int arysize = sizeof(testAry) / sizeof(testAry[0]); sort(testAry, testAry + arysize); cout<<'
Sorted Array is
'; for(int i=0;i Resultado:
Matriz classificada é
0 1 2 3 4 5 6 7 8 9
Chave = 2 encontrada na matriz
Chave = 10 não encontrada na matriz
No código fornecido, fornecemos uma matriz na qual precisamos pesquisar um elemento-chave usando a pesquisa binária. Uma vez que a pesquisa binária requer um array classificado, primeiro classificamos o array usando o algoritmo “sort” e, em seguida, fazemos uma chamada de função para “binary_search” fornecendo os parâmetros necessários.
Primeiro, chamamos o algoritmo binary_search para chave = 2 e, em seguida, para chave = 10. Dessa forma, com apenas uma chamada de função, podemos convenientemente fazer uma pesquisa binária em um array ou classificá-lo.
Algoritmos Numéricos
cabeçalho em STL contém várias funções que operam em valores numéricos. Essas funções variam desde encontrar lcds, gcds até calcular a soma dos elementos em um contêiner, como matrizes, vetores em um determinado intervalo, etc.
Discutiremos algumas funções importantes aqui com exemplos.
(i) acumular
A sintaxe geral da função acumular é:
accumulate (first, last, sum);
Esta função retorna a soma de todos os elementos dentro de um intervalo [primeiro, último] em uma soma variável. Na notação de sintaxe acima, primeiro e último são os endereços do primeiro e do último elemento em um contêiner e soma é o valor inicial da variável sum.
(ii) parcial_sum
A sintaxe geral da função partial_sum é:
partial_sum(first, last, b)
Aqui
primeiro: endereço do elemento inicial do contêiner.
Último: endereço do último elemento do container.
B: array em que será armazenada a soma parcial dos elementos correspondentes do array.
Assim, a função partial_sum calcula a soma parcial da matriz correspondente ou dos elementos do vetor e os armazena em uma matriz diferente.
Se a representa o elemento no intervalo [primeiro, último] e b representa o elemento na matriz resultante, a soma parcial será:
b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2 ... e assim por diante.
Vejamos um exemplo para demonstrar os dois Essas funções em um programa:
#include #include using namespace std; int main() { int A[] = {21,25,64,32}; int sum = 0; int b[4]; cout<<'
Result of accumulate function is: '< Resultado:
O resultado da função acumular é: 142
como adicionar valores a uma matriz
parcial_sum da matriz A: 21 46 110 142
Conforme mostrado no programa acima, primeiro calculamos a soma dos elementos usando a função acumular e, em seguida, chamamos a função partial_sum para calcular a soma parcial dos elementos correspondentes do array.
Outros algoritmos suportados por STL e cabeçalho:
- iota: Preenche um intervalo com incrementos sucessivos do valor inicial.
- reduzir: Semelhante a acumular, exceto fora de serviço.
- produto Interno: Calcula o produto interno de dois intervalos de elementos.
- adjacente_differência: Calcula as diferenças entre os elementos adjacentes em um intervalo.
- inclusive_scan: Semelhante a partial_sum, inclui o iº elemento de entrada na iª soma.
- exclusiva_scan: Semelhante a partial_sum, exclui o iésimo elemento de entrada da iésima soma.
Algoritmos não modificadores
Os algoritmos não modificadores ou não transformadores são aqueles que não alteram o conteúdo do contêiner em que estão operando. O STL oferece suporte a muitos algoritmos não modificadores.
Listamos alguns deles abaixo:
- contar: Retorna o número de valores no intervalo fornecido.
- igual: Compara os elementos em dois intervalos e retorna um valor booleano.
- incompatibilidade: Retorna um par de iteradores quando dois iteradores são comparados e ocorre uma incompatibilidade.
- procurar: Pesquisa uma determinada sequência em um determinado intervalo.
- search_n: Pesquisa em um determinado intervalo por uma sequência do valor de contagem.
Vamos elaborar mais sobre as funções “contar” e “igualar” !!
contagem (primeiro, último, valor) retorna o número de vezes que o ‘valor’ aparece no intervalo [primeiro, último].
#include #include using namespace std; int main () { int values[] = {5,1,6,9,10,1,12,5,5,5,1,8,9,7,46}; int count_5 = count(values, values+15, 5); cout<<'The number of times '5' appears in array= '< Resultado:
O número de vezes que ‘5’ aparece em uma matriz = 4
Como você pode ver neste código, definimos um valor de matriz e, em seguida, chamamos a função de contagem fornecendo o intervalo de valor e valor de 5. A função retorna o número de vezes (contagem) que o valor 5 aparece no intervalo.
Vamos dar um exemplo para demonstrar a função ‘igual’.
igual (primeiro1, último1, primeiro2) compara os elementos no intervalo [primeiro1, último1] com o primeiro elemento apontado por primeiro2 e retorna verdadeiro se todos os elementos forem iguais, caso contrário, falso.
#include #include using namespace std; int main() { int inputs1[] = { 1,2,3,4,5,6,7,8}; int inputs2[] = { -1,2,1,2,3,4,6,7,8,9}; if (equal( inputs1 , inputs1+8 , inputs2 )==1) cout<<'Elements in Two ranges are equal'; else cout<<'Elements in two ranges are not equal'; }
Resultado:
Elementos em dois intervalos não são iguais.
No código acima, definimos duas matrizes de inteiros e comparamos seus elementos correspondentes usando a função 'igual'. Como os elementos da matriz não são iguais, igual retorna falso.
Modificando Algoritmos
Os algoritmos de modificação modificam ou transformam o conteúdo dos contêineres quando são executados.
Os algoritmos de modificação mais populares e amplamente usados incluem “troca” e “reversão” que trocam dois valores e invertem os elementos no contêiner, respectivamente.
Vejamos os exemplos dessas funções:
#include #include #include #include using namespace std; int main () { vector vec1 = {1,1,2,3,5}; vector vec2 = {2,4,6,8,10}; swap(vec1,vec2); cout<<'Vector 1 : '; for (auto it = vec1.begin(); it < vec1.end(); ++it) cout << *it << ' '; cout< Resultado:
Vetor 1: 2 4 6 8 10
Vetor 2: 1 1 2 3 5
Vetor invertido 1: 10 8 6 4 2
Vetor invertido 2: 5 3 2 1 1
Como visto, temos dois vetores definidos no programa. Primeiro, usando a função de troca, trocamos o conteúdo de vetor1 e vetor2. A seguir, invertemos o conteúdo de cada vetor usando a função reversa.
O programa gera o vetor 1 e o vetor 2 depois de trocar seus conteúdos e também depois de reverter o conteúdo.
Operações mínimas e máximas
Esta categoria consiste em funções mín e máx que descobrem os valores mínimo e máximo, respectivamente, a partir dos dois valores dados.
A sintaxe geral dessas funções é:
max(objecta, objectb); min(objecta, objectb);
Também podemos fornecer um terceiro parâmetro para fornecer ‘compare_function’ ou os critérios que seriam usados para encontrar o valor mínimo / máximo. Se não for fornecido, a função max usa o operador ‘>’ para comparação, enquanto a função min usa ‘<’ operator for comparison.
Vamos demonstrar essas funções usando um programa.
#include #include using namespace std; int main() { int x=4, y=5; cout<<'Max of 4 and 5 : '; cout << max(x,y); cout< Resultado:
Máximo de 4 e 5: 5
Mínimo de 4 e 5: 4
String máxima: string menor
String mínima: string mais longa
O programa acima é autoexplicativo, pois usamos as funções mín. E máx. Nos números primeiro e, em seguida, nas strings. Como não fornecemos ‘compare_function’ opcional, as funções mín / máx atuaram nos operadores ‘’ respectivamente.
Conclusão
Com isso, chegamos ao final deste tutorial sobre os principais algoritmos usados em STL.
Em nossos tutoriais subsequentes, discutiremos os iteradores em detalhes junto com as funções comuns usadas em STL, independentemente dos contêineres.
=> Leia a série de treinamento Easy C ++.
Leitura recomendada
- Matrizes em STL
- Iteradores em STL
- Fila prioritária em STL
- Introdução aos algoritmos de pesquisa em C ++
- Cordas, pares e tuplas em STL
- CONFIGURAR em STL
- Mais de 70 MELHORES tutoriais em C ++ para aprender programação C ++ GRATUITAMENTE
- Best FREE C # Tutorial Series: The Ultimate C # Guide for Beginners