Программирование. Принципы и практика использования C++ Исправленное издание

5. Напишите функцию, считывающую пары из потока cin и помещающую их в контейнер msi.

6. Прочитайте десять пар из потока ввода и поместите их в контейнер msi.

7. Запишите элементы контейнера msi в поток cout.

8. Выведите сумму (целых) значений из контейнера msi.

9. Определите контейнер map с именем mis.

10. Введите значения из контейнера msi в контейнер mis; иначе говоря, если в контейнере msi есть элемент ("lecture",21), то контейнер mis также должен содержать элемент (21,"lecture").

11. Выведите элементы контейнера mis в поток cout.

Несколько заданий, касающихся контейнера vector.

1. Прочитайте несколько чисел с плавающей точкой (не меньше 16 значений) из файла в контейнер vector с именем vd.

2. Выведите элементы контейнера vd в поток cout.

3. Создайте вектор vi типа vector с таким же количеством элементов, как в контейнере vd; скопируйте элементы из контейнера vd в контейнер vi.

4. Выведите в поток cout пары (vd[i], vi[i]) по одной в строке.

5. Выведите на экран сумму элементов контейнера vd.

6. Выведите на экран разность между суммой элементов контейнеров vd и vi.

7. Существует стандартный алгоритм reverse, получающий в качестве аргументов последовательность (пару итераторов); поменяйте порядок следования элементов vd на противоположный и выведите их в поток cout.

8. Вычислите среднее значение элементов в контейнере vd и выведите его на экран.

9. Создайте новый контейнер vector с именем vd2 и скопируйте в него элементы контейнера vd, которые меньше среднего значения.

10. Отсортируйте контейнер vd и выведите его элементы на экран.

Контрольные вопросы

1. Приведите примеры полезных алгоритмов из библиотеки STL?

2. Что делает алгоритм find? Приведите по крайней мере пять примеров.

3. Что делает алгоритм count_if?

4. Что алгоритм sort(b,e) использует в качестве критерия поиска?

5. Как алгоритмы из библиотеки STL получают контейнеры в качестве аргумента ввода?

6. Как алгоритмы из библиотеки STL получают контейнеры в качестве аргумента вывода?

7. Как алгоритмы из библиотеки STL обозначают ситуации “не найден” или “сбой”?

8. Что такое функция-объект?

9. Чем функция-объект отличается от функции?

10. Что такое предикат?

11. Что делает алгоритм accumulate?

12. Что делает алгоритм inner_product?

13. Что такое ассоциативный контейнер? Приведите не менее трех примеров.

14. Является ли класс list ассоциативным контейнером? Почему нет?

15. Сформулируйте принцип организации бинарного дерева.

16. Что такое (примерно) сбалансированное дерево?

17. Сколько места занимает элемент в контейнере map?

18. Сколько места занимает элемент в контейнере vector?

19. Зачем нужен контейнер unordered_map, если есть (упорядоченный) контейнер map?

20. Чем контейнер set отличается от контейнера map?

21. Чем контейнер multimap отличается от контейнера map?

22. Зачем нужен алгоритм copy, если мы вполне могли бы написать простой цикл?

23. Что такое бинарный поиск?

Термины

Упражнения

1. Перечитайте главу и выполните все упражнения из врезок ПОПРОБУЙТЕ, если вы еще не сделали этого.

2. Найдите надежный источник документации по библиотеке STL и перечислите все стандартные алгоритмы.

3. Самостоятельно реализуйте алгоритм count. Протестируйте его.

4. Самостоятельно реализуйте алгоритм count_if. Протестируйте его.

5. Что нам следовало бы сделать, если бы мы не могли вернуть итератор end, означающий, что элемент не найден? Заново спроектируйте и реализуйте алгоритмы find и count, чтобы они получали итераторы, установленные на первый и последний элементы. Сравните результаты со стандартными версиями.

6. В примере класса Fruit из раздела 21.6.5 мы копировали структуры Fruit в контейнер set. Что делать, если мы не хотим копировать эти структуры? Мы могли бы вместо этого использовать контейнер set. Однако в этом случае мы были бы вынуждены определить оператор сравнения для этого контейнера. Выполните это упражнение еще раз, используя контейнер set, Fruit_comparison>. Обсудите разницу между этими реализациями.

7. Напишите функцию бинарного поиска для класса vector (без использования стандартного алгоритма). Выберите любой интерфейс, какой захотите. Протестируйте его. Насколько вы уверены, что ваша функция бинарного поиска работает правильно? Напишите функцию бинарного поиска для контейнера list. Протестируйте ее. Насколько похожи эти две функции бинарного поиска? Как вы думаете, были бы они настолько похожи, если бы вам не было ничего известно о библиотеке STL?

8. Вернитесь к примеру, связанному с подсчетом частоты слов из раздела 21.6.1, и модифицируйте его, чтобы слова выводились в порядке следования частот, а не в лексикографическом порядке. Например, на экран должна выводиться строка 3: C++, а не C++: 3.