C++
Standardowe algorytmy biblioteczne

std :: for_each

template<class InputIterator, class Function>
    Function for_each(InputIterator first, InputIterator last, Function f);

Efekty:

Stosuje f do wyniku dereferencji każdego iteratora w przedziale [first, last) zaczynając od first i przechodząc do last - 1 .

Parametry:

first, last - zakres zastosowania f celu.

f - wywoływalny obiekt, który jest stosowany do wyniku wyłuskiwania każdego iteratora w zakresie [first, last) .

Zwracana wartość:

f (do C ++ 11) i std::move(f) (od C ++ 11).

Złożoność:

Dotyczy f dokładnie last - first czasów.

Przykład:

std::vector<int> v { 1, 2, 4, 8, 16 };
std::for_each(v.begin(), v.end(), [](int elem) { std::cout << elem << " "; });

Stosuje podaną funkcję do każdego elementu wektora v stdout ten element na standardowe 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 );

Efekty:
Przesunąć sekwencję danych zakresu [pierwsza, ostatnia) do następnej leksykograficznie wyższej permutacji. Jeśli cmpFun , reguła permutacji jest dostosowywana.

Parametry:
first - początek zakresu, który ma być permutowany, włącznie
last - koniec zakresu do permutacji, wyłączny

Zwracana wartość:
Zwraca true, jeśli taka permutacja istnieje.
W przeciwnym razie zakres zostanie zamieniony na leksykograficznie najmniejszą permutację i zwróci false.

Złożoność:
O (n), n to odległość od first do last .

Przykład :

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() ) );

wydrukuj wszystkie przypadki permutacji 1,2,3 w porządku rosnącym leksykograficznie.
wynik:

123  
132
213
231
312
321

std :: akumuluj

Zdefiniowany w nagłówku <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)

Efekty:

std ::umulate wykonuje operację składania za pomocą funkcji f w zakresie [first, last) zaczynając od init jako wartości akumulatora.

Skutecznie odpowiada to:

T acc = init;
for (auto it = first; first != last; ++it)
    acc = f(acc, *it);
return acc;

W wersji (1) zamiast f stosuje się operator+ , więc kumulacja nad pojemnikiem jest równa sumie elementów kontenera.

Parametry:

first, last - zakres zastosowania f celu.
init - wartość początkowa akumulatora.
f - funkcja składania binarnego.

Zwracana wartość:

Skumulowana wartość aplikacji f .

Złożoność:

O (n × k) , gdzie n jest odległością od first do last , O (k) jest złożonością funkcji f .

Przykład:

Prosty przykład sumy:

std::vector<int> v { 2, 3, 4 };
auto sum = std::accumulate(v.begin(), v.end(), 1);
std::cout << sum << std::endl;

Wynik:

10

Konwertuj cyfry na liczbę:

class Converter {
public:
    int operator()(int a, int d) const { return a * 10 + d; }
};

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;

Wynik:

123

std :: find

template <class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val);

Efekty

Znajduje pierwsze wystąpienie val w przedziale [pierwszy, ostatni)

Parametry

first => iterator wskazuje na początek zakresu last => iterator wskazuje na koniec zakresu val => Wartość do znalezienia w zakresie

Powrót

Iterator, który wskazuje na pierwszy element w zakresie równym (==) val, iterator wskazuje na ostatni, jeśli val nie zostanie znaleziony.

Przykład

#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;
}

Wynik

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);

Efekty

Liczy liczbę elementów, które są równe val

Parametry

first => iterator wskazujący na początek zakresu
last => iterator wskazujący na koniec zakresu
val => Wystąpienie tej wartości w zakresie zostanie policzone

Powrót

Liczba elementów w zakresie, które są równe (==) do val.

Przykład

#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;
}

Wynik

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);

Efekty

Liczy liczbę elementów w zakresie, dla którego określona funkcja predykatu jest prawdziwa

Parametry

first => iterator wskazujący na początek zakresu last => iterator wskazujący na koniec zakresu red => funkcja predykatu (zwraca wartość true lub false)

Powrót

Liczba elementów w określonym zakresie, dla której funkcja predykatu zwróciła wartość true.

Przykład

#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;
}

Wynik

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);

Efekty

Znajduje pierwszy element w zakresie, dla którego funkcja predykatu pred zwraca true.

Parametry

first => iterator wskazuje na początek zakresu last => iterator wskazuje na koniec zakresu pred => funkcja predykatu (zwraca wartość true lub false)

Powrót

Iterator, który wskazuje pierwszy element w zakresie, dla którego funkcja predykatu pred zwraca true. Iterator wskazuje na ostatni, jeśli val nie zostanie znaleziony

Przykład

#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;
}

Wynik

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);

Efekty

Znajduje minimalny element w zakresie

Parametry

first - iterator wskazujący początek zakresu
last - iterator wskazujący na koniec zakresu comp - wskaźnik funkcji lub obiekt funkcji, który pobiera dwa argumenty i zwraca wartość true lub false wskazując, czy argument jest mniejszy niż argument 2. Ta funkcja nie powinna modyfikować danych wejściowych

Powrót

Iterator do minimalnego elementu w zakresie

Złożoność

Liniowy o jeden mniej niż liczba porównywanych elementów.

Przykład

#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;
}

Wynik

min int from default: 6
min pair from PairLessThanFunction: 2

Korzystanie ze std :: nth_element w celu znalezienia mediany (lub innych kwantyli)

Algorytm std::nth_element przenosi trzy iteratory: iterator na początek, n- tą pozycję i koniec. Gdy funkcja powróci, n- ty element (według kolejności) będzie n- tym najmniejszym elementem. (Funkcja ma bardziej skomplikowane przeciążenia, np. Niektóre biorące funktory porównania; patrz powyższy link dla wszystkich wariantów).

Uwaga Ta funkcja jest bardzo wydajna - ma złożoność liniową.

Na potrzeby tego przykładu zdefiniujmy medianę sekwencji o długości n jako element, który byłby w pozycji ⌈n / 2⌉. Na przykład mediana sekwencji o długości 5 jest trzecim najmniejszym elementem, podobnie jak mediana sekwencji o długości 6.

Aby użyć tej funkcji do znalezienia mediany, możemy użyć następujących. Powiedzmy, że zaczynamy

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].

Aby znaleźć p kwantyl , zmienilibyśmy niektóre z powyższych linii:

const std::size_t pos = p * std::distance(b, e);

std::advance(nth, pos);

i poszukaj kwantyla w pozycji pos .