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

массиве на два; увеличьте значение каждого элемента в массиве на три; увеличьте значение каждого элемента в массиве на пять.

6. Напишите простую операцию copy()

template<class Iter1, class Iter2>

Iter2 copy(Iter f1, Iter1 e1, Iter2 f2);

копирующую последовательность [f1,e1] в последовательность [f2,f2+(e1–f1)] и, точно так же, как стандартная библиотечная функция копирования, возвращающую число f2+(e1–f1). Обратите внимание на то, что если f1==e1, то последовательность пуста и копировать нечего.

7. Используйте вашу функцию copy() для копирования массива в вектор или списка — в массив.

8. Используйте стандартную библиотечную функцию find() для того, чтобы убедиться, что вектор содержит значение 3, и выведите на экран соответствующую позицию этого числа в векторе, если это число в нем есть. Используйте стандартную библиотечную функцию find(), чтобы убедиться, что список содержит значение 27, и выведите на экран соответствующую позицию этого числа в списке, если это число в нем есть. Позиция первого элемента равна нулю, позиция второго элемента равна единице и т.д. Если функция find() возвращает итератор, установленный на конец последовательности, то значение в ней не найдено. Не забывайте тестировать программу после каждого этапа.

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

1. Почему программы, написанные разными людьми, выглядят по-разному? Приведите примеры.

2. Какие простые вопросы мы обычно задаем, думая о данных?

3. Перечислите разные способы хранения данных?

4. Какие основные операции можно выполнить с коллекцией данных?

5. Каких принципов следует придерживаться при хранении данных?

6. Что такое последовательность в библиотеке STL?

7. Что такое итератор в библиотеке STL? Какие операции поддерживают итераторы?

8. Как установить итератор на следующий элемент?

9. Как установить итератор на предыдущий элемент?

10. Что произойдет, если вы попытаетесь установить итератор на ячейку, следующую за концом последовательности?

11. Какие виды итераторов могут перемещаться на предыдущий элемент?

12. Почему полезно отделять данные от алгоритмов?

13. Что такое STL?

14. Что такое связанный список? Чем он в принципе отличается от вектора?

15. Что такое узел (в связанном списке)?

16. Что делает функция insert()? Что делает функция erase()?

17. Как определить, что последовательность пуста?

18. Какие операции предусмотрены в итераторе для класса list?

19. Как обеспечить перемещение по контейнеру, используя библиотеку STL?

20. В каких ситуациях лучше использовать класс string, а не vector?

21. В каких ситуациях лучше использовать класс list, а не vector?

22. Что такое контейнер?

23. Что должны делать функции begin() и end() в контейнере?

24. Какие контейнеры предусмотрены в библиотеке STL?

25. Перечислите категории итераторов? Какие виды итераторов реализованы в библиотеке STL?

26. Какие операции предусмотрены в итераторе с произвольным доступом, но неподдерживаются двунаправленным итератором?

Термины

Упражнения

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

2. Попробуйте запрограммировать пример с Джеком и Джилл из раздела 20.1.2. Для тестирования используйте несколько небольших файлов.

3. Проанализируйте пример с палиндромом (см. раздел 20.6); еще раз выполните задание из п. 2, используя разные приемы.

4. Найдите и исправьте ошибки, сделанные в примере с Джеком и Джилл в разделе 20.3.1, используя приемы работы с библиотекой STL.

5. Определите операторы ввода и вывода (>> и <<) для класса vector.

6. Напишите операцию “найти и заменить” для класса Document, используя информацию из раздела 20.6.2.

7. Определите лексикографически последнюю строку в неупорядоченном классе vector<string>.

8. Напишите функцию, подсчитывающую количество символов в объекте класса Document.

9. Напишите программу, подсчитывающую количество слов в объекте класса Document. Предусмотрите две версии: одну, в которой слово — это последовательность символов, разделенных пробелами, и вторую, в которой слово — это неразрывная последовательность символов из алфавита. Например, при первом определении выражения alpha.numeric и as12b — это слова, а при втором — каждое из них рассматривается как два слова.

10. Напишите программу, подсчитывающую слова, в которой пользователь мог бы сам задавать набор символов-разделителей.

11. Создайте объект класса vector<double> и скопируйте в него элементы списка типа list<int>, передавая его как параметр (по ссылке). Проверьте, что копия полна и верна. Затем выведите на экран элементы в порядке возрастания их значений.

12. Завершите определение класса list из разделов 20.4.1 и 20.4.2 и продемонстрируйте работу функции high(). Выделите память для объекта класса Link, представляющего узел, следующий за концом списка.

13. На самом деле в классе list нам не нужен реальный объект класса Link, расположенный за последним элементом. Модифицируйте свое решение из предыдущего упражнения так, чтобы в качестве указателя на несуществующий объект класса Link (list<Elem>::end()) использовалось значение 0; иначе говоря, размер пустого списка может быть равен размеру отдельного указателя.

14. Определите односвязный список slist, ориентируясь на стиль класса std::list. Какие операции из класса list стоило бы исключить из класса slist, поскольку он не содержит указателя на предыдущий элемент?

15. Определите класс pvector, похожий на вектор указателей, за исключением того, что он содержит указатели объекта и каждый объект уничтожается его деструктором.

16. Определите класс ovector, похожий на класс pvector, за исключением того, что операции [ ] и * возвращают не указатели, а ссылки на объект, на который ссылается соответствующий элемент.

17. Определите класс ownership_vector, хранящий указатели на объект как и класс pvector, но предусматривающий механизм, позволяющий пользователю решить, какие объекты принадлежат вектору (т.е. какие объекты удалены деструктором). Подсказка: это простое упражнение, если вы вспомните главу 13.

18. Определите итератор с проверкой выхода за пределы допустимого диапазона для класса vector (итератор с произвольным доступом).

19. Определите итератор с проверкой выхода за пределы допустимого диапазона для класса list (двунаправленный итератор).

20. Выполните эксперимент, посвященный сравнению временных затрат при работе с классами vector и list. Способ измерения длительности работы программы изложен в разделе 26.6.1. Сгенерируйте N случайных целых чисел в диапазоне [0:N]. Вставьте каждое сгенерированное число в вектор vector<int> (после каждой вставки увеличивающийся на один элемент). Храните объект класса vector в упорядоченном виде; иначе говоря, значение должно быть вставлено так, чтобы все предыдущие значения были меньше или равны ему, а все последующие значения должны быть больше него. Выполните тот же эксперимент, используя класс