И.А. Волкова, А.В. Иванов, Л.Е. Карпов - Основы объектно-ориентированного программирования. Язык программирования С++ (ЧБ) (1114895), страница 18
Текст из файла (страница 18)
Зная, как устроены алгоритмы, можно писатьнеобходимые дополнительные алгоритмы обработки, которые не будут зависетьот контейнера.Каждый алгоритм представлен шаблоном функции или набором шаблоновфункций. Все стандартные алгоритмы находятся в пространстве имен std, а ихобъявления – в библиотечном файле <algorithm>.Можно выделить три основные группы алгоритмов:1.
Немодифицирующие алгоритмы, те, которые извлекают информациюиз контейнера (о его устройстве, об элементах, которые там есть и т. д.),но никак не модифицируют сам контейнер (ни элементы, ни порядок ихрасположения).Примеры:find()count()for_each()– поиск первого вхождения элемента с заданнымзначением– количество вхождений элемента с заданным значением– для применения некоторой операции к каждомуэлементу, не изменяющей элементы контейнера2. Модифицирующие алгоритмы, которые каким-либо образом изменяютсодержимое контейнера.
Либо сами элементы меняются, либо их порядок, либо их количество.102Примеры:transform()reverse()copy()– для применения некоторой операции к каждомуэлементу, изменяющей элементы контейнера в отличиеот алгоритма for_each– переставляет элементы в последовательности– создает новый контейнер3. Сортировка.Примеры:sort()– простая сортировкаstable_sort() – сохраняет порядок следования одинаковых элементовmerge()– объединяет две отсортированные последовательности16.5. Достоинства и недостатки STL-подхода+Каждый контейнер обеспечивает стандартный интерфейс в виденабора операций, так что один контейнер может использоваться вместо другого, причем это не влечет существенного изменения кода+Дополнительная общность использования обеспечивается черезстандартные итераторы.Каждый контейнер связан с распределителем памяти (аллокатором),+который можно переопределить с тем, чтобы реализовать собственный механизм распределения памяти.+Для каждого контейнера можно определить дополнительные итераторы и интерфейсы, что позволит оптимальным образом настроить его длярешения конкретной задачи.+Контейнеры по определению однородны, т.е.
должны содержатьэлементы одного типа, но возможно создание разнородных контейнеров какконтейнеров, содержащих указатели на общий базовый класс.+Алгоритмы, входящие в состав STL, предназначены для работы ссодержимым контейнеров. Все алгоритмы представляют собой шаблонныефункции, следовательно, их можно использовать для работы с любым контейнером.Контейнеры не имеют фиксированного стандартного представления.Они не являются производными от некоторого базового класса.
Это же вернои для итераторов. Использование стандартных контейнеров и итераторов неподразумевает никакой явной или неявной проверки типов во время выполнения.Каждый доступ к итератору приводит к вызову виртуальной функции. Эти затраты по сравнению с вызовом обычной функции могут бытьзначительными.Предотвращение выхода за пределы контейнера по-прежнему возлагается на программиста, при этом каких-то специальных средств для такогоконтроля не предлагается.10316.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());// конструктор умолчания – создается вектор нулевой// длины104explicit vector(size_type n, const T& value = T(),const A& = A());// создается вектор из n элементов со значением value// (или со значениями типа Т, создаваемыми по умолчанию,// если второй параметр отсутствует.
В этом случае// конструктор умолчания в классе Т – обязателен)template <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) {...}// вставка перед элементом…ivalue…res (на вставленный элемент)iterator insert (iterator i, size_type number,const T & value){...}// вставка нескольких одинаковых элементов перед элементомvoid push_back (const T&value) {insert(end(),value);}//вставка в конец контейнера105void clear () {erase (begin(), end());}// уничтожение всех элементов, при этом память не// освобождается, так как деструктор самого вектора не// вызываетсяiterator erase (iterator i) { ... return (res); }// уничтожение заданного элемента и выдача итератора// элемента, следующего за удалённымires……iterator erase (iterator start, iterator finish)// уничтожение диапазона [start,finish) и выдача// итератора элемента, следующего за последним удалённым{ ...
return (finish);}startfinish = res……void pop_back () {erase (end() - 1); }// уничтожение последнего элементаreference front () {return * begin (); }// содержимое первого элементаreference back () {return *(end () – 1); }// содержимое последнего элементаreference operator [](size_type i) {return * (begin () + i); // индексация вектора}reference at (size_t i) { ... } // (аналог индексации) выдает// содержимое элемента i.// Метод at() может возбудить// исключение out_of_range.}Для организации поиска в контейнере в обратном порядке (от конца к началу) обычно пишутся такие циклы: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 ();}106Применив обратный итератор, можно воспользоваться библиотечнойфункцией поиска со всеми её преимуществами и без потери эффективности: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 (ri == c.rend ())return c.end ();typename C::const_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); // перед заданным// элементом// вставить ещё один,// с обратным знакомbreak;}107v.capacity()vector vv.size()past-the-end-elementэлементыдополнительное пространствоv.rend()v.begin()16.7.v.rbegin() v.end()Контейнер списокКонтейнер Список имеет аналогичный с контейнером список набор основных методов.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(),const A& = A());// создается список из n элементов со значением value//(или со значениями типа Т, создаваемыми по умолчанию,// если второй параметр отсутствует. В этом случае// конструктор умолчания в классе Т – обязателен)108template <class I> list(I first, I last, const A& = A());// I - итератор.
Инициализация списка копированием// элемента, на который указывает итератор first, во все// элементы из диапазона [first, last) (уже было// отмечено, что функция end() возвращает итератор,// который указывает на элемент, следующий за последним// элементом).list(const list <T,A> & obj);// конструктор копирования~list(); // деструктор// .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
