Язык программирования C Пятое издание
 Скачать 1.85 Mb.
|
|
Упражнение 11.27. Для решения каких видов задач используется функция count()? Когда вместо нее можно использовать функцию find()? Упражнение 11.28. Определите и инициализируйте переменную, содержащую результат вызова функции find() для карты строк и векторов целых чисел. Упражнение 11.29. Что возвращают функции upper_bound(), lower_bound() и equal_range(), Page 550/1103 когда им передается ключ, отсутствующий в контейнере? Упражнение 11.30. Объясните значение операнда pos.first->second, использованного в выражении вывода последней программы данного раздела. Упражнение 11.31. Напишите программу, определяющую контейнер multimap авторов и их работ. Используйте функцию find() для поиска элемента и его удаления. Убедитесь в корректности работы программы, когда искомого элемента нет в карте. Упражнение 11.32. Используя контейнер multimap из предыдущего упражнения, напишите программу вывода списка авторов и их работ в алфавитном порядке. 11.3.6. Карта преобразования слов Завершим этот раздел программой, иллюстрирующей создание, поиск и перебор карты. Программа получает одну строку и преобразует ее в другую. Программе передаются два файла: первый содержит правила, используемые для преобразования текста во втором файле. Каждое правило состоит из слова, которое может встретиться во входном файле, и фразы, используемой вместо него. Идея в том, чтобы, встретив во вводе некое слово, заменить его соответствующей фразой. Второй файл содержит преобразуемый текст. Вот содержимое файла преобразования слов. brb be right back k okay? y why r are u you pic picture thk thanks! l8r later Подлежащий преобразованию текст таков: where r u y dont u send me a pic k thk l8r Программа должна создать следующий вывод: where are you why dont you send me a picture okay? thanks! later Программа преобразования слова Page 551/1103 Решение подразумевает использование трех функций. Функция word_transform() будет осуществлять общую обработку. Потребуются два аргумента типа ifstream: первый будет связан с файлом преобразования слов, а второй — с текстовым файлом, который предстоит преобразовать. Функция buildMap() будет читать файл правил преобразования и создавать элемент карты для каждого слова и результата его преобразования. Функция transform() получит строку и, если она есть в карте, возвратит результат преобразования. Давайте начнем с определения функции word_transform(). Важнейшие ее части — вызовы функций buildMap() и transform(): void word_transform(ifstream &map_file, ifstream &input) { auto trans_map = buildMap(map_file); // хранит преобразования string text; // содержит каждую строку из ввода while (getline(input, text)) { // читать строку из ввода istringstream stream(text); // читать каждое слово string word; bool firstword = true; // контролирует вывод пробела while (stream >> word) { if (firstword) firstword = false; else cout << " "; // вывод пробела между словами // transform() возвращает свой первый аргумент или // результат преобразования cout << transform(word, trans_map); // вывод результата } Page 552/1103 cout << endl; // обработка текущей строки ввода окончена } } Функция начинается вызовом функции buildMap(), создающим карту преобразования слов. Результат сохраняется в карте trans_map. Остальная часть функции обрабатывает входной файл. Цикл while использует функцию getline() для чтения входного файла по одной строке за раз. Построчно чтение осуществляется для того, чтобы строки вывода заканчивались там же, где и строки входного файла. Для получения слов каждой строки используется вложенный цикл while, использующий строковый поток istringstream (см. раздел 8.3) для обработки каждого слова текущей строки. Внутренний цикл while выводит результат, используя логическую переменную firstword, чтобы решить, выводить ли пробел. Вызов функции transform() получает подлежащее выводу слово. Значение, возвращенное функцией transform(), будет либо исходным словом строки, либо соответствующим ему преобразованием из карты transmap. Создание карты преобразования Функция buildMap() читает переданный ей файл и создает карту преобразований. map<string, string> buildMap(ifstream &map_file) { map<string, string> trans_map; // хранит преобразования string key; // слово для преобразования string value; // фраза, используемая вместо него // прочитать первое слово в ключ, а остальную часть строки в значение while (map_file >> key && getline(map_file, value)) if (value.size() > 1) // проверить, есть ли преобразование trans_map[key] = value.substr(1); // убрать предваряющий // пробел else throw runtime_error("no rule for " + key); Page 553/1103 return trans_map; } Каждая строка файла map_file соответствует правилу. Каждое правило — это слово, сопровождаемое фразой, способной содержать несколько слов. Для чтения слов, преобразуемых в ключи, используется оператор >> и функция getline() для чтения остальной части строки в значение. Поскольку функция getline() не отбрасывает предваряющие пробелы (см. раздел 3.2.2), необходимо убрать пробел между словом и соответствующим ему правилом. Прежде чем сохранить преобразование, осуществляется проверка наличия в нем хотя бы одного символа. Если это так, то происходит вызов функции substr() (см. раздел 9.5.1), позволяющий устранить пробел, отделяющий фразу преобразования от соответствующего ему слова, и сохранить эту подстроку в карте trans_map. Обратите внимание на использование оператора индексирования при добавлении пары ключ-значение. При этом неявно игнорируется происходящее при повторении слова в файле преобразования. Если слово повторяется несколько раз, то в карте trans_map окажется последняя соответствующая фраза. По завершении цикла while карта trans_map содержит все данные, необходимые для преобразования ввода. Осуществление преобразования Фактическое преобразование осуществляет функция transform(). Ее параметры — ссылки на преобразуемую строку и карту преобразования. Если переданная строка находится в карте, функция transform() возвращает соответствующую ей фразу преобразования. Если переданной строки в карте нет, функция transform() возвращает свой аргумент: const string & transform(const string &s, const map<string, string> &m) { // фактическая работа карты; это основная часть программы auto map_it = m.find(s); // если слово есть в карте преобразования if (map it != m.cend()) return map_it->second; // использовать замену слова else return s; // в противном случае возвратить исходное слово } Код начинается с вызова функции find(), позволяющего определить, находится ли данная строка в карте. Если это так, то функция find() возвращает итератор на соответствующий элемент. В противном случае функция find() возвращает итератор на элемент после конца. Если элемент найден, обращение к значению итератора возвращает пару, содержащую ключ Page 554/1103 и значение этого элемента (см. раздел 11.3). Функция возвращает значение переменной-члена second этой пары, являющееся преобразованной фразой, используемой вместо строки s. Упражнения раздела 11.3.6 Упражнение 11.33. Реализуйте собственную версию программы преобразования слов. Упражнение 11.34. Что будет, если в функции transform() вместо функции find() использовать оператор индексирования ? Упражнение 11.35. Что будет (если будет) при таком изменении функции buildMap(): trans_map[key] = value.substr(1); as trans_map.insert({key, value.substr(1)})? Упражнение 11.36. Текущая версия программы не проверяет допустимость входного файла. В частности, она подразумевает, что все правила в файле преобразований корректны. Что будет, если строка в этом файле содержит ключ, один пробел и больше ничего? Проверьте свой ответ на текущей версии программы. 11.4. Неупорядоченные контейнеры Новый стандарт определяет четыре неупорядоченных ассоциативных контейнера (unordered container). Вместо оператора сравнения для организации своих элементов эти контейнеры используют хеш-функцию (hash function) и оператор == типа ключа. Неупорядоченный контейнер особенно полезен, когда имеющийся тип ключа не дает очевидных отношений для упорядочивания элементов. Эти контейнеры полезны также в приложениях, где цена упорядочивания элементов высока. Хотя в принципе хеширование обеспечивает лучшую среднюю производительность, достижение хороших результатов на практике зачастую требует серьезной проверки производительности и настройки. В результате обычно проще (а зачастую и производительней) использовать упорядоченный контейнер. Используйте неупорядоченный контейнер, если тип ключа принципиально неупорядочен или если проверка производительности свидетельствует о проблеме, решить которую позволит только хеширование. Использование неупорядоченного контейнера Кроме функций управления хешированием, неупорядоченные контейнеры предоставляют те же функции (find(), insert() и т.д.), что и упорядоченные контейнеры. Это значит, что функции, использовавшиеся для контейнеров map и set, применимы также к контейнерам unordered_map и unordered_set. Аналогично неупорядоченные контейнеры имеют версии с не уникальными ключами. В результате вместо соответствующего упорядоченного контейнера можно обычно использовать неупорядоченный контейнер, и наоборот. Но поскольку элементы хранятся неупорядочено, вывод программы, использующей неупорядоченный контейнер, будет (обычно) отличаться от такового при использовании упорядоченного контейнера. Например, первоначальную программу подсчета слов из раздела 11.1 можно переписать так, Page 555/1103 чтобы использовать контейнер unordered_map: // подсчет слов, но слова не в алфавитном порядке unordered_map<string, size_t> word_count; string word; while (cin >> word) ++word_count[word]; // получить и прирастить счетчик слов for (const auto &w : word_count) // для каждого элемента карты // отобразить результаты cout << w.first << " occurs " << w.second << ((w.second >1) ? " times" : " time") << endl; Единственное различие между этой программой и первоначальной заключается в типе word_count. Если запустить эту версию для того же ввода, то получится то же количество для каждого слова. containers occurs 1 time use occurs 1 time can occurs 1 time examples occurs 1 time Но вывод вряд ли будет в алфавитном порядке. Управление ячейками Неупорядоченные контейнеры организованы как коллекция ячеек, каждая из которых содержит любое количество элементов. Для группировки элементов в ячейки контейнер использует хеш-функцию. Для доступа к элементу контейнер сначала вычисляет хеш-код элемента, указывающий, где искать ячейку. Контейнер помещает все элементы с одинаковым значением хеш-функции в ту же ячейку. Если контейнер допускает несколько элементов с одинаковым ключом, то все элементы с этим ключом будут находиться в той же ячейке. В результате производительность неупорядоченного контейнера зависит от качеств его хеш-функции, количества и размера его ячеек. Хеш-функция всегда возвращает тот же результат, будучи вызванной с тем же аргументом. В идеале хеш-функция сопоставляет также каждое конкретное значение с уникальной ячейкой. Однако хеш-функция может сопоставить элементы с разными ключами с той же ячейкой. Когда ячейка содержит несколько элементов, поиск искомого среди них осуществляется последовательно. Как правило, вычисление хеш-кода элемента и поиск его ячейки осуществляется очень быстро. Но если в ячейке много элементов, то для поиска определенного элемента может понадобиться много сравнений. Page 556/1103 Неупорядоченные контейнеры предоставляют набор перечисленных в табл. 11.8 функций, позволяющих управлять ячейками. Эти функции-члены позволяют запрашивать состояние контейнера и реорганизовать его по мере необходимости. Таблица 11.8. Функции управления неупорядоченным контейнером Взаимодействие с ячейками с.bucket_count() Количество используемых ячеек c.max_bucket_count() Наибольшее количество ячеек, которое может содержать данный контейнер c.bucket_size(n) Количество элементов в ячейке n c.bucket(k) Ячейка, в которой следует искать элементы с ключом k Перебор ячеек local_iterator Тип итератора, способный обращаться к элементам в ячейке const_local_iterator Константная версия итератора ячейки c.begin(n), c.end(n) Итераторы на первый и следующий после последнего элементы ячейки n c.cbegin(n), c.cend(n) Возвращают итератор const_local_iterator Политика хеша c.load_factor() Среднее количество элементов на ячейку. Возвращает тип float c.max_load_factor() Средний размер ячейки, который пытается поддерживать контейнер c. Контейнер с добавляет ячейки, чтобы сохранить соотношение load_factor <= max_load_factor. Возвращает тип float c.rehash(n) Реорганизует хранилище так, чтобы bucket_count >= n и bucket_count > size/max_load_factor c.reserve(n) Реорганизует контейнер c так, чтобы он мог содержать n элементов без вызова функции rehash() Требования к типу ключа неупорядоченных контейнеров По умолчанию для сравнения элементов неупорядоченные контейнеры используют оператор == типа ключа. Они также используют объект типа hash<key_type> при создании хеш-кода для каждого элемента. Библиотека поставляет также версии шаблона хеша для встроенных типов, включая указатели. Она определяет также шаблон hash для некоторых из библиотечных типов, включая строки и интеллектуальные указатели, которые рассматривались в главе 12. Таким образом, можно непосредственно создать неупорядоченный контейнер, ключ которого имеет один из встроенных типов (включающий типы указателей) либо тип string или интеллектуального указателя. Однако нельзя непосредственно определить неупорядоченный контейнер, использующий для ключа собственные типы классов. В отличие от контейнеров, шаблон хеша нельзя использовать непосредственно. Вместо этого придется предоставить собственную версию шаблона hash. Это будет описано в разделе 16.5. Вместо хеша по умолчанию можно применить стратегию, подобную используемой при переопределении заданного по умолчанию оператора сравнения ключей упорядоченных контейнеров (см. раздел 11.2.2). Чтобы использовать тип Sales_data для ключа, необходимо предоставить функцию для замены оператора == и вычисления хеш-кода. Начнем с определения этих функций: size_t hasher(const Sales_data &sd) { return hash<string>()(sd.isbn()); } bool eqOp(const Sales_data &lhs, const Sales_data &rhs) { return lhs.isbn() == rhs.isbn(); } Чтобы создать хеш-код для переменной-члена ISBN, функция hasher() использует объект библиотечного типа hash для типа string. Точно так же функция eqOp() сравнивает два Page 557/1103 объекта класса Sales_data, сравнивая их ISBN. Эти функции можно также использовать для определения контейнера unordered_multiset следующим образом: using SD_multiset = unordered_multiset<Sales_data, decltype(hasher)*, decltype(eqOp)*>; // аргументы - размер ячейки, указатель на оператор равенства и // хеш-функцию SD_multiset bookstore(42, hasher, eqOp); Чтобы упростить объявление bookstore, определим сначала псевдоним типа (см. раздел 2.5.1) для контейнера unordered_multiset, у хеша и оператора равенства которого есть те же типы, что и у функций hasher() и eqOp(). Используя этот тип, определим bookstore, передав указатели на функции, которые он должен использовать. Если у класса есть собственный оператор ==, можно переопределить только хеш-функцию: // использовать FooHash для создания хеш-кода; // у Foo должен быть оператор == unordered_set<Foo, decltype(FooHash)*> fooSet(10, FooHash); Упражнения раздела 11.4 Упражнение 11.37. Каковы преимущества неупорядоченного контейнера по сравнению с упорядоченной версией этого контейнера? Каковы преимущества упорядоченной версии? Упражнение 11.38. Перепишите программы подсчета слов (см. раздел 11.1) и преобразования слов (см. раздел 11.3.6) так, чтобы использовать контейнер unordered_map. Резюме Ассоциативные контейнеры обеспечивают эффективный поиск и возвращение элементов по ключу. Использование ключа отличает ассоциативные контейнеры от последовательных, в которых к элементам обращаются по позиции. Существует восемь ассоциативных контейнеров со следующими свойствами. • Карта хранит пары ключ-значение; набор хранит только ключи. • Есть контейнеры с уникальными ключами и с не уникальными. • Ключи могут храниться упорядоченными или нет. Page 558/1103 Упорядоченные контейнеры используют функцию сравнения для упорядочивания элементов по ключу. По умолчанию для сравнения используется оператор < типа ключа. Неупорядоченные контейнеры используют для организации своих элементов оператор == типа ключа и объект типа hash<key_type>. Имена контейнеров с не уникальными ключами включают слово multi; а имена контейнеров, использующих хеширование, начинаются словом unordered. Контейнер set — это упорядоченная коллекция, каждый ключ которой уникален; контейнер unordered_multiset — это неупорядоченная коллекция, ключи которой могут повторяться. Ассоциативные контейнеры имеют много общих операций с последовательными контейнерами. Но ассоциативные контейнеры определяют некоторые новые функции и переопределяют значение и типы возвращаемого значения некоторых функций, общих для последовательных и ассоциативных контейнеров. Различия в функциях отражают способ использования ключей в ассоциативных контейнерах. Итераторы упорядоченных контейнеров обеспечивают доступ к элементам по ключу. Элементы с тем же ключом хранятся рядом друг с другом и в упорядоченных, и в неупорядоченных контейнерах. Термины Ассоциативный контейнер (associative container). Тип, содержащий коллекцию объектов и обеспечивающий эффективный поиск по ключу. Ассоциативный массив (associative array). Массив, элементы которого проиндексированы по ключу, а не по позиции. Таким образом, массив сопоставляет (ассоциирует) ключ со значением. Контейнер map (карта). Ассоциативный контейнер, аналогичный ассоциативному массиву. Подобно типу vector, тип map является шаблоном класса. Но при создании карты необходимо указать два типа: тип ключа и тип связанного с ним значения. В контейнере map ключи уникальны, они не повторяются. Каждый ключ связан с определенным значением. Обращение к значению итератора карты возвращает объект типа pair, который содержит константный ключ и связанное (ассоциированное) с ним значение. Контейнер multimap. Ассоциативный контейнер, подобный контейнеру map, но способный содержать одинаковые ключи. Контейнер multiset. Ассоциативный контейнер, который содержит только ключи. В отличие от набора, способен содержать одинаковые ключи. Контейнер set (набор). Ассоциативный контейнер, который содержит только ключи. Ключи в контейнере set не могут совпадать. Контейнер unordered_map. Контейнер, элементы которого являются парами ключ-значение. Допустим только один элемент на ключ. Контейнер unordered_multimap. Контейнер, элементы которого являются парами ключ-значение. Допустимо несколько элементов на ключ. Контейнер unordered_multiset. Контейнер, хранящий ключи. Допустимо несколько элементов на ключ. Page 559/1103 Контейнер unordered_set. Контейнер, хранящий ключи. Допустим только один элемент на ключ. Неупорядоченный контейнер (unordered container). Ассоциативные контейнеры, использующие хеширование, а не сравнение ключей для хранения и доступа к элементам. Эффективность этих контейнеров зависит от качества хеш-функции. Оператор *. Оператор обращения к значению, примененный к итератору контейнера map, set, multimap или multiset, возвращает объект типа value_type. Обратите внимание на то, что типом value_type контейнера map и multimap является пара (pair). Оператор []. Оператор индексирования, примененный к контейнеру map, получает индекс, типом которого должен быть key_type (или тип, допускающий преобразование в него). Возвращает значение типа mapped_type. Строгое сравнение (strict weak ordering). Отношения между ключами ассоциативного контейнера. При строгом сравнении можно сравнить два любых значения и выяснить, которое из них меньше. Если ни одно из значений не меньше другого, они считаются равными. Тип key_type. Тип, определенный в шаблоне ассоциативного контейнера, которому соответствует тип ключей, используемых для сохранения и возвращения значения. У контейнера map тип key_type используется для индексации. У контейнера set типы key_type и value_type совпадают. Тип mapped_type. Тип, определенный в шаблонах ассоциативных контейнеров map и multimap, которому соответствует тип хранимых значений. Тип pair (пара). Тип, объект которого содержит две открытые переменные-члена по имени first (первый) и second (второй). Тип pair является шаблоном, при создании класса которого указывают два типа: тип первого и тип второго элемента. Тип value_type. Тип элемента, хранимого в контейнере. У контейнеров set и multiset типы value_type и key_type совпадают. У контейнеров map и multimap этот тип представляет собой пару, первый элемент которой (first) имеет тип const key_type, а второй (second) — тип mapped_type. Хеш (hash). Специальный библиотечный шаблон, который используют неупорядоченные контейнеры для управления позицией элементов. Хеш-функция (hash function). Функция, сопоставляющая значения заданного типа с целочисленными значениями (size_t). Равные значения должны сопоставляться с равными целыми числами; неравные значения должны сопоставляться с неравными целым числами, если это возможно. Глава 12 Динамическая память Написанные до сих пор программы использовали объекты, имевшие четко определенную продолжительность существования. Глобальные объекты создаются при запуске программы и освобождаются по завершении выполнения программы. Локальные автоматические объекты создаются при входе в блок, где они определены, и удаляются при выходе из него. Статические локальные объекты создаются перед их первым использованием и удаляются по Page 560/1103 завершении программы. В дополнение к автоматическим и статическим объектам язык С++ позволяет создавать объекты динамически. Продолжительность существования объектов, созданных динамически, не зависит от того, где они созданы; они существуют, пока не будут освобождены явно. Процесс освобождения динамических объектов оказывается удивительно богатым источником ошибок. Чтобы сделать использование динамических объектов безопасней, библиотека определяет два типа интеллектуальных указателей, управляющих динамическим созданием объектов. Интеллектуальные указатели гарантируют, что объекты, на которые они указывают, будут автоматически освобождены в соответствующий момент. До сих пор наши программы использовали только статические объекты или объекты, располагаемые в стеке. Статическая память используется для локальных статических переменных (см. раздел 6.1.1), для статических переменных-членов классов (см. раздел 7.6), а также для переменных, определенных вне функций. Стек используется для нестатических объектов, определенных в функциях. Объекты, расположенные в статической памяти или в стеке, автоматически создаются и удаляются компилятором. Объекты из стека существуют, только пока выполняется блок, в котором они определены; статические объекты создаются прежде, чем они будут использованы, и удаляются по завершении программы. Кроме статической памяти и стека, у каждой программы есть также пул памяти, которую она может использовать. Это динамическая память (free store) или распределяемая память (heap). Программы используют распределяемую память для объектов, называемых динамически созданными объектами (dynamically allocated object), место для которых программа резервирует во время выполнения. Программа сама контролирует продолжительность существования динамических объектов; наш код должен явно освобождать такие объекты, когда они больше не нужны. Хотя динамическая память иногда необходима, ее корректное освобождение зачастую довольно сложно. 12.1. Динамическая память и интеллектуальные указатели Для управления динамической памятью в языке С++ используются два оператора: оператор new, который резервирует (а при необходимости и инициализирует) объект в динамической памяти и возвращает указатель на него; и оператор delete, который получает указатель на динамический объект и удаляет его, освобождая зарезервированную память. Работа с динамической памятью проблематична, поскольку на удивление сложно гарантировать освобождение памяти в нужный момент. Если забыть освобождать память, то появится утечка памяти, если освободить область памяти слишком рано, пока еще есть указатели на нее, то получится указатель на не существующую более область памяти. Page 561/1103 Чтобы сделать использование динамической памяти проще (и безопасный), новая библиотека предоставляет два типа интеллектуальных указателей (smart pointer) для управления динамическими объектами. Интеллектуальный указатель действует, как обычный указатель, но с важным дополнением: автоматически удаляет объект, на который он указывает. Новая библиотека определяет два вида интеллектуальных указателей, отличающихся способом управления своими базовыми указателями: указатель shared_ptr позволяет нескольким указателям указывать на тот же объект, а указатель unique_ptr — нет. Библиотека определяет также сопутствующий класс weak_ptr, являющийся второстепенной ссылкой на объект, управляемый указателем shared_ptr. Все три класса определены в заголовке memory. 12.1.1. Класс shared_ptr Подобно векторам, интеллектуальные указатели являются шаблонами (см. раздел 3.3). Поэтому при создании интеллектуального указателя следует предоставить дополнительную информацию — в данном случае тип, на который способен указывать указатель. Подобно векторам, этот тип указывают в угловых скобках, следующих за именем типа определяемого интеллектуального указателя: shared_ptr<string> p1; // shared_ptr может указывать на строку shared_ptr<list<int>> p2; // shared_ptr может указывать на // список целых чисел Инициализированный по умолчанию интеллектуальный указатель хранит нулевой указатель (см. раздел 2.3.2). Дополнительные способы инициализации интеллектуального указателя рассматриваются в разделе 12.1.3. Интеллектуальный указатель используется теми же способами, что и обычный указатель. Обращение к значению интеллектуального указателя возвращает объект, на который он указывает. Когда интеллектуальный указатель используется в условии, результат проверки может засвидетельствовать, не является ли он нулевым: // если указатель p1 не нулевой и не указывает на пустую строку if (p1 && p1->empty()) *p1 = "hi"; // обратиться к значению p1, чтобы присвоить ему // новое значение строки Page 562/1103 Список общих функций указателей shared_ptr и unique_ptr приведен в табл. 12.1. Функции, специфические для указателя shared_ptr, перечислены в табл. 12.2. Таблица 12.1. Функции, общие для указателей shared_ptr и unique_ptr shared_ptr<T> sp unique_ptr<T> up Нулевой интеллектуальный указатель, способный указывать на объекты типа Т p При использовании указателя p в условии возвращается значение true, если он указывает на объект *p Обращение к значению указателя p возвращает объект, на который он указывает p->mem Синоним для (*p).mem p.get() Возвращает указатель, хранимый указателем p. Используйте его осторожно, поскольку объект, на который он указывает, может прекратить существование после удаления его интеллектуальным указателем swap(p, q) p.swap(q) Обменивает указатели в p и q Таблица 12.2. Функции, специфические для указателя shared_ptr make_shared<T>( args ) Возвращает указатель shared_ptr на динамически созданный объект типа Т. Аргументы args используются для инициализации создаваемого объекта shared_ptr<T> p(q) p — копия shared_ptr q; инкремент счетчика q. Тип содержащегося в q указателя должен быть приводим к типу Т* (см. раздел 4.11.2) p = q p и q — указатели shared_ptr, содержащие указатели, допускающие приведение друг к другу. Происходит декремент счетчика ссылок p и инкремент счетчика q; если счетчик указателя p достиг 0, память его объекта освобождается p.unique() Возвращает true, если p.use_count() равно единице, и значение false в противном случае p.use_count() Возвращает количество объектов, совместно использующих указатель p; может выполняться очень медленно, предназначена прежде всего для отладки Функция make_shared() Наиболее безопасный способ резервирования и использования динамической памяти подразумевает вызов библиотечной функции make_shared(). Она резервирует и инициализирует объект в динамической памяти, возвращая указатель типа shared_ptr на этот объект. Как и типы интеллектуальных указателей, функция make_shared() определена в заголовке memory. При вызове функции make_shared() следует указать тип создаваемого объекта. Это подобно использованию шаблона класса — за именем функции следует указание типа в угловых скобках: // указатель shared_ptr на объект типа int со значением 42 shared_ptr<int> p3 = make_shared<int>(42); // р4 указывает на строку со значением '9999999999' shared_ptr<string> р4 = make_shared<string>(10, '9'); // р5 указывает на объект типа int со значением по // Page 563/1103 умолчанию (p. 3.3.1) 0 shared_ptr<int> р5 = make_shared<int>(); Подобно функции-члену emplace() последовательного контейнера (см. раздел 9.3.1), функция make_shared() использует свои аргументы для создания объекта заданного типа. Например, при вызове функции make_shared<string>() следует передать аргумент (аргументы), соответствующий одному из конструкторов типа string. Вызову функции make_shared<int>() можно передать любое значение, которое можно использовать для инициализации переменной типа int, и т.д. Если не передать аргументы, то объект инициализируется значением по умолчанию (см. раздел 3.3.1). Для облегчения определения объекта, содержащего результат вызова функции make_shared(), обычно используют ключевое слово auto (см. раздел 2.5.2): // p6 указывает на динамически созданный пустой вектор vector<string> auto p6 = make_shared<vector<string>>(); Копирование и присвоение указателей shared_ptr При копировании и присвоении указателей shared_ptr каждый из них отслеживает количество других указателей shared_ptr на тот же объект: auto p = make_shared<int>(42); // объект, на который указывает p // имеет только одного владельца auto q(p); // p и q указывают на тот же объект // объект, на который указывают p и q, имеет двух владельцев С указателем shared_ptr связан счетчик, обычно называемый счетчиком ссылок (reference count). При копировании указателя shared_ptr значение счетчика увеличивается. Например, значение связанного с указателем shared_ptr счетчика увеличивается, когда он используется для инициализации другого указателя shared_ptr, а также при использовании его в качестве правого операнда присвоения, или при передаче его функции (см. раздел 6.2.1), или при возвращении из функции по значению (см. раздел 6.3.2). Значение счетчика увеличивается при присвоении нового значения указателю shared_ptr, а когда он удаляется или когда локальный указатель shared_ptr выходит из области видимости (см. раздел 6.1.1), значение счетчика уменьшается. Как только счетчик указателя shared_ptr достигает нуля, он автоматически освобождает объект, на который указывает: auto r = make_shared<int>(42); // объект int, на который указывает r, Page 564/1103 // имеет одного владельца r = q; // присвоение r переводит этот указатель на другой адрес // приращение счетчика владельцев объекта, на который указывает q // уменьшение счетчика владельцев объекта, на который указывает r // объект, на который указывал r, не имеет более владельцев; // он освобождается автоматически Здесь резервируется переменная типа int, а ее адрес сохраняется в указателе r. Затем указателю r присваивается новое значение. В данном случае r — единственный указатель типа shared_ptr, указывающий на этот объект. В результате присвоения r = q переменная int автоматически освобождается. Будет ли использован счетчик или другая структура данных для отслеживания количества указателей на совместно используемый объект, зависит от реализации компилятора. Главное то, что класс отслеживает количество указателей shared_ptr на тот же объект и автоматически освобождает его в подходящий момент. Указатель shared_ptr автоматически удаляет свои объекты… Когда последний указатель shared_ptr на объект удаляется, его класс автоматически удаляет объект, на который он указывает. Для этого используется другая специальная функция-член — деструктор (destructor), аналогичная конструкторам, которые есть у каждого класса. Подобно тому, как конструктор контролирует инициализацию, деструктор контролирует происходящее при удалении объектов этого типа. Деструкторы обычно освобождают ресурсы, зарезервированные объектом. Например, конструкторы класса string (как и другие его члены) резервируют память для содержания составляющих ее символов. Деструктор класса string освобождает эту память. Точно так же некоторые функции класса vector резервируют память для хранения элементов вектора. Деструктор класса vector удаляет эти элементы и освобождает используемую ими память. Деструктор указателя shared_ptr осуществляет декремент счетчика ссылок объекта, на который он указывает. Когда счетчик достигает нуля, деструктор указателя shared_ptr удаляет объект, на который он указывает, и освобождает используемую им память. …и автоматически освобождает их память Тот факт, что класс shared_ptr автоматически освобождает динамические объекты, когда они больше не нужны, существенно облегчает использование динамической памяти. Рассмотрим, например, функцию, которая возвращает указатель shared_ptr на динамически созданный Page 565/1103 объект типа Foo, который может быть инициализирован аргументом типа Т: // функция factory() возвращает указатель shared_ptr на динамически // созданный объект shared_ptr<Foo> factory(Т arg) { // обработать аргумент соответствующим образом // shared_ptr позаботится об освобождении этой памяти return make_shared<Foo>(arg); } Функция factory() возвращает указатель shared_ptr, гарантирующий удаление созданного ею объекта в подходящий момент. Например, следующая функция сохраняет указатель shared_ptr, возвращенный функцией factory(), в локальной переменной: void use_factory(Т arg) { shared_ptr<Foo> p = factory(arg); // использует p } // p выходит из области видимости; память, на которую он указывал, // освобождается автоматически Поскольку указатель p является локальным для функции use_factory(), он удаляется по ее завершении (см. раздел 6.1.1). Когда указатель p удаляется, осуществляется декремент его счетчика ссылок и проверка. В данном случае p — единственный указатель на объект в памяти, возвращенный функцией factory(). Поскольку указатель p выходит из области видимости, объект, на который он указывает, удаляется, а память, в которой он располагался, освобождается. Память не будет освобождена, если на нее будет указывать любой другой указатель типа shared_ptr: shared_ptr<Foo> use_factory(Т arg) { shared_ptr<Foo> p = factory(arg); // Page 566/1103 использует p return p; // при возвращении p счетчик ссылок увеличивается } // p выходит из области видимости; память, на которую он указывал, // не освобождается В этой версии функции use_factory() оператор return возвращает вызывающей стороне (см. раздел 6.3.2) копию указателя p. Копирование указателя shared_ptr добавляет единицу к счетчику ссылок этого объекта. Теперь, когда указатель p удаляется, останется другой владелец области памяти, на которую указывал указатель p. Класс shared_ptr гарантирует, что пока есть хоть один указатель shared_ptr на данную область памяти, она не будет освобождена. Поскольку память не освобождается, пока не удаляется последний указатель shared_ptr, важно гарантировать, что ни одного указателя shared_ptr не остается после того, как необходимость в них отпадет. Если не удалить ненужный указатель shared_ptr, программа будет выполнятся правильно, но может впустую тратить память. Одна из возможностей оставить указатели shared_ptr после употребления — поместить их в контейнер, а затем переупорядочить его так, чтобы эти элементы оказались не нужны. Поэтому важно гарантировать удаление элементов с указателями shared_ptr, как только они больше не нужны. Если указатели shared_ptr помещаются в контейнер, но впоследствии будут использованы лишь некоторые из них, а не все, то следует не забыть самостоятельно удалить остальные элементы. Классы, ресурсы которых имеют динамическую продолжительность существования Обычно динамическую память используют в следующих случаях. 1. Неизвестно необходимое количество объектов. 2. Неизвестен точный тип необходимых объектов. 3. Нельзя разрешать совместное использование данных несколькими объектами. Классы контейнеров — хороший пример классов, использующих динамическую память, как в первом случае. Примеры второго рассматриваются в главе 15. В данном разделе определяется класс, использующий динамическую память для того, чтобы позволить нескольким объектам совместно использовать те же данные. Использованные до сих пор классы резервировали ресурсы, которые существовали, только пока существовал объект. Например, каждому вектору принадлежат его собственные элементы. При копировании вектора элементы исходного вектора копировались в независимые элементы другого: vector<string> v1; // пустой вектор Page 567/1103 { // новая область видимости vector<string> v2 = {"a", "an", "the"}; v1 = v2; // копирует элементы из v2 в v1 } // v2 удаляется, что удаляет элементы v2 // v1 содержит три элемента, являющихся копиями элементов v2 Элементы вектора существуют, только пока существует сам вектор. Когда вектор удаляется, удаляются и его элементы. Некоторые классы резервируют ресурсы, продолжительность существования которых не зависит от первоначального объекта. Например, необходимо определить класс Blob, содержащий коллекцию элементов. В отличие от контейнеров, объекты класса Blob должны быть копиями друг друга и совместно использовать те же элементы. Таким образом, при копировании объекта класса Blob элементы копии должны ссылаться на те же элементы, что и оригинал. Обычно, когда два объекта совместно используют те же данные, они не удаляются при удалении одного из объектов: Blob<string> b1; // пустой Blob { // новая область видимости Blob<string> b2 = {"a", "an", "the"}; b1 = b2; // b1 и b2 совместно используют те же элементы } // b2 удаляется, но элементы b2 нет // b1 указывает на элементы, первоначально созданные в b2 В этом примере объекты b1 и b2 совместно используют те же элементы. Когда объект b2 выходит из области видимости, эти элементы должны остаться, поскольку объект b1 все еще использует их. Основная причина использования динамической памяти в том, чтобы позволить нескольким объектам совместно использовать те же данные. Определение класса StrBlob Page 568/1103 В конечном счете класс Blob будет реализован как шаблон, но это только в разделе 16.1.2, а пока определим его версию, способную манипулировать только строками. Поэтому назовем данную версию этого класса StrBlob. Простейший способ реализации нового типа коллекции подразумевает использование одного из библиотечных контейнеров. Это позволит библиотечному типу управлять собственно хранением элементов. В данном случае для хранения элементов будет использован класс vector. Однако сам вектор не может храниться непосредственно в объекте Blob. Члены объекта удаляются при удалении самого объекта. Предположим, например, что объекты b1 и b2 класса Blob совместно используют тот же вектор. Если бы вектор хранился в одном из этих объектов, скажем в b2, то, как только объект b2 выйдет из области видимости, элементы вектора перестанут существовать. Чтобы гарантировать продолжение существования элементов, будем хранить вектор в динамической памяти. Для реализации совместного использования снабдим каждый объект класса StrBlob указателем shared_ptr на вектор в динамической памяти. Указатель-член shared_ptr будет следить за количеством объектов класса StrBlob, совместно использующих тот же самый вектор, и удалит его, когда будет удален последний объект класса StrBlob. Осталось решить, какие функции будет предоставлять создаваемый класс. Реализуем пока небольшое подмножество функций вектора. Изменим также функции обращения к элементам (включая front() и back()): в данном классе при попытке доступа к не существующим элементам они будут передавать исключения. У класса будет стандартный конструктор и конструктор с параметром типа initializer_list<string> (см. раздел 6.2.6). Этот конструктор будет получать список инициализаторов в скобках. class StrBlob { public: typedef std::vector<std::string>::size_type size_type; StrBlob(); StrBlob(std::initializer_list<std::string> il); size_type size() const { return data->size(); } bool empty() const { return data->empty(); } // добавление и удаление элементов void push_back(const std::string &t) {data->push_back(t);} void pop_back(); // доступ к элементам std::string& front(); Page 569/1103 std::string& back(); private: std::shared_ptr<std::vector<std::string>> data; // передать сообщение при недопустимости data[i] void check(size_type i, const std::string &msg) const; }; В классе будут реализованы функции-члены size(), empty() и push_back(), которые передают свою работу через указатель data внутреннему вектору. Например, функция size() класса StrBlob вызывает функцию data->size() и т.д. Конструкторы класса StrBlob Для инициализации своей переменной-члена data указателем на динамически созданный вектор каждый конструктор использует собственный список инициализации (см. раздел 7.1.4). Стандартный конструктор резервирует пустой вектор: StrBlob::StrBlob(): data(make_shared<vector<string>>()) { } StrBlob::StrBlob(initializer_list<string> il): data(make_shared<vector<string>>(il)) { } Конструктор, получающий тип initializer_list, передает свой параметр для соответствующего конструктора класса vector (см. раздел 2.2.1). Этот конструктор инициализирует элементы вектора копиями значений из списка. Функции-члены доступа к элементам Функции pop_back(), front() и back() обращаются к соответствующим функциям-членам вектора. Эти функции должны проверять существование элементов прежде, чем попытаться получить доступ к ним. Поскольку несколько функций-членов должны осуществлять ту же проверку, снабдим класс закрытой вспомогательной функцией check(), проверяющей принадлежность заданного индекса диапазону. Кроме индекса, функция check() получает аргумент типа string, передаваемый обработчику исключений. Строка описывает то, что пошло не так, как надо: void StrBlob::check(size_type i, const string &msg) const { if (i >= data->size()) throw out_of_range(msg); } Функция pop_back() и функции-члены доступа к элементам сначала вызывают функцию check(). Если проверка успешна, эти функции-члены передают свою работу соответствующим функциям вектора: strings StrBlob::front() { // если вектор пуст, функция check() передаст следующее Page 570/1103 check(0, "front on empty StrBlob"); return data->front(); } strings StrBlob::back() { check(0, "back on empty StrBlob"); return data->back(); } void StrBlob::pop_back() { check(0, "pop_back on empty StrBlob"); data->pop_back(); } Функции-члены front() и back() должны быть перегружены для констант (см. раздел 7.3.2). Определение этих версий остается в качестве самостоятельного упражнения. Копирование, присвоение и удаление объектов класса StrBlob Подобно классу Sales_data, класс StrBlob использует стандартные версии функций копирования, присвоения и удаления объектов (см. раздел 7.1.5). По умолчанию эти функции копируют, присваивают и удаляют переменные-члены класса. У класса StrBlob есть только одна переменная-член — указатель shared_ptr. Поэтому при копировании, присвоении и удалении объекта класса StrBlob его переменная-член shared_ptr будет скопирована, присвоена или удалена. Как уже упоминалось выше, копирование указателя shared_ptr приводит к инкременту его счетчика ссылок; присвоение одного указателя shared_ptr другому приводит к инкременту счетчика правого операнда и декременту счетчика левого; удаление указателя shared_ptr приводит к декременту его счетчика. Если значение счетчика указателя shared_ptr доходит до нуля, объект, на который он указывает, удаляется автоматически. Таким образом, вектор, созданный конструкторами класса StrBlob, будет автоматически удален при удалении последнего объекта класса StrBlob, указывающего на этот вектор. Упражнения раздела 12.1.1 |