Алгоритмы

  • Статья
  • Чтение занимает 3 мин

Алгоритмы являются важнейшей частью стандартной библиотеки C++. Алгоритмы работают не с самими контейнерами, а с итераторами. Поэтому один и тот же алгоритм можно использовать с большинством, а то и со всеми контейнерами стандартной библиотеки C++. В этом разделе рассматриваются правила и терминология алгоритмов стандартной библиотеки C++.

Комментарии

Описания шаблонов функций алгоритма используют несколько сокращенных фраз:

  • Фраза "в диапазоне [A, B)" означает последовательность нулевых или более дискретных значений, начиная с A до , но не включая B. Диапазон действителен, только если B доступен из A, можно сохранить A в объекте N (N = A), можно увеличить объект ноль или более раз (++N), а объект равен B после конечного числа приращений (N == B).

  • Фраза "каждый N в диапазоне [A, B)" означает, что N начинается со значения A и увеличивается ноль или более раз, пока не будет равно значению B. Случай N == B не в диапазоне.

  • Фраза "наименьшее значение N в диапазоне [A, B) таким образом, что X" означает, что условие X определяется для каждого N в диапазоне [AB) вплоть до выполнения условия X.

  • Фраза "наибольшее значение N в диапазоне [A, B) таким образом, что X" означает, что условие X определяется для каждого N в диапазоне [A, B). Функция сохраняет в K копию N при каждом выполнении условия X . Если происходит такое хранение, функция заменяет конечное значение N, равное B, на значение K. Однако для итератора с двунаправленным или случайным доступом это также может означать, что N начинается с наибольшего значения в диапазоне и уменьшается по диапазону до тех пор, пока не будет выполнено условие X .

  • Выражения, такие как X - Y, где X и Y могут быть итераторами, отличными от итераторов произвольного доступа, предназначены в математическом смысле. Функция не обязательно вычисляет оператор - , если она должна определить такое значение. То же самое справедливо и для таких выражений, как X + N и X - N, где N — целочисленный тип.

Несколько алгоритмов используют предикат, выполняющие попарное сравнение, например, operator==, для получения результата bool. Функция предиката operator== или любая ее замена не должны изменять ни один из операндов. Он должен давать один и тот же bool результат при каждой оценке, и должен давать тот же результат, если копия любого из операндов заменяется операндом.

Некоторые алгоритмы используют предикат, который налагает строгое слабое упорядочение к парам элементов из последовательности. Для предиката pred(X, Y):

  • Строгий означает, что pred(X, X) имеет значение false.

  • Слабый означает, что X и Y имеют эквивалентный порядок, если ! pred(X, Y) && ! pred(Y, X) (X == Y не нужно определять).

  • Упорядочение означает, что pred(X, Y) &&pred(Y, Z) подразумевает pred(X, Z).

Некоторые из этих алгоритмов неявно используют предикат X<Y. Другие предикаты, которые обычно удовлетворяют строгому требованию к упорядочению, — это X>Y, less(X, Y) и greater(X, Y). Однако обратите внимание, что предикаты, такие как X<= Y и X>= Y , не удовлетворяют этому требованию.

Последовательность элементов, определяемая итераторами в диапазоне [First, ), является последовательностью, Lastупорядоченной оператором < , если для каждого N в диапазоне [0, Last - First) и для каждого M в диапазоне (N, Last - First) предикат !( *(First + M) < *(First + N)) имеет значение true. (Обратите внимание, что элементы сортируются по возрастанию.) Функция operator<предиката или ее замена не должны изменять ни один из ее операндов. Он должен давать один и тот же bool результат при каждой оценке, и должен давать тот же результат, если копия любого из операндов заменяется операндом. Кроме того она должен применить строгого слабое упорядочение с операндами, которые она сравнивает.

Последовательность элементов, обозначаемых итераторами в диапазоне [First, Last), представляет собой кучу, упорядоченную по operator< , если для каждого N в диапазоне [1, Last - First) предикат !( *Первое< *(First + N)) имеет значение true. (Первый элемент является самым большим.) В противном случае его внутренняя структура известна только функциям make_heapшаблона , pop_heapи push_heap. Как и в случае с упорядоченной последовательностью, функция operator<предиката или ее замена не должны изменять ни один из своих операндов, и она должна налагать строгий слабый порядок на сравниваемых операнды. Он должен давать один и тот же bool результат при каждой оценке, и должен давать тот же результат, если копия любого из операндов заменяется операндом.

Алгоритмы стандартной библиотеки C++ находятся в файлах заголовков <algorithm> и <numeric> .

См. также раздел

Справочник по стандартной библиотеке C++
Потокобезопасность в стандартной библиотеке C++