C++
Algoritmi di libreria standard
Ricerca…
std :: for_each
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);
effetti:
Applica f al risultato del dereferenziamento di ogni iteratore nell'intervallo [first, last) iniziando dal first e procedendo fino last - 1 .
parametri:
first, last - l'intervallo per applicare f a.
f - oggetto richiamabile che viene applicato al risultato del dereferenziamento di ogni iteratore nell'intervallo [first, last) .
Valore di ritorno:
f (fino a C ++ 11) e std::move(f) (dal C ++ 11).
Complessità:
Applica f esattamente l' last - first volte.
Esempio:
std::vector<int> v { 1, 2, 4, 8, 16 };
std::for_each(v.begin(), v.end(), [](int elem) { std::cout << elem << " "; });
Applica la funzione data per ogni elemento del vettore v stampando questo elemento su 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 );
effetti:
Setaccia la sequenza di dati dell'intervallo [primo, ultimo] nella successiva permutazione lessicograficamente più alta. Se viene fornito cmpFun , la regola di permutazione è personalizzata.
parametri:
first : l'inizio dell'intervallo da permutare, inclusivo
last - la fine della gamma deve essere permutata, esclusiva
Valore di ritorno:
Restituisce vero se tale permutazione esiste.
Altrimenti l'intervallo viene scambiato con la permutazione lessicograficamente più piccola e restituisce false.
Complessità:
O (n), n è la distanza dal first last .
Esempio :
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() ) );
stampare tutti i casi di permutazione di 1,2,3 in ordine crescente lessicograficamente.
produzione:
123
132
213
231
312
321
std :: accumulano
Definito nell'intestazione <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)
effetti:
std :: accumula esegue l'operazione di piega usando la funzione f nell'intervallo [first, last) iniziando con init come valore dell'accumulatore.
In effetti è equivalente a:
T acc = init;
for (auto it = first; first != last; ++it)
acc = f(acc, *it);
return acc;
Nella versione (1) l' operator+ è usato al posto di f , quindi accumulare sul contenitore equivale alla somma degli elementi del contenitore.
parametri:
first, last - l'intervallo per applicare f a.
init - valore iniziale dell'accumulatore.
f - funzione di piegatura binaria.
Valore di ritorno:
Valore accumulato di domande f .
Complessità:
O (n × k) , dove n è la distanza dal first last , O (k) è la complessità della funzione f .
Esempio:
Esempio di somma semplice:
std::vector<int> v { 2, 3, 4 };
auto sum = std::accumulate(v.begin(), v.end(), 1);
std::cout << sum << std::endl;
Produzione:
10
Converti cifre in numero:
class Converter {
public:
int operator()(int a, int d) const { return a * 10 + d; }
};
e più tardi
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;
Produzione:
123
std :: trovare
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
effetti
Trova la prima occorrenza di val all'interno dell'intervallo [primo, ultimo]
parametri
first => iteratore che punta all'inizio dell'intervallo last => iteratore che punta alla fine dell'intervallo val => Il valore da trovare nell'intervallo
Ritorno
Un iteratore che punta al primo elemento all'interno dell'intervallo uguale (==) a val, l'iteratore punta a durare se val non viene trovato.
Esempio
#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;
}
Produzione
first occurence of: 9
only occurence of: 43
element after first 9: 10
last element: 48
std :: count
template <class InputIterator, class T>
typename iterator_traits<InputIterator>::difference_type
count (InputIterator first, InputIterator last, const T& val);
effetti
Conta il numero di elementi uguali a val
parametri
first => iteratore che punta all'inizio della gamma
last => iteratore che punta alla fine dell'intervallo
val => Verrà conteggiato il verificarsi di questo valore nell'intervallo
Ritorno
Il numero di elementi nell'intervallo uguali (==) a val.
Esempio
#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;
}
Produzione
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);
effetti
Conta il numero di elementi in un intervallo per il quale una funzione di predicato specificata è vera
parametri
first => iteratore che punta all'inizio dell'intervallo last => iteratore che punta alla fine dell'intervallo red => funzione predicato (restituisce vero o falso)
Ritorno
Il numero di elementi nell'intervallo specificato per il quale la funzione del predicato ha restituito true.
Esempio
#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;
}
Produzione
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);
effetti
Trova il primo elemento in un intervallo per il quale la funzione predicato pred restituisce true.
parametri
first => iteratore che punta all'inizio dell'intervallo last => iteratore che punta alla fine dell'intervallo pred => funzione predicato (restituisce vero o falso)
Ritorno
Un iteratore che punta al primo elemento all'interno dell'intervallo, la funzione predicato per cui predice restituisce true. L'iteratore punta a durare se val non viene trovato
Esempio
#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;
}
Produzione
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);
effetti
Trova l'elemento minimo in un intervallo
parametri
first - iteratore che punta all'inizio della gamma
last - iteratore che punta alla fine dell'intervallo comp - un puntatore di funzione o oggetto di funzione che accetta due argomenti e restituisce vero o falso indicando se l'argomento è inferiore all'argomento 2. Questa funzione non dovrebbe modificare gli input
Ritorno
Iteratore sull'elemento minimo dell'intervallo
Complessità
Lineare in uno in meno rispetto al numero di elementi confrontati.
Esempio
#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;
}
Produzione
min int from default: 6
min pair from PairLessThanFunction: 2
Uso di std :: nth_element per trovare la mediana (o altri quantili)
Lo std::nth_element algoritmo prende tre iteratori: un iteratore all'inizio, n ° posizione, e la fine. Una volta che la funzione ritorna, il n elemento (dell'ordine) sarà il n ° elemento più piccolo. (La funzione ha sovraccarichi più elaborati, ad esempio alcuni che assumono funzioni di comparazione, vedi il link sopra per tutte le varianti.)
Nota Questa funzione è molto efficiente - ha una complessità lineare.
Per questo esempio, definiamo la mediana di una sequenza di lunghezza n come l'elemento che sarebbe in posizione ⌈n / 2⌉. Ad esempio, la mediana di una sequenza di lunghezza 5 è il terzo elemento più piccolo, e quindi è la mediana di una sequenza di lunghezza 6.
Per utilizzare questa funzione per trovare la mediana, possiamo usare quanto segue. Diciamo che iniziamo 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].
Per trovare il p esimo quantile , vorremmo cambiare alcune delle linee di cui sopra:
const std::size_t pos = p * std::distance(b, e);
std::advance(nth, pos);
e cerca il quantile in posizione pos .
