algorithms stl
Un estudio explícito de algoritmos y sus tipos en STL.
cómo agregar repositorio svn en eclipse
STL admite varios algoritmos que actúan sobre contenedores a través de iteradores. Como estos algoritmos actúan sobre iteradores y no directamente sobre contenedores, se pueden utilizar en cualquier tipo de iteradores.
Los algoritmos STL están integrados y, por lo tanto, ahorran mucho tiempo y también son más confiables. También mejoran la reutilización del código. Estos algoritmos normalmente son solo una llamada de función y no necesitamos escribir un código exhaustivo para implementarlos.
=> Busque toda la serie de formación en C ++ aquí.
Lo que vas a aprender:
Tipos de algoritmos STL
STL admite los siguientes tipos de algoritmos
- Algoritmos de búsqueda
- Algoritmos de clasificación
- Algoritmos numéricos
- Algoritmos de no transformación / modificación
- Transformar / modificar algoritmos
- Operaciones mínimas y máximas
Discutiremos cada uno de estos tipos en detalle en los siguientes párrafos.
Algoritmos de búsqueda y clasificación
El algoritmo de búsqueda más destacado en STL es una búsqueda binaria. El algoritmo de búsqueda binaria opera en una matriz ordenada y busca el elemento dividiendo la matriz por la mitad.
Esto se hace comparando primero el elemento que se buscará con el elemento medio de la matriz y luego limitando la búsqueda a 1S tla mitad o 2Dakota del Nortela mitad de la matriz dependiendo de si el elemento a buscar es menor o mayor que el elemento del medio.
La búsqueda binaria es el algoritmo de búsqueda más utilizado.
Su sintaxis general es:
|_+_|Dónde,
startaddr: dirección del primer elemento de la matriz.
endaddr: dirección del último elemento del arreglo.
clave: el elemento a buscar.
STL nos proporciona un algoritmo de 'clasificación' que se utiliza para organizar los elementos en un contenedor en un orden particular.
La sintaxis general del algoritmo de ordenación es:
|_+_|Dónde,
startAddr: dirección de inicio de la matriz a ordenar.
endAddr: dirección final de la matriz a ordenar.
Internamente, STL usa el algoritmo Quicksort para ordenar la matriz.
Tomemos un ejemplo para demostrar la búsqueda binaria y el algoritmo de ordenación:
|_+_|Producción:
La matriz ordenada es
0 1 2 3 4 5 6 7 8 9
Key = 2 encontrado en la matriz
Clave = 10 no encontrado en la matriz
En el código dado, proporcionamos una matriz en la que necesitamos buscar un elemento clave usando la búsqueda binaria. Dado que la búsqueda binaria requiere una matriz ordenada, primero ordenamos la matriz usando el algoritmo 'sort' y luego hacemos una llamada de función a 'binary_search' proporcionando los parámetros requeridos.
Primero, llamamos al algoritmo binary_search para key = 2 y luego para key = 10. De esta manera, con solo una llamada a la función, podemos hacer una búsqueda binaria en una matriz u ordenarla.
Algoritmos numéricos
El encabezado en STL contiene varias funciones que operan en valores numéricos. Estas funciones van desde encontrar lcds, gcds hasta incluso calcular la suma de los elementos en un contenedor como matrices, vectores sobre un rango dado, etc.
Discutiremos algunas funciones importantes aquí con ejemplos.
(i) acumular
La sintaxis general de la función de acumulación es:
|_+_|Esta función devuelve la suma de todos los elementos dentro de un rango (primero, último) en una suma variable. En la notación de sintaxis anterior, el primero y el último son las direcciones del primer y último elemento de un contenedor y la suma es el valor inicial de la variable suma.
(ii) suma_parcial
La sintaxis general de la función de suma_parcial es:
|_+_|Aquí
primero: dirección del elemento inicial del contenedor.
Last: dirección del último elemento del contenedor.
B: matriz en la que se almacenará la suma parcial de los elementos correspondientes de la matriz.
Por lo tanto, la función suma_parcial calcula la suma parcial de la matriz correspondiente o los elementos del vector y los almacena en una matriz diferente.
Si a representa el elemento en el rango (primero, último) y b representa el elemento en la matriz resultante, la suma_parcial será:
b0 = a0
b1 = a0 + a1
b2 = a0 + a1 + a2… y así sucesivamente.
Veamos un ejemplo para demostrar tanto Estas funciones en un programa:
|_+_|Producción:
El resultado de la función de acumulación es: 142
suma_parcial de la matriz A: 21 46110142
Como se muestra en el programa anterior, primero calculamos la suma de los elementos usando la función de acumulación y luego llamamos a la función suma_parcial para calcular la suma parcial de los elementos de matriz correspondientes.
Otros algoritmos compatibles con STL y encabezado:
- iota: Llena un rango con incrementos sucesivos del valor inicial.
- reducir: Similar a acumular, excepto fuera de servicio.
- producto Interno: Calcula el producto interno de dos rangos de elementos.
- adyacente_difference: Calcula las diferencias entre elementos adyacentes en un rango.
- inclusive_scan: Similar a la suma_parcial, incluye el i-ésimo elemento de entrada en la i-ésima suma.
- exploración_exclusiva: Similar a la suma_parcial, excluye el i-ésimo elemento de entrada de la i-ésima suma.
Algoritmos no modificadores
Los algoritmos no modificadores o no transformadores son los que no cambian el contenido del contenedor en el que están operando. STL admite muchos algoritmos no modificadores.
A continuación, enumeramos algunos de ellos:
- contar: Devuelve el número de valores en el rango dado.
- igual: Compara los elementos en dos rangos y devuelve un valor booleano.
- discordancia: Devuelve un par de iteradores cuando se comparan dos iteradores y se produce una falta de coincidencia.
- buscar: Busca una secuencia determinada en un rango determinado.
- search_n: Busca en un rango determinado una secuencia del valor de recuento.
¡¡Vamos a desarrollar más sobre las funciones 'contar' e 'igual' !!
count (primero, último, valor) devuelve el número de veces que aparece el 'valor' en el rango (primero, último).
|_+_|Producción:
El número de veces que aparece '5' en una matriz = 4
Como puede ver en este código, definimos un valor de matriz y luego llamamos a la función de recuento proporcionando el rango de valor y valor de 5. La función devuelve el número de veces (recuento) que el valor 5 aparece en el rango.
Tomemos un ejemplo para demostrar la función 'igual'.
equal (first1, last1, first2) compara los elementos en el rango (first1, last1) con el primer elemento señalado por first2 y devuelve verdadero si todos los elementos son iguales en caso contrario falso.
|_+_|Producción:
Los elementos de dos rangos no son iguales.
En el código anterior, definimos dos matrices de números enteros y comparamos sus elementos correspondientes usando la función 'igual'. Como los elementos de la matriz no son iguales, equal devuelve falso.
Modificar algoritmos
Los algoritmos de modificación modifican o transforman el contenido de los contenedores cuando se ejecutan.
Los algoritmos de modificación más populares y ampliamente utilizados incluyen 'swap' e 'reverse' que intercambian dos valores e invierten los elementos en el contenedor respectivamente.
Veamos los ejemplos de estas funciones:
|_+_|Producción:
Vector 1: 2 4 6 8 10
Vector 2: 1 1 2 3 5
Vector invertido 1:10 8 6 4 2
Vector invertido 2: 5 3 2 1 1
Como se ve, tenemos dos vectores definidos en el programa. Primero, usando la función de intercambio, intercambiamos el contenido de vector1 y vector2. A continuación, invertimos el contenido de cada vector usando la función inversa.
El programa genera Vector 1 y Vector 2 después de intercambiar sus contenidos y también después de invertir los contenidos.
Operaciones mínimas y máximas
Esta categoría consta de funciones mínimas y máximas que averiguan los valores mínimo y máximo respectivamente a partir de los dos valores dados.
cómo arreglar la puerta de enlace predeterminada no disponible
La sintaxis general de estas funciones es:
|_+_|También podemos proporcionar un tercer parámetro para proporcionar 'función_comparar' o los criterios que se utilizarían para encontrar el valor mínimo / máximo. Si no se proporciona, entonces la función max usa el operador '>' para la comparación, mientras que la función min usa '<’ operator for comparison.
Demostremos estas funciones usando un programa.
|_+_|Producción:
Máximo de 4 y 5: 5
Min de 4 y 5: 4
Max String: cuerda más pequeña
Cadena mínima: cadena más larga
El programa anterior se explica por sí mismo, ya que usamos funciones mínimas y máximas en los números primero y luego en las cadenas. Como no proporcionamos 'función_comparar' opcional, las funciones mín. / Máx. Actuaron sobre operadores '' respectivamente.
Conclusión
Con esto, llegamos al final de este tutorial sobre los principales algoritmos utilizados en STL.
En nuestros tutoriales posteriores, analizaremos los iteradores en detalle junto con las funciones comunes utilizadas en STL independientemente de los contenedores.
=> Lea la serie de formación Easy C ++.
Lectura recomendada
- Matrices en STL
- Iteradores en STL
- Cola de prioridad en STL
- Introducción a los algoritmos de búsqueda en C ++
- Cuerdas, pares y tuplas en STL
- CONFIGURAR EN STL
- 70+ MEJORES Tutoriales de C ++ para aprender programación C ++ GRATIS
- La mejor serie de tutoriales de C # GRATIS: la guía definitiva de C # para principiantes