5.7. Algorytmy przeznaczone dla zakresów posortowanych
W bibliotece STL znajdujÄ… siÄ™ algorytmy wykonujÄ…ce operacje na
posortowanych zakresach (ang. sorted range algorithms). Tabela 5.7
przedstawia zestaw algorytmów przeznaczonych do operacji na posortowanych
kolekcjach. Omawiane algorytmy mają dość skomplikowane definicje i zasady
korzystania. W każdym przypadku ich użycia, należy zaznajomić się z ich
opisem technicznym.
156
5. Algorytmy
Tabela 5.7 Algorytmy operujÄ…ce na kolekcjach posortowanych
( b – poczÄ…tek pierwszego zakresu, b1 – poczÄ…tek drugiego zakresu,
b2 – poczÄ…tek trzeciego zakresu, e – koniec pierwszego zakresu, e1 – koniec
drugiego zakresu, bp – predykat binarny, v - wartość)
Algorytm
działanie
binary_search(b,e,v)
Sprawdza, czy w zakresie [b,e] jest
element v
binary_search(b,e,v,bp)
Sprawdza, czy w zakresie [b,e] jest
element v, bp jest kryterium
sortowania
equal_range(b,e,v)
Dla elementu v szuka miejsca
wstawienia
equal_range(b,e,v,bp)
Dla elementu v szuka miejsca
wstawienia, bp jest kryterium
wyszukiwania
includes(b,e,b1,e1)
Sprawdza czy posortowany zakres
[b,e] zawiera wszystkie elementy z
zakresu [b1,e1]
includes(b,e,b1,e1,bp)
Sprawdza czy posortowany zakres
[b,e] zawiera wszystkie elementy z
zakresu [b1,e1], bp jest kryterium
sortowania
inplace_merge(b,e,e1)
Scala elementy z zakresu [b,e] oraz
[e,e1]
inplace_merge(b,e,e1,bp)
Scala elementy z zakresu [b,e] oraz
[e,e1]
lower_bound(b,e,v)
Zwraca pozycjÄ™ pierwszego elementu
o wartości v
lower_bound(b,e,v,bp)
Zwraca pozycjÄ™ pierwszego elementu
o wartości v, bp jest kryterium
sortowania
merge(b,e,b1,e,b2)
Scala wszystkie elementy z zakresu
[b,e] i [b1,e1]
merge(b,e,b1,e,b2,bp)
Scala wszystkie elementy z zakresu
[b,e] i [b1,e1], bp jest kryterium
sortowania
set_difference(b,e,b1,e1,b2)
Scala elementy z zakresów [b,e] i
[b1,e1], tak, że zbiór wynikowy
zawiera elementy, które nie
występują w drugim zbiorze.
set_difference(b,e,b1,e1,b2,bp)
Scala elementy z zakresów [b,e] i
Wprowadzenie do STL
157
[b1,e1], tak, że zbiór wynikowy
zawiera elementy, które nie
występują w drugim zbiorze, bp -
predykat
set_intersection(b,e,b1,e1,b2)
Scala dwa zbiory tak, że zbiór
wynikowy zawiera elementy, które
występują w obu zbiorach
set_intersection(b,e,b1,e1,b2, bp)
Scala dwa zbiory tak, że zbiór
wynikowy zawiera elementy, które
wystÄ™pujÄ… w obu zbiorach, bp –
kryterium sortowania
set_symetric_difference(b,e,b1,
Scala dwa zbiory tak, że zbiór
e1, b2)
wynikowy zawiera elementy, które
występują albo w pierwszym, albo w
drugim, ale nie jednocześnie
set_symetric_difference(b,e,b1,
Scala dwa zbiory tak, że zbiór
e1, b2, bp)
wynikowy zawiera elementy, które
występują albo w pierwszym, albo w
drugim, ale nie jednoczeÅ›nie, bp –
kryterium sortowania
set_union(b,e,b1,e1,b2)
Scala dwa zbiory tak, że zbiór
wynikowy zawiera elementy, które
występują albo w pierwszym, albo w
drugim, albo w obydwu
set_union(b,e,b1,e1,b2,bp)
Scala dwa zbiory tak, że zbiór
wynikowy zawiera elementy, które
występują albo w pierwszym, albo w
drugim, albo w obydwu, bp jest
kryterium sortowania
upper_bound(b,e,v)
Zwraca pozycjÄ™ ostatniego elementu
o wartości v
upper_bound(b,e,v,bp)
Zwraca pozycjÄ™ ostatniego elementu
o wartości v, bp jest kryterium
sortowania.
Zilustrujemy prostym przykładem zastosowania wybranych algorytmów
scalających. W programie utworzone zostaną dwa zbiory liczb całkowitych, a
następnie wykonane zostaną podstawowe operacje na zbiorach:
ï‚· unia (ang. union)
 różnica (ang. difference)
 różnica symetryczna (ang. symmetric difference)
 przecięcie (ang. intersection)
158
5. Algorytmy
Wydruk 5.17. Algorytmy scalajÄ…ce – set_intersection, set_union,