C++
Standaard bibliotheekalgoritmen
Zoeken…
std :: for_each
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);
Effecten:
Geldt f het resultaat van elke iterator dereferentie in het bereik [first, last) vanaf first en gaan tot last - 1 .
parameters:
first, last - het bereik waarop f moet worden toegepast.
f - opvraagbaar object dat wordt toegepast op het resultaat van derefereren van elke iterator in het bereik [first, last) .
Winstwaarde:
f (tot C ++ 11) en std::move(f) (sinds C ++ 11).
complexiteit:
Geldt f precies als last - first keer.
Voorbeeld:
std::vector<int> v { 1, 2, 4, 8, 16 };
std::for_each(v.begin(), v.end(), [](int elem) { std::cout << elem << " "; });
Past de gegeven functie toe voor elk element van de vector v drukt dit element af naar 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 );
Effecten:
Schuif de gegevensreeks van het bereik [eerste, laatste) naar de volgende lexicografisch hogere permutatie. Als cmpFun is opgegeven, is de permutatieregel aangepast.
parameters:
first - het begin van het te permuteren bereik, inclusief
last - het einde van het te permuteren bereik, exclusief
Winstwaarde:
Retourneert true als een dergelijke permutatie bestaat.
Anders wordt het bereik omgezet in de lexicografisch kleinste permutatie en wordt false geretourneerd.
complexiteit:
O (n), n is de afstand van first tot last .
Voorbeeld :
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() ) );
print alle permutatiegevallen van 1,2,3 in lexicografisch toenemende volgorde.
output:
123
132
213
231
312
321
std :: accumuleren
Gedefinieerd in kop <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)
Effecten:
std :: accumuleren voert vouwbewerking uit met behulp van de f functie op bereik [first, last) beginnend met init als accumulatorwaarde.
In feite is het equivalent van:
T acc = init;
for (auto it = first; first != last; ++it)
acc = f(acc, *it);
return acc;
In versie (1) wordt operator+ gebruikt in plaats van f , dus accumuleren over container is equivalent aan som van containerelementen.
parameters:
first, last - het bereik waarop f moet worden toegepast.
init - beginwaarde van de accumulator.
f - binaire vouwfunctie.
Winstwaarde:
Geaccumuleerde waarde van f toepassingen.
complexiteit:
O (n × k) , waarbij n de afstand van first tot last , O (k) is de complexiteit van de f functie.
Voorbeeld:
Eenvoudig somvoorbeeld:
std::vector<int> v { 2, 3, 4 };
auto sum = std::accumulate(v.begin(), v.end(), 1);
std::cout << sum << std::endl;
Output:
10
Converteer cijfers naar nummer:
class Converter {
public:
int operator()(int a, int d) const { return a * 10 + d; }
};
en later
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;
Output:
123
std :: vondst
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
Effecten
Vindt het eerste optreden van val binnen het bereik [eerste, laatste)
parameters
first => iterator wijzend naar het begin van het bereik last => iterator wijzend naar het einde van het bereik val => De waarde die moet worden gevonden binnen het bereik
terugkeer
Een iterator die verwijst naar het eerste element binnen het bereik dat gelijk is (==) aan val, de iterator wijst naar de duur als val niet wordt gevonden.
Voorbeeld
#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;
}
uitgang
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);
Effecten
Telt het aantal elementen dat gelijk is aan val
parameters
first => iterator die naar het begin van het bereik wijst
last => iterator die naar het einde van het bereik wijst
val => Het voorkomen van deze waarde in het bereik wordt geteld
terugkeer
Het aantal elementen in het bereik dat gelijk is (==) aan val.
Voorbeeld
#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;
}
uitgang
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);
Effecten
Telt het aantal elementen in een bereik waarvoor een opgegeven predikaatfunctie waar is
parameters
first => iterator wijst naar het begin van het bereik last => iterator wijst naar het einde van het bereik red => predikaatfunctie (retourneert true of false)
terugkeer
Het aantal elementen binnen het opgegeven bereik waarvoor de predikaatfunctie true retourneerde.
Voorbeeld
#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;
}
uitgang
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);
Effecten
Zoekt het eerste element in een bereik waarvoor de predikaatfunctie pred true retourneert.
parameters
first => iterator wijst naar het begin van het bereik last => iterator wijst naar het einde van het bereik pred => predikaatfunctie (retourneert true of false)
terugkeer
Een iterator die verwijst naar het eerste element binnen het bereik waarvoor de predikaatfunctie pred waar retourneert. De iterator wijst naar de laatste als val niet wordt gevonden
Voorbeeld
#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;
}
uitgang
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);
Effecten
Hiermee wordt het minimumelement in een bereik gevonden
parameters
first - iterator die naar het begin van het bereik wijst
last - iterator wijst naar het einde van het bereik comp - een functiepointer of functieobject dat twee argumenten aanneemt en waar of onwaar retourneert om aan te geven of argument kleiner is dan argument 2. Deze functie mag geen invoer wijzigen
terugkeer
Iterator tot het minimale element in het bereik
ingewikkeldheid
Lineair in één minder dan het aantal vergeleken elementen.
Voorbeeld
#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;
}
uitgang
min int from default: 6
min pair from PairLessThanFunction: 2
Std :: nth_element gebruiken om de mediaan (of andere kwantielen) te vinden
De std::nth_element algoritme duurt drie iterators: een iterator naar het begin, n e plaats, en het einde. Zodra de functie terugkeert, is het n de element (in volgorde) het n kleinste element. (De functie heeft uitgebreidere overbelastingen, bijv. Sommige nemen vergelijkingsfactoren; zie de bovenstaande link voor alle variaties.)
Opmerking Deze functie is zeer efficiënt - het heeft een lineaire complexiteit.
Laten we voor dit voorbeeld de mediaan van een reeks met lengte n definiëren als het element dat zich in positie ⌈n / 2⌉ zou bevinden. De mediaan van een reeks met lengte 5 is bijvoorbeeld het op twee na kleinste element, evenals de mediaan van een reeks met lengte 6.
Om deze functie te gebruiken om de mediaan te vinden, kunnen we het volgende gebruiken. Stel dat we beginnen
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].
Om de pde vinden -kwantiel , zouden we een aantal van de lijnen boven te wijzigen:
const std::size_t pos = p * std::distance(b, e);
std::advance(nth, pos);
en zoek de kwantiel op positie pos .
