STL-функции-алгоритмы - презентация, доклад, проект скачать

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему STL-функции-алгоритмы. Доклад-сообщение содержит 35 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1

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

Тест с отчетом 4 Ответ : AAAA

Слайд 2

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

STL – прямой (однонаправленный) итератор Прямые итераторы представляют собой комбинацию итераторов ввода и вывода. Они обладают всеми свойствами итераторов ввода и большинством свойств итераторов вывода. В отличие от итераторов ввода и вывода прямые итераторы могут ссылаться на один и тот же элемент коллекции и обрабатывать его по несколько раз.

Слайд 3

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

STL – прямой (однонаправленный) итератор Существует одно важное ограничение, из-за которого код, действительный для итераторов вывода, оказывается недействительным для прямых итераторов. Итераторы вывода позволяют записывать данные без проверки конца последовательности. Более того, нельзя сравнить итератор вывода с конечным итератором, потому что итераторы вывода не поддерживают операцию сравнения. Следовательно, для итератора вывода pos следующий цикл правилен, а для прямого итератора - нет: // ОК для итераторов вывода // ОШИБКА для прямых итераторов while (true) { *pos = foo(); ++pos; }

Слайд 4

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

STL – прямой (однонаправленный) итератор При работе с прямыми итераторами перед разыменованием(обращением к данным) необходимо заранее убедиться в том, что это возможно. Приведенный цикл неправилен для прямых итераторов, поскольку он приводит к попытке обращения по итератору end() в конце коллекции с непредсказуемыми последствиями. Для прямых итераторов цикл необходимо изменить следующим образом: // ОК для прямых итераторов // ОШИБКА для итераторов вывода whi1e (pos != соl1.end() ) { *pos = foo(); ++pos; }

Слайд 5

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

STL – двунаправленный итератор Двунаправленными итераторами называются прямые итераторы, поддержи-вающие возможность перебора элементов в обратном направлении. Для этой цели в них определяется дополнительный оператор --.

Слайд 6

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

STL – итераторы вставки Итератор вставки представляет собой итераторный адаптер, преобразующий присваи-вание нового значения во вставку нового значения. С помощью итераторов вставки алго-ритмы вставляют новые значения вместо того, чтобы записывать их на место старых. Все итераторы вставки относятся к категории итераторов вывода, то есть поддержи-вают только вставку новых значений. Обычно алгоритмы присваивают значения элемен-там, на которые ссылаются приемные итераторы. Для примера - алгоритм сору(): namespace std { template OutputIterator сору (Inputlterator from_pos, // Начало источника InputIterator from end, // Конец источника Outputlterator to pos) // Начало приемника { while (from_pos != from_end) { *to_pos = *from_pos; // Копирование значений ++from pos; ++to_pos; } return to_pos: }

Слайд 7

$STL – итератор вставки - пример #include #include #include int main( ) { using namespace std; int i; list ::iterator L_Iter; list L; for ( i = -2 ; i...$

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

STL – итератор вставки - пример #include #include #include int main( ) { using namespace std; int i; list ::iterator L_Iter; list L; for ( i = -2 ; i < 4 ; ++i ) { L.push_back ( i ); } // Вывод содержимого списка cout

Слайд 8

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

Простой объект функции #include #include #include using namespace std; class Printlnt { public: void operator() (int elem) const { cout

Слайд 9

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

Простой объект функции – зачем это нужно? (1) 1) Объект функции - это «умная функция». Объекты, которые ведут себя как указатели, называются «умными указателями». По аналогии объекты, которые ведут себя как функции, можно назвать «умными функциями», поскольку их возможности не ограничиваются вызовом оператора (). Объекты функций могут представлять другие функции и иметь другие атрибуты, а это означает, что объекты функций обладают состоянием. Одна и та же функция, представленная объектом функции, в разные моменты времени может находиться в разных состояниях. У обычных функций такая возможность отсутствует. Из этого следует одно из достоинств объектов функций – возможность их инициализации на стадии выполнения перед вызовом / использованием.

Слайд 10

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

Простой объект функции – зачем это нужно? (2) 2) Каждому объекту функции соответствует свой тип. Обычные функции обладают разными типами только при различиях в их сигнатурах. С другой стороны, объекты функций могут иметь разные типы даже при полном совпадении сигнатур. Это открывает новые возможности для унифицированного программирования с применени-ем шаблонов, потому что функциональное поведение может передаваться как параметр шаблона. Например, это позволяет контейнерам разных типов использовать единственный объект функции в качестве критерия сортировки. Тем самым предотвращается возможное присваивание, слияние и сравнение коллекций, использующих разные критерии сортировки. Вы даже можете спроектировать иерархию объектов функций, например, для определения нескольких специализированных версий одного общего критерия.

Слайд 11

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

Простой объект функции – зачем это нужно? (3) 3) Объекты функций обычно работают быстрее функций. Шаблоны обычно лучше оптимизируются, поскольку на стадии компиляции доступно больше информации. Следовательно, передача объекта функции вместо обычной функции часто повышает быстродействие программы.

Слайд 12

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

Простой объект функции – зачем это нужно? (4) Предположим, что нам требуется провести увеличение всех элементов контейнера на 10. Вариант решения: void add10 (int& elem ) { elem += 10; } void func() { vector соl; … for_each(col.begin(), col.end(), // Интервал add10) ; // Операция }

Слайд 13

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

Простой объект функции – зачем это нужно? (5) Можно оформить шаблон функции. Вариант решения: template void add (int& elem) { elem += theValue; } void func() { vector соl; … for_each(col.begin(), col.end(), // Интервал add) ; // Операция }

Слайд 14

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

Простой объект функции – зачем это нужно? (6) Используем объект функции. Вариант решения: // Объект функции прибавляет к значению элемента приращение. // заданное при его инициализации class AddValue { private: int theValue; // Приращение public: // Конструктор инициализирует приращение AddValue(int v) : theValue(v) { } // Суммирование выполняется "вызовом функции" для элемента void operator() (int& elem) const { elem += theValue; } } ; for_each (col.begin(), col.end(), AddValue(10)) ; // использование AddValue(*col. begin()) // увеличить на первый элемент (а не 10…)

Слайд 15

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

Стандартные объекты функций Чтобы использовать стандартные объекты функций, необходимо включить в программу заголовочный файл (ранее – function.h)

Слайд 16

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

Функциональные адаптеры Функциональным адаптером называется объект, который позволяет комбинировать объекты функций друг с другом, с определенными значениями или со специальными функциями. Функциональные адаптеры тоже объявляются в заголовочном файле . Например, в следующей команде выражение bind2nd(greater(),42) создает комбинированный объект функции для проверки условия «целое число больше 42»: find_if (соl.begin(), col.end(), // Интервал bind2nd(greater() ,42)) // Критерий Фактически bind2nd() преобразует бинарный объект функции (например, greater) в унарный объект функции. Второй параметр всегда используется в качестве второго аргумента бинарной функции, передаваемой в первом параметре. Следовательно, в приведенном примере greater всегда вызывается со вторым аргументом, равным 42. Классы стандартных функциональных адаптеров:

Слайд 17

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

Функциональные адаптеры Функциональные адаптеры сами по себе являются объектами функций, поэтому их можно объединять с другими адаптерами и объектами функций для построения более мощных (и более сложных) выражений. Например, следующая команда находит первый четный элемент коллекции: pos = find_if (соl.begin(), col.end(), // Интервал not1( bind2nd( modulus(), 2))); // Критерий в этой команде выражение bind2nd( modulus(), 2) возвращает 1 для нечетных значений. Следовательно, оно может использоваться в качестве критерия для нахождения первого нечетного элемента, потому что значение 1 эквивалентно true. Адаптер not1() производит логическую инверсию результата, поэтому вся команда ищет первый элемент с четным значением. Объединяя объекты функций при помощи функциональных адаптеров, можно строить достаточно сложные выражения. Подобный стиль программирования называется функциональной композицией.

Слайд 18

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

Функциональные адаптеры Функциональные адаптеры для функций классов позволяют вызвать некоторую функцию класса для каждого элемента коллекции

Слайд 19

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

Алгоритмы SТL Чтобы использовать алгоритмы библиотеки, необходимо включить в программу заголовочный файл . Некоторые алгоритмы STL, предназначенные для обработки числовых данных, определяются в заголовочном файле .

Слайд 20

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

Предикаты применяются . . . Функция, возвращающая логическое значение, называется предикатом. Предикаты применяются в следующих ситуациях: Функция (или объект функции), определяющая унарный предикат, может передаваться алгоритму поиска в качестве критерия поиска. Унарный предикат проверяет, соответствует ли элемент заданному критерию. Например, это позволяет найти первый элемент со значением, меньшим 50. Функция (или объект функции), определяющая бинарный предикат, может передаваться алгоритму сортировки в качестве критерия сортировки. Бинарный предикат сравнивает два элемента. Например, с помощью бинарного предиката можно отсортировать объекты, представляю щи е людей, по фамилиям и по именам. Унарный предикат может использоваться как критерий, определяющий, к каким элементам должна применяться операция. Например, из коллекции можно удалить только элементы с нечетными значениями. Предикаты также используются для модификации операций в численных алгоритмах. Например, алгоритм accumulate(), обычно вычисляющий сумму элементов, также позволяет вычислять произведения всех элементов.

Слайд 21

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

Классификация алгоритмов (по основным областям применения) По названию алгоритма можно получить первое представление о его назначении. Проектировщики STL ввели два специальных суффикса. Суффикс _if. Суффикс _if используется при наличии двух похожих форм алгоритма с одинаковым количеством параметров; первой форме передается значение, а второй - функция или объект функции. В этом случае версия без суффикса _if используется при передаче значения, а версия с суффиксом _if - при передаче функции или объекта функции. Например, алгоритм fiпd() ищет элемент с заданным значением, а алгоритм fiпd_if() элемент, удовлетворяю-щий критерию, определенному в виде функции или объекта функции. Впрочем, не все алгоритмы, получающие функции и объекты функций, имеют суффикс _if. Если такая версия вызывается с дополнительными аргументами, отличающими ее от других версий, за ней сохраняется прежнее имя. Например, версия алгоритма min_еlеmепt() с двумя аргументами находит в интервале минимальный элемент, при этом элементы сравниваются оператором

Слайд 22

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

Классификация алгоритмов (по группам) немодифицирующие алгоритмы; модифицирующие алгоритмы; алгоритмы удаления; перестановочные алгоритмы; алгоритмы сортировки; алгоритмы упорядоченных интервалов; численные алгоритмы. Если алгоритм принадлежит сразу нескольким категориям, он описывается только в одной из них.

Слайд 23

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

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

Слайд 24

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

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

Слайд 25

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

Модифицирующие алгоритмы В группе модифицирующих алгоритмов центральное место занимают алгоритмы fоr_each() (снова) и transform(). Оба алгоритма используются для модификации элементов последовательности, однако работают они по-разному. Алгоритму for_each() передается операция, которая модифицирует его аргумент. Это означает, что аргумент должен передаваться по ссылке. Пример: void square (int& elem) // Передача по ссылке { elem=elem*elem ; } // Прямое присваивание вычисленного значения ... for_each (соl.begin(), соl.end(), // Интервал square) ; // Операция Алгоритм transform() использует операцию, которая возвращает модифицированный аргумент. Результат присваивается исходному элементу. Пример: void square (int elem) // Передача по значению { return elem*elem; } ... for_each (соl.begin(), соl.end(), // Интервал соl.begin(), // Приемник square) ; // Операция Алгоритм transform() работает чуть медленнее. С другой стороны, этот подход более гибок, поскольку он также может использоваться для модификации элементов в процессе копирования в другой интервал. Кроме того, у алгоритма transform() есть еще одна версия, которая позволяет обрабатывать и комбинировать элементы из двух разных интервалов.

Слайд 26

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

Aлгоритмы удаления Алгоритмы удаления составляют отдельную подгруппу модифицирующих алгоритмов. Они предназначены для удаления элементов либо в отдельном интервале, либо в процессе копирования в другой интервал. Как и в случае с модифицирующими алгоритмами, их приемником не может быть ассоциативный контейнер, поскольку элементы ассоциативного контейнера считаются const.

Слайд 27

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

Перестановочные алгоритмы Перестановочными алгоритмами называются алгоритмы, изменяющие порядок следования элементов (но не их значения) посредством присваивания и перестановки их значений. Их приемником не может быть ассоциативный контейнер, поскольку элементы ассоциативного контейнера считаются const.

Слайд 28

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

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

Слайд 29

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

Алгоритмы сортировки (sort) Алгоритмы сортировки часто критичны по времени, поэтому стандартная библиотека С++ содержит несколько алгоритмов, различающихся по способу сортировки или составу сортируемых элементов (полная/частичная сортировка).

Слайд 30

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

Алгоритмы сортировки (partial_sort) Исторически этот алгоритм основан на механизме сортировки в куче (heapsoгt), гарантирующем сложность n*log(n) в любом случае. Тем не менее обычно сортировка в куче выполняется в 2-5 раз медленнее быстрой сортировки. И так, с учетом реализаций sort() и partial_sort(), алгоритм partial_sort() лучше по сложности, но по скорости работы sort() обычно превосходит его. Преимущество алгоритма partial_sort() заключается в том, что сложность n*log(n) гарантирована и никогда не ухудшается до квадратичной сложности. Алгоритм partial_sort() также обладает особым свойством: он прекращает сортировку, когда требуется отсортировать только n первых элементов. Чтобы отсортировать все элементы, передайте конец последовательности во втором и в последнем аргументах; /* Сортировка всех элементов * - всегда сложность n*log(n) * - но обычно работает вдвое медленнее sort() */ partial_sort (col.begin(), col.end(), col.end());

Слайд 31

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

Алгоритмы сортировки (stable_sort) Исторически этот алгоритм основан на механизме сортировки со слиянием. Для достижения сложности n*log(n) необходима дополнительная память, в противном случае алгоритм выполняется со сложностью n*log(n)*log(n). Достоинством stable_sort() является сохранение порядка следования равных элементов. /* Сортировка всех элементов * - сложность n*log(n) или n*log(n)*log(n) */ stable_sort (col.begin(), col.end()); Алгоритм сортирует все элементы переданного интервала.

Слайд 32

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

Алгоритмы сортировки (nth_element) Алгоритм nth_element() прекращает работу, когда n-й элемент последова-тельности занимает правильное место в соответствии с критерием сортировки. Для остальных элементов он гарантирует только то, что предшествующие элементы имеют меньшее либо равное, а последующие элементы – большее либо равное значение. Таким образом алгоритм nth_element() разделяет элементы на два подмножества в соответствии с критерием сортировки. Алгоритму nth_element() передается требуемое количество элементов в первой части (а следовательно, и во второй). Пример: // Перемещение четырех наименьших элементов в начало nth_element (col.begin(), // Начало интервала col.begin()+3, // Позиция, отделяющая первую часть от второй col.end()); // Конец интервала Но после вызова невозможно сказать, по какому критерию первая часть отличается от второй. Более того, в обеих частях могут присутствовать элементы, совпадающие по значению с n-м элементом. 3,7,8,3,2,1,4,5,6,3,5 1,2,3,3,3,4,5,5,6,7,8

Слайд 33

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

Алгоритмы сортировки (partition и stable_partition) Алгоритму partition() передается конкретный критерий сортировки, определяющий различия между первой и второй частями: // Перемещение всех элементов, меньших 3, в начало vector::iterator pos; pos = partition (col.begin(), col.end(), bind2nd(less(),7)); На этот раз после вызова невозможно сказать, сколько элементов входит в первую и вторую части. Возвращаемый итератор pos указывает на первый элемент второй части, которая содержит все элементы, не соответствующие критерию. Алгоритм stable_partition() в целом аналогичен partition(), но он дополнительно гарантирует сохранение порядка следования элементов в обеих частях по отношению к другим элементам, входящим в ту же часть. Любому алгоритму сортировки в необязательном аргументе всегда можно передавать критерий сортировки. По умолчанию критерием сортировки является объект функции less< >, а элементы сортируются по возрастанию значений. Приемником алгоритмов сортировки не может быть ассоциативный контейнер. Алгоритмы сортировки не могут вызываться для списков.

Слайд 34

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

Алгоритмы упорядоченных интервалов Алгоритмы упорядоченных интервалов требуют, чтобы интервалы, с которыми они работают, были изначально упорядочены по соответствующему критерию. Достоинством этих алгоритмов является невысокая сложность.