14. Группы алгоритмов. Алгоритмы «по месту», копирующие алгоритмы. Сравнение функций stl и методов контейнеров stl

Группы алгоритмов

STL разделяет библиотеку алгоритмов на четыре группы:  немодифицирующие (non mutating) последовательные операции;  модифицирующие (mutating) последовательные операции;  сортирующие (sort) и связанные с ними операции;  обобщенные числовые операции. Первые три группы описаны в заголовочном файле algorithm, а четвертая группа, будучи специально ориентированной на числовые данные, имеет собственный заголовочный файл numeric (раньше algo.h). Немодифицирующие последовательные операции обрабатывают каждый элемент в диапазоне. Эти операции оставляют контейнер без изменений. Например, find() и for_each() относятся к этой категории. Модифицирующие последовательные операции также обрабатывают каждый элемент в контейнере. Они могут изменить содержимое контейнера. Изменения могут касаться значений либо порядка, в котором они сохранены. Функции transform(), random_shuffle() и copy() относятся к этой категории. Сортирующие и связанные с ними операции включают некоторые сортирующие функции (в том числе sort()), а также ряд других функций, включая операции с наборами (множествами). Числовые операции включают функции для суммирования содержимого диапазона, вычисления внутреннего произведения двух контейнеров, подсчета частичных сумм и вычисления разностей соседних элементов. Как правило, эти операции характерны для массивов, поэтому vector — это контейнер, который наиболее вероятно будет использован с ними.

Один из способов классификации алгоритмов основан на том, куда должен быть помещен результат работы алгоритма. Некоторые алгоритмы делают свою работу на месте, другие создают копии. Например, по завершении работы функции sort() результат занимает то же местоположение, которое занимали исходные данные. Поэтому функция sort() является алгоритмом называемым "поместу". Однако функция сору() отправляет результат своей работы в другое местоположение, поэтому она является копирующим алгоритмом. Функция transform() может делать и то, и другое. Подобно сору(), она использует выходной итератор для указания места помещения результата. Но, в отличие от сору(), transform() позволяет выходному итератору указывать позицию внутри входного диапазона, поэтому она может копировать трансформированные значения поверх исходных. Некоторые алгоритмы имеют две версии: "по месту" и копирующую. В соответствии с соглашением STL, к имени копирующей версии добавляется _сору.

СРАВНЕНИЕ ФУНКЦИЙ И МЕТОДОВ КОНТЕЙНЕРОВ Возникают ситуации, когда требуется произвести выбор между использованием метода STL либо функции STL. Обычно лучшим вариантом является метод контейнера. Во-первых, он должен быть лучше оптимизирован для конкретного контейнера. Во-вторых, будучи методом-элементом, он может пользоваться средствами управления памятью класса шаблона и при необходимости изменять размер контейнера. Предположим, например, что имеется список чисел, и нужно удалить из него все экземпляры определенного значения, скажем, 4. Если intList — это объект list, то можно применить метод remove() списка: intList.remove(4);//удаление всех четверок из списка После вызова этого метода все элементы со значением 4 удаляются из списка и размер списка автоматически изменяется. В STL существует также алгоритм remove(). Вместо того чтобы вызываться объектом, он принимает аргументы, задающие диапазон. Поэтому, если intList — это объект list, то вызов данной функции может выглядеть следующим образом: remove (intList.begin(), intList.end(), 4); Однако, поскольку функция remove() не является элементом класса, то она не может изменить размер списка. Вместо этого она удостоверяется, что все не удаленные элементы располагаются в начале списка, и возвращает итератор, указывающий на новое значение за концом списка. Затем этот итератор можно применять для корректировки размеров списка. Например, метод erase() списка можно использовать для удаления диапазона, который описывает более не нужную часть списка.