Практикум по спецкурсу Стандартная библиотека C++

Задание 1. Обобщенные алгоритмы

Указание к выполнению

Реализовать следующие алгоритмы. Привести примеры их работы с вектором и списком.

Задачи

1.

template<typename FwdIt, typename Pred>
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. Объекты-функции

1. С помощью алгоритма generate сгенерировать последовательность чисел Фибоначчи.
2. С помощью алгоритма generate сгенерировать последовательность, являющуюся арифметической прогрессией
3. С помощью алгоритма generate сгенерировать последовательность случайных чисел из данного множества чисел.
4. Найти максимальный элемент в массиве и его индекс с помощью for_each.
5. Найти количество элементов, больших своих левых соседей, с помощью for_each.
6. Найти количество локальных максимумов в последовательности с помощью for_each.
7. Отсортировать список студентов с помощью l.sort(cmp), где cmp — класс-сравнитель студентов, в конструктор которого передается критерий сравнения (по какому полю).
8. Обойти массив списков целых, выводя его содержимое, используя двойной for_each, объекты-функции и не используя циклы.
9. Выдать матрицу, используя двойной for_each, объекты-функции и не используя циклы.
10. Создать filtered_back_inserter, позволяющий добавлять в конец не все элементы, а только те, которые удовлетворяют некоторому условию. Условие передается как параметр конструктора filtered_back_inserter. Воспользоваться им в алгоритме copy.
11. С помощью count_if посчитать, сколько слов в списке слов содержат хотя бы одну букву из заданной строки s.
12. С помощью remove_if удалить из вектора строк те строки, которые заканчиваются на одну из букв заданной строки s.
13. С помощью copy_if скопировать из списка строк в вектор строк только строки с длиной в диапазоне [a,b], где a и b задаются.
14. Создайте итератор, накапливающий сумму пройденных элементов. С помощью copy заполните вектор так, чтобы его i-тый элемент был равен сумме элементов списка от 1-го до i-того.
15. Сделайте 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 букв и являющихся перевертышами. Выдать эти списки отсортированными.