C++/Algorytmy w STL
< C++
Wstęp
[edytuj]Cóż znaczą biblioteki bez <algorithm>? Na pewno mniej, ponieważ każde modyfikacje na wektorach czy ciągach znaków są bardziej uciążliwe i wymagają od użytkownika dodatkowego wkładu pracy na napisanie algorytmu do wykonania określonego problemu. Weźmy pod uwagę przykładowo problem sortowania. Poniżej przedstawiona jest funkcja sortująca bąbelkowo n-elementową tablicę 1-wymiarową.
void sortowanie_babelkowe(int tab[], int n)
{
for (int j=n-1; j>0; --j)
for (int i=0; i<j; ++i)
if (tab[i]>tab[i+1])
{
int temp=tab[i];
tab[i]=tab[i+1];
tab[i+1]=temp;
}
}
Kod nie jest długi, ale wygodniej jest napisać:
sort(tab,tab+n);
Lista funkcji zawartych w bibliotece <algorithm>
[edytuj]Lista tematyczna
[edytuj]- for_each — wykonuje operację na każdym elemencie ciągu
- count — liczy ilość wystąpień danej wartości w ciągu
- count_if — zlicza w ciągu ilość wystąpień wartości spełniających warunek
- equal — określa czy dwa zbiory elementów są takie same
- mismatch — znajduje pierwszą parę różnych elementów dwóch ciągów
- find — znajduje pierwsze wystąpienie wartości w ciągu
- find_if — znajduje w ciągu pierwsze wystąpienie wartości spełniającej warunek
- find_end — znajduje ostatnie wystąpienie ciągu jako podciągu
- find_first_of — znajduje jakikolwiek element ze zbioru w danym ciągu
- adjacent_find — znajduje sąsiadującą parę wartości
- search — znajduje pierwsze wystąpienie ciągu jako podciągu
- search_n — znajduje pierwsze wystąpienie ciągu n-tu wartości w ciągu
- copy — kopiuje elementy jednego ciągu do drugiego
- copy_backward — kopiuje ciąg do drugiego ciągu, wstawiając elementy na jego koniec
- fill — zastępuje elementy ciągu podaną wartością
- fill_n — zastępuje n elementów ciągu podaną wartością
- generate — zastępuje elementy ciągu wartościami będącymi wynikiem funkcji
- generate_n — zastępuje n elementów ciągu wartościami będącymi wynikiem funkcji
- transform — wykonuje podaną funkcję dla argumentów ze zbioru i zapisuje wyniki w nowym ciągu
- remove — usuwa elementy o podanej wartości
- remove_if — usuwa elementy spełniające warunek
- remove_copy — kopiuje ciąg, usuwając elementy o podanej wartości
- remove_copy_if — kopiuje ciąg, usuwając elementy spełniające warunek
- replace — zastępuje elementy o danej wartości inną wartością
- replace_if — zastępuje elementy spełniające warunek
- replace_copy — kopiuje ciąg, zastępując elementy o danej wartości inną wartością
- replace_copy_if — kopiuje ciąg, zastępując elementy spełniające warunek
- partition — umieszcza elementy spełniające warunek przed tymi które go nie spełniają
- stable_partition — umieszcza elementy spełniające warunek przed tymi które go nie spełniają, zachowuje wzajemną kolejność
- random_shuffle — w losowy sposób zmienia kolejność elementów ciągu
- reverse — odwraca kolejność elementów w ciągu
- reverse_copy — kopiuje ciąg, odwracając kolejność elementów
- rotate — dokonuje rotacji elementów ciągu
- rotate_copy — kopiuje ciąg, przesuwając elementy (rotacja)
- unique — usuwa powtórzenia, w taki sposób że wśród sąsiadujących elementów nie ma dwóch takich samych
- unique_copy — kopiuje ciąg, w taki sposób że wśród sąsiadujących elementów nie ma dwóch takich samych
- swap — zamienia ze sobą dwa elementy
- swap_ranges — zamienia ze sobą dwa zbiory elementów
- iter_swap — zamienia ze sobą dwa elementy wskazywane przez iteratory
- sort — sortuje ciąg rosnąco
- partial_sort — sortuje pierwsze N najmniejszych elementów w ciągu
- partial_sort_copy — tworzy kopię N najmniejszych elementów ciągu
- stable_sort — sortuje ciąg zachowując wzajemną kolejność dla równych elementów
- nth_element — ciąg jest podzielony na dwie nieposortowane części elementów mniejszych i większych od wybranego elementu
Operacje na posortowanych ciągach
- lower_bound — zwraca iterator do pierwszego elementu równego lub większego od podanego
- upper_bound — zwraca iterator do pierwszego elementu większego od podanego
- binary_search — stwierdza czy element występuje w ciągu
- equal_range — zwraca parę określającą przedział wewnątrz którego występuje dana wartość (lub ich ciąg).
Operacje na posortowanych ciągach
- merge — łączy dwa ciągi w posortowany ciąg
- inplace_merge — łączy dwie posortowane części ciągu
- includes — zwraca prawdę jeśli pierwszy ciąg jest podciągiem drugiego
- set_difference — tworzy różnicę dwóch zbiorów
- set_intersection — tworzy przecięcie dwóch zbiorów
- set_symmetric_difference — tworzy zbiór złożony z elementów występujących w tylko jednym z dwóch ciągów
- set_union — tworzy sumę zbiorów
- is_heap — zwraca prawdę jeśli ciąg tworzy kopiec
- make_heap — przekształca ciąg elementów tak aby tworzyły kopiec
- push_heap — dodaje element do kopca
- pop_heap — usuwa element ze szczytu kopca
- sort_heap — przekształca ciąg o strukturze kopca w ciąg posortowany
- max — zwraca większy z dwóch elementów
- max_element — zwraca największy z elementów w ciągu
- min — zwraca mniejszy z elementów
- min_element — zwraca najmniejszy z elementów w ciągu
- lexicographical_compare — sprawdza czy jeden ciąg poprzedza leksykograficznie drugi ciąg
- next_permutation — przekształca ciąg elementów w leksykograficznie następną permutację
- prev_permutation — przekształca ciąg elementów w leksykograficznie poprzedzającą permutację
Zdefiniowane w nagłówku <numeric>
- accumulate — sumuje ciąg elementów
- inner_product — oblicza iloczyn skalarny na elementach dwóch ciągów
- adjacent_difference — oblicza różnice pomiędzy sąsiadującymi elementami w ciągu
- partial_sum — oblicza sumy częściowe ciągu elementów