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 argumentfunc
.
-
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 argumentfunc
.
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 zwracatrue
-
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 zwracatrue
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"));
- wersja bez predykatu binarnego porównuje elementy wykorzystując
-
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łaniecomp(*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ścival
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 predykatpred
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
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ścival
. Elementy muszą być posortowane w porządku rosnącym za pomocą operatora mniejszości lub funkcjicomp
-
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 elementyval
. Jeżeli wartościval
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 elementval
. 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 elementval
. 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 iteratorresult
. 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 warunekpred
, do zakresu, którego początek wskazuje iteratorresult
-
OutIt
copy_n
(InpIt first, Size n, OutIt result)¶ Kopiuje
n
elementów z zakresu wskazanego przez iteratorfirst
, do zakresu, którego początek wskazuje iteratorresult
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
don
pierwszych elementów w zakresie wskazanym przezfirst
-
void
generate
(FwdIt first, FwdIt last, Gen gen)¶ Zapełnia zakres
[first, last)
wartościami zwracanymi przez powtarzane wywołania funkcjigen()
.
-
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 pseudolosowychURBG
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ównychval
. Zwracany jest taki iteratorreturn
, że wszystkie wartości z zakresu[first, return)
nie są równeval
.
-
OutIt
remove_if
(FwdIt first, FwdIt last, Pred pred)¶ Działa podobnie do
remove
. Do reorganizacji sekwencji korzysta z predykatupred
.
-
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 iteratorresult
. Kopiowane są jedynie te elementy, które nie są równe wartościval
.
-
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 iteratorresult
, 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ściold_val
wartościaminew_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łaniepred(*iter)
zwracatrue
, wartościaminew_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 sekwencjivector<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ę odfirst
, 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});
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ą predykatpred
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łaniepred(*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 przezresult1
, a nie spełniające doresult2
.
-
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 docelowegostd::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 odvalue
(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żywaoperator +
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żnaRet fun(const T1& a, const T2& b)
, gdzie:- typ
T
musi być konwertowalny doT1
- dereferencja
InpIt
musi być konwertowalna doT2
Ret
musi być takim typem, że obiekt typuT
może mieć przypisaną wartość typuRet
- typ
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