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

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 в упорядоченном виде; иначе говоря, значение должно быть вставлено так, чтобы все предыдущие значения были меньше или равны ему, а все последующие значения должны быть больше него. Выполните тот же эксперимент, используя класс list<int> для хранения целых чисел. При каких значениях N класс list обеспечивает более высокое быстродействие, чем класс vector? Попробуйте объяснить результаты эксперимента. Впервые этот эксперимент был предложен Джоном Бентли (John Bentley).

Послесловие

Если бы у нас было N видов контейнеров, содержащих данные, и M операций, которые мы хотели бы над ними выполнить, то мы могли бы легко написать N*M фрагментов кода. Если бы данные имели K разных типов, то нам пришлось бы написать N*M*K фрагментов кода. Библиотека STL решает эту проблему, разрешая задавать тип элемента в виде параметра (устраняя множитель K) и отделяя доступ к данным от алгоритмов. Используя итераторы для доступа к данным в любом контейнере и в любом алгоритме, мы можем ограничиться N+M алгоритмами. Это огромное облегчение. Например, если бы у нас было 12 контейнеров и 60 алгоритмов, то прямолинейный подход потребовал бы создания 720 функций, в то время как стратегия, принятая в библиотеке STL, требует только 60 функций и 12 определений итераторов: тем самым мы экономим 90% работы. Кроме того, в библиотеке STL приняты соглашения, касающиеся определения алгоритмов, упрощающие создание корректного кода и облегчающие его композицию с другими кодами, что также экономит много времени.

Глава 21 Алгоритмы и ассоциативные массивы

“Теоретически практика проста”.

Тригве Рийнскауг (Trygve Reenskaug)

В этой главе мы завершаем описание идей, лежащих в основе библиотеки STL, и наш обзор ее возможностей. Здесь мы сосредоточим свое внимание на алгоритмах. Наша главная цель — ознакомить читателей с десятками весьма полезных алгоритмов, которые сэкономят им дни, если не месяцы, работы. Описание каждого алгоритма сопровождается примерами его использования и указанием технологий программирования, которые обеспечивают его работу. Вторая цель, которую мы преследуем, — научить читателей писать свои собственные элегантные и эффективные алгоритмы в тех случаях, когда ни стандартная, ни другие доступные библиотеки не могут удовлетворить их потребности. Кроме того, мы рассмотрим еще три контейнера: map, set и unordered_map.