книга (И.А. Волкова, А.В. Иванов, Л.Е. Карпов - Основы объектно-ориентированного программирования. Язык программирования С++), страница 18

Такие операции являются универсальными для любого из контейнеров и поэтому находятся вне этих контейнеров. Зная, как устроены алгоритмы, можно писать необходимые дополнительные алгоритмы обработки,которые не будут зависеть от контейнера.Каждый алгоритм представлен шаблоном функции или набором шаблонов функций. Все стандартные алгоритмы находятся в пространстве именstd, а их объявления — в библиотечном файле ‹algorithm›.Можно выделить три основные группы алгоритмов:1) Немодифицирующие алгоритмы, те, которые извлекают информацию из контейнера (о его устройстве, об элементах, которые таместь и т.

д.), но никак не модифицируют сам контейнер (ни элементы, ни порядок их расположения).Примеры:— find() — поиск первого вхождения элемента с заданным значением;— count() — количество вхождений элемента с заданным значением;— for_each() — для применения некоторой операции к каждому элементу, не изменяющей элементы контейнера.2) Модифицирующие алгоритмы, которые каким-либо образом изменяют содержимое контейнера. Либо сами элементы меняются,либо их порядок, либо их количество.Примеры:— transform() — для применения некоторой операции к каждому элементу, изменяющей элементы контейнера в отличие от алгоритмаfor_each;— reverse() — переставляет элементы в последовательности;117Стандартная Библиотека шаблонов STL—copy() — создает новый контейнер.3) Сортировка.Примеры:sort() — простая сортировка;— stable_sort() — сохраняет порядок следования одинаковых элементов;— merge() — объединяет две отсортированные последовательности.—16.5.

Достоинства и недостаткиSTL-подходаДостоинстваНедостаткиКаждый контейнер обеспечиваетстандартный интерфейс в виде набора операций, так что один контейнерможет использоваться вместо другого, причем это не влечет существенного изменения кодаКонтейнеры не имеют фиксированного стандартного представления.Они не являются производными отнекоторого базового класса. Это жеверно и для итераторов. Использование стандартных контейнеровДополнительная общность исполь- и итераторов не подразумевает низования обеспечивается через стан- какой явной или неявной проверкитипов во время выполнения.дартные итераторы.Каждыйконтейнерсвязанс распределителем памяти (аллокатором), который можно переопределить с тем, чтобы реализовать собственный механизм распределения памяти.Для каждого контейнера можно определить дополнительные итераторыи интерфейсы, что позволит оптимальным образом настроить его длярешения конкретной задачи.Контейнеры по определению однородны, т.е. должны содержать элементы одного типа, но возможносоздание разнородных контейнеровкак контейнеров, содержащих указатели на общий базовый класс.Алгоритмы, входящие в состав STL,предназначеныдляработыс содержимым контейнеров.

Все алгоритмы представляют собой шаблонные функции, следовательно, ихможно использовать для работы118Каждый доступ к итератору приводит к вызову виртуальной функции.Эти затраты по сравнению с вызовомобычной функции могут быть значительными.Предотвращение выхода за пределыконтейнера по-прежнему возлагаетсяна программиста, при этом каких-тоспециальных средств для такогоконтроля не предлагается.Стандартная Библиотека шаблонов STLс любым контейнером.16.6. Контейнер векторtemplate <class T , class A = allocator <T> > сlass vector{// vector — имя контейнера,// T — тип элементов контейнера (value_type),// A — распределитель памяти (allocator_type) —необязательный параметр........public:// Типы - typedef// . .

.// Итераторы// . . .//// Доступ к элементам://reference operator[] ( size_type n );// проверки// диапазона// доступ безconst_reference operator[] ( size_type n ) const;заreference at ( size_type n );// доступ с проверкой диапазона (если индекс выходит// пределы диапазона, то возбуждается исключение// out_of_range)const_reference at ( size_type n ) const;reference front();вектора// первый элементconst_reference front() const;reference back();вектора// последний элементconst_reference back() const;//////////////////Конструкторы:Конструкторы, которые могут вызываться с однимпараметром, для предотвращения случайногопреобразования объявлены explicit.Это означает, что конструктор может вызыватьсятолько явно:vector<int>v=10 - ошибка, попытка неявногопреобразования числа 10 в vector<int>explicit vector ( const A&=A() );// конструктор умолчания — создается вектор нулевой// длиныexplicit vector ( size_type n, const T& value = T(),const A& = A() );// создается вектор из n элементов со значением value// (или со значениями типа Т, создаваемыми поумолчанию,// если второй параметр отсутствует.

в этом случае// конструктор умолчания в классе Т — обязателен)119Стандартная Библиотека шаблонов STLtemplate <class I> vector ( I first, I last,const A& = A() );// I - итератор. Инициализация вектора копированием// элемента, на который указывает итератор first, вовсе// элементы из диапазона [first, last) (уже было// отмечено, что функция end() возвращает итератор,// который указывает на элемент, следующий запоследним// элементом).vector ( const vector < T, A > & obj );// конструктор копирования~vector(); // деструктор// . .

.// Некоторые методы класса vector//vector& operator = ( const vector < T, A > & obj );bool empty () const{...}//истина, если контейнер пустsize_type size () const{...} //выдача текущего размераiterator insert ( iterator i, const T& value ){...}// вставка перед элементомiterator insert ( iterator i, size_type number,const T & value ){...}// вставка нескольких одинаковых элементов передэлементомvoid push_back ( const T&value ){insert ( end(),value );}//вставка в конец контейнера120Стандартная Библиотека шаблонов STLvoid clear (){erase ( begin(), end() );}// уничтожение всех элементов, при этом память не// освобождается, так как деструктор самого вектора не// вызываетсяiterator erase ( iterator i ){...return ( i );}// уничтожение заданного элемента и выдача// итератора элемента, следующего за удалённымiterator erase ( iterator start, iterator finish )// уничтожение диапазона [start,finish) и выдача// итератора элемента, следующего за последним// удалённым{...return ( finish );}// уничтожение последнего элементаvoid pop_back (){erase (end() - 1);}// содержимое первого элементаreference front (){return * begin ();}// содержимое последнего элементаreference back (){return *(end () — 1);}reference operator [](size_type i){121Стандартная Библиотека шаблонов STLreturn * (begin () + i); // индексация вектора}/* (аналог индексации) выдает содержимое элемента i.Метод at() может возбудить исключение out_of_range.

*/reference at (size_t i){ ... }}Для организации поиска в контейнере в обратном порядке (от конца кначалу) обычно пишутся такие циклы:template <class C> typename C::const_iterator find_last(const C& c, typename C::value_type v){typename C::const_iterator p = c.end ();while (p != c.begin ()) if (* --p == v) return p;return c.end ();}Применив обратный итератор, можно воспользоваться библиотечнойфункцией поиска со всеми её преимуществами и без потери эффективности:template <class C> typename C::const_iterator find_last (const C& c, typename C::value_type v){typename C::const_reverse_iterator ri = find (c.rbegin (), c.rend (), v);if ( i == c.rend ()return c.end ();typename C::iterator i = ri.base ();return --i;}Для обратного итератора выполнение операции ri.base() выдаёт значение типа iterator, указывающее на один элемент вперёд позиции, на которуюуказывает сам обратный итератор ri.

Между итератором i и соответствующимобратным итератором существует фундаментальное отношение, выражающееся равенством&*(reverse_iterator(i)) == &*(i - 1)Операции insert() и erase() определены только для обычных итераторов,поэтому организуя циклы по обратным итераторам, эти обратные итераторынадо сначала преобразовывать к обычным, а лишь затем выполнять вставкуили уничтожение элементов:vector <int> :: reverse_iterator ri = v.rbegin ();while (ri != v.rend ())if (* ri ++ == Element){vector<int>::iterator i = ri.base ();v.insert (i, - Element); // перед заданным// элементом122Стандартная Библиотека шаблонов STL// вставить ещё один,// с обратнымbreak;}16.7.

Контейнер списокКонтейнер Список имеет аналогичный с контейнером список набор основных методов.template <class T, class A = allocator <T> > сlass list{// list — имя контейнера,// T — тип элементов, которые будут храниться в списке,// A — распределитель памяти.// ...........public:// Типы - typedef//. .

.// Итераторы//. . .//// Доступ к элементам//reference front(); // первый элемент спискаconst_reference front() const;reference back();// последний элемент спискаconst_reference back() const;//// Конструкторы://explicit list(const A&=A()); // создается список// нулевой длиныexplicit list(size_type n, const T& value = T(),constA& = A());// создается список из n элементов со значением value//(или со значениями типа Т, создаваемыми поумолчанию,// если второй параметр отсутствует. в этом случае// конструктор умолчания в классе Т — обязателен)template <class I> list(I first, I last, const A& =A());// I - итератор.