C++
Algoritmos de la biblioteca estándar
Buscar..
std :: for_each
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);
Efectos:
Aplica f al resultado de la desreferenciación de todos los iteradores en el rango [first, last) partir del first y continúa hasta el last - 1 .
Parámetros:
first, last - el rango para aplicar f a.
f - objeto llamable que se aplica al resultado de la anulación de la referencia de cada iterador en el rango [first, last) .
Valor de retorno:
f (hasta C ++ 11) y std::move(f) (desde C ++ 11).
Complejidad:
Se aplica f exactamente el last - first vez.
Ejemplo:
std::vector<int> v { 1, 2, 4, 8, 16 };
std::for_each(v.begin(), v.end(), [](int elem) { std::cout << elem << " "; });
Aplica la función dada para cada elemento del vector v imprimiendo este elemento a la stdout .
std :: next_permutation
template< class Iterator >
bool next_permutation( Iterator first, Iterator last );
template< class Iterator, class Compare >
bool next_permutation( Iterator first, Iterator last, Compare cmpFun );
Efectos:
Tamice la secuencia de datos del rango [primero, último) en la siguiente permutación lexicográficamente más alta. Si se proporciona cmpFun , la regla de permutación se personaliza.
Parámetros:
first - el comienzo del rango a permutar, inclusive
last - el final del rango a ser permutado, exclusivo
Valor de retorno:
Devuelve true si existe tal permutación.
De lo contrario, el rango se cambia a la permutación lexicográficamente más pequeña y devuelve false.
Complejidad:
O (n), n es la distancia del first al last .
Ejemplo :
std::vector< int > v { 1, 2, 3 };
do
{
for( int i = 0; i < v.size(); i += 1 )
{
std::cout << v[i];
}
std::cout << std::endl;
}while( std::next_permutation( v.begin(), v.end() ) );
Imprima todos los casos de permutación de 1,2,3 en orden lexicográficamente creciente.
salida:
123
132
213
231
312
321
std :: acumular
Definido en el encabezado <numeric>
template<class InputIterator, class T>
T accumulate(InputIterator first, InputIterator last, T init); // (1)
template<class InputIterator, class T, class BinaryOperation>
T accumulate(InputIterator first, InputIterator last, T init, BinaryOperation f); // (2)
Efectos:
std :: Se acumula realiza la operación de plegado usando la función f en el rango [first, last) comenzando con init como valor acumulador.
Efectivamente es equivalente a:
T acc = init;
for (auto it = first; first != last; ++it)
acc = f(acc, *it);
return acc;
En la versión (1) el operator+ se usa en lugar de f , por lo que acumular sobre el contenedor es equivalente a la suma de los elementos del contenedor.
Parámetros:
first, last - el rango para aplicar f a.
init - valor inicial del acumulador.
f - función de plegado binario.
Valor de retorno:
Valor acumulado de f aplicaciones.
Complejidad:
O (n × k) , donde n es la distancia de la first a la last , O (k) es la complejidad de la función f .
Ejemplo:
Ejemplo de suma simple:
std::vector<int> v { 2, 3, 4 };
auto sum = std::accumulate(v.begin(), v.end(), 1);
std::cout << sum << std::endl;
Salida:
10
Convertir dígitos a número:
class Converter {
public:
int operator()(int a, int d) const { return a * 10 + d; }
};
y después
const int ds[3] = {1, 2, 3};
int n = std::accumulate(ds, ds + 3, 0, Converter());
std::cout << n << std::endl;
const std::vector<int> ds = {1, 2, 3};
int n = std::accumulate(ds.begin(), ds.end(),
0,
[](int a, int d) { return a * 10 + d; });
std::cout << n << std::endl;
Salida:
123
std :: encontrar
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
Efectos
Encuentra la primera aparición de val dentro del rango [primero, último)
Parámetros
first => iterador que apunta al comienzo del rango last => iterador que apunta al final del rango val => el valor a encontrar dentro del rango
Regreso
Un iterador que apunta al primer elemento dentro del rango que es igual (==) a val, el iterador apunta a durar si no se encuentra val.
Ejemplo
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
//create a vector
vector<int> intVec {4, 6, 8, 9, 10, 30, 55,100, 45, 2, 4, 7, 9, 43, 48};
//define iterators
vector<int>::iterator itr_9;
vector<int>::iterator itr_43;
vector<int>::iterator itr_50;
//calling find
itr_9 = find(intVec.begin(), intVec.end(), 9); //occurs twice
itr_43 = find(intVec.begin(), intVec.end(), 43); //occurs once
//a value not in the vector
itr_50 = find(intVec.begin(), intVec.end(), 50); //does not occur
cout << "first occurence of: " << *itr_9 << endl;
cout << "only occurence of: " << *itr_43 << Lendl;
/*
let's prove that itr_9 is pointing to the first occurence
of 9 by looking at the element after 9, which should be 10
not 43
*/
cout << "element after first 9: " << *(itr_9 + 1) << ends;
/*
to avoid dereferencing intVec.end(), lets look at the
element right before the end
*/
cout << "last element: " << *(itr_50 - 1) << endl;
return 0;
}
Salida
first occurence of: 9
only occurence of: 43
element after first 9: 10
last element: 48
std :: cuenta
template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count (InputIterator first, InputIterator last, const T& val);
Efectos
Cuenta el número de elementos que son iguales a val.
Parámetros
first => iterador que apunta al comienzo del rango
last => iterador que apunta al final del rango
val => La ocurrencia de este valor en el rango será contada
Regreso
El número de elementos en el rango que son iguales (==) a val.
Ejemplo
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int main(int argc, const char * argv[]) {
//create vector
vector<int> intVec{4,6,8,9,10,30,55,100,45,2,4,7,9,43,48};
//count occurences of 9, 55, and 101
size_t count_9 = count(intVec.begin(), intVec.end(), 9); //occurs twice
size_t count_55 = count(intVec.begin(), intVec.end(), 55); //occurs once
size_t count_101 = count(intVec.begin(), intVec.end(), 101); //occurs once
//print result
cout << "There are " << count_9 << " 9s"<< endl;
cout << "There is " << count_55 << " 55"<< endl;
cout << "There is " << count_101 << " 101"<< ends;
//find the first element == 4 in the vector
vector<int>::iterator itr_4 = find(intVec.begin(), intVec.end(), 4);
//count its occurences in the vector starting from the first one
size_t count_4 = count(itr_4, intVec.end(), *itr_4); // should be 2
cout << "There are " << count_4 << " " << *itr_4 << endl;
return 0;
}
Salida
There are 2 9s
There is 1 55
There is 0 101
There are 2 4
std :: count_if
template <class InputIterator, class UnaryPredicate>
typename iterator_traits<InputIterator>::difference_type
count_if (InputIterator first, InputIterator last, UnaryPredicate red);
Efectos
Cuenta el número de elementos en un rango para el que una función de predicado especificada es verdadera
Parámetros
first => iterador que apunta al principio del rango last => iterador que apunta al final del rango red => función de predicado (devuelve verdadero o falso)
Regreso
El número de elementos dentro del rango especificado para el cual la función de predicado devolvió verdadero.
Ejemplo
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
Define a few functions to use as predicates
*/
//return true if number is odd
bool isOdd(int i){
return i%2 == 1;
}
//functor that returns true if number is greater than the value of the constructor parameter provided
class Greater {
int _than;
public:
Greater(int th): _than(th){}
bool operator()(int i){
return i > _than;
}
};
int main(int argc, const char * argv[]) {
//create a vector
vector<int> myvec = {1,5,8,0,7,6,4,5,2,1,5,0,6,9,7};
//using a lambda function to count even numbers
size_t evenCount = count_if(myvec.begin(), myvec.end(), [](int i){return i % 2 == 0;}); // >= C++11
//using function pointer to count odd number in the first half of the vector
size_t oddCount = count_if(myvec.begin(), myvec.end()- myvec.size()/2, isOdd);
//using a functor to count numbers greater than 5
size_t greaterCount = count_if(myvec.begin(), myvec.end(), Greater(5));
cout << "vector size: " << myvec.size() << endl;
cout << "even numbers: " << evenCount << " found" << endl;
cout << "odd numbers: " << oddCount << " found" << endl;
cout << "numbers > 5: " << greaterCount << " found"<< endl;
return 0;
}
Salida
vector size: 15
even numbers: 7 found
odd numbers: 4 found
numbers > 5: 6 found
std :: find_if
template <class InputIterator, class UnaryPredicate>
InputIterator find_if (InputIterator first, InputIterator last, UnaryPredicate pred);
Efectos
Encuentra el primer elemento en un rango para el cual la función de predicado pred devuelve true.
Parámetros
first => iterador que apunta al principio del rango last => iterador que apunta al final del rango pred => función de predicado (devuelve verdadero o falso)
Regreso
Un iterador que apunta al primer elemento dentro del rango para el que predice la función predate devuelve true para. El iterador apunta a durar si no se encuentra val
Ejemplo
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
/*
define some functions to use as predicates
*/
//Returns true if x is multiple of 10
bool multOf10(int x) {
return x % 10 == 0;
}
//returns true if item greater than passed in parameter
class Greater {
int _than;
public:
Greater(int th):_than(th){
}
bool operator()(int data) const
{
return data > _than;
}
};
int main()
{
vector<int> myvec {2, 5, 6, 10, 56, 7, 48, 89, 850, 7, 456};
//with a lambda function
vector<int>::iterator gt10 = find_if(myvec.begin(), myvec.end(), [](int x){return x>10;}); // >= C++11
//with a function pointer
vector<int>::iterator pow10 = find_if(myvec.begin(), myvec.end(), multOf10);
//with functor
vector<int>::iterator gt5 = find_if(myvec.begin(), myvec.end(), Greater(5));
//not Found
vector<int>::iterator nf = find_if(myvec.begin(), myvec.end(), Greater(1000)); // nf points to myvec.end()
//check if pointer points to myvec.end()
if(nf != myvec.end()) {
cout << "nf points to: " << *nf << endl;
}
else {
cout << "item not found" << endl;
}
cout << "First item > 10: " << *gt10 << endl;
cout << "First Item n * 10: " << *pow10 << endl;
cout << "First Item > 5: " << *gt5 << endl;
return 0;
}
Salida
item not found
First item > 10: 56
First Item n * 10: 10
First Item > 5: 6
std :: min_element
template <class ForwardIterator>
ForwardIterator min_element (ForwardIterator first, ForwardIterator last);
template <class ForwardIterator, class Compare>
ForwardIterator min_element (ForwardIterator first, ForwardIterator last,Compare comp);
Efectos
Encuentra el elemento mínimo en un rango.
Parámetros
first - iterador que apunta al comienzo del rango
last : iterador que apunta al final del rango comp : un puntero de función u objeto de función que toma dos argumentos y devuelve verdadero o falso, lo que indica si el argumento es menor que el argumento 2. Esta función no debe modificar las entradas
Regreso
Iterador al elemento mínimo en el rango.
Complejidad
Lineal en uno menos que el número de elementos comparados.
Ejemplo
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility> //to use make_pair
using namespace std;
//function compare two pairs
bool pairLessThanFunction(const pair<string, int> &p1, const pair<string, int> &p2)
{
return p1.second < p2.second;
}
int main(int argc, const char * argv[]) {
vector<int> intVec {30,200,167,56,75,94,10,73,52,6,39,43};
vector<pair<string, int>> pairVector = {make_pair("y", 25), make_pair("b", 2), make_pair("z", 26), make_pair("e", 5) };
// default using < operator
auto minInt = min_element(intVec.begin(), intVec.end());
//Using pairLessThanFunction
auto minPairFunction = min_element(pairVector.begin(), pairVector.end(), pairLessThanFunction);
//print minimum of intVector
cout << "min int from default: " << *minInt << endl;
//print minimum of pairVector
cout << "min pair from PairLessThanFunction: " << (*minPairFunction).second << endl;
return 0;
}
Salida
min int from default: 6
min pair from PairLessThanFunction: 2
Usando std :: nth_element para encontrar la mediana (u otros cuantiles)
El algoritmo std::nth_element toma tres iteradores: un iterador al principio, a la posición n y al final. Una vez que la función devuelve, el n-ésimo elemento (por orden) será el n-ésimo elemento más pequeño. (La función tiene sobrecargas más elaboradas, p. Ej., Algunos tienen funciones de comparación; consulte el enlace anterior para ver todas las variaciones).
Nota Esta función es muy eficiente, tiene una complejidad lineal.
Por el bien de este ejemplo, definamos la mediana de una secuencia de longitud n como el elemento que estaría en la posición ⌈n / 2⌉. Por ejemplo, la mediana de una secuencia de longitud 5 es el tercer elemento más pequeño, y también lo es la mediana de una secuencia de longitud 6.
Para usar esta función para encontrar la mediana, podemos usar lo siguiente. Digamos que empezamos con
std::vector<int> v{5, 1, 2, 3, 4};
std::vector<int>::iterator b = v.begin();
std::vector<int>::iterator e = v.end();
std::vector<int>::iterator med = b;
std::advance(med, v.size() / 2);
// This makes the 2nd position hold the median.
std::nth_element(b, med, e);
// The median is now at v[2].
Para encontrar el p th cuantil , cambiaríamos algunas de las líneas de arriba:
const std::size_t pos = p * std::distance(b, e);
std::advance(nth, pos);
y buscar el cuantil en pos .
