C++
Algorithmes de bibliothèque standard
Recherche…
std :: for_each
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);
Effets:
Applique f à la suite de déréférencement chaque itération dans l'intervalle [first, last) à partir de first et de procéder à last - 1 .
Paramètres:
first, last - la gamme d'appliquer f à.
f - objet appelable qui est appliqué au résultat du déréférencement de chaque itérateur de la plage [first, last) .
Valeur de retour:
f (jusqu'à C ++ 11) et std::move(f) (depuis C ++ 11).
Complexité:
Applique f exactement last - first fois.
Exemple:
std::vector<int> v { 1, 2, 4, 8, 16 };
std::for_each(v.begin(), v.end(), [](int elem) { std::cout << elem << " "; });
Applique la fonction donnée à chaque élément du vecteur v imprimant cet élément à 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 );
Effets:
Tamisez la séquence de données de la plage [première, dernière] dans la prochaine permutation lexicographique supérieure. Si cmpFun est fourni, la règle de permutation est personnalisée.
Paramètres:
first - le début de la plage à permuter, inclusivement
last - la fin de la gamme à permuter, exclusive
Valeur de retour:
Renvoie true si une telle permutation existe.
Sinon, la plage est convertie en la plus petite permutation lexicographique et renvoie false.
Complexité:
O (n), n est la distance entre le first et le last .
Exemple :
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() ) );
imprimer tous les cas de permutation de 1,2,3 dans l'ordre croissant de lexicographie.
sortie:
123
132
213
231
312
321
std :: accumuler
Défini dans l'en-tête <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)
Effets:
std :: accumulate exécute une opération de pliage en utilisant la fonction f sur la plage [first, last) commençant par init tant que valeur de l'accumulateur.
En effet c'est l'équivalent de:
T acc = init;
for (auto it = first; first != last; ++it)
acc = f(acc, *it);
return acc;
Dans la version (1), operator+ est utilisé à la place de f , donc accumuler sur le conteneur est équivalent à la somme des éléments du conteneur.
Paramètres:
first, last - la gamme d'appliquer f à.
init - valeur initiale de l'accumulateur.
f - fonction de pliage binaire.
Valeur de retour:
Valeur cumulée des applications f .
Complexité:
O (n × k) , où n est la distance entre le first et le last , O (k) est la complexité de la fonction f .
Exemple:
Exemple de somme simple:
std::vector<int> v { 2, 3, 4 };
auto sum = std::accumulate(v.begin(), v.end(), 1);
std::cout << sum << std::endl;
Sortie:
10
Convertir les chiffres en nombre:
class Converter {
public:
int operator()(int a, int d) const { return a * 10 + d; }
};
et ensuite
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;
Sortie:
123
std :: find
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
Effets
Trouve la première occurrence de val dans l'intervalle [premier, dernier]
Paramètres
first => itérateur pointant au début de la plage last => itérateur pointant vers la fin de la plage val => valeur à trouver dans la plage
Revenir
Un itérateur qui pointe vers le premier élément dans la plage égale à = (==), l'itérateur pointe sur last si val est introuvable.
Exemple
#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;
}
Sortie
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);
Effets
Compte le nombre d'éléments égaux à val
Paramètres
first => itérateur pointant vers le début de la plage
last => itérateur pointant vers la fin de la plage
val => L'occurrence de cette valeur dans la plage sera comptée
Revenir
Le nombre d'éléments compris dans la plage (==) à val.
Exemple
#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;
}
Sortie
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);
Effets
Compte le nombre d'éléments dans une plage pour laquelle une fonction de prédicat spécifiée est vraie
Paramètres
first => itérateur pointant vers le début de la plage last => itérateur pointant vers la fin de la plage red => fonction du prédicat (retourne true ou false)
Revenir
Nombre d'éléments dans la plage spécifiée pour lesquels la fonction de prédicat a renvoyé la valeur true.
Exemple
#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;
}
Sortie
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);
Effets
Trouve le premier élément d'une plage pour laquelle la fonction de prédicat pred renvoie true.
Paramètres
first => itérateur pointant vers le début de la plage last => itérateur pointant vers la fin de la plage pred => fonction prédicat (retourne true ou false)
Revenir
Un itérateur qui pointe vers le premier élément de la plage dans laquelle la fonction de prédicat pred renvoie true pour. L'itérateur pointe sur last si val est introuvable
Exemple
#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;
}
Sortie
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);
Effets
Trouve l'élément minimum dans une plage
Paramètres
first - itérateur pointant vers le début de la plage
last -iterator pointant vers la fin de la plage comp - un pointeur de fonction ou un objet fonction qui prend deux arguments et renvoie true ou false indiquant si l'argument est inférieur à l'argument 2. Cette fonction ne doit pas modifier les entrées
Revenir
Itérateur à l'élément minimum de la gamme
Complexité
Linéaire en un moins que le nombre d'éléments comparés.
Exemple
#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;
}
Sortie
min int from default: 6
min pair from PairLessThanFunction: 2
Utiliser std :: nth_element pour trouver la médiane (ou d'autres quantiles)
L'algorithme std::nth_element prend trois itérateurs: un itérateur au début, n ème position et fin. Une fois que la fonction retourne, le n ième élément (par ordre) sera le n ième élément le plus petit. (La fonction a des surcharges plus élaborées, par exemple, certains prenant des foncteurs de comparaison; voir le lien ci-dessus pour toutes les variations.)
Remarque Cette fonction est très efficace - elle présente une complexité linéaire.
Par souci de cet exemple, définissons la médiane d'une séquence de longueur n en tant qu'élément qui serait en position ⌈n / 2⌉. Par exemple, la médiane d'une séquence de longueur 5 est le troisième élément le plus petit, de même que la médiane d'une séquence de longueur 6.
Pour utiliser cette fonction pour trouver la médiane, nous pouvons utiliser ce qui suit. Disons que nous commençons avec
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].
Pour trouver le p e quantile , nous changerions quelques - unes des lignes ci - dessus:
const std::size_t pos = p * std::distance(b, e);
std::advance(nth, pos);
et recherchez le quantile à la position pos .
