Class Т определяет тип элементов, хранимых в векторе. class А определяет тип класса, отвечающего за распределение памяти для элементов вектора. - презентация

1

2

3

4

5

6 class Т определяет тип элементов, хранимых в векторе. class А определяет тип класса, отвечающего за распределение памяти для элементов вектора.

7 По умолчанию память для элементов вектора распределяется и освобождается глобальными операторами new() и delete (). Таким образом, для создания нового элемента вектора вызывается конструктор класса Т. Для встроенных типов данных векторы можно определить следующим образом: //Вектор целых чисел vector vints; //Вектор чисел типа double vector vDbls; Обычно пользователь знает, сколько элементов будет содержаться в векторе. В этом случае он может зарезервировать память в векторе для нужного числа элементов, указав его после имени объекта в круглых скобках, например: vector int s(50); Количество элементов в векторе можно узнать с помощью функции- члена size (): size_type size() const; Функция resize изменяет величину вектора. Она имеет следующий прототип: void resize(size_type sz);

8 Если новая величина вектора sz больше текущей, то в конец вектора добавляется нужное число элементов класса Т. Если же новая величина вектора меньше текущей, вектор усекается с конца. Функция void pop_back();//удаляет последний элемент вектора. Обращаться к элементам вектора можно по индексам. Значения индекса начинаются с нуля. Например, присвоить значение четвертому элементу объявленного выше вектора можно следующим образом: ints[3] = 15; Если первоначально зарезервированная память для элементов вектора исчерпана, число элементов вектора будет автоматически увеличено. Добавить элемент в конец вектора можно с помощью функции-члена push_back(), однако она требует, чтобы в классе хранимых в контейнере объектов был определен конструктор копирования (эта функция добавляет в контейнер копию элемента). Она имеет следующий прототип: void push_back(const Т& х); //Добавить элемент в конец вектора Проверить, не является ли контейнер пустым, можно с помощью функции- члена empty (): bool empty() const; //является ли контейнер пустым Она принимает значение true, если контейнер пуст. Функция clear (), имеющая следующий прототип: void clear();//удаляет все элементы из вектора.

9 Функция front () возвращает ссылку на первый элемент в списке, а функция back () - на последний. Функция at () работает подобно оператору индексирования ( [ ] ), но является более безопасной, поскольку проверяет, попадает ли переданный ей индекс в диапазон допустимых значений. Если индекс вне диапазона, она генерирует исключение out_of _range. Функция insert () вставляет один или несколько элементов, начиная с указанной позиции в векторе. Функция pop_back () удаляет из вектора последний элемент. Кроме того, для класса vector определены обычные операции сравнения.

10 Пример использования вектора в качестве контейнера: #include using namespace std; int main() {//Создаем вектор нулевой длины vector v; int i; //Помещение значений в вектор for (i=0; i

11

12 Функция iterator insert (iterator position, const T& x); вставляет элемент x перед элементом, позиция которого задана параметром position. Возвращаемое значение указывает на вставленный элемент. Кроме обычных итераторов, в контейнере определены обратные (или реверсивные) итераторы, которые имеют тип reverse_iterator. Такие итераторы используются для прохода последовательного контейнера в обратном направлении, то есть от последнего элемента к первому. Инкремент обратного итератора приводит к тому, что он начинает указывать на предыдущий элемент, а декремент - к тому, что он указывает на следующий элемент. Функция reverse_iterator rbegin();возвращает обратный итератор произвольного доступа, который указывает на область памяти за последним элементом. Функция reverse_iterator rend();возвращает обратный итератор произвольного доступа, который указывает на первый элемент.

13 Рассмотрим пример работы с векторным контейнером с помощью итераторов. #include using namespace std; int main() { //Создаем вектор нулевой длины vector v; int i; //Помещение значений в вектор for (i=0; i

14 Списки Список - это контейнер, предназначенный для обеспечения оптимального выполнения вставок и удалений объектов. Библиотека STL содержит контейнерный класс list, предоставляющий в распоряжение двусвязный (двунаправленный) список. Он определен в заголовочном файле в пространстве имен std. Этот класс имеет такие же функции, как вектор и ряд дополнительных функций. Если с векторами итераторы используются редко, то при работе со списком они являются основным средством. Для создания списков предназначены конструкторы, которые имеют несколько форм. Конструктор explicit list(const Allocator& alloc = Allocator() ) создает список, не содержащий элементов, причем список использует для распределения памяти объект alloc. Следующий конструктор explicit list(size_type n); создает список длины n, содержащий копии значения по умолчанию объектов типа Т. Тип Т должен иметь конструктор по умолчанию. Список использует для распределения памяти объект alloc.

15 Конструктор list(size_type n, const T& value, const Allocator & alloc = Allocator()); создает список длины n, содержащий копии значения value объектов типа Т. Тип Т должен иметь конструктор по умолчанию. Список использует для распределения памяти объект alloc. В классе list определены дополнительные функции. Функции void push_front(const T& x); и void pop_front(); аналогичны функциям push_back() и pop_back(), однако осуществляют добавление и удаление элементов в начале списка. Функция void remove(const Т& value); удаляет элемент из списка.

16 Вызвав функцию sort (), можно отсортировать список: void sort(); Эта функция сортирует список в соответствии с отношением порядка, задаваемым операторной функцией operator< (). Например, в следующей программе создается список случайных символов, а затем эти символы сортируются: #include using namespace std; typedef list CList; int main() { CList clist; //заполнение списка for (int i=0; i

17

18 Функции-члены begin () и end () возвращают итераторы произвольного доступа, которые позволяют осуществлять доступ к произвольным элементам, а не двунаправленные итераторы, как в случае списка. Дек поддерживает операции вставки и удаления элементов в начало и конец контейнера, а также вставку в середину контейнера, которая занимает большее время. Вставка элементов выполняется функциями insert (), push_front () или push_back () и может потенциально приводить к неправильным значениям всех действующих итераторов и ссылок на элементы в деке. Поскольку деки обеспечивают итераторы, к ним могут применяться все описываемые ниже универсальные алгоритмы. Вектор хранит элементы в одном большом блоке памяти. С другой стороны, дек использует большое число меньших блоков памяти. Это может оказаться важным при выборе типа контейнера на системах с ограниченными ресурсами.

19

20

21

22

23 //пример использования дека: #include using namespace std; int main() { deque dq; int x; cout x, x!=0) { if (x % 2 == 0) dq. push_back (x); else dq.push_front(x); } deque ::iterator i; cout

24 В этом примере пользователю предлагается ввести последовательность целых чисел, завершив ее нулем. Вводимые числа размещаются в деке. Если число четно, оно помещается в конец дека, а если нечетно, - в начало. Затем содержимое дека выводится на экран.

25 Стек является одной из самых распространенных в программировании структур данных. Данные в стеке организованы по принципу "последним вошел - первым вышел" (LIFO -Last In - First Out). Это означает, что добавлять и удалять элементы стека можно только с одного конца. Доступный конец стека называется его вершиной, операция добавления элемента в стек называется помещением в стек (по англ. push()), а операция извлечения элемента из стека - выталкиванием (по англ. pop ()). Абстрактный тип данных стек традиционно определяется как объект, который реализует перечисленные ниже операции: Функция Реализуемая операция empty () Возвращает true, если стек пуст size () Возвращает число элементов стека top () Возвращает (но не удаляет) в вершине стека push (newElernent)Помещает новый элемент в стек pop () Удаляет (но не возвращает) элемент из вершины стека

26 Доступ к вершине стека и удаление элемента из вершины стека реализуются как отдельные операции. В библиотеке STL определен шаблонный класс stack, реализующий возможности стека. Для использования стандартного стека нужно подключить к программе заголовочный файл. В отличие от программного стека, абстрактный тип данных стек предназначен для хранения элементов одного типа. Это же ограничение относится и к стандартному классу stack. Ввиду того, что класс stack не реализует итератор, универсальные алгоритмы, описываемые ниже, не могут применяться к стандартным стекам. Объявление и инициализация стека Стек не является независимым контейнерным классом. По терминологии STL он представляет собой контейнерный адаптер, который строится поверх других контейнеров, которые в действительности хранят элементы. Класс stack лишь позволяет контейнеру вести себя как стек. В связи с этим объявление стека должно задавать тип элементов, которые будут помещаться и извлекаться из него, а также - тип контейнера, который будет использоваться для хранения элементов. Контейнером по умолчанию для стека является дек, однако можно использовать также и список или вектор. Векторная версия, вообще говоря, меньше, тогда как версия, использующая дек в качестве контейнера, работает несколько быстрее.

27 Для элементов, хранимых в очереди, должны быть определены операции меньше ( stackTwo; stack > stackThree; stack > stackFour; В последнем примере стек создается из объектов объявленного пользователем типа Customer. Замечание. Для большинства компиляторов важно оставлять пробел между двумя правыми угловыми скобками в объявлении стека, чтобы они не интерпретировались как оператор сдвига вправо.

28

29 Как и любая абстрактная структура данных типа очередь, класс queue поддерживает операции: Функция Реализуемая операция empty () Возвращает true, если очередь пуста size() Возвращает число элементов очереди front() Возвращает (но не удаляет) элемент из начала очереди back() Возвращает (но не удаляет) элемент из конца очереди push(newElement). Помещает новый элемент в конец очереди pop () Удаляет (но не возвращает) элемент из начала очереди Заметим, что операции доступа к элементам и удаления их из очереди реализованы отдельно. Для использования стандартной очереди нужно подключить к программе заголовочный файл. Ввиду того, что класс queue не реализует итератор, универсальные алгоритмы, описываемые ниже, не могут применяться к стандартным очередям.

30 Объявление и инициализация очереди Объявление очереди должно задавать тип хранимых элементов и вид используемого контейнера. Ниже приведены простые объявления очереди: queue > queueOne; // Использует дек queue > queueTwo; queue > queueThree; queue > queueFour; В последнем примере создается очередь элементов определенного пользователем типа Customer.

31 //пример использования очереди: #include using namespace std; int main(void) { //Создаем очередь, используя список //в качестве контейнера queue q; //Помещаем в него два значения q.push(1); q.push(2); //Извлекаем из очереди два значения cout

32 При выполнении программа выводит на экран:

33 Ассоциативные контейнеры

34 пример использования карты в качестве ассоциативного контейнера: #include using namespace std; int main() { char c; map m; //создаём ассоциативный список for (int i=0; i

35 Эта программа вначале создает карту или ассоциативный список, состоящий из пар ключ/значение. В качестве ключей используются буквенные символы, начиная с буквы 'А', а в качестве значений - параметр цикла for. Для создания пар ключ/значение используется шаблонный класс pair. Поиск нужного значения в ассоциативном списке по ключу осуществляется с помощью функции find(). Эта функция возвращает итератор соответствующего ключу элемента или итератор конца списка, если итератор не найден.

36 Универсальные алгоритмы STL предоставляет около 60 универсальных алгоритмов, которые выполняют рутинные операции над данными, характерными для контейнеров. Все они определены в заголовочном файле в пространстве имен std. Чтобы понять, как работают универсальные алгоритмы, нужно познакомиться с понятием объектов-функций. Объект-функция - это объект класса, в котором определен перегруженный оператор вызова функции (т.е. operator ()). В результате этот объект может вызываться как функция. Объекты-функции важны для эффективного использования универсальных алгоритмов библиотеки STL, поскольку в качестве параметров шаблонных алгоритмов можно передавать как указатели на функции, так и объекты- функции. Эта библиотека содержит много видов стандартных объектов- функций, которые можно использовать в качестве базовых для создания собственных объектов-функций.

37 Для использования этих возможностей необходимо подключить к программе заголовочный файл Объекты-функции, которые принимают один аргумент, называются унарными. Унарные объекты-функции должны содержать объявления типов данных argument__type и result_type. Объекты-функции, которые принимают два аргумента, называются бинарными. Они должны содержать объявления типов данных first_argument_type, second_argument_type, и result_type. Классы unary_function и binary_function облегчают создание шаблонных объектов-функций. Объекты-функции, включенные в STL, и их назначения:

38 НазваниеОперация арифметические функции Plusсложение х + у Minusвычитание х - у Multipliesумножение х * у Dividesделение х / у Modulusостаток х % у Negateунарный минус – х функции сравнения equal_tопроверка на равенство х == у not_equal_toпроверка на неравенство х != у Greaterсравнение больше х > у Lessсравнение меньше, чем х < у greater_equalсравнение больше или равно х >= у less_equalсравнение меньше или равно х

39 //пример использования стандартных объектов-функций. # include #include #include #include #include using namespace std; //Создаем новый объект-функцию из унарной функции template class factorial: public unary_function { public: Arg operator()(const Arg& arg) { Arg a = 1; for(Arg i = 2; i d(init, init+7); //Создаем пустой вектор для хранения факториалов vector v((size_t)7); //Преобразуем числа в деке в их факториалы и сохраняем в векторе transform(d.begin(), d.end(), v.begin(), factorial ()); //Выводим на экран результат cout (cout," ")); cout (cout," ")); return 0; }

40 STL позволяет применять универсальные алгоритмы к контейнерам. Она предоставляет совокупность таких алгоритмов для поиска, сортировки, слияния, преобразования и т.д. Каждый из алгоритмов может применяться не только к стандартным контейнерам, включенным в библиотеку, но и к контейнерам, определенным пользователем. В самом широком смысле все алгоритмы классифицируются на две категории: алгоритмы, изменяющие содержимое контейнера (например, fill (), сору () и sort ()) алгоритмы, не изменяющие содержимое контейнера (например, find (), search (), count () и for_each ()). Названия и назначение стандартных алгоритмов АлгоритмНазначение Search() Ищет подпоследовательность в последовательности max_element () Находит максимальное значение в последовательности min_element () Находит минимальное значение в последовательности mismatch () Находит первое несовпадение в двух последовательностях

41 Алгоритмы для преобразований "по месту" reverse() Устанавливает обратный порядок элементов в последовательности replace() Заменяет определенные значения новым replace__if () Заменяет элементы, соответствующие предикату Rotate() Переставляет элементы последовательности относительно заданной точки partition() Разбивает элементы на две группы Stable_partition() Разбивает элементы на группы, сохраняя исходный порядок next_permutation () Генерирует перестановки в последовательности prev_permutation () Генерирует перестановки в последовательности, имеющей обратный порядок элементов inplace_merge() Объединяет две смежные последовательности в одну Random_shuffle() Переупорядочивает элементы последовательности случайным образом Алгоритмы, удаляющие элементы Remove() Удаляет элементы, которые соответствуют заданному условию Unique() Удаляет все элементы последовательности до первого дубликата Алгоритмы, приводящие к скалярам count() Подсчитывает число элементов с заданным значением count_if() Подсчитывает число элементов, соответствующих предикату accumulate() Сводит последовательность к скалярному значению

42 inner_product() Дает скалярное произведение двух последовательностей equal() Проверяет равенство двух последовательностей lexicographical_compare() Лексикографически сравнивает две последовательности Алгоритмы, генерирующие последовательности transform() Преобразует каждый элемент partial_sum() Генерирует последовательность частичных сумм adjacent difference() Генерирует последовательность из несовпадающих элементов двух последовательностей Различные операции for_each() Применяет функцию к каждому элементу совокупности Алгоритмы инициализации последовательности Fill() Заполняет последовательность начальным значением fill_n() Заполняет п позиций последовательности начальным значением сору() Копирует последовательность в другую copy_backward() Копирует последовательность в другую Generate() Инициализирует последовательность с помощью генератора Generate_n() Инициализирует п позиций последовательности с помощью генератора swap_ranges() Меняет местами значения двух последовательностей

43 Алгоритмы поиска find () Находит элемент, соответствующий аргументу find_if() Находит элемент, соответствующий условию Adjacent_find() Находит последовательные дубликаты элементов find_first_of() Находит первое появление одного члена последовательности в другой find_end() Находит последнее появление подпоследовательности в последовательности Для использования универсальных алгоритмов нужно подключить в программу соответствующий заголовочный файл. Большинство алгоритмов определены в заголовочном файле. Однако алгоритмы accumulate (), inner_product (), раrtiаl_sum(), и adjacent_diffеrеnсе() определены в заголовочном файле.

44

45 #include using namespace std; //Класс для создания объектов-функций, //которые умножают свой аргумент на х template class out_times_x: private unary_function { private: Arg multiplier; public: out_times_x(const Arg& x) : multiplier(x){} void operator()(const Arg& x) {cout

46 В качестве примера алгоритма, изменяющего контейнер, рассмотрим алгоритм fill() заполнения последовательности заданным значением. Он имеет следующий интерфейс вызова: template void fill(Forwardlterator first, Forwardlterator last, const T& value); #include using namespace std; int main () { int d1[4] = {1,2,3,4}; //Создаем два вектора vector v1(d1,d1 + 4), v2(d1,d1 + 4); //Создаем пустой вектор vector v3; //Заполняем вектор v1 цифрами 9 fill(v1.begin(),v1.end(),9); //все 9 – их 4 штуки //Заполняем первые три элемента вектора v2 цифрами 7 fill_n(v2.begin(),3,7); //3 штуки по 7 //заполнить 11 элементов вектора v3 цифрами 5 fill_n (v3.begin(),5,11); //5 штук по 11 При выполнении программа выводит на экран: //Выводим все три вектора на экран ostream_iterator out(cout," ") ; ???????????????? copy(v1.begin(),v1.end(),out); cout