Share via

Algorytmy

  • Artykuł

Algorytmy są podstawową częścią standardowej biblioteki języka C++. Algorytmy nie działają z samymi kontenerami, ale z iteratorami. W związku z tym ten sam algorytm może być używany przez większość, jeśli nie wszystkie kontenery biblioteki standardowej języka C++. W tej sekcji omówiono konwencje i terminologię algorytmów standardowej biblioteki języka C++.

Uwagi

Opisy szablonów funkcji algorytmu używają kilku skróconych fraz:

  • Fraza "w zakresie [A, B)" oznacza sekwencję zera lub większej liczby dyskretnych wartości rozpoczynających się od A do, ale nie w tym B. Zakres jest prawidłowy tylko wtedy, gdy B jest osiągalny z A, można przechowywaćA w obiekcie N (N = A), można zwiększać obiekt zero lub więcej razy (++N) i mieć obiekt porównywany z B po skończonej liczbie przyrostów (N == B).

  • Wyrażenie "każdy N w zakresie [A, B)" oznacza, że N zaczyna się od wartości A i jest zwiększana zero lub więcej razy, dopóki nie będzie równa wartości B. Przypadek N == B nie znajduje się w zakresie.

  • Wyrażenie "najniższa wartość N w zakresie [A, B), takie jak X" oznacza, że warunek X jest określany dla każdego N w zakresie [A, B) do momentu spełnienia warunku X.

  • Wyrażenie "najwyższa wartość N w zakresie [A, B), takie jak X" oznacza, że X jest określany dla każdego N w zakresie [A, B). Funkcja przechowuje w K kopię N za każdym razem, gdy warunek X jest spełniony. Jeśli wystąpi taki magazyn, funkcja zastępuje końcową wartość N, która jest równa B, z wartością K. W przypadku iteratora dwukierunkowego lub losowego dostępu może również oznaczać, że N zaczyna się od najwyższej wartości w zakresie i jest dekrementowany w zakresie do momentu spełnienia warunku X .

  • Wyrażenia, takie jak X - Y, gdzie X i Y mogą być iteratorami innymi niż iteratory dostępu losowego, są przeznaczone w sensie matematycznym. Funkcja nie musi oceniać operatora - , jeśli musi określić taką wartość. To samo dotyczy również wyrażeń, takich jak X + N i X - N, gdzie N jest typem liczby całkowitej.

Kilka algorytmów korzysta z predykatu, który wykonuje porównanie parowe, takie jak z operator==, w celu uzyskania bool wyniku. Funkcja operator==predykatu lub jej zamiana nie może zmieniać żadnego z jego operandów. Musi zwracać ten sam wynik za każdym razem, gdy jest obliczany, i musi zwracać ten sam bool wynik, jeśli kopia dowolnego operandu zostanie zastąpiona argumentem operandu.

Kilka algorytmów korzysta z predykatu, który musi nakładać ścisłe słabe kolejność na pary elementów z sekwencji. Dla predykatu pred(X, Y):

  • Strict oznacza, że pred(X, X) jest fałszywe.

  • Weak oznacza, że X i Y mają równoważne kolejność, jeśli !pred(X, Y) && !pred(Y, X) (X == nie musi być zdefiniowany).

  • Kolejność oznacza, że pred(X, Y) && pred(Y, Z) oznacza pred(X, Z).

Niektóre z tych algorytmów niejawnie używają predykatu X<Y. Inne predykaty, które zwykle spełniają ścisłe wymagania dotyczące słabego porządkowania, to X>Y, less(X, Y) i greater(X, Y). Należy jednak pamiętać, że predykaty, takie jak X<= Y i X>= Y, nie spełniają tego wymagania.

Sekwencja elementów wyznaczonych przez iteratory w zakresie [First, ) jest sekwencją uporządkowaną według operatora<, jeśli dla każdego N w zakresie [0, LastFirst - ) i dla każdego M w zakresie (N, LastFirst - ) predykat !( Last *(M) < *(First + First + N)) ma wartość true. (Pamiętaj, że elementy są sortowane w kolejności rosnącej). Funkcja operator<predykatu lub jej zamiana nie może zmieniać żadnego z jego operandów. Musi zwracać ten sam wynik za każdym razem, gdy jest obliczany, i musi zwracać ten sam bool wynik, jeśli kopia dowolnego operandu zostanie zastąpiona argumentem operandu. Ponadto musi narzucić ścisłe słabe porządkowanie operandów, które porównuje.

Sekwencja elementów wyznaczonych przez iteratory w zakresie [First, ) jest stertą uporządkowaną wedługoperator<, jeśli dla każdego N w zakresie [1, Last - First) predykat !( Last *Pierwszy< *(First + N)) ma wartość true. (Pierwszy element jest największy). Jego struktura wewnętrzna jest inaczej znana tylko z funkcji make_heapszablonu , pop_heapi push_heap. Podobnie jak w przypadku uporządkowanej sekwencji, funkcja operator<predykatu lub jakikolwiek zamiennik dla niego, nie może zmienić żadnego z jego operandów i musi narzucić ścisłe słabe kolejność na operandach, które porównuje. Musi zwracać ten sam wynik za każdym razem, gdy jest obliczany, i musi zwracać ten sam bool wynik, jeśli kopia dowolnego operandu zostanie zastąpiona argumentem operandu.

Algorytmy standardowej biblioteki języka C++ znajdują się w plikach nagłówków <algorithm> i .<numeric>

Zobacz też

Dokumentacja standardowej biblioteki C++
Bezpieczeństwo wątku w standardowej bibliotece C++