C++/Algorytmy w STL

Z Wikibooks, biblioteki wolnych podręczników.
< 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]

Operacje niemodyfikujące[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

Operacje niemodyfikujące - szukanie[edytuj]

  • 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

Operacje modyfikujące[edytuj]

  • 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

Operacje zmieniające kolejność[edytuj]

  • 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

Operacje sortujące[edytuj]

  • 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 wyszukiwania binarnego[edytuj]

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 zbiorze[edytuj]

Operacje na posortowanych ciągach

Operacje na kopcu[edytuj]

  • 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

Operacje min max[edytuj]

  • 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ę

Operacje numeryczne[edytuj]

Zdefiniowane w nagłówku <numeric>