с двойной связью, которые будут
- (*2) Определите семейство списков с двойной связью, которые будут двойниками списков с одной связью, определенных в §8.3.
- (*3) Определите шаблон типа String, параметром которого является тип символа. Покажите как его можно использовать не только для обычных символов, но и для гипотетического класса lchar, который представляет символы не из английского алфавита или расширенный набор символов. Нужно постараться так определить String, чтобы пользователь не заметил ухудшения характеристик программы по памяти и времени или в удобстве по сравнению с обычным строковым классом.
- (*1.5) Определите класс Record (запись) с двумя членами-данными: count (количество) и price (цена). Упорядочите вектор из таких записей по каждому из членов. При этом нельзя изменять функцию сортировки и шаблон Vector.
- (*2) Завершите определения шаблонного класса Map, написав недостающие функции-члены.
- (*2) Задайте другую реализацию Map из §8.8, используя списочный класс с двойной связью.
- (*2.5) Задайте другую реализацию Map из §8.8, используя сбалансированное дерево. Такие деревья описаны в §6.2.3 книги Д. Кнут "Искусство программирования для ЭВМ" т.1, "Мир", 1978 [K].
- (*2) Сравните качество двух реализаций Map. В первой используется класс Link со своей собственной функцией размещения, а во второй - без нее.
- (*3) Сравните производительность программы подсчета слов из §8.8 и такой же программы, не использующей класса Map. Операции ввода-вывода должны одинаково использоваться в обеих программах. Сравните несколько таких программ, использующих разные варианты класса Map, в том числе и класс из вашей библиотеки, если он там есть.
- (*2.5) С помощью класса Map реализуйте топологическую сортировку. Она описана в [K] т.1, стр. 323-332. (см. упражнение 6).
- (*2) Модифицируйте программу из §8.8 так, чтобы она работала правильно для длинных имен и для имен, содержащих пробелы (например, "thumb back").
- (*2) Определите шаблон типа для чтения различных видов строк, например, таких (предмет, количество, цена).
- (*2) Определите класс Sort из §8.4.5, использующий сортировку по методу Шелла. Покажите как можно задать метод сортировки с помощью параметра шаблона. Алгоритм сортировки описан в [K] т.3, §5.2.1 (см. упражнение 6).
- (*1) Измените определения Map и Mapiter так, чтобы постфиксные операции ++ и -- возвращали объект Mapiter.
- (*1.5) Используйте шаблоны типа в стиле модульного программирования, как это было показано в §8.4.5 и напишите функцию сортировки, рассчитанную сразу на Vector<T> и T[].
