Операция объединения merge. Категории итераторов. (Лекция 3)

Нажмите для полного просмотра!

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №2

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №3

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №4

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №5

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №6

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №7

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №8

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №9

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №10

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №11

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №12

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №13

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №14

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №15

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №16

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №17

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №18

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №19

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №20

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №21

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №22

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №23

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №24

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №25

Операция объединения merge. Категории итераторов. (Лекция 3), слайд №26

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Операция объединения merge. Категории итераторов. (Лекция 3). Доклад-сообщение содержит 26 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Лекция 3 Операция объединения merge. Категории итераторов

Слайд 2

Описание слайда:

Алгоритм merge (объединение) Рассмотрим операцию объединения a и b в c : Алгоритм merge можно использовать для каждого из 4 типов последовательных контейнеров (массивы, векторы, двусторонние очереди и списки). Три участника алгоритма (a, b и с на рисунке ) не обязаны принадлежать к одному и тому же контейнерному типу.

Слайд 3

Описание слайда:

Объединение вектора и массива в список #include #include #include #include #include using namespace std; int merge() { vector a(5); a[0] = 2; a[1] = 3; a[2] = 8; a[3] = 20; a[4] = 25; int b[6] = {7, 9, 23, 28, 30, 33}; list с; // Список сначала пуст merge(a.begin(), a.end(), b, b+6, inserter(c, c.begin())); list::iterator i; for (i=c.begin(); i != c.end(); ++i) cout

Слайд 4

Описание слайда:

Замечания Здесь также нужно использовать итератор вставки, если хотим писать в с в режиме вставки. В качестве альтернативы мы могли бы написать: list с (11); // принимаем 5 + 6 = 11 элементов merge(a.begin(), a.end(), b, b+6, с.begin()); выделив достаточно места при определении принимающего списка с. Сам по себе алгоритм merge работает в режиме замещения, то есть не создает новых элементов контейнера, а помещает значения в существующие. Чтобы вставлять новые элементы (режим вставки) при объединении, мы должны использовать вставляющий итератор, как показано в полной программе. В любом случае результат работы программы следующий: 2 3 7 8 9 20 23 25 28 30 33

Слайд 5

Описание слайда:

Типы, определенные пользователем Кроме стандартных типов, таких как int, в контейнерах STL можно хранить типы, определенные пользователем. Так как вызов merge(...) в программе merge.cpp основан на операции сравнения “меньше чем”

Слайд 6

Описание слайда:

Типы, определенные пользователем // merge2.срр: Объединяем записи, используя // имена в качестве ключей. #include #include #include using namespace std; // Описание operator< находится внутри // структуры entry struct entry { long nr; char name[30]; bool operator

Слайд 7

Описание слайда:

В качестве ключей используются имена int merge2() { entry a[3] = {{10, "Betty"}, {11, "James"}, {80, "Jim"}}, b[2] = {{16, "Fred"}, {20, "William"}}, с[5], *p; merge(a, a+3, b, b+2, c); for (p=c; p != c+5; p++) cout nr

Слайд 8

Описание слайда:

В качестве ключей используются числа Чтобы числа шли в порядке возрастания, их нужно было бы перечислить в таком порядке в заданных массивах а и b и, кроме того, заменить определение оператора “меньше”. Поскольку числа и так уже расположены в порядке возрастания в обоих массивах, нам остается только вместо функции-члена operator < использовать следующую: struct entry { long nr; char name[30]; bool operator

Слайд 9

Описание слайда:

В качестве ключей используются числа Результат: 10 Betty 11 James 16 Fred 20 William Jim Функция operator< не обязана быть членом класса (или структуры) entry. Иными словами, мы могли бы написать: struct entry { long nr; char name[30]; }; bool operator

Слайд 10

Описание слайда:

Категории итераторов Мы можем использовать алгоритм sort (произвольный доступ) для массивов, векторов и двусторонних очередей, но не для списков. Алгоритм find, напротив, может быть использован для всех четырех типов последовательных контейнеров. В обоих случаях используются итераторы, но алгоритм sort требует “более мощных” итераторов, нежели алгоритм find. Итераторы можно поделить на пять категорий, в соответствии с теми операциями, которые для них определены.

Слайд 11

Описание слайда:

Предположим, что i и j - итераторы одного вида. Предположим, что i и j - итераторы одного вида. Тогда, основные операции, выполняемые с любым итератором: Разыменование итератора; если i - итератор, то *i – значение объекта, на который он ссылается. Присваивание одного итератора другому: i = j . Сравнение итераторов: i == j, i != j. Перемещение итератора по всем элементам контейнера: с помощью префиксного (++i) или постфиксного (i++) инкремента. Т.к. реализация итератора специфична для каждого класса, то при объявлении итераторов указывается область видимости: vector:: iterator iv; .

Слайд 12

Описание слайда:

Пусть i – итератор; просмотр элементов контейнера записывается так: Пусть i – итератор; просмотр элементов контейнера записывается так: for (i = first; i != last; ++i) где first – значение итератора, указывающего на первый элемент контейнера, last – значение итератора, указывающего на воображаемый элемент, следующий за последним элементом контейнера. Операция сравнения < заменена на операцию !=, поскольку операции для итераторов в общем случае не поддерживаются. Методы begin() и end() возвращают адреса first и last соответственно.

Слайд 13

Описание слайда:

Таблица операций, применимых к итераторам х - переменная того же типа, что и элементы рассматриваемого контейнера, а n – int.

Слайд 14

Описание слайда:

Категории итераторов Входные (input) итераторы используются для чтения значений из контейнера, аналогично вводу данных из потока cin. Выходные (output) итераторы используются для записи значений в контейнер, аналогично выводу данных в поток cout. Прямые (forward) итераторы поддерживают навигацию по контейнеру только в прямом направлении, позволяют читать и изменять данные в контейнере. Двунаправленные (bidirectional) итераторы в дополнение ко всем операциям прямых итераторов, поддерживают навигацию и в прямом, и в обратном направлениях (реализованы операции префиксного и постфиксного уменьшения).

Слайд 15

Описание слайда:

Категории итераторов Итераторы произвольного доступа (random access) получили, добавив к двунаправленному итератору операции +, -, +=, -=, , =, т.е. доступа к произвольному элементу контейнера. Добавление целого числа к итератору возможно только для итераторов произвольного доступа; эта операция требуется, к примеру, для алгоритма сортировки. Так как список не предоставляет итераторов произвольного доступа, мы не можем применить к списку алгоритм sort. Теперь понятно, что выражение i - 1 допустимо только для операторов произвольного доступа, тогда как --i поддерживается также двунаправленными итераторами.

Слайд 16

Описание слайда:

Слайд 17

Описание слайда:

Категории итераторов и алгоритмы Алгоритм find требует исключительно тех операций над итераторами, которые определены для входных итераторов, потому что ему достаточно только читать элементы последовательности, исполняя, например, операцию присваивания х = *i. Алгоритм replace, заменяющий одно определенное значение на другое требует только прямых итераторов с соответствующими операциями. На двунаправленных итераторах базируются алгоритмы, выполняющие реверсивные операции, например, алгоритм reverse. Этот алгоритм меняет местами все объекты в цепочке, на которую ссылаются переданные ему итераторы.

Слайд 18

Описание слайда:

Категории итераторов и алгоритмы Итераторы двунаправленного доступа возвращаются несколькими контейнерами STL: list, set, multiset, map и multimap. Итераторы произвольного доступа возвращают такие контейнеры, как vector и deque. Итераторы произвольного доступа – самые "умелые" из основных итераторов и, как правило, все сложные алгоритмы, требующие расширенных вычислений, оперируют с этими итераторами. Создаем переменную типа "итератор произвольного доступа". Для этого берем итератор и на его основе создаем другой, более удобный: typedef vector::iterator vectItr; vectItr itr ;

Слайд 19

$Потоковые итераторы Можно применить алгоритм сору для вывода: #include const int N = 4; int a[N] = {7, 6, 9, 2}; copy(a, a+N, ostream_iterator(cout,...$

Описание слайда:

Потоковые итераторы Можно применить алгоритм сору для вывода: #include const int N = 4; int a[N] = {7, 6, 9, 2}; copy(a, a+N, ostream_iterator(cout, " ")); Это можно сделать таким образом: ostream_iterator i (cout, " ") ; copy (a, a+N, i) ; // потоковый итератор – 3-й аргумент В поток стандартного вывода cout будут выведены числа 7, 6, 9 и 2, как если бы написали: for (int* p=a; p!= a+N; p++) cout

Слайд 20

Описание слайда:

Потоковые итераторы Программа читает из стандартного потока cin числа, вводимые пользователем и дублирует их на экране. Работа программы заканчивается, при вводе числа 77: #include #include #include #include void prog1() { istream_iterator is(cin); ostream_iterator os(cout, " "); int input; while((input = *is) != 77) { *os++ = input; is++ ; } }

Слайд 21

Описание слайда:

Операции с итераторами К итераторам произвольного доступа можно применять арифметические операции: int n, dist; // i и i0 – итераторы произвольного доступа i0 = i; i += n; dist = i – i0; // dist == n Существуют функции advance и distance: int n, dist; // i и i0 – итераторы, но необязательно //произвольного доступа i0 = i; advance(i, n); dist = 0; distance(i0, i, dist); // dist == n advance(i, n) i += n distance(i0, i, dist) dist = i – i0 Функция distance служит для определения расстояния между элементами контейнера. Операции advance и distance будут выполняться гораздо быстрее для итераторов произвольного доступа, чем для итераторов других типов.

Слайд 22

Описание слайда:

Алгоритм replace replace позволяет найти все элементы с определенным значением в заданном контейнере и заменить их другим значением. #include #include #include using namespace std; int replace_massiv() { char str[ ] = "abcabcabc"; int n = strlen(str); replace(str, str+n, 'b', ‘q'); cout

Слайд 23

Описание слайда:

Алгоритм reverse reverse позволяет заменить последовательность на обратную ей. Этот алгоритм требует двунаправленных итераторов, которые предоставляют все четыре контейнера. #include #include #include using namespace std; int reverse_massiv() { char str[ ] = "abcklmxyz"; reverse(str, str+strlen(str)); cout

Слайд 24

Описание слайда:

Краткие итоги Рассмотрели алгоритмы: 1. merge() – объединение элементов различных контейнеров. merge(a.begin(), a.end(), b, b+6, inserter(c, c.begin())); – в режиме вставки. merge(a.begin(), a.end(), b, b+6, с.begin()); – в режиме замещения. Каждая из объединяемых последовательностей упорядочена!!! Иначе алгоритм не будет равильно работать. operator< – оператор “меньше”, определяет операции упорядочивания (сравнения) для типов, определенных пользователем. merge(a, a+3, b, b+2, c); – рассматривали структуры, объединение производилось по одному из ключей (либо по имени, либо по номеру). Именно оператор operator< задаёт для алгоритма merge() вид упорядочивания.

Слайд 25

Описание слайда:

Краткие итоги 2. replace() – замена одних элементов на другие replace (str, str+n, 'b', ‘q'); 3. reverse позволяет заменить последовательность на обратную ей. reverse (str, str+strlen(str)); Категории итераторов Входные (input) итераторы используются для чтения значений из контейнера. find() Выходные (output) итераторы используются для записи значений в контейнер. copy() Прямые (forward) итераторы поддерживают навигацию по контейнеру только в прямом направлении, позволяют читать и изменять данные в контейнере. replace()

Слайд 26

Описание слайда:

Краткие итоги Категории итераторов Двунаправленные (bidirectional) итераторы в дополнение ко всем операциям прямых итераторов, поддерживают навигацию и в прямом, и в обратном направлениях. reverse() Итераторы произвольного доступа (random access) получили, добавив к двунаправленному итератору операции +, -, +=, -=, , =, т.е. доступа к произвольному элементу контейнера. sort()