Podstawy programowania 12

Algorytmy biblioteki standardowej języka C++

Biblioteka standardowa oprócz kontenerów dostarcza też wielu algorytmów mających na celu uproszczenie życia programistom. Implementacja tych algorytmów często jest jedną z najlepszych możliwych – bardzo ciężko jest napisać własną metodę, która jest szybsza od dobrze wykorzystanej metody bibliotecznej. Do tego nasz kod jest czytelniejszy dla pozostałych programistów. Niestety, dla elastyczności biblioteczne implementacje algorytmów używają iteratorów, więc aby dobrze z nich korzystać, trzeba opanować iteratory (i wskaźniki). Wspomnimy tutaj tylko o najważniejszych resztę można znaleźć w dokumentacji.

Zakres definiowany przez parę iteratorów

Wiele z algorytmów działa na tablicach lub pewnych kolekcjach elementów. Konwencją biblioteki standardowej jest, że takie kolekcje opisujemy parą iteratorów. Pierwszy z nich wskazuje na pierwszy rozważany element, drugi wskazuje na element znajdujący się zaraz za ostatnim rozważanym elementem. Tym samym zakres opisywany przez parę iteratorów begin i end to [begin, end). Może się to wydawać na początku dziwne, ale wbrew pozorom, dzięki temu używanie wielu algorytmów jest prostsze. Dla przykładu, jeżeli T jest tablicą o n elementach, to aby ją posortować należy napisać sort(T, T + n). Przypomnijmy, że nazwa tablicy T może być traktowana jako wskaźnik na jej pierwszy element. Zgodnie z tym co wiemy o arytmetyce wskaźników, T + n jest więc wskaźnikiem na element T[n], pierwszym którego w tablicy już nie ma. Metoda sort posortuje zatem elementy T[0], T[1],..., T[n-1].

Przypomnijmy, że kontenery standardowe mają metody begin() i end(), które działają w sposób pasujący do opisanego przed chwilą schematu.

Argumenty funkcyjne

Niektóre funkcje biblioteczne przyjmują dodatkowe argumenty będące funkcjami wpływające na działanie algorytmów. Najczęściej pojawiają się predykaty i funkcje porównujące.

Predykaty

Predykaty to funkcje zwracające wartość logiczną true lub false. Jako argumenty funkcji bibliotecznych znajdziemy predykaty jednoargumentowe (dalej zapisywane jako unPred) i dwuargumentowe (dalej oznaczane jako binPred).

Funkcje porównujące

Funkcje porównujące jak sama nazwa wskazuje, porównują obiekty przekazywanych kolekcji. Funkcja taka przyjmuje dwie wartości i implementuje porządek (relację antyzwrotną, antysymetryczną i przechodnią) na swoich argumentach. Funkcja ta zwraca true, jeżeli pierwszy argument jest mniejszy od drugiego, false w przeciwnym przypadku. Do wielu funkcji można ją przekazać jako dodatkowy parametr, zmieniając tym samym rozpatrywany porządek.

Algorytmy niemodyfikujące przekazanego zakresu

Algorytmy te znajdują we wskazanym zakresie zadaną wartość, względnie element spełniający zadany warunek. Najważniejsze z nich to:

Powyższe algorytmy wymagają od iteratorów jedynie możliwości ich inkrementacji. Poniższe są szybsze (używają przeszukiwania binarnego) potrzebują do tego jednak iterotaorów implementujących pełną arytmetykę wskaźników. Przekazany zakres musi być posortowany:

Algorytmy modyfikujące przekazany zakres

Poniższe algorytmy zmieniają jeden z przekazanych zakresów

Algorytmy sortujące

Przykład użycia algorytmów

Poniższy kod pokazuje użycie niektórych z poznanych tutaj algorytmów. Oprócz omówionych konstrukcji języka występują też inne, nieomówione. Wiele z nich należy do bardziej zaawansowanej części języka, częśc z nich jest naprawdę świeża i została wprowadzona wraz ze standardem C++11. Proszę traktować to jako zaproszenie do dalszego pogłębiania wiedzy na własną ręką z użyciem książek, dokumentacji, artykułów, for internetowych itp.

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <random>
#include <functional>
using namespace std;

// Kod dla przejrzystości korzysta z C++11,
// kompilować z odpowiednimi ustawieniami.

template<class T>
void f(T x) {
  cout << x << ' ';
}

bool even(int x) {
  return x % 2 == 0;
}

int main() {
  vector<int> v({0, 1, 2, 3, 4, 5, 6, 7, 8, 9 });

  for_each(v.cbegin(), v.cend(), f<decltype(v)::value_type>);
  cout << endl;

  ostream_iterator<decltype(v)::value_type> coutIt(cout, " ");
  copy(v.cbegin(), v.cend(), coutIt);
  cout << endl;

  fill(v.begin(), v.begin()+3, 10);
  copy(v.cbegin(), v.cend(), coutIt);
  cout << endl;


  random_device rd;
  mt19937 g(rd());
  shuffle(v.begin(), v.end(), g);
  copy(v.cbegin(), v.cend(), coutIt);
  cout << endl;

  auto it = find_if(v.cbegin(), v.cend(), even);
  cout << "Pierwszy parzysty element: " << *it << endl;

  sort(v.begin(), v.begin(), greater<decltype(v)::value_type>());
  copy(v.cbegin(), v.cend(), coutIt);
  cout << endl;

  // wypełniamy losowymi wartościami
  uniform_int_distribution<> dist(0, 99);
  generate(v.begin(), v.end(), [&]() { return dist(g); });

  // Sortujemy po cyfrze jedności
  stable_sort(v.begin(), v.end(), [](int x, int y) {
    return x % 10 < y % 10;
  });
  copy(v.cbegin(), v.cend(), coutIt);
  cout << endl;
  return 0;
}