C++
Standardbibliotekalgoritmer
Sök…
std :: for_each
template<class InputIterator, class Function>
Function for_each(InputIterator first, InputIterator last, Function f);
effekter:
Gäller f för resultatet av dereferencing varje iterator i intervallet [first, last) börjar från first och fortsätter till last - 1 .
parametrar:
first, last - intervallet som ska tillämpas f till.
f - utrangbart objekt som tillämpas på resultatet av att återföra varje iterator inom området [first, last) .
Returvärde:
f (tills C ++ 11) och std::move(f) (sedan C ++ 11).
Komplexitet:
Gäller f exakt last - first gånger.
Exempel:
std::vector<int> v { 1, 2, 4, 8, 16 };
std::for_each(v.begin(), v.end(), [](int elem) { std::cout << elem << " "; });
Tillämpar den givna funktionen för varje element i vektorn v skriver ut detta element till 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 );
effekter:
Sikt datasekvensen för intervallet [först, sista) till nästa leksikografiskt högre permutation. Om cmpFun tillhandahålls anpassas permutationsregeln.
parametrar:
first - början på intervallet som ska permuteras, inklusive
last - slutet på intervallet som ska permuteras, exklusivt
Returvärde:
Returnerar sant om sådan permutation finns.
Annars byts intervallet till den leksikografiskt minsta permutationen och returnerar falsk.
Komplexitet:
O (n), n är avståndet från first till last .
Exempel :
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() ) );
skriv ut alla permutationsfall på 1,2,3 i leksikografiskt ökande ordning.
produktion:
123
132
213
231
312
321
std :: ackumulera
Definieras i rubriken <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)
effekter:
std :: ackumulering utför vikfunktion med f funktionen på området [first, last) börjar med init som ackumulatorvärde.
Effektivt motsvarar det:
T acc = init;
for (auto it = first; first != last; ++it)
acc = f(acc, *it);
return acc;
I version (1) används operator+ i stället för f , så ackumulering över behållare motsvarar summan av behållarelement.
parametrar:
first, last - intervallet som ska tillämpas f till.
init - ackumulatorns initiala värde.
f - binär vikningsfunktion.
Returvärde:
Ackumulerat värde för f applikationer.
Komplexitet:
O (n × k) , där n är avståndet från first till last , O (k) är komplexiteten för f funktionen.
Exempel:
Exempel på enkel summa:
std::vector<int> v { 2, 3, 4 };
auto sum = std::accumulate(v.begin(), v.end(), 1);
std::cout << sum << std::endl;
Produktion:
10
Konvertera siffror till nummer:
class Converter {
public:
int operator()(int a, int d) const { return a * 10 + d; }
};
och senare
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;
Produktion:
123
std :: find
template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);
effekter
Hitta den första förekomsten av val inom intervallet [först, sista)
parametrar
first => iterator som pekar på början av intervallet last => iterator som pekar till slutet av intervallet val => Värdet att hitta inom intervallet
Lämna tillbaka
En iterator som pekar på det första elementet inom området som är lika (==) till val, iteratorn pekar till sist om val inte hittas.
Exempel
#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;
}
Produktion
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);
effekter
Räknar antalet element som är lika med val
parametrar
first => iterator som pekar på början av intervallet
last => iterator som pekar mot slutet av intervallet
val => Förekomsten av detta värde i intervallet räknas
Lämna tillbaka
Antalet element i intervallet som är lika (==) till val.
Exempel
#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;
}
Produktion
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);
effekter
Räknar antalet element i ett intervall för vilket en specificerad predikatfunktion är sann
parametrar
first => iterator som pekar på början av intervallet last => iterator som pekar till slutet av intervallet red => predikatfunktion (returnerar sant eller fel)
Lämna tillbaka
Antalet element inom det specificerade intervallet för vilket predikatfunktionen returnerade sant.
Exempel
#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;
}
Produktion
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);
effekter
Hitta det första elementet i ett intervall för vilket predikatfunktionen pred returnerar sant.
parametrar
first => iterator som pekar på början av intervallet last => iterator som pekar mot slutet av intervallet pred => predikatfunktion (returnerar sant eller fel)
Lämna tillbaka
En iterator som pekar på det första elementet inom det område predikatfunktionen pred returnerar true för. Iteratorn pekar på sist om val inte hittas
Exempel
#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;
}
Produktion
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);
effekter
Hitta minsta element i ett intervall
parametrar
first - iterator som pekar på början av intervallet
last - iterator som pekar till slutet av intervallet comp - en funktion pekare eller funktionsobjekt som tar två argument och returnerar sant eller falskt indikerar huruvida argumentet är mindre än argument 2. Denna funktion bör inte ändra ingångar
Lämna tillbaka
Iterator till minsta element i intervallet
Komplexitet
Linjärt i ett mindre än antalet jämförda element.
Exempel
#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;
}
Produktion
min int from default: 6
min pair from PairLessThanFunction: 2
Använda std :: nth_element för att hitta median (eller andra kvantiteter)
std::nth_element algoritmen tar tre iteratorer: en iterator till början, n: e positionen och slutet. När funktionen återgår är det n: a elementet (efter ordning) det n: a minsta elementet. (Funktionen har mer detaljerade överbelastningar, t.ex. vissa som jämför jämförande funktorer; se ovanstående länk för alla variationer.)
Obs! Denna funktion är mycket effektiv - den har linjär komplexitet.
För detta exempel, låt oss definiera medianen för en sekvens med längd n som elementet som skulle vara i position ⌈n / 2⌉. Till exempel är medianen för en sekvens med längd 5 det tredje minsta elementet, och detsamma är medianen för en sekvens med längd 6.
För att använda denna funktion för att hitta median kan vi använda följande. Säg att vi börjar med
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].
För att hitta p- kvantilen , skulle vi ändra några av raderna ovan:
const std::size_t pos = p * std::distance(b, e);
std::advance(nth, pos);
och leta efter kvantilen vid position pos .
