|
Programming Taskbook |
|
|
||
|
Электронный задачник по программированию |
||||
|
© М. Э. Абрамян (Южный федеральный университет, Университет МГУ-ППИ в Шэньчжэне), 1998–2024 |
|
|
Знакомство с итераторами и алгоритмами: STL1Iter17Создание проекта-заготовки и знакомство с заданиемЗадания группы STL1Iter знакомят учащегося с такими базовыми средствами стандартной библиотеки, как итераторы и алгоритмы. Итераторы представляют собой объекты, обеспечивающие перемещение по последовательности и доступ к ее элементам (можно сказать, что итератор — это абстракция понятия указателя). Хотя обычно итераторы используются при работе с контейнерами, наиболее простые виды итераторов — итераторы для чтения и итераторы для записи — могут применяться в программе для доступа к потокам чтения/записи, поэтому начать знакомство с итераторами можно без предварительного изучения контейнеров STL (которым посвящены группы STL2Seq, STL4Str и STL5Assoc). Впрочем, сами по себе итераторы не позволяют воспользоваться всеми возможностями стандартной библиотеки: для этого их необходимо применять совместно с алгоритмами — функциями из библиотеки STL, обеспечивающими выполнение различных стандартных операций над последовательностями данных и использующих итераторы для доступа к обрабатываемым последовательностям. Благодаря применению итераторов алгоритмы не «привязываются» к конкретному виду последовательности (например, контейнеру определенного типа), а могут обрабатывать любые последовательности, поддерживающие работу с итераторами (даже если они не хранятся в памяти, а извлекаются из некоторого потока ввода или, наоборот, после генерации элементов немедленно передаются в поток вывода). В заданиях группы STL1Iter для обработки исходных наборов данных требуется использовать простейшие алгоритмы STL, которые применяются непосредственно к потокам ввода-вывода через связанные с ними итераторы. В качестве потоков ввода-вывода используются стандартные файловые потоки, а также специальный поток pt, определенный в задачнике Programming Taskbook. Большинство важных особенностей заданий группы STL1Iter можно проиллюстрировать на примере выполнения задания STL1Iter17. STL1Iter17. Дана строка name и набор символов. Записать в текстовый файл с именем name удвоенные кодовые значения всех символов из исходного набора в том же порядке, добавляя после каждого числа один пробел. Использовать итераторы ptin_iterator, ostream_iterator и алгоритм transform. Выполнение задания с применением задачника Programming Taskbook начинается с
создания проекта-заготовки для выбранного задания. Для создания заготовки
предназначен программный модуль PT4Load, входящий в состав задачника. Вызвать этот
модуль можно с помощью ярлыка Load.lnk, который автоматически создается в рабочем
каталоге учащегося (по умолчанию рабочий каталог размещается на диске C и имеет имя
PT4Work; с помощью программы PT4Setup, также входящей в состав задачника и
доступной из его меню «Пуск | Программы | Programming Taskbook 4», можно определить
любое количество других рабочих каталогов; начиная с версии 4.15, новые рабочие
каталоги можно определить и непосредственно из модуля PT4Load, нажав на кнопку
Группы заданий, связанные со стандартной библиотекой шаблонов C++, не входят в базовый набор электронного задачника Programming Taskbook. Для того чтобы эти группы были доступны, необходимо после установки задачника Programming Taskbook установить его дополнение Programming Taskbook for STL — задачник по стандартной библиотеке шаблонов. После запуска модуля PT4Load на экране появится его окно, в котором будут перечислены все доступные группы заданий:
В заголовке окна указывается имя текущей среды программирования и номер ее версии. Приведенный рисунок соответствует настройке, при которой текущей средой является среда Microsoft Visual Studio 2012 для языка C++. При выполнении заданий, посвященных стандартной библиотеке шаблонов C++, можно
использовать любые среды программирования для языка C++, которые поддерживаются
электронным задачником. В версии 4.15 задачника это среды Microsoft Visual Studio
2008, 2010, 2012, 2013, 2015 и Code::Blocks 13. Если указана среда, отличная от
требуемой, следует вызвать контекстное меню модуля PT4Load (щелкнув в его окне
правой кнопкой мыши или нажав на кнопку В списке групп должна содержаться группа STL1Iter. Ее отсутствие может объясняться двумя причинами: либо в качестве текущего языка выбран язык, отличный от C++, либо на компьютере не установлено дополнение Programming Taskbook for STL. После ввода имени задания (в нашем случае STL1Iter 17) кнопка «Загрузка» в окне PT4Load станет доступной, и нажав ее (или клавишу [Enter]), мы создадим заготовку для указанного задания, которая будет немедленно загружена в среду Visual Studio. Созданный проект будет состоять из нескольких файлов, однако для решения задачи нам потребуется только файл с именем STL1Iter17.cpp. Именно этот файл будет загружен в редактор среды Visual Studio. Приведем текст файла STL1Iter17.cpp (этот текст будет одинаковым для всех сред программирования, которые можно использовать для решения задания): #include "pt4.h"
using namespace std;
void Solve()
{
Task("STL1Iter17");
}
Файл начинается с директивы подключения заголовочного файла pt4.h, в котором содержатся описания дополнительных функций, обеспечивающих взаимодействие программы учащегося с задачником (в число этих функций входит, в частности, функция Task, предназначенная дли инициализации требуемого задания). Затем указывается директива using namespace std, благодаря которой в последующем тексте программы можно не уточнять стандартное пространство имен std для связанных с ним типов (заметим, что все типы библиотеки STL, за очень небольшим исключением, определены именно в пространстве имен std). Наконец, описывается функция Solve, в которой и требуется запрограммировать решение задачи; в этой функции уже содержится вызов функции Task, инициализирующей задание. Следует обратить внимание на то, что в тексте файла STL1Iter17.cpp отсутствует описание стартовой функции (которая обычно имеет имя main или, для среды Visual Studio, WinMain). Данная функция, разумеется, присутствует в созданном проекте, но поскольку корректировать ее содержание не требуется, ее описание перенесено в другой файл (а именно, в файл pt4.h). Для запуска созданной программы достаточно нажать клавишу [F5] (при использовании среды Code::Blocks можно использовать клавишу [F9]). Примечание. Если при попытке запуска программы система Visual Studio пытается выполнить другое действие, то следует щелкнуть правой кнопкой мыши на имени проекта ptprj в окне «Solution Explorer» («Обозреватель решений») и в появившемся контекстном меню выполнить команду «Set as StartUp Project» («Назначить запускаемым проектом»). После запуска программы на экране появится окно задачника. Приведенный на рисунке вид соответствует режиму с динамической компоновкой (появившемуся в версии 4.11 задачника).
В дальнейшем мы всегда будем использовать режим с динамической компоновкой. Если окно отображается в «старом» режиме с фиксированной компоновкой (см. следующий рисунок), то для переключения на новый режим достаточно нажать клавишу [F4].
Поскольку в программе не выполняются действия по вводу и выводу данных, запуск программы считается ознакомительным. При ознакомительном запуске в окне задачника отображаются три раздела: с формулировкой задания, исходными данными и примером верного решения. Все исходные данные выделяются особым цветом, чтобы отличить их от комментариев: если для окна установлен цветовой режим «на черном фоне» (как на приведенных выше рисунках), то данные выделяются желтым цветом; в режиме «на белом фоне» данные выделяются синим цветом. Для переключения цветового режима достаточно нажать клавишу [F3]. Запуск программы позволяет ознакомиться с образцом исходных данных и соответствующим этим исходным данным примером правильного решения. В нашем случае в набор исходных данных входит имя текстового файла, в который требуется записать полученную последовательность (это имя снабжено комментарием «name =» и заключено в двойные кавычки), количество элементов в исходном символьном наборе (это количество заключено в круглые скобки) и сами символьные элементы набора (каждый из которых заключен в одинарные кавычки). Во всех заданиях, входящих в задачник Programming Taskbook for STL все исходные последовательности, предлагаемые задачником (за исключением тех, которые содержатся в исходных текстовых файлах), задаются аналогичным образом: вначале указывается количество элементов последовательности, а затем — значения самих элементов (на экране количество элементов заключается в скобки и отделяется от списка значений двоеточием), причем значения могут располагаться на нескольких экранных строках. Символьные данные заключаются в одинарные кавычки, а строковые — в двойные, что соответствует представлению символьных и строковых констант, принятому в языке C++. Использование кавычек позволяет, в частности, «увидеть» пустые строки, входящие в наборы исходных или результирующих данных, или строки, начинающиеся или оканчивающиеся пробелами (как в примере верного решения, приведенном на предыдущих рисунках). В разделе «Пример верного решения» содержится единственная текстовая строка, которая должна быть записана в результирующий файл; эта строка содержит удвоенные коды всех символов из исходного набора, причем после каждого кода требуется указывать по одному пробелу. Для выхода из программы достаточно нажать кнопку «Выход», клавишу [Esc] или клавишу [F5], т. е. ту же клавишу, которая обеспечивает запуск программы из среды Visual Studio .NET (в случае использования среды Code::Blocks окно задачника можно закрыть, нажав клавишу [F9]). Чтобы более подробно ознакомиться с заданием, можно использовать два специальных режима задачника: демонстрационный режим и режим отображения заданий в формате html. Для запуска программы в демонстрационном режиме достаточно дополнить параметр
метода Task символом «?» (в нашем случае вызов метода примет вид
Для отображения задания в формате html достаточно дополнить параметр метода Task
символом «#» (в нашем случае вызов метода примет вид Режим html-страницы удобен в нескольких отношениях. Во-первых, только в этом режиме можно ознакомиться с преамбулами к группе заданий и входящим в нее подгруппам и тем самым получить дополнительные сведения, которые могут оказаться полезными при выполнении заданий. Во-вторых, окно браузера с html-страницей не требуется закрывать для того, чтобы продолжить работу над заданием; таким образом, с помощью этого окна можно в любой момент ознакомиться с формулировкой задания, даже если текущее состояние программы не позволяет откомпилировать ее и запустить на выполнение. Имеется возможность отобразить в html-режиме все задания, входящие в некоторую
группу. Для этого в параметре метода Task следует удалить номер задания, оставив
только имя группы и символ «#» (например, Закончив на этом обзор возможностей задачника, предназначенных для формирования проекта-заготовки и ознакомления с выбранным заданием, перейдем к описанию самого процесса решения. Выполнение заданияНачнем выполнение задания с добавления к программе новых директив #include. Поскольку задание связано с записью данных в текстовый файл (и использованием итераторов, связанных с файловыми потоками), подключим заголовок <fstream>. Так как при выполнении задания требуется использовать один из алгоритмов STL (а именно, transform), подключим заголовок <algorithm>. В результате начальная часть файла STL1Iter 17.cpp (до описания функции Solve) примет следующий вид: #include "pt4.h" #include <fstream> #include <algorithm> using namespace std; Заметим, что подключать заголовок <string> не требуется, хотя мы и будем использовать в программе текстовые строки. Теперь реализуем ввод исходных данных. По условию задачи вначале дается строка - имя результирующего файла. Введем это имя в строковую переменную s, используя поток ввода pt (этот поток определен в заголовочном файле pt4.h и связан с электронным задачником). В результате функция Solve примет следующий вид: void Solve()
{
Task("STL1Iter17");
string s;
pt >> s;
}
При запуске полученного варианта программы окно задачника будет содержать сообщение о том, что введены не все требуемые исходные данные, а фон сообщения станет оранжевым:
Сообщения об ошибках всегда выводятся на фоне, цвет которого является одним из оттенков красного. Например, оранжевый цвет связывается с ситуацией, при которой введено или выведено недостаточное количество данных, малиновый цвет — если введено или выведено избыточное количество данных, а фиолетовый — если была попытка ввести или вывести данные неверного типа. Таким же цветом выделяется и заголовок раздела окна, связанного с обнаруженной ошибкой (в нашем случае так выделяется заголовок с исходными данными). В разделе индикаторов, расположенном над разделом с формулировкой задания, тоже выводится оранжевый прямоугольный маркер, причем он отображается в левой части раздела (эта часть содержит информацию о вводе данных). Там же указывается, что был фактически прочитан только один элемент исходных данных из имеющихся 19. Следует также обратить внимание на то, что в средней части раздела индикаторов отсутствует информация о выведенных данных. Это связано с тем, что по условию задачи не требуется пересылать результаты задачнику; вместо этого необходимо создать новый файл и записать полученные результаты в созданный файл. В такой ситуации задачник не следит за количеством выведенных данных, а просто проверяет содержимое созданного файла. Впрочем, в нашем случае до проверки результатов дело не дошло, так как раньше была выявлена ошибка, связанная с вводом исходных данных. Для ввода остальных данных можно было бы прочесть количество элементов, а затем в цикле читать сами элементы и сразу их обрабатывать (или сохранять в массиве или другом подходящем контейнере). Однако в задании предлагается использовать для ввода другой способ, основанный на применении итераторов, — ведь именно такой способ является наиболее соответствующим «идеологии» стандартной библиотеки STL. Так как исходные данные предлагаются задачником, для их ввода надо использовать специальный итератор для потока ввода pt, имеющий имя ptin_iterator. Итератор является шаблонным классом, который надо специализировать типом вводимых элементов; в данном случае это тип char (заметим, что аналогичным образом специализируются и стандартные итераторы файлового ввода). Кроме того, при создании итератора обычно указывается набор параметров, определяющий свойства итератора. Если требуется создать итератор ptin_iterator, связанный с началом последовательности, то требуется указать целочисленный параметр, равный количеству элементов этой последовательности. Предусмотрено особое значение для этого параметра, равное 0; в этом случае итератор сам определяет количество элементов, считывая его из потока ввода pt перед вводом самих элементов. Заметим, что для итераторов файлового ввода, связанных с началом последовательности, также необходимо указывать параметр — имя файлового потока (количество элементов в данном случае не указывается, так как итератор файлового ввода читает данные до конца файла). Итератор ptin_iterator, связываемый с концом последовательности, не имеет параметров (как и итератор, связываемый с концом файлового потока). Итак, для указания начала и конца последовательности символов, получаемой из потока
pt, при условии, что перед элементами этой последовательности передается их
количество, следует использовать итераторы typedef ptin_iterator<char> ptin; Как проверить, что данные итераторы обеспечат правильный ввод исходных данных? Удобным способом является отладочная печать, выполняемая в специальный раздел окна задачника. Для отладочной печати предусмотрены функции Show и ShowLine, определенные в файле pt4.h, причем для них имеются шаблонные варианты, обеспечивающие вывод последовательности с использованием ее итераторов (в этом отношении шаблонные варианты методов Show и ShowLine с параметрами-итераторами ведут себя аналогично стандартным алгоритмам из библиотеки STL). Добавим в конец функции Solve вызов функции Show, обеспечивающий вывод исходной последовательности в раздел отладки. При задании параметров функции Show будем использовать ранее определенный псевдоним ptin для итератора ввода. Получим следующий вариант функции Solve (перед ним должен располагаться оператор определения псевдонима ptin): void Solve()
{
Task("STL1Iter17");
string s;
pt >> s;
Show(ptin(0), ptin());
}
Заметим, что если бы мы использовали функцию ShowLine, то каждый элемент последовательности выводился бы на новой строке раздела отладки. В вариантах функций Show и ShowLine с параметрами-итераторами можно указывать необязательный третий параметр — строку-комментарий, которая выводится перед первым элементом последовательности. После запуска программы окно задачника примет следующий вид:
Теперь наша программа правильно вводит все исходные данные, хотя и не выводит результаты. Можно считать, что мы успешно прошли первый этап решения, связанный с вводом данных. Чтобы отметить этот факт, в разделе индикаторов, связанном с вводом данных, выводится зеленый маркер, а информационная панель содержит текст на светло-синем фоне: «Запуск с правильным вводом данных: все требуемые исходные данные введены, результирующий файл не создан». Поскольку результаты не выведены, в окне отсутствует раздел полученных результатов. Следует также обратить внимание на нижнюю часть окна задачника. В ней появился раздел отладки, в котором выведены все элементы исходной последовательности. В нашем варианте программы введенные данные не сохранялись в памяти, а сразу перенаправлялись функции Show для вывода в разделе отладки. Аналогичным образом можно перенаправить эти данные в результирующий текстовый файл. Однако перед записью в файл данные надо преобразовать. Для преобразования элементов исходной последовательности и получения новой последовательности, содержащей преобразованные элементы, в библиотеке STL имеется алгоритм transform, который, согласно формулировке задачи STL1Iter17, следует использовать при ее решении. Алгоритм transform реализован в двух вариантах; нас интересует вариант, принимающий одну входную последовательность: OutIter transform(InIter first, InIter last, OutIter result, UnaryOp unop); Первые два параметра этого алгоритма задают начало и конец исходной последовательности (в виде двух итераторов), третий параметр содержит итератор на начало преобразованной последовательности, а последний параметр представляет собой функциональный объект с одним параметром, определяющий правило, по которому должны преобразовываться элементы исходной последовательности. В простейшем случае в качестве функционального объекта можно использовать указатель на обычную функцию. Алгоритм transform возвращает итератор, указывающий на конец преобразованной последовательности. Преобразованную последовательность не обязательно сохранять в памяти. Если использовать в качестве третьего параметра алгоритма transform итератор, связанный с файловым потоком, то преобразованная последовательность будет записана в соответствующей файл. Именно это действие и требуется выполнить в нашем задании. Итак, для решения задания нам осталось определить функцию (назовем ее f), преобразующую символы в удвоенные значения их кодов, создать файловый поток вывода os (связав его с именем файла s) и вызвать алгоритм transform, передав ему требуемые параметры: int f(char c)
{
return 2 * c;
}
void Solve()
{
Task("STL1Iter17");
string s;
pt >> s;
ofstream os(s);
transform(ptin(0), ptin(), ostream_iterator<int>(os, " "), f);
}
При описании функции f мы учли тот факт, что в языке C++ (в отличие от многих других современных языков программирования) возможно неявное преобразование типа char в тип int. В дополнительном комментарии нуждается второй, необязательный параметр конструктора ostream_iterator: в нем можно указать разделитель, который будет автоматически добавляться после записи в поток каждого элемента последовательности. По умолчанию разделитель отсутствует. Заметим также, что при выполнении задания в системе Visual Studio 2008 в конструкторе
класса ofstream необходимо преобразовать строку s к типу ofstream os(s.c_str()); В последующих версиях Visual Studio и в среде Code::Blocks указанное преобразование выполнять не требуется. При запуске полученной программы на экране появится окно прогресса тестирования, в котором отображается число пройденных тестов:
Наша программа является правильной, поэтому все пять требуемых тестов будут пройдены успешно, после чего на экране появится окно задачника с сообщением о том, что задание выполнено:
Не закрывая окна задачника, можно просмотреть историю выполнения задания. Для этого достаточно нажать клавишу [F2] или щелкнуть мышью на метке «Результаты» в правом верхнем углу окна. На экране появится окно еще одного вспомогательного программного модуля задачника — PT4Results, в котором будут перечислены все запуски нашей программы: STL1Iter17 c29/01 15:03 Ознакомительный запуск.--2 STL1Iter17 c29/01 15:10 Введены не все требуемые исходные данные. STL1Iter17 c29/01 15:14 Запуск с правильным вводом данных. STL1Iter17 c29/01 15:18 Задание выполнено! Символ «c», указанный перед датой, означает, что задание выполнялось на языке С++. Другой вариант правильного решенияВ новом стандарте языка C++, для которого обычно используется обозначение C++11, появилось замечательная возможность, существенно упрощающая определение и использование функциональных объектов: лямбда-выражения. Лямбда-выражение представляет собой анонимный функциональный объект, определяемый в месте его непосредственного использования. Лямбда-выражения позволяют значительно сократить размеры программ, применяющих STL, и, что не менее важно, сделать эти программы более наглядными. Лямбда-выражения можно использовать во всех версиях Visual Studio, поддерживаемых
задачником, за исключением версии 2008. Их также можно использовать в системе
Code::Blocks, если для подключенного к ней компилятора GNU GCC
установить опцию компиляции Приведем вариант решения, использующий лямбда-выражение (описывать функцию f в данном случае не требуется): void Solve()
{
Task("STL1Iter17");
string s;
pt >> s;
ofstream os(s);
transform(ptin(0), ptin(), ostream_iterator<int>(os, " "),
[](char c){return 2 * c;});
}
Простейший вариант лямбда-выражения (не выполняющего захват внешних переменных) начинается с пустых квадратных скобок, за которыми идет список параметров и тело определяемого функционального объекта, причем если это тело содержит единственный оператор return (как обычно и бывает), то не требуется указывать тип возвращаемого значения. Примечание. В формулировках некоторых заданий группы STL1Iter говорится, что исходные данные размещаются во внешнем текстовом файле, а полученные результаты следует переслать непосредственно задачнику (используя поток вывода pt). В этом случае для ввода надо использовать стандартный итератор чтения из файлового потока istream_iterator, а для вывода — итератор ptout_iterator, определенный в файле pt4.h. Возможны и другие комбинации размещения входных и выходных данных. При этом во всех заданиях этой группы достаточно выполнять преобразование входной последовательности в выходную «на лету», применяя подходящий алгоритм и не используя вспомогательные контейнеры.
|
).
) и выбрать нужную среду из
появившегося списка.
|
|
Разработка сайта: |
Последнее обновление: |