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,
W trosce o komfort korzystania z naszego serwisu chcemy dostarczaÄ Ci coraz lepsze usĹugi. By mĂłc to robiÄ prosimy, abyĹ wyraziĹ zgodÄ na dopasowanie treĹci marketingowych do Twoich zachowaĹ w serwisie. Zgoda ta pozwoli nam czÄĹciowo finansowaÄ rozwĂłj Ĺwiadczonych usĹug.
PamiÄtaj, Ĺźe dbamy o TwojÄ prywatnoĹÄ. Nie zwiÄkszamy zakresu naszych uprawnieĹ bez Twojej zgody. Zadbamy rĂłwnieĹź o bezpieczeĹstwo Twoich danych. WyraĹźonÄ zgodÄ moĹźesz cofnÄ Ä w kaĹźdej chwili.