Волкова немного о её семинарах (1119514), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

3. Сортировка.

Примеры :

Sort () – простая сортировка . Имеется также сортировка по возрастанию (операция должна быть определена для типа элемента в данном контейнере ).

Stable_sort () – сохраняет порядок следования одинаковых элементов (например, это бывает существенно при сортировке по нескольким ключам).

Merge () – склеивает две отсортированные последовательности.

Итераторы

Каждый контейнер обеспечивает свои итераторы, также поддерживающие стандартный набор итерационных операций со стандартными именами и смыслом. Итераторные классы и функции находятся в заголовочном файле <iterator>.

Итератор – это класс, объекты, которого по отношению к контейнерам играют роль указателей, они, по сути, склеивают ядро STL в одну библиотеку. Итераторы поддерживают абстрактную модель данных как последовательности объектов (что и представляет собой любой контейнер). Идея итератора достаточно проста. Обычно, основное действие с последовательностью элементов – перебор, и организуется он с помощью итераторов. Т.е. итератор – это класс, чьи объекты выполняют ту же роль по отношению к контейнеру, которую выполняют указатели по отношению к массиву. Указатель может использоваться в качестве средства доступа к элементам массива, а итератор - в качестве средства доступа к элементам контейнера. Но, понятия "нулевой итератор" не существует, при организации циклов происходит сравнение с концом последовательности.

Каждый контейнер содержит ряд ключевых функций-членов, позволяющих найти концы последовательности элементов в виде соответствующих значений итераторов. Это:

iterator begin(); – возвращает итератор, который указывает на первый элемент последовательности.

const_iterator begin() const;

iterator end(); – возвращает итератор, который указывает на элемент, следующий за последним элементом последовательности (используется при оформлении циклов).

const_iterator end () const;

reverse_iterator rbegin(); - возвращает итератор, указывающий на первый элемент в обратной последовательности (используется для работы с элементами последовательности в обратном порядке).

const_reverse_iterator begin() const;

reverse_iterator rend(); - возвращает итератор, указывающий на элемент, следующий за последним в обратной последовательности.

const_reverse_iterator rend () const;

“прямые “ итераторы :

“обратные” итераторы :

Пусть р - объект типа итератор. К каждому итератору можно применить, как минимум, три ключевые операции:

• *р – элемент, на который указывает итератор,

• р++ - переход к следующему элементу последовательности,

• == - операция сравнения.

Пример: iterator p = v.begin(); – такое присваивание верно независимо от того, какой контейнер v . Теперь *p – первый элемент контейнера v.

Замечание: при проходе последовательности как прямым, так и обратным итератором переход к следующему элементу будет р++ (а не р-- !).

Не все виды итераторов поддерживают один и тот же набор операций.

В библиотеке STL введено 5 категорий итераторов:

1. Вывода (output) ( запись в контейнер - *р = , ++ )

2. Ввода (input) (считывание из контейнера - = *р, , ++, ==, !=)

3. Однонаправленный (forward) (считывание и запись в одном направлении - *р =, , =*р, ++ , ==, != )

4. Двунаправленный (bidirectional) ( *р=, =*р, , ++,--, ==, != ) - list, map, set

5. C произвольным доступом (random_access) ( все 4. плюс [], +, -, +=, -=, <, >, <=, >= ) - vector,deque

Каждая последующая категория является более мощной, чем предыдущая.

Принято такое соглашение, что при описании алгоритмов, входящих в STL используют стандартные имена формальных параметров. В зависимости от названия итератора в профиле алгоритма, должен использоваться итератор уровня «не ниже чем». То есть по названию параметров шаблона можно понять, какого рода итератор нам нужен, то есть к какому контейнеру применим этот алгоритм.

Пример: шаблонная функция find(). Нужен итератор, с какого начинается поиск, каким заканчивается и элемент, который мы ищем. Для целей функции достаточно итератора ввода (из контейнера).

Template < class InputInterator, class T >

InputIterator find ( InputIterator first, InputIterator last, const T& value ) {

while ( first != last && first != value ) first ++;

return first;

}

Однако категория итераторов не принимает участия в вычислениях. Этот механизм относится исключительно к компиляции.

Контейнер вектор

template < class T , class A = allocator < T > > сlass vector {

.......

public:

// vector – имя контейнера,

// T – тип элементов контейнера (value_type),

// A – распределитель памяти (allocator_type) - необязательный параметр.

// Типы - 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 (или с "нулями" типа

// Т, если второй параметр отсутствует; в этом случае конструктор

// умолчания в классе Т обязателен)

template <class I> vector (I first, I last, const A& = A()); // инициализация вектора копированием элементов из [first, last), I - итератор для чтения

vector (const vector < T, A > & obj ); // конструктор копирования

vector& operator = (const vector < T, A > & obj );

~vector();

//……

// Некоторые функции-члены класса vector

//

iterator erase (iterator i ); // удаляет элемент, на который указывает данный

// итератор. Возвращает итератор элемента, следующего за удаленным.

iterator erase (iterator st, iterator fin); // удалению подлежат все элементы

// между st и fin, но fin не удаляется. Возвращает fin.

Iterator insert ( iterator i , const Т& value = T()); // вставка некоторого

// значения value перед i. Возвращает итератор вставленного элемента).

void insert (iterator i , size_type n, const T&value); // вставка n копий

// элементов со значением value перед i.

void push_back ( const T&value ) ; // добавляет элемент в конец вектора

void pop_back () ; // удаляет последний элемент (не возвращает значение!)

size_type size() const; // выдает количество элементов вектора

bool empty () const; // возвращает истину, если вызывающий вектор пуст

void clear(); //удаляет все элементы вектора

……….

}

Пример 1. Печать элементов вектора в прямом порядке.

# include < vector >;

using namespace std;

int main () {

vector < int > V( 100,5 );

vector < int > :: const_iterator p = V.begin ();

while (p != V.end ()) {

cout << *p << ’ ’;

p++;

}

cout << endl ;

}

Или в обратном порядке :

…

vector < int > :: const_reverse_iterator q = V.rbegin ( );

while ( q != V.rend ()) {

cout << *q << ’ ’; // печать в обратном порядке //

q++;

}

cout << endl;

…

Пример 2. Формирование вектора из чисел от 0 до 9

int main () {

vector < int > V ; // вектор 0-ой длины //

int i ;

for ( i = 0 ; i < 10 ; i++ ) V.push_back (i) ;

cout << V.size () << endl ; //10

// vector <int > :: iterator p=V.begin ( ) ;

// p+=2; // p++ ; p++;

}

Контейнер список

template < class T , class A = allocator < T > > сlass list {

...........

public:

// list – имя контейнера,

// T – тип элементов, которые будут храниться в списке,

// A – распределитель памяти.

// Типы

// ……..

// Итераторы

// ……..

//

// Доступ к элементам

//

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 (или с "нулями" типа

// Т, если второй параметр отсутствует

template <class I> list (I first, I last, const A& = A()); // инициализация списка копированием элементов из [first, last), I - итератор для чтения

list (const list < T, A > & obj ); // конструктор копирования

list& operator = (const list < T, A > & obj );

~list();

//……

// Некоторые функции-члены класса list

//

iterator erase (iterator i ); // удаляет элемент, на который указывает данный

// итератор. Возвращает итератор элемента, следующего за удаленным.

iterator erase (iterator st, iterator fin); // удалению подлежат все элементы

// между st и fin, но fin не удаляется. Возвращает fin.

Iterator insert ( iterator i , const Т& value = T()); // вставка некоторого

// значения value перед i. Возвращает итератор вставленного элемента).

void insert (iterator i , size_type n, const T&value); // вставка n копий

// элементов со значением value перед i.

void push_back ( const T&value ) ; // добавляет элемент в конец списка

void push_front ( const T&value ) ; // добавляет элемент в начало списка

void pop_back () ; // удаляет последний элемент (не возвращает значение!)

void pop_front () ; // удаляет первый элемент списка

size_type size() const; // выдает количество элементов списка

bool empty () const; // возвращает истину, если вызывающий список пуст

void clear(); //удаляет все элементы списка

……….

}

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

# include < iostream >

# include < list >

using namespace std;

void g (list <double> &lst) {

list < double > :: const_iterator p = lst.begin ();

double s = 0; int n;

while ( p!=lst.end ()) {

s = s+*p; n++; p++;

}

if (n != 0) lst.push_back (s/n); // lst.push_back (s/lst.size());

}

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

Характеристики

Список файлов семинаров