Oprócz klas kontenerów i iteratorów STL udostępnia także szereg ogólnych algorytmów do pracy z elementami klas kontenerów. Umożliwiają one wyszukiwanie, sortowanie, wstawianie, zmianę kolejności, usuwanie i kopiowanie elementów klasy kontenera.
Zauważ, że algorytmy są implementowane jako funkcje działające przy użyciu iteratorów. Oznacza to, że każdy algorytm musi zostać zaimplementowany tylko raz i zazwyczaj będzie działał automatycznie dla wszystkich kontenerów udostępniających zestaw iteratorów (w tym niestandardowych klas kontenerów). Chociaż jest to bardzo przydatne i może prowadzić do możliwości bardzo szybkiego pisania złożonego kodu, ma też ciemną stronę: niektóre kombinacje algorytmów i typów kontenerów mogą nie działać, mogą powodować nieskończone pętle lub mogą działać, ale działać bardzo słabo. Używaj ich więc na własne ryzyko.
STL udostępnia sporo algorytmów — omówimy tutaj tylko niektóre z bardziej powszechnych i łatwych w użyciu. Reszta (i wszystkie szczegóły) zostaną zapisane w rozdziale poświęconym algorytmom STL.
Aby użyć dowolnego algorytmu STL, po prostu dołącz plik nagłówkowy algorytmu.
min_element i max_element
Klasa std::min_element i std::max_element algorytmy znajdują element min i max w klasie kontenera. std::iota generuje ciągłą serię wartości.
#include <algorithm> // std::min_element and std::max_element
#include <iostream>
#include <list>
#include <numeric> // std::iota
int main()
{
std::list<int> li(6);
// Fill li with numbers starting at 0.
std::iota(li.begin(), li.end(), 0);
std::cout << *std::min_element(li.begin(), li.end()) << ' '
<< *std::max_element(li.begin(), li.end()) << '\n';
return 0;
}Drukuje:
0 5
znajdź (i list::insert)
W tym przykładzie użyjemy std::find() algorytmu, aby znaleźć wartość w klasie listy, a następnie użyjemy funkcji list::insert(), aby dodać w tym miejscu nową wartość do listy.
#include <algorithm>
#include <iostream>
#include <list>
#include <numeric>
int main()
{
std::list<int> li(6);
std::iota(li.begin(), li.end(), 0);
// Find the value 3 in the list
auto it{ std::find(li.begin(), li.end(), 3) };
// Insert 8 right before 3.
li.insert(it, 8);
for (int i : li) // for loop with iterators
std::cout << i << ' ';
std::cout << '\n';
return 0;
}To wypisuje wartości
0 1 2 8 3 4 5
Gdy algorytm wyszukiwania nie znajdzie tego, czego szukał, zwraca iterator końcowy.
Jeśli nie wiedzieliśmy na pewno, że 3 jest elementem li, musielibyśmy sprawdzić, czy std::find znaleźli, zanim użyjemy zwróconego iteratora do czegokolwiek innego.
if (it == li.end())
{
std::cout << "3 was not found\n";
}
else
{
// ...
}sortowanie i odwracanie
W tym przykładzie posortujemy wektor, a następnie odwrócimy it.
#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> vect{ 7, -3, 6, 2, -5, 0, 4 };
// sort the vector
std::sort(vect.begin(), vect.end());
for (int i : vect)
{
std::cout << i << ' ';
}
std::cout << '\n';
// reverse the vector
std::reverse(vect.begin(), vect.end());
for (int i : vect)
{
std::cout << i << ' ';
}
std::cout << '\n';
return 0;
}Daje to wynik:
-5 -3 0 2 4 6 7 7 6 4 2 0 -3 -5
Alternatywnie możemy przekazać niestandardową funkcję porównawczą jako trzeci argument do std::sort. W nagłówku <function> znajduje się kilka funkcji porównawczych, których możemy użyć, dzięki czemu nie musimy pisać własnych. Możemy przekazać std::greater Do std::sort i usunąć wywołanie do std::reverse. Wektor zostanie natychmiast posortowany od najwyższej do najniższej.
Zauważ to std::sort() nie działa na klasach kontenerów list — klasa list udostępnia własną sort() funkcję składową, która jest znacznie wydajniejsza niż byłaby wersja ogólna.
Wnioski
Chociaż jest to tylko przedsmak algorytmów udostępnianych przez STL, powinno wystarczyć pokazanie, jak łatwo można ich używać w połączeniu z iteratorami i podstawowymi klasami kontenerów. Jest wystarczająco dużo innych algorytmów, aby wypełnić cały rozdział!