Algorytmy standardowe¶

Język C++ definiuje zestaw szablonów funkcji (zwanych algorytmami) pracujących z iteratorami. Dzięki zastosowaniu abstrakcji w postaci iteratorów algorytmy mogą pracować na dowolnym typie kontenera.

Większość standardowych algorytmów zadeklarowana jest w pliku nagłówkowym <algorithm>

Algorytmy zostały pogrupowane wg spełnianej przez nie funkcji. Są to:

Operacje niemodyfikujące
Porównania
Wyszukiwanie
Operacje modyfikujące sekwencje
Sortowanie oraz łączenie
Operacje na zbiorach

Nazwy parametrów szablonów określają rodzaj oczekiwanego argumentu szablonu (szczególnie kategorii iteratora). Kategoria iteratora określa minimalną funkcjonalność (np. w miejscu, gdzie wymagany jest iterator postępujący, można zastosować iterator o dostępie swobodnym).

Pewna część algorytmów wymaga podania posortowanych zakresów albo zastosowania funkcji porównującej, sprawdzającej zależność „mniejszy niż”. Każdy algorytm w bibliotece jest przeciążony. Jedna wersja stosuje operator < a druga pobiera funkcję lub funktor wykonujący porównanie.

Algorytmy a iteratory¶

Konwencja nazewnicza kategorii iteratorów jako parametrów algorytmów

BidirectIt: Iterator dwukierunkowy
FwdIt: Iterator postępujący
InpIt: Iterator wejściowy
OutIt: Iterator wyjściowy
RndIt: Iterator o dostępie swobodnym

Operacje niemodyfikujące¶

Algorytmy for_each¶

Func for_each(InpIt first, InpIt last, Func func)¶: Dla każdego elementu z zakresu [first;last) wywołuje funkcję func. Zwracana wartość to kopia funktora przekazanego jako argument func.

InpIt for_each_n(InpIt first, Size n, Func func)¶: Dla elementu z zakresu [first; first + n) wywołuje funkcję func. Zwracana wartość to kopia funktora przekazanego jako argument func.

Przykład użycia algorytmu for_each():

// funkcja wywoływana dla każdego elementu
void print(int item)
{
    std::cout << item << '\n';
}

std::vector<int> coll = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

std::for_each(coll.begin(), coll.end(),  // range
         &print);                        // function


std::for_each_n(begin(coll), 4, [](int& x) { x *= 2; });

Algorytmy niemodyfikujące¶

sprawdzają wszystkie elementy sekwencji ale nie modyfikują ich kolejności

count(InpIt first, InpIt last, const T &val)¶: Zwraca liczbę wystąpień elementu val w zakresie [first; last). Elementy są porównywane przy pomocy operatora równości (==)

count_if(InpIt first, InpIt last, Pred pred)¶: Sprawdza , ile razy predykat pred zwrócił wartość true w zakresie [first; last)

Przykład użycia algorytmów count() i count_if():

auto is_even = [](int x) {
    return x % 2 == 0;
};

std::vector<int> coll = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

// count elements that equal 4
auto n = std::count(coll.begin(), coll.end(),       // zakres
                    4);                                     // wartość


// count with a given predicate
auto m = std::count_if(coll.begin(), coll.end(), // range
                       is_even);                 // predicate

bool all_of(InpIt first, InpIt last, UnaryPredicate func)¶: Sprawdza, czy każdy element w zakresie [first, last) spełnia predykat (zwraca true). Dla pustego zakresu zwraca true

bool any_of(InpIt first, InpIt last, UnaryPredicate func)¶: Sprawdza, czy przynajmniej jeden element w zakresie [first, last) spełnia predykat. Dla pustego zakresu zwraca false

bool none_of(InpIt first, InpIt last, UnaryPredicate func)¶

Sprawdza, czy żaden element w zakresie [first, last) spełnia predykat (zwraca true). Dla pustego zakresu zwraca true

using namespace std;

auto lst = { 2, 4, 6, 8 };

assert(all_of(begin(lst), end(lst), is_even));
assert(any_of(begin(lst), end(lst), [](int x) { return x > 5; }));
assert(none_of(begin(lst), end(lst), [](int x) { return x > 10; }));

Porównania¶

Porównują ze sobą obiekty lub sekwencje ale nie zmieniają samych elementów.

bool equal(InpIt1 first1, InpIt1 last1, InpIt2 first2)¶

bool equal(InpIt1 first1, InpIt1 last1, InpIt2 first2, BinPred pred)¶

bool equal(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2)¶

bool equal(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2, BinPred pred)¶

Sprawdza, czy dwa zakresy mają taką samą zawartość.

wersja bez predykatu binarnego porównuje elementy wykorzystując operator==
jeśli zakres [first1, last1) ma inną długość od zakresu [first2, last2) zwracana jest wartość false

bool is_palindrome(std::string_view s)
{
    return std::equal(s.begin(), s.begin() + s.size()/2, s.rbegin());
}

assert(is_palindrome("potop"));

bool lexicographical_compare(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2)¶

bool lexicographical_compare(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2, Cmp comp)¶

Sprawdza, czy zakres [first1, last1) jest mniejszy niż zakres [first2, last2). Pierwsza wersja wykorzystuje operator <, a druga wywołanie comp(*iter1, *iter2)

std::vector<char> v1 {'a', 'b', 'c', 'd'};
std::vector<char> v2 {'a', 'b', 'd', 'd'};

assert(std::lexicographical_compare(v1.begin(), v1.end(), v2.begin(), v2.end());

const T &max(const T &a, const T &b)¶
const T &max(const T &a, const T &b, Cmp comp)¶: Zwraca maksimum z dwóch elementów.

FwdIt max_element(FwdIt first, FwdIt last)¶
FwdIt max_element(FwdIt first, FwdIt last, Cmp comp)¶: Zwraca iterator wskazujący na pierwszy wystąpienie największego elementu w zakresie [first, last)

const T &min(const T &a, const T &b)¶
const T &min(const T &a, const T &b, Cmp comp)¶: Zwraca minimum z dwóch elementów.

FwdIt min_element(FwdIt first, FwdIt last)¶
FwdIt min_element(FwdIt first, FwdIt last, Cmp comp)¶: Zwraca iterator wskazujący na pierwszy wystąpienie najmniejszego elementu w zakresie [first, last)

pair<FwdIt, FwdIt> minmax_element(FwdIt first, FwdIt last)¶

pair<FwdIt, FwdIt> minmax_element(FwdIt first, FwdIt last, Cmp comp)¶

Zwraca parę iteratorów wskazujących na pierwszy wystąpienie najmniejszego i największego elementu w zakresie [first, last)

std::vector<int> vec = { 52, 123, 665, 235, 42, 333 };

auto [min_pos, max_pos] = std::minmax_element(vec.begin(), vec.end());

assert(*min_pos == 42);
assert(*max_pos == 665);

Wyszukiwanie¶

Poniższe algorytmy wyszukują w podanej sekwencji pewnej wartości lub pod-sekwencji ale nie modyfikują elementów.

FwdIt adjacent_find(FwdIt first, FwdIt last)¶

FwdIt adjacent_find(FwdIt first, FwdIt last, BinPred pred)¶

W zakresie [first, last) algorytm znajduje pierwszą pozycję, na której element *iter jest równy swojemu sąsiadowi *(iter+1)

std::vector<int> vec = { 1, 2, 3, 4, 4, 5, 6 };

auto adjacent_pos = std::adjacent_find(vec.begin(), vec.end());

assert(*adjacent_pos == (*adjacent_pos + 1));

InpIt find(InpIt first, InpIt last, const T &val)¶

Znajduje w zakresie [first, last) pierwsze wystąpienie wartości val i zwraca iterator wskazujący na tę wartość

std::list<int> coll = { 1, 3, 1, 4, 6, 7, 9, 8 };

if (auto pos = find(coll.begin(), coll.end(), 4); pos != coll.end())
{
    std::cout << "Found: " << *pos << '\n';
}

InpIt find_if(InpIt first, InpIt last, Pred pred)¶: W zakresie [first; last) wyszukuje pierwszy element, dla którego predykat pred zwróci wartość true

FwdIt find_end(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2)¶

Wyszukuje w zakresie [first1; last1) ostatniego wystąpienia podsekwencji [first2; last2)

std::vector vec = { 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 };
auto seq = { 1, 2, 3 };

auto last_pos =  std::find_end(vec.begin(), vec.end(), seq.begin(), seq.end());
assert(std::distance(vec.begin(), last_pos) == 11);

FwdIt find_first_of(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2)¶

W zakresie [first1, last2) wyszukuje pierwszą pozycję, na której element jest równy dowolnemu elementowi z zakresu [first2, last2)

std::string text = "token1 token2,token3";
std::string_view separators = " ,";

auto pos = std::find_first_of(text.begin(), text.end(), separators.begin(), separators.end());

std::string_view extracted(pos, std::distance(text.begin(), pos));
assert(extracted == "token1");

FwdIt1 search(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2)¶: W zakresie [first1, last1) wyszukuje podsekwencję [first2, last2) i zwraca iterator wskazujący na pierwsze jej wystąpienie

FwdIt search_n(FwdIt first, FwdIt last, Size count, const T &val)¶
FwdIt search_n(FwdIt first, FwdIt last, Size count, const T &val, BinPred pred)¶: W zakresie [first; last) wyszukuje sekwencję składającą sie z count powtórzeń elementu val i zwraca iterator wskazujący na pierwsze wystąpienie

Wyszukiwanie binarne¶

Poniższe algorytmy wykonują operację wyszukiwania binarnego w posortowanych zakresach.

Zakres musi być posortowany w porządku rosnącym z wykorzystaniem operatora mniejszości (<) lub funkcji porównującej.

bool binary_search(FwdIt first, FwdIt last, const T &val)¶
bool binary_search(FwdIt first, FwdIt last, const T &val, Cmp comp)¶: W zakresie [first, last) szuka wartości val. Elementy muszą być posortowane w porządku rosnącym za pomocą operatora mniejszości lub funkcji comp

pair<FwdIt, FwdIt> equal_range(FwdIt first, FwdIt last, const T &val)¶
pair<FwdIt, FwdIt> equal_range(FwdIt first, FwdIt last, const T &val, Cmp comp)¶: W zakresie [first, last) wyszukuje górną i dolną granicę pozycji zajętych przez elementy val. Jeżeli wartości val nie ma w podanym zakresie, oba zwracane iteratory wskazują miejsce, w którym ta wartość powinna się znaleźć.

FwdIt lower_bound(FwdIt first, FwdIt last, const T &val)¶
FwdIt lower_bound(FwdIt first, FwdIt last, const T &val, Cmp comp)¶: W posortowanym zakresie [first, last) wyszukuje dolną granicę pozycji zajętych przez element val. Jeżeli wartości nie ma w przeszukiwanym zakresie, zwracany iterator wskazuje na pierwszy element większy od szukanej wartości

FwdIt upper_bound(FwdIt first, FwdIt last, const T &val)¶
FwdIt upper_bound(FwdIt first, FwdIt last, const T &val, Cmp comp)¶: W posortowanym zakresie [first, last) wyszukuje górną granicę pozycji zajętych przez element val. Jeżeli wartości nie ma w przeszukiwanym zakresie, zwracany iterator wskazuje na pierwszy element większy od szukanej wartości

Przykład wykorzystania operacji wyszukiwania binarnego:

std::vector<int> coll = { 1, 3, 3, 3, 4, 5, 7, 8 };

// check if 6 is in collection
bool is_inside = binary_search(coll.begin(), coll.end(), 6);
assert(is_inside == false);

// insert 6 preserving an order
coll.insert(upper_bound(coll.begin(), coll.end(), 6), 6);

Operacje modyfikujące sekwencje¶

OutIt copy(InpIt first, InpIt last, OutIt result)¶: Kopiuje wszystkie elementy z zakresu [first, last), do zakresu, którego początek wskazuje iterator result. Należy się upewnić, czy w zakresie wyjściowym jest wystarczająca ilość miejsca.

OutIt copy_if(InpIt first, InpIt last, OutIt result, UnaryPred pred)¶: Kopiuje wszystkie elementy z zakresu [first, last) spełniające warunek pred, do zakresu, którego początek wskazuje iterator result

OutIt copy_n(InpIt first, Size n, OutIt result)¶: Kopiuje n elementów z zakresu wskazanego przez iterator first, do zakresu, którego początek wskazuje iterator result

Przykład kopiowania:

std::string txt = "1234567890";
std::string out;

std::copy_n(txt.begin(), 4, std::back_inserter(out));  // out: "1234"

void fill(FwdIt first, FwdIt last, const T &val)¶: Wypełnia zakres [first, last) kopiami wartości val

void fill_n(OutIt first, Size n, const T &val)¶: Przypisuje wartość val do n pierwszych elementów w zakresie wskazanym przez first

void generate(FwdIt first, FwdIt last, Gen gen)¶: Zapełnia zakres [first, last) wartościami zwracanymi przez powtarzane wywołania funkcji gen().

void generate_n(OutIt first, Size n, Gen gen)¶: Zapełnia zakres [first, first+n) wartościami zwracanymi przez gen()

Przykład wykorzystania fill_n oraz generate_n:

std::vector<int> coll = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

std::fill_n(coll.begin(), 4, 0); // coll : { 0, 0, 0 ,0 , 5, 6, 7, 8, 9, 10 }

size_t seed = 10;
auto generator = [seed]() mutable { return ++seed; };

std::generate_n(std::back_inserter(coll), 4, generator);
// coll : { 0, 0, 0 ,0 , 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 }

void shuffle(RndIt first, RndIt last, URBG &&g)¶

Miesza elementy z zakresu [first, last) w losowej kolejności wykorzystując generator liczb pseudolosowych URBG

std::vector v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

std::random_device rd;
std::mt19937 g(rd());

std::shuffle(v.begin(), v.end(), g);

FwdIt remove(FwdIt first, FwdIt last, const T &val)¶: Reorganizuje zakres [first, last), przygotowując go do usunięcia wszystkich wartości równych val. Zwracany jest taki iterator return, że wszystkie wartości z zakresu [first, return) nie są równe val.

OutIt remove_if(FwdIt first, FwdIt last, Pred pred)¶: Działa podobnie do remove. Do reorganizacji sekwencji korzysta z predykatu pred.

FwdIt unique(FwdIt first, FwdIt last)¶
FwdIt unique(FwdIt first, FwdIt last, Binpred pred)¶: Reorganizuje zakres [first, last) przygotowując go do usunięcia wszystkich elementów posiadających identycznego sąsiada (*iter == *(iter+1)). Zwracany jest iterator wskazujący na pozycję następującą za ostatnim unikalnym elementem zakresu.

Aby usunąć rzeczywiście elementy z kontenera, należy połączyć algorytm remove lub unique z operacją erase() kontenera.

vector<int> coll = { 1, 7, 3, 4, 5, 6, 7, 7, 7, 8, 7 };

auto new_end = remove(coll.begin(), coll.end(), 7);

// after remove 7 still can be in a container
coll.erase(new_end, coll.end()); // erasing garbage

OutIt remove_copy(InpIt first, InpIt last, OutIt result, const T &val)¶: Zakres [first, last) jest kopiowany do zakresu rozpoczynającego się od elementu wskazywanego przez iterator result. Kopiowane są jedynie te elementy, które nie są równe wartości val.

OutIt remove_copy_if(InpIt first, InpIt last, OutIt result, Pred pred)¶: Działa podobnie do remove_copy, ale korzysta z predykatu pred.

OutIt unique_copy(InpIt first, InpIt last, OutIt result)¶: Kopiuje elementy z zakresu [first, last) do zakresu rozpoczynającego się od elementu wskazywanego przez iterator result, unikając kopiowania sąsiadujących elementów, które są sobie równe.

void replace(FwdIt first, FwdIt last, const T &old_val, const T &new_val)¶: W zakresie [first, last) zamienia wszystkie wystąpienia wartości old_val wartościami new_val. Wykorzystuje operator ==.

void replace_if(FwdIt first, FwdIt last, Pred pred, const T &new_val)¶: W zakresie [first, last) zamienia wszystkie wartości, dla których wywołanie pred(*iter) zwraca true, wartościami new_val.

void reverse(BidirectIt first, BidirectIt last)¶: Odwraca kolejność elementów zakresu [first, last)

OutIt reverse_copy(BidirectIt first, BidirectIt last, OutIt result)¶: Kopiuje w odwrotnej kolejności zakres [first, last) do zakresu zaczynającego się od elementu wskazywanego przez iterator result

void rotate(FwdIt first, FwdIt middle, FwdIt last)¶

Przesuwa elementy zakresu [first, last) w lewą stronę, tak że elementy z zakresu [middle, last) są przesuwane na początek wynikowej sekwencji. Elementy z zakresu [first, middle) są przesuwane na koniec sekwencji

vector<int> coll = { 1, 2, 3, 4, 5, 6 };

// rotation to the left
rotate(coll.begin(), coll.begin() + 1, v.end()); // coll: { 2, 3, 4, 5, 6, 1 }

// rotation to the right
rotate(coll.rbegin(), coll.rbegin() + 1, coll.rend()); // { 1, 2, 3, 4, 5, 6 }

OutIt transform(InpIt first, InpIt last, OutIt result, UnOp unop)¶
OutIt transform(InpIt first1, InpIt last1, InpIt2 first2, OutIt result, BinOp binop)¶: Modyfikuje każdy element z podanego zakresu poprzez wywołanie funkcji transformującej i zapisuje wynik tej funkcji w zakresie rozpoczynającym się od elementu wskazywanego przez iterator result.

Przykład transformacji:

vector<int> numbers = { 1, 2, 3, 4 };
vector<int> squares(numbers.size());

// transformation using lambda expression
transform(numbers.begin(), numbers.end(), squares.begin(), [](int x) { return x * x; });

// the same with STL functor
transform(numbers.begin(), numbers.end(), numbers.begin(), squares.begin(), multiplies<int>{});

Sortowanie¶

bool is_sorted(FwdIt first, FwdIt last)¶
bool is_sorted(FwdIt first, FwdIt last, Cmp comp)¶: Sprawdza czy zakres [first, last) jest posortowany

FwdIt is_sorted_until(FwdIt first, FwdIt)¶
FwdIt is_sorted_until(FwdIt first, FwdIt, Cmp comp)¶: Sprawdza zakres [first, last) i znajduje największy zakres rozpoczynający się od first, w którym elementy są posortowane w kolejności rosnącej.

Poniższe algorytmy są związane z operacjami sortowania i podziału. Do wykonywania tych operacji można wykorzystać domyślny operator < albo podać własną funkcję lub funktor porównujący.

Funkcje częściowego sortowania i funkcje wykonujące podziały mają złożoność logarytmiczną.

void nth_element(RndIt first, RndIt nth, RndIt last)¶

void nth_element(RndIt first, RndIt nth, RndIt last, Cmp comp)¶

Dzieli zakres [first, last) w ten sposób, że wartość *nth znajduje się na tej samej pozycji, na której znajdowałaby się, gdyby cały zakres był posortowany. Wszystkie elementy z zakresu [first, nth) są mniejsze lub równe elementom z zakresu [nth, last). Średnia złożoność algorytmu jest liniowa, jednak w przypadku pesymistycznym może być wyższa.

std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};

std::nth_element(v.begin(), v.begin() + v.size() / 2, v.end());
std::cout << "The median is " << v[v.size() / 2] << '\n';

std::nth_element(v.begin(), v.begin() + 1, v.end(), std::greater<>());
std::cout << "The second largest element is " << v[1] << '\n';

void partial_sort(RndIt first, RndIt middle, RndIt last)¶
void partial_sort(RndIt first, RndIt middle, RndIt last, Cmp comp)¶: Dzieli zakres [first, last) w ten sposób, że wszystkie elementy z zakresu [first, middle) są mniejsze lub równe wszystkim elementom z zakresu [middle, last). Zakres [first, middle) jest posortowany w porządku rosnącym.

RndIt partial_sort_copy(InpIt first, InpIt last, RndIt result_first, RndIt result_last)¶

RndIt partial_sort_copy(InpIt first, InpIt last, RndIt result_first, RndIt result_last, Cmp comp)¶

Kopiuje i sortuje elementy z zakresu [first, last) do zakresu (result_first, result_last). Liczba kopiowanych elementów jest równa liczbie elementów w mniejszym z podanych zakresów. Z zakresu wejściowego pobierane są wszystkie elementy, nawet jeśli zakres wyjściowy jest mniejszy.

std::array<int, 10> s{5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

std::partial_sort(s.begin(), s.begin() + 3, s.end());

RandomIt partial_sort_copy(InpIt first, InpIt last, RndIt d_first, RndIt d_last)

RandomIt partial_sort_copy(InpIt first, InpIt last, RndIt d_first, RndIt d_last, Cmp comp)

Sortuje elementy z zakresu [first, last) w kolejności rosnącej (lub określonej funktorem comp) zapisując wyniki do zakresu [d_first, d_last). Względna kolejność elementów równoważnych nie jest zachowana. Zwracany jest iterator definiujący górną granicę posortowanego zakresu.

std::vector<int> v0{4, 2, 5, 1, 3};
std::vector<int> v1{10, 11, 12};
std::vector<int> v2{10, 11, 12, 13, 14, 15, 16};
std::vector<int>::iterator it;

it = std::partial_sort_copy(v0.begin(), v0.end(), v1.begin(), v1.end());
assert(v1 == vector{1, 2, 3});
assert(it == v1.end());

it = std::partial_sort_copy(v0.begin(), v0.end(), v2.begin(), v2.end(),
                            std::greater<int>());
assert(v2 == vector{5 4 3 2 1 15 16});

void sort(RndIt first, RndIt last)¶

void sort(RndIt first, RndIt last, Cmp comp)¶

Sortuje podany zakres w porządku rosnącym.

std::array<int, 10> s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};

std::sort(begin(s), end(s));
std::sort(begin(s), end(s), std::greater<>{});

void stable_sort(RndIt first, RndIt last)¶
void stable_sort(RndIt first, RndIt last, Cmp comp)¶: Działa podobnie do sort, ale względna kolejność elementów równoważnych nie jest zmieniana.

Partycjonowanie¶

Operacje partycjonowania:

bool is_partitioned(InpIt first, InpIt last, UnaryPred pred)¶: Zwraca true jeśli wszystkie elementy w zakresie [first, last), które spełniają predykat pred poprzedzają elementy nie spełniające predykatu.

BidirectIt partition(BidirectIt first, BidirectIt last, Pred pred)¶: Reorganizuje zakres [first, last) w taki sposób, że elementy, dla których wywołanie pred(*iter) zwróciło wartość true znajdują się przed elementami, dla których predykat zwrócił wartość false.

pair<OutIt1, OutIt2> partition_copy(InpIt first, InpIt last, OutIt1 result1, OutIt2 result2, UnaryPred pred)¶: Kopiuje elementy z zakresu [first, last) do dwóch różnych kontenerów w zależności od rezultatu wywołania predykatu. Elementy spełniające predykat są zapisywane w kontenerze wskazanym przez result1, a nie spełniające do result2.

BidirectIt stable_partition(BidirectIt first, BidirectIt last, Pred pred)¶: Działa podobnie do partition, ale względna kolejność elementów wewnątrz podziału się nie zmienia.

Łączenie¶

Poniższe algorytmy łączą dwie posortowane sekwencje.

void inplace_merge(BidirectIt first, BidirectIt mid, BidirectIt last)¶
void inplace_merge(BidirectIt first, BidirectIt mid, BidirectIt last, Cmp comp)¶: Łączy dwa następujące po sobie podzakresy, tworząc jeden posortowany zakres. Dwa zakresy wejściowe to zakresy [first, mid) i [mid, last), natomiast zakresem wynikowym jest [first, last).

OutIt merge(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2, OutIt result)¶
OutIt merge(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2, OutIt result, Cmp comp)¶: Łączy dwa posortowane zakresy i kopiuje wynik łączenia do osobnego zakresu. Dwa zakresy wejściowe to zakresy [first1, last1) i [first2, last2), natomiast początek zakresu wynikowego jest wskazywany przez iterator result. Należy się upewnić, czy w zakresie wyjściowym jest wystarczająca ilość miejsca na skopiowanie obu zakresów wejściowych. Zwracany jest iterator wskazujący na pozycję następującą za ostatnim elementem zakresu wyjściowego.

Operacje na zbiorach¶

Poniższe algorytmy wykonują na posortowanych sekwencjach operacje normalnie wykonywane na zbiorach. Złożoność tych algorytmów jest liniowa.

bool includes(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2)¶

bool includes(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2, Cmp comp)¶

Sprawdza, czy posortowany zakres [first2, last2) jest podzbiorem zakresu [first1, last1). Wartość true zwracana jest tylko wtedy, gdy każdy element z drugiego zakresu występuje również w pierwszym zakresie.

std::vector<int> s1 = { 1, 2, 3, 4, 5, 6, 7 };
std::vector<int> s2 = { 4, 6, 7 };

assert(std::includes(s1.begin(), s1.end(), s2.begin(), s2.end());

OutIt set_difference(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2, OutIt result)¶

OutIt set_difference(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2, OutIt result, Cmp comp)¶

Do zakresu wskazywanego przez iterator result kopiuje różnicę posortowanych zakresów [first1, last1) i [first2, last2). Do zakresu wynikowego kopiowane są tylko te elementy, które nie występują w drugim zakresie. Należy się upewnić, czy w zakresie wyjściowym jest wystarczająca ilość miejsca na skopiowanie elementów z zakresu wejściowego. Zwracany jest iterator wskazujący na pozycję następującą za ostatnim elementem zakresu wyjściowego.

std::vector<int> s1 = { 1, 2, 3, 4, 5, 6, 7 };
std::vector<int> s2 = { 4, 6, 7 };

std::vector<int> result;

std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(result));

assert(result == vector {1, 2, 3, 5 });

OutIt set_intersection(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2, OutIt result)¶

OutIt set_intersection(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2, OutIt result, Cmp comp)¶

Do zakresu wskazywanego przez iterator result kopiuje część wspólną posortowanych zakresów [first1, last1) i [first2, last2). Do zakresu wynikowego kopiowane są tylko te elementy pierwszego zakresu, które występują również w drugim zakresie. Zwracany jest iterator wskazujący na pozycję następującą za ostatnim elementem zakresu wyjściowego.

std::vector<int> s1 = { 1, 2, 3, 4, 5, 6, 7 };
std::vector<int> s2 = { 4, 6, 7, 8, 9 };

std::vector<int> result;

std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(result));

assert(result == vector {4, 6, 7});

OutIt set_symmetric_difference(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2, OutIt result)¶

OutIt set_symmetric_difference(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2, OutIt result, Cmp comp)¶

Do zakresu wskazywanego przez iterator result kopiuje różnicę symetryczną posortowanych zakresów [first1, last1) i [first2, last2). Do zakresu wynikowego kopiowane są z obu zakresów wejściowych tylko te elementy, które występują tylko w jednym zakresie (elementy występujące w obu zakresach nie są kopiowane). Zwracany jest iterator wskazujący na pozycję następującą za ostatnim elementem zakresu wyjściowego.

std::vector<int> s1 = { 1, 2, 3, 4, 5, 6, 7 };
std::vector<int> s2 = { 4, 6, 7, 8, 9 };

std::vector<int> result;

std::set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(result));

assert(result == vector {1, 2, 3, 5, 8, 9});

OutIt set_union(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2, OutIt result)¶

OutIt set_union(InpIt1 first1, InpIt1 last1, InpIt2 first2, InpIt2 last2, OutIt result, Cmp comp)¶

Do zakresu wskazywanego przez iterator result kopiuje unię posortowanych zakresów [first1, last1) i [first2, last2). Do zakresy wynikowego kopiowane są wszystkie elementy obu zakresów wejściowych, ale jeśli dany element występuje w obu zakresach (w zakresie pierwszym m razy, a w drugim n razy), to jest on kopiowany do zakresu docelowego std::max(m, n) razy z zachowaniem względnej kolejności. Zwracany jest iterator wskazujący na pozycję następującą za ostatnim elementem zakresu wyjściowego.

std::vector<int> s1 = { 1, 2, 3, 3,    4, 4, 4, 5 };
std::vector<int> s2 = {       3, 3, 3, 4, 4,      6, 7, 8 };

std::vector<int> result;

std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), std::back_inserter(result));

assert(result == vector {1, 2, 3, 3, 3, 4, 4, 4, 5, 6, 7, 8 });

Algorytmy numeryczne¶

Algorytmy numeryczne są zdefiniowane w pliku nagłówkowym <numeric>.

void iota(FwdIt first, FwdIt last, T value)¶: Zapełnia zakres [first, last) kolejnymi wartościami począwszy od value (wykonując w każdej iteracji ++value)

#include <list>
#include <numeric>

using namespace std;

list<int> lst(10);

iota(lst.begin(), lst.end(), -5); // lst : { -5, -4, -3, -2, -1, 0, 1, 2, 3, 4 }

T accumulate(InpIt first, InpIt last, T init)¶

T accumulate(InpIt first, InpIt last, T init, BinaryOperation op)¶

Oblicza sumę wartości value i elementów w zakresie [first, last). Wersja pierwsza używa operator + do sumowania elementów. Druga wersja wykorzystuje dwuargumentową funkcję op, która:

nie może mieć efektów ubocznych
nie może unieważniać iteratorów, lub modyfikować jakiegokolwiek elementu w zakresie
sygnatura funkcji op musi być równoważna Ret fun(const T1& a, const T2& b), gdzie:
- typ T musi być konwertowalny do T1
- dereferencja InpIt musi być konwertowalna do T2
- Ret musi być takim typem, że obiekt typu T może mieć przypisaną wartość typu Ret

vector<string> words = {"stl", "raii", "sfinae" };

auto sentence = accumulate(words.begin(), words.end(), ""s); // string: "stlraiisfinae"

auto total_length =
    accumulate(words.begin(), words.end(), 0,
               [](int total, const string& w) { return total + w.length(); });

// total_length: 13