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

18. Что такое двусвязный список?

19. Что собой представляет переменная this и когда она нужна?

Термины

Упражнения

1. Какой формат вывода значений указателя в вашей реализации языка? Подсказка: не читайте документацию.

2. Сколько байтов занимают типы int, double и bool? Ответьте на вопрос, не используя оператор sizeof.

3. Напишите функцию void to_lower(char* s), заменяющую все прописные символы в строке s в стиле языка С на их строчные эквиваленты. Например, строка “Hello, World!” примет вид “hello, world!”. Не используйте стандартные библиотечные функции. Строка в стиле языка С представляет собой массив символов, который завершается нулем, поэтому если вы обнаружите символ 0, то это значит, что вы находитесь в конце массива.

4. Напишите функцию char* strdup(const char*), копирующую строку в стиле языка C в свободную память одновременно с ее выделением. Не используйте стандартные библиотечные функции.

5. Напишите функцию char* findx(const char* s,const char* x), находящую первое вхождение строки x в стиле языка C в строку s.

6. В этой главе ничего не говорилось о том, что произойдет, если, используя оператор new, вы выйдете за пределы памяти. Это называется исчерпанием памяти (memory exhaustion). Выясните, что случится. У вас есть две альтернативы: обратиться к документации или написать программу с бесконечным циклом, в котором постоянно происходит выделение памяти и никогда не выполняется ее освобождение. Попробуйте оба варианта. Сколько памяти вы можете использовать, пока она не исчерпается?

7. Напишите программу, считывающую символы из потока cin в массив, расположенный в свободной памяти. Читайте отдельные символы, пока не будет введен знак восклицания (!). Не используйте класс std::string. Не беспокойтесь об исчерпании памяти.

8. Выполните упр. 7 еще раз, но теперь считывайте символы в строку std::string, а не в свободную память (класс string знает, как использовать свободную память). 9. Как увеличивается стек: вверх (в сторону старших адресов) или вниз (в сторону младших адресов)? В каком направлении возрастает занятая память изначально (т.е. пока вы не выполнили оператор delete)? Напишите программу, позволяющую выяснить это.

10. Посмотрите на решение упр. 7. Может ли ввод вызвать переполнение массива; иначе говоря, можете ли вы ввести больше символов, чем выделено памяти (это серьезная ошибка)? Что произойдет, если вы введете больше символов, чем выделено памяти?

11. Завершите программу, создающую список богов, из раздела 17.10.1 и выполните ее.

12. Зачем нужны две версии функции find()?

13. Модифицируйте класс Link из раздела 17.10.1, чтобы он хранил значение типа struct God. Класс God должен иметь члены типа string: имя, мифология, транспортное средство и оружие. Например, God("Зевс", "Греция", "", "молния") and God("Один", "Норвегия", "Восьминогий летающий конь по имени Слейпнер", ""). Напишите программу print_all(), выводящую имена богов и их атрибуты построчно. Добавьте функцию-член add_ordered(), размещающую новый элемент с помощью оператора new в правильной лексикографической позиции. Используя объекты класса Link со значениями типа God, составьте список богов из трех мифологий; затем переместите элементы (богов) из этого списка в три лексикографически упорядоченных списка — по одному на каждую мифологию.

14. Можно ли написать список богов из раздела 17.10.1 в виде односвязного списка; другими словами, могли бы мы удалить член prev из класса Link? Какие причины могли бы нас заставить это сделать? В каких ситуациях разумно использовать односвязные списки? Переделайте этот пример с помощью односвязного списка.

Послесловие

Зачем возиться с такими низкоуровневыми механизмами, как указатель и свободная память, а не просто использовать класс vector? Один из ответов состоит в том, что кто-то же написал класс vector и аналогичные абстракции, поэтому нам важно знать, как это можно сделать. Существуют языки программирования, не содержащие указателей и не имеющие проблем, связанных с низкоуровневым программированием. По существу, программисты, работающие на таких языках, перепоручают решение задач, связанных с непосредственным доступом к аппаратному обеспечению, программистам, работающим на языке C++ (или на других языках, допускающих низкоуровневое программирование). Однако нам кажется, что главная причина заключается в том, что невозможно понять компьютер и программирование, не зная, как программа взаимодействует с физическими устройствами. Люди, ничего не знающие об указателях, адресах памяти и так далее, часто имеют неверные представления о возможностях языка программирования, на которых они работают; такие заблуждения приводят к созданию программ, которые “почему-то не работают”.

Глава 18

Векторы и массивы

“Покупатель, будь бдителен!”

Полезный совет

В этой главе показано, как копировать векторы и обращаться к ним с помощью индексов. Для этого мы обсуждаем копирование в целом и рассматриваем связь вектора с низкоуровневым массивом. Мы демонстрируем также связь массива с указателями и анализируем проблемы, возникающие вследствие этой связи. В главе также рассматриваются пять важнейших операций, которые должны быть предусмотрены для любых типов: создание, создание по умолчанию, создание с копированием, копирующее присваивание и уничтожение.

18.1. Введение

Для того чтобы подняться в воздух, самолет должен разогнаться до скорости взлета. Пока самолет грохочет по взлетной полосе, он представляет собой не более чем тяжелый и неуклюжий грузовик. Однако, поднявшись в воздух, самолет становится необыкновенным, элегантным и эффективным транспортным средством. Это объясняется тем, что в воздухе самолет находится в своей стихии.

• Объект в памяти имеет фиксированный размер.

• Объект в памяти занимает конкретное место.

• Компьютер предоставляет только самые необходимые операции над объектами (например, копирование слова, сложение двух слов и т.д.).

По существу, эти ограничения относятся к встроенным типам и операциям языка С++ (и унаследованы от языка С; см. раздел 22.2.5 и главу 27). В главе 17 мы уже ознакомились с типом vector, управляющим доступом ко всем своим элементам и обеспечивающим операции, которые выглядят натурально с точки зрения пользователя, но не с точки зрения аппаратного обеспечения.