Однако они не являются методами контейнерных классов. Наоборот, алгоритмы представлены в STL в форме глобальных шаблонных функций

Благодаря этому достигается их универсальность: эти функции можно применять не только к объектам различных контейнерных классов, но также и к массивам.

Независимость от типов контейнеров достигается за счет косвенной связи функции с контейнером: в функцию передается не сам контейнер, а пара адресов first, last, задающая диапазон обрабатываемых элементов.

Реализация указанного механизма взаимодействия базируется на использовании так называемых итераторов.

Итераторы — это обобщение концепции указателей: они ссылаются на элементы контейнера. Их можно инкрементировать, как обычные указатели, для последовательного продвижения по контейнеру, а также разыменовывать для получения или изменения значения элемента. Для них должны быть определены операции сравнения, операция присваивания.

Итераторы предназначены для предоставления единого метода последовательного доступа (перебора) элементов контейнера, не зависящего от вида контейнера и типа элементов в нем. Итератор может пробегать как все элементы, так и некоторое их подмножество

В результате использования итераторов алгоритм может «не замечать», с каким контейнером он работает. Тем самым появляется возможность унификации алгоритмов.

Итератор обеспечивает:

· единый механизм перебора элементов контейнера, не зависящий ни от его вида, ни от его реализации, ни от типа элементов;

· множественный доступ к контейнеру, позволяющий работать с контейнером сразу нескольким клиентам, при этом каждый из клиентов будет пользоваться своим итератором.

При последовательном переборе элементов контейнера итератор не обязательно перемещается только по смежным (соседним) элементам.

Алгоритм последовательного перебора элементов для каждого вида итератора и для различных контейнеров может быть определен по-своему.

Но для алгоритма – пользователя, который пользуется итератором, обращаясь к элементам контейнера, совокупность перебираемых элементов представляется в виде последовательности, имеющей начало и конец.

Итератор – это абстракция, обобщающая понятие указателя. Подобно тому, как значением указателя является адрес элемента массива, так значением итератора служит позиция элемента в контейнере.

Внешне одинаковые операции, получаемые при операциях с итераторами разных контейнеров, могут быть по - разному получены внутри контейнеров.

Так перемещение итератора к следующему элементу контейнера (операция ++) по-разному реализуется в векторе и в списке.

Следовательно, для каждого класса контейнеров должен быть определен свой класс (или несколько классов) итераторов (локальный или дружественный), предоставляющий средства для создания итератора для обхода элементов контейнера.

Контейнер содержит элементы последовательности, начало и конец последовательности представляются значениями итераторов.

Эти значения доступны с помощью методов любого контейнерного класса:

begin()- возвращает значение итератора (позицию в контейнере), установленного на начало последовательности;

end()- возвращает значение итератора, установленного за последним элементом последовательности.