Algoritmos STL

lower_bound y upper_bound son funciones de búsqueda binaria integradas.

lower_bound: una función que, en tiempo logarítmico, encuentra el elemento más pequeño en una matriz ordenada que es mayor o igual que el valor dado k.
Toma los límites de la matriz y el valor de k como argumentos.
Devuelve un iterador al elemento encontrado, o al final (no incluido) de la matriz si no existe dicho elemento.
Puede leer más en la documentación.

upper_bound - una función que en tiempo logarítmico en una matriz ordenada encuentra el elemento más pequeño que es estrictamente mayor que el valor k dado.
Toma los límites de la matriz y el valor de k como argumentos.
Devuelve un iterador al elemento encontrado, o al final (no incluido) de la matriz si no existe dicho elemento.
Puede leer más en documentación.

Vale la pena aclarar que el uso de estas funciones en un conjunto o conjunto múltiple no funciona en tiempo logarítmico debido a la falta de iteradores en las colecciones de acceso aleatorio anteriores.
Sin embargo, estas colecciones tienen métodos incorporados correspondientes (es decir, debe usarlos "a través de un punto").

Ejemplos:
  vector a = { 0, 1, 3, 5, 7 }; vector::iterarlo; it = límite_inferior(a.begin(), a.end(), 4); // *es == 5 it = límite_inferior(a.begin(), a.end(), 5); // *es == 5 it = límite_inferior(a.begin(), a.end(), 8); // it == a.end() it = límite_superior(a.begin(), a.end(), 4); // *es == 5 it = límite_superior(a.begin(), a.end(), 5); // *es == 7 it = límite_superior(a.begin(), a.end(), -1); // *es == 0 // al restar los iteradores, puede obtener el índice del elemento encontrado int ind = límite_inferior(a.begin(), a.end(), 4) - a.begin(); // indicador == 3 // necesita usar métodos en lugar de funciones para conjuntos y colecciones similares conjunto s{ 1, 3, 5 }; establecer::iterador sentarse; sentarse = s.lower_bound(3); // *sentarse == 3 sentarse = s.superior_límite(3); // *sentarse == 5  

único - una función que comprime todas las secuencias de elementos consecutivos idénticos en uno en tiempo lineal.
Como argumento, se pasan los límites de la matriz, dentro de los cuales es necesario aplicar compresión.
Se devuelve un iterador al nuevo extremo (no inclusivo) de la matriz. Debe tener cuidado con los elementos posteriores al nuevo final pero anteriores al antiguo, ya que tendrán un valor indefinido.
Puede leer más en documentación.

Si está utilizando esta función en un vector, es conveniente cambiar el tamaño utilizando el resultado devuelto (más información a continuación).

Ejemplos:
  vector a = { 3, 3, 3, 2, 3, 3, 1, 1, 4, 5, 5 }; único(a.begin(), a.end()); // a = [3, 2, 3, 1, 4, 5, ?, ?, ?, ?, ?] // es conveniente usar la función única // matriz auxiliar para compresión de coordenadas a = { 235, 10, 41, 10, 41, 41, 235, 500, 500 }; sort(a.begin(), a.end()); // un = [10, 10, 41, 41, 41, 235, 235, 500, 500] a.resize(unique(a.begin(), a.end()) - a.begin()); // un = [10, 41, 235, 500]  

fusionar: una función que fusiona dos matrices ordenadas, es decir, en tiempo lineal obtiene una matriz ordenada, que consta de los elementos de la primera y la segunda matriz.
Se necesitan 5 argumentos: dos límites para cada matriz y el límite izquierdo del destino (donde se colocarán los elementos de la matriz resultante).
Se pueden encontrar más detalles en la documentación.

Ejemplos: // las matrices de origen deben ordenarse vector a = { 1, 3, 5, 7 }; vector b = { 2, 4, 6 }; // necesita que el destino sea lo suficientemente grande vector c(7); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 3, 4, 5, 6, 7] // los elementos se pueden repetir a = {1, 2, 4, 4}; b = {2, 3, 3, 3, 4, 4}; c.redimensionar(10); merge(a.begin(), a.end(), b.begin(), b.end(), c.begin()); // c = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]  Esta función es muy útil en el contexto de la ordenación por fusión.

nth_element es una función que le permite encontrar el elemento nth en una matriz en orden ordenado en tiempo lineal.
La función toma el extremo izquierdo de la matriz, un iterador a la posición cuyo valor en orden ordenado se encuentra y el extremo derecho de la matriz.
Después de aplicar la función, el valor requerido se ubicará en el lugar indicado por el iterador, mientras que los valores restantes adquirirán un orden caótico, pero a la izquierda del n no habrá valores más que él, y a la derecha nada menos. Es decir, debe entenderse que esta función destruye el orden original de los elementos.
Puede leer más en la documentación (https://www.cplusplus.com/reference/algorithm/nth_element/).

Ejemplo: vector a = { 4, 0, 3, 9, 2, 1, 8, 5, 6, 7 }; // busca el elemento en el índice 4 // presta atención al orden de los argumentos nth_element(a.begin(), a.begin() + 4, a.end()); // un = [#, #, #, #, 4, $, $, $, $, $] // donde # <= 4 y 4 <= $  

Una permutación de longitud n es una colección ordenada sin repeticiones de los números 1, 2, ..., n. Por ejemplo, [3, 1, 2] y [5, 4, 3, 2, 1] son ​​permutaciones, pero [1, 2, 1, 3] y [1, 2, 4] no lo son.

Si la tarea se reduce al hecho de que es necesario iterar sobre todas las permutaciones de longitud n, entonces puede usar un mecanismo conveniente en C ++, que se llama "next_permutation".

Puede leer más sobre esto en documentación, pero el punto es que esta función cambia la matriz pasada a la permutación posterior en orden lexicográfico (que generalmente es claro y su nombre).

Para usar next_permutation, debe incluir la biblioteca de algoritmos (es decir, escriba #include <algorithm> al comienzo del programa)

Ejemplos: vectorarr; matriz = { 1, 2, 3 }; // la matriz es [1, 2, 3] next_permutation(arr.begin(), arr.end()); // pasar todo el arreglo a la función // la matriz ahora es [1, 3, 2] matriz = { 2, 3, 1 }; // la matriz es [2, 3, 1] next_permutation(arr.begin(), arr.end()); // pasar todo el arreglo a la función // la matriz ahora es [3, 1, 2] next_permutation(arr.begin() + 1, arr.begin() + 3); // es posible aplicar una función a una parte de una matriz, pero en la práctica esto rara vez es necesario // la matriz ahora es [3, 2, 1]
En este caso, la función tiene un valor de retorno booleano que es verdadero si se generó la siguiente permutación y falso si no hubo ninguna (el caso en que se pasa a la función la máxima permutación en orden lexicográfico).
Esto hace posible usar la función en un bucle, lo que nos permitirá iterar sobre todas las permutaciones a la vez. Debido a la indexación 0, en la práctica suele ser más conveniente trabajar con una permutación de números de 0 a n - 1, aunque una permutación contiene formalmente números de 1 a n. Pero, afortunadamente, esto no conduce a superposiciones adicionales en el código, porque la función next_permutation está adaptada a permutaciones indexadas en 0 (e incluso elementos duplicados en una matriz, pero puede encontrar más por su cuenta).

En general, el código para iterar sobre todas las permutaciones tiene este aspecto:   interno; // tamaño de la permutación vectorperm(n); // perm es la abreviatura de "permutación", es decir "permutación" para (int i = 0; i < n; i++) permanente[i] = i; // inicializa la permutación inicial 0, 1, ..., n - 1 hacer { // dentro del bucle procesamos la permutación actual } while (next_permutation(perm.begin(), perm.end())); // si no hay permutación siguiente, finaliza el bucle

Este código se ejecuta en O(n! * f(n)), donde f(n) es el tiempo que le lleva procesar una permutación en particular.