C++
Standard-Bibliotheksalgorithmen
Suche…
std :: for_each
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);
Auswirkungen:
Wendet f auf das Ergebnis der Dereferenzierung jedes Iterators im Bereich [first, last) beginnend mit dem first und dem last - 1 .
Parameter:
first, last - der Bereich, auf den f soll.
f - Callable Object, das auf das Ergebnis der Dereferenzierung jedes Iterators im Bereich [first, last) angewendet wird.
Rückgabewert:
f (bis C ++ 11) und std::move(f) (seit C ++ 11).
Komplexität:
Wendet f genau das last - first Mal an.
Beispiel:
std::vector<int> v { 1, 2, 4, 8, 16 };
std::for_each(v.begin(), v.end(), [](int elem) { std::cout << elem << " "; });
Wendet die angegebene Funktion für jedes Element des Vektors v , das dieses Element auf 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 );
Auswirkungen:
Verschieben Sie die Datenfolge des Bereichs [first, last] in die nächste lexikographisch höhere Permutation. Wenn cmpFun bereitgestellt wird, wird die Permutationsregel angepasst.
Parameter:
first - der Beginn des zu permutierenden Bereichs einschließlich
last - das Ende des zu permutierenden Bereichs, exklusiv
Rückgabewert:
Gibt true zurück, wenn eine solche Permutation vorhanden ist.
Andernfalls wird der Bereich auf die lexikographisch kleinste Permutation getauscht und false zurückgegeben.
Komplexität:
O (n), n ist der Abstand vom first bis zum last .
Beispiel :
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() ) );
Drucke alle Permutationsfälle von 1,2,3 in lexikographisch ansteigender Reihenfolge.
Ausgabe:
123
132
213
231
312
321
std :: akkumulieren
Definiert in Kopfzeile <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)
Auswirkungen:
std :: Accumulate führt eine Fold- Operation aus, wobei die f Funktion im Bereich [first, last) beginnend mit init als Akkumulatorwert verwendet wird.
Im Grunde entspricht es:
T acc = init;
for (auto it = first; first != last; ++it)
acc = f(acc, *it);
return acc;
In Version (1) wird der operator+ anstelle von f , sodass das Sammeln über Container der Summe der Containerelemente entspricht.
Parameter:
first, last - der Bereich, auf den f soll.
init - Anfangswert des Akkus.
f - binäre Faltfunktion.
Rückgabewert:
Gesamtwert der f Anwendungen.
Komplexität:
O (n × k) , wobei n der Abstand vom first bis zum last , O (k) die Komplexität der f Funktion.
Beispiel:
Einfaches Summenbeispiel:
std::vector<int> v { 2, 3, 4 };
auto sum = std::accumulate(v.begin(), v.end(), 1);
std::cout << sum << std::endl;
Ausgabe:
10
Ziffern in Zahl umrechnen:
class Converter {
public:
int operator()(int a, int d) const { return a * 10 + d; }
};
und später
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;
Ausgabe:
123
std :: find
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
Auswirkungen
Findet das erste Vorkommen von val innerhalb des Bereichs [first, last)
Parameter
first => Iterator zeigt auf den Anfang des Bereichs. last => Iterator zeigt auf das Ende des Bereichs. val => Der zu val Wert innerhalb des Bereichs
Rückkehr
Ein Iterator, der auf das erste Element innerhalb des Bereichs zeigt, der gleich (==) mit val ist. Der Iterator zeigt auf das letzte Element, wenn val nicht gefunden wird.
Beispiel
#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;
}
Ausgabe
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);
Auswirkungen
Zählt die Anzahl der Elemente, die val entsprechen
Parameter
first => Iterator zeigt auf den Anfang des Bereichs
last => Iterator zeigt auf das Ende des Bereichs
val => Das Vorkommen dieses Wertes im Bereich wird gezählt
Rückkehr
Die Anzahl der Elemente im Bereich, die gleich (==) bis val sind.
Beispiel
#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;
}
Ausgabe
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);
Auswirkungen
Zählt die Anzahl der Elemente in einem Bereich, für die eine angegebene Prädikatfunktion wahr ist
Parameter
first => Iterator zum Anfang des Bereichs zeigt last => Iterator auf das Ende des Bereichs zeigt red => Prädikatfunktion (gibt wahr oder falsch)
Rückkehr
Die Anzahl der Elemente innerhalb des angegebenen Bereichs, für die die Prädikatfunktion true zurückgegeben hat.
Beispiel
#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;
}
Ausgabe
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);
Auswirkungen
Findet das erste Element in einem Bereich, für das die Prädikatfunktion pred true zurückgibt.
Parameter
first => Iterator zum Anfang des Bereichs zeigt last => Iterator auf das Ende des Bereichs zeigt pred => Prädikatfunktion (gibt wahr oder falsch)
Rückkehr
Ein Iterator, der auf das erste Element innerhalb des Bereichs zeigt, für den die Prädikatfunktion pred true zurückgibt. Der Iterator zeigt auf den letzten Punkt, wenn val nicht gefunden wird
Beispiel
#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;
}
Ausgabe
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);
Auswirkungen
Findet das minimale Element in einem Bereich
Parameter
first Iterator zeigt auf den Anfang des Bereichs
last iterator, der auf das Ende des Bereichs comp - ein Funktionszeiger oder ein Funktionsobjekt, das zwei Argumente verwendet und true oder false zurückgibt, um anzugeben, ob das Argument weniger als Argument 2 ist
Rückkehr
Iterator auf das minimale Element im Bereich
Komplexität
Linear in einem weniger als die Anzahl der verglichenen Elemente.
Beispiel
#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;
}
Ausgabe
min int from default: 6
min pair from PairLessThanFunction: 2
Std :: nth_element verwenden, um den Median (oder andere Quantile) zu finden
Der std::nth_element Algorithmus benötigt drei Iteratoren: einen Iterator an den Anfang, die n- te Position und das Ende. Sobald die Funktion zurückkehrt, ist das n- te Element (in Reihenfolge) das n- te kleinste Element. (Die Funktion hat aufwendigere Überladungen, z. B. einige Vergleichsfunktionen; der Variationsbereich ist oben angegeben.)
Hinweis Diese Funktion ist sehr effizient - sie ist linear komplex.
In diesem Beispiel definieren wir den Median einer Sequenz der Länge n als das Element, das sich in Position ⌈n / 2⌉ befinden würde. Zum Beispiel ist der Median einer Sequenz der Länge 5 das drittkleinste Element und ebenso der Median einer Sequenz der Länge 6.
Um diese Funktion zum Finden des Medians zu verwenden, können wir Folgendes verwenden. Sagen wir, wir fangen mit an
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].
Um das p- te Quantil zu finden , würden wir einige der obigen Zeilen ändern:
const std::size_t pos = p * std::distance(b, e);
std::advance(nth, pos);
und suchen Sie das Quantil an Position pos .
