Алгоритмы

  • Статья

Алгоритмы являются важнейшей частью стандартной библиотеки 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). Функция сохраняет копию N при каждом выполнении условия X. Если такое хранилище происходит, функция заменяет окончательное значение N, равное B, значениеМ K. Однако для двунаправленного или случайного итератора доступа может также означать, что N начинается с самого высокого значения в диапазоне и уменьшается по диапазону до тех пор, пока условие X не будет выполнено.

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

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

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

  • Strict означает, что 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, (X, lessY) и greater(X, Y). Обратите внимание, что предикаты, такие как X<= Y и X>= Y , не удовлетворяют этому требованию.

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

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

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

См. также

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