Практикум по спецкурсу Стандартная библиотека C++
Содержание
Задание 1. Обобщенные алгоритмы
Указание к выполнению
Реализовать следующие алгоритмы. Привести примеры их работы с вектором и списком.
Задачи
1.
template<typename FwdIt, typename BinPred>
FwdIt adjacent_find(FwdIt first, FwdIt last, BinPred pr);
Ищет первую пару одинаковых соседних элементов в диапазоне, ограниченном итераторами [first , last). Если соседние дубликаты найдены, то алгоритм возвращает однонаправленный итератор, указывающий на первый элемент пары, в противном случае возвращается last. Равенство понимается в смысле выполнения бинарного предиката BinPred pr.
2.
template<typename FwdIt1, typename FwdIt2>
FwdIt1 search(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2);
Bозвращает итератор, указывающий на первую позицию в диапазоне [first1, last1), начиная с которой второй диапазон входит как подпоследовательность.
3.
template<typename FwdIt1, typename FwdIt2>
FwdIt1 find_first_of(FwdIt1 first1, FwdIt1 last1, FwdIt2 first2, FwdIt2 last2);
Возвращает итератор, указывающий на первое вхождение любого элемента последовательности [first2, last2) в последовательности, ограниченной итераторами [first1, last1).
4.
template<typename InIt, typename OutIt, typename Unop>
OutIt transform(InIt first, InIt last, OutIt x, Unop uop);
Генерирует новую последовательность, применяя операцию uop к каждому элементу из диапазона [first1 , last1). Bозвращает итератор за концом скопированных данных во второй последовательности.
5.
template<typename InIt, typename OutIt, typename T>
OutIt replace_copy(InIt first, InIt last, OutIt x, const T& vold, const T& vnew);
Заменяет в диапазоне [first, last) все элементы со значением vold на vnew , копируя результат в новую последовательность. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным.
6.
template<typename FwdIt, typename Pred>
FwdIt remove_if(FwdIt first, FwdIt last, Pred pr);
Удаляет из диапазона [first , last) все элементы, для которых значение предиката pr равно true. Удаленные элементы сдвигаются в конец контейнера. Возвращает итератор на первый удаленный элемент.
7.
template<typename InIt, typename OutIt, typename T>
OutIt remove_copy(InIt first, InIt last, OutIt x, const T& val);
Копирует все элементы, кроме имеющих значение val, в контейнер, на начало которого указывает x. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным.
8.
template<typename InIt, typename OutIt, typename Pred>
OutIt remove_copy_if(InIt first, InIt last, OutIt x, Pred pr);
Копирует все элементы, для которых предикат pr равен false, в контейнер, на начало которого указывает x. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным.
9.
template<typename FwdIt>
FwdIt unique(FwdIt first, FwdIt last);
Все группы равных соседних элементов заменяются одним. Копии передвигаются в конец, возвращаемый итератор указывает на начало остатка
10.
template<typename RanIt>
void random_shuffle(RanIt first, RanIt last);
Переставляет элементы из диапазона [first, last) в случайном порядке.
11.
template<typename BidIt, typename Pred>
void partition(BidIt first, BidIt last, Pred pr);
Переупорядочивает элементы в диапазоне [first, last). Все элементы, для которых предикат pr равен true, помещаются перед элементами, для которых он равен false.
12.
template<typename InIt1, typename InIt2, typename OutIt>
OutIt merge(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);
Объединяет две отсортированные последовательности в одну. Возвращает итератор, который указывает на элемент, расположенный за последним скопированным.
13.
template<typename InIt1, typename InIt2>
bool includes(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2);
Определяет, содержится ли множество [first1, last1) во множестве [first2, last2).
14.
template<typename InIt1, typename InIt2, typename OutIt>
OutIt set_union(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);
Записывает начиная с итератора x результат объединения множеств [first1, last1) и [first2, last2).
15.
template<typename InIt1, typename InIt2, typename OutIt>
OutIt set_intersection(InIt1 first1, InIt1 last1,InIt2 first2, InIt2 last2, OutIt x);
Записывает начиная с итератора x результат пересечения множеств [first1, last1) и [first2, last2).
16.
template<typename InIt1, typename InIt2, typename OutIt>
OutIt set_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);
Записывает начиная с итератора x результат разности множеств [first1, last1) и [first2, last2).
17.
template<typename InIt1, typename InIt2, typename OutIt>
OutIt set_symmetric_difference(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2, OutIt x);
Записывает начиная с итератора x результат симметрической разности множеств [first1, last1) и [first2, last2).
18.
template<typename InIt1, typename InIt2>
bool lexicographical_compare(InIt1 first1, InIt1 last1, InIt2 first2, InIt2 last2);
Осуществляет лексикографическое сравнение последовательностей множеств [first1, last1) и [first2, last2) на <.
Задание 2. Объекты-функции
- С помощью алгоритма generate сгенерировать последовательность чисел Фибоначчи.
- С помощью алгоритма generate сгенерировать последовательность, являющуюся арифметической прогрессией
- С помощью алгоритма generate сгенерировать последовательность случайных чисел из данного множества чисел.
- Найти максимальный элемент в массиве и его индекс с помощью for_each.
- Найти количество элементов, больших своих левых соседей, с помощью for_each.
- Найти количество локальных максимумов в последовательности с помощью for_each.
- Отсортировать список студентов с помощью l.sort(cmp), где cmp — класс-сравнитель студентов, в конструктор которого передается критерий сравнения (по какому полю).
- Обойти массив списков целых, выводя его содержимое, используя двойной for_each, объекты-функции и не используя циклы.
- Выдать матрицу, используя двойной for_each, объекты-функции и не используя циклы.
- Создать filtered_back_inserter, позволяющий добавлять в конец не все элементы, а только те, которые удовлетворяют некоторому условию. Условие передается как параметр конструктора filtered_back_inserter. Воспользоваться им в алгоритме copy.
- С помощью count_if посчитать, сколько слов в списке слов содержат хотя бы одну букву из заданной строки s.
- С помощью remove_if удалить из вектора строк те строки, которые заканчиваются на одну из букв заданной строки s.
- С помощью copy_if скопировать из списка строк в вектор строк только строки с длиной в диапазоне [a,b], где a и b задаются.
- Создайте итератор, накапливающий сумму пройденных элементов. С помощью copy заполните вектор так, чтобы его i-тый элемент был равен сумме элементов списка от 1-го до i-того.
- Сделайте filtered_ostream_iterator, выводящий в поток символов только английские буквы.
Задание 3. Эффективное использование контейнеров и алгоритмов
1. Неориентированный граф задан в файле в виде списков инцидентных вершин
количество вершин вершина 1 список инцидентных вершин вершина 2 список инцидентных вершин ... вершина n список инцидентных вершин
Считать его в память. Представление в памяти — в виде массива списков инцидентных вершин. Найти все его компоненты связности и сохранить в файл.
2. Неориентированный граф задан в файле в виде списков инцидентных вершин. Считать его в память. Представление в памяти — также в виде списков инцидентных вершин. Задан номер вершины. Ввести дополнительную нумерацию вершин: заданной вершине присвоить номер 0, всем инцидентным с ней вершинам (слой 1) — номер 1, всем еще не просмотренным вершинам, инцидентным вершинам с номером 1 (слой 2) — номер 2 и т.д. Для этого хранить на каждом шаге список вершин текущего слоя. Вывести в файл вершины по слоям.
3. Неориентированный граф задан в файле в виде списков инцидентных вершин. Считать его в память. Представление в памяти — также в виде списков инцидентных вершин. Найти остовное дерево графа и сохранить в файл в том же формате. Для нахождения остовного дерева можно, например, на каждом шаге выбирать дугу, соединяющую уже просмотренную верши-ну с еще не просмотренной.
4. В файле записаны слова. Имеется некоторое множество ключевых слов, хранимых в другом файле. Создать таблицу встречаемости для неключевых слов в виде
слово (строка, столбец), … , (строка, столбец)
и сохранить ее в третьем файле.
5. Разработать структуру данных «словарь, пополняемый словами из файлов». В словаре хранить слово и количество его повторений. Словарь должен уметь себя сохранять в файл, восстанавливать себя из файла и выдавать на экран слова, упорядоченные по алфавиту и по встречаемости.
6. В файле записаны слова. Имеется таблица синонимов, записанная в другом файле (для одного слова может быть несколько синонимов). Разработать структуру данных, поддерживающую таблицу синонимов. Заменить каждое слово в исходном файле на случайный синоним и результат записать в третий файл.
7. Дан список html-файлов, задаваемый в виде строки файлов, перечисляемых через запятую. Найти в них все вхождения URL-адресов в формате протокол://www.tratata.ppp.ru, где протокол – http, ftp, gopher, news, telnet, file. Выдать для каждого URL список вхождений (файл, строка, столбец).
8. В файле записаны существительные в разных падежах. Имеется таблица падежей для каждого слова. Разработать структуру данных, поддерживающую таблицу падежей. Выдать в другой файл слова из первого файла в формате
Именительный падеж слова (наименование падежа)
9. Имеется список 40 студентов, изучающих математику, физику, биологию и химию, заданный в файле в виде строк
Фамилия предмет
Каждый предмет изучает около 20 студентов. Разработать структуры данных, позволяющих эффективно отвечать на запросы вида «Выдать всех студентов, изучающих биологию и химию, но не изучающих физику».
10. Разработать контейнер строк hash_set, реализованный в виде хеш-таблицы. Контейнер должен содержать методы добавления, удаления и проверки на принадлежность, а также эффективную хеш-функцию. Контейнер должен быть устроен так же как и контейнеры стандартной библиотеки: возвращать свой итератор, который может перемещаться по элементам контейнера в некотором порядке. Заполнить контейнер словами из заданного файла. Сформировать из него два списка слов: содержащих менее 5 букв и являющихся перевертышами. Выдать эти списки отсортированными.