- •Предисловие
- •Структура книги
- •Благодарности
- •1. Начинаем
- •1.1. Решение задачи
- •1.2. Программа на языке C++
- •1.2.1. Порядок выполнения инструкций
- •1.3. Директивы препроцессора
- •1.4. Немного о комментариях
- •1.5. Первый взгляд на ввод/вывод
- •1.5.1. Файловый ввод/вывод
- •2. Краткий обзор С++
- •2.1. Встроенный тип данных “массив”
- •2.2. Динамическое выделение памяти и указатели
- •2.3. Объектный подход
- •2.4. Объектно-ориентированный подход
- •2.5. Использование шаблонов
- •2.7. Использование пространства имен
- •2.8. Стандартный массив – это вектор
- •Часть II
- •3. Типы данных С++
- •3.1. Литералы
- •3.2. Переменные
- •3.2.1. Что такое переменная
- •3.2.2. Имя переменной
- •3.2.3. Определение объекта
- •3.3. Указатели
- •3.4. Строковые типы
- •3.4.1. Встроенный строковый тип
- •3.4.2. Класс string
- •3.5. Спецификатор const
- •3.6. Ссылочный тип
- •3.7. Тип bool
- •3.8. Перечисления
- •3.9. Тип “массив”
- •3.9.1. Многомерные массивы
- •3.9.2. Взаимосвязь массивов и указателей
- •3.10. Класс vector
- •3.11. Класс complex
- •3.12. Директива typedef
- •3.14. Класс pair
- •3.15. Типы классов
- •4. Выражения
- •4.2. Арифметические операции
- •4.3. Операции сравнения и логические операции
- •4.4. Операции присваивания
- •4.5. Операции инкремента и декремента
- •4.6. Операции с комплексными числами
- •4.7. Условное выражение
- •4.8. Оператор sizeof
- •4.9. Операторы new и delete
- •4.10. Оператор “запятая”
- •4.11. Побитовые операторы
- •4.12. Класс bitset
- •4.13. Приоритеты
- •4.14. Преобразования типов
- •4.1. Что такое выражение?
- •4.14.1. Неявное преобразование типов
- •4.14.2. Арифметические преобразования типов
- •4.14.3. Явное преобразование типов
- •4.14.4. Устаревшая форма явного преобразования
- •4.15. Пример: реализация класса Stack
- •5. Инструкции
- •5.1. Простые и составные инструкции
- •5.2. Инструкции объявления
- •5.3. Инструкция if
- •5.4. Инструкция switch
- •5.5. Инструкция цикла for
- •5.6. Инструкция while
- •5.8. Инструкция do while
- •5.8. Инструкция break
- •5.9. Инструкция continue
- •5.10. Инструкция goto
- •5.11. Пример связанного списка
- •5.11.1. Обобщенный список
- •6. Абстрактные контейнерные типы
- •6.1. Система текстового поиска
- •6.2. Вектор или список?
- •6.3. Как растет вектор?
- •6.4. Как определить последовательный контейнер?
- •6.5. Итераторы
- •6.6. Операции с последовательными контейнерами
- •6.6.1. Удаление
- •6.6.2. Присваивание и обмен
- •6.6.3. Обобщенные алгоритмы
- •6.7. Читаем текстовый файл
- •6.8. Выделяем слова в строке
- •6.9. Обрабатываем знаки препинания
- •6.10. Приводим слова к стандартной форме
- •6.11. Дополнительные операции со строками
- •6.12. Строим отображение позиций слов
- •6.12.2. Поиск и извлечение элемента отображения
- •6.12.3. Навигация по элементам отображения
- •6.12.4. Словарь
- •6.12.5. Удаление элементов map
- •6.13. Построение набора стоп-слов
- •6.13.2. Поиск элемента
- •6.13.3. Навигация по множеству
- •6.14. Окончательная программа
- •6.15. Контейнеры multimap и multiset
- •6.16. Стек
- •6.17. Очередь и очередь с приоритетами
- •6.18. Вернемся в классу iStack
- •Часть III
- •7. Функции
- •7.1. Введение
- •7.2. Прототип функции
- •7.2.1. Тип возвращаемого функцией значения
- •7.2.2. Список параметров функции
- •7.2.3. Проверка типов формальных параметров
- •7.3. Передача аргументов
- •7.3.1. Параметры-ссылки
- •7.3.2. Параметры-ссылки и параметры-указатели
- •7.3.3. Параметры-массивы
- •7.3.5. Значения параметров по умолчанию
- •7.3.6. Многоточие
- •7.4. Возврат значения
- •7.5. Рекурсия
- •7.6. Встроенные функции
- •7.7. Директива связывания extern "C" A
- •7.8.1. Класс для обработки параметров командной строки
- •7.9. Указатели на функции
- •7.9.1. Тип указателя на функцию
- •7.9.2. Инициализация и присваивание
- •7.9.3. Вызов
- •7.9.4. Массивы указателей на функции
- •7.9.5. Параметры и тип возврата
- •7.9.6. Указатели на функции, объявленные как extern "C"
- •8. Область видимости и время жизни
- •8.1. Область видимости
- •8.1.1. Локальная область видимости
- •8.2. Глобальные объекты и функции
- •8.2.1. Объявления и определения
- •8.2.2. Сопоставление объявлений в разных файлах
- •8.2.3. Несколько слов о заголовочных файлах
- •8.3. Локальные объекты
- •8.3.1. Автоматические объекты
- •8.3.2. Регистровые автоматические объекты
- •8.3.3. Статические локальные объекты
- •8.4. Динамически размещаемые объекты
- •8.4.2. Шаблон auto_ptr А
- •8.4.3. Динамическое создание и уничтожение массивов
- •8.4.5. Оператор размещения new А
- •8.5. Определения пространства имен А
- •8.5.1. Определения пространства имен
- •8.5.2. Оператор разрешения области видимости
- •8.5.3. Вложенные пространства имен
- •8.5.4. Определение члена пространства имен
- •8.5.5. ПОО и члены пространства имен
- •8.5.6. Безымянные пространства имен
- •8.6. Использование членов пространства имен А
- •8.6.1. Псевдонимы пространства имен
- •8.6.2. Using-объявления
- •8.6.3. Using-директивы
- •8.6.4. Стандартное пространство имен std
- •9. Перегруженные функции
- •9.1. Объявления перегруженных функций
- •9.1.1. Зачем нужно перегружать имя функции
- •9.1.2. Как перегрузить имя функции
- •9.1.3. Когда не надо перегружать имя функции
- •9.1.4. Перегрузка и область видимости A
- •9.1.5. Директива extern "C" и перегруженные функции A
- •9.1.6. Указатели на перегруженные функции A
- •9.1.7. Безопасное связывание A
- •9.2. Три шага разрешения перегрузки
- •9.3. Преобразования типов аргументов A
- •9.3.1. Подробнее о точном соответствии
- •9.3.3. Подробнее о стандартном преобразовании
- •9.3.4. Ссылки
- •9.4. Детали разрешения перегрузки функций
- •9.4.1. Функции-кандидаты
- •9.4.2. Устоявшие функции
- •9.4.3. Наилучшая из устоявших функция
- •9.4.4. Аргументы со значениями по умолчанию
- •10. Шаблоны функций
- •10.1. Определение шаблона функции
- •10.2. Конкретизация шаблона функции
- •10.3. Вывод аргументов шаблона А
- •10.4. Явное задание аргументов шаблона A
- •10.5. Модели компиляции шаблонов А
- •10.5.1. Модель компиляции с включением
- •10.5.2. Модель компиляции с разделением
- •10.5.3. Явные объявления конкретизации
- •10.6. Явная специализация шаблона А
- •10.7. Перегрузка шаблонов функций А
- •10.8. Разрешение перегрузки при конкретизации A
- •10.9. Разрешение имен в определениях шаблонов А
- •10.10. Пространства имен и шаблоны функций А
- •10.11. Пример шаблона функции
- •11. Обработка исключений
- •11.1. Возбуждение исключения
- •11.2. try-блок
- •11.3. Перехват исключений
- •11.3.1. Объекты-исключения
- •11.3.2. Раскрутка стека
- •11.3.3. Повторное возбуждение исключения
- •11.3.4. Перехват всех исключений
- •11.4. Спецификации исключений
- •11.4.1. Спецификации исключений и указатели на функции
- •11.5. Исключения и вопросы проектирования
- •12. Обобщенные алгоритмы
- •12.1. Краткий обзор
- •12.2. Использование обобщенных алгоритмов
- •12.3. Объекты-функции
- •12.3.1. Предопределенные объекты-функции
- •12.3.2. Арифметические объекты-функции
- •12.3.3. Сравнительные объекты-функции
- •12.3.4. Логические объекты-функции
- •12.3.5. Адаптеры функций для объектов-функций
- •12.3.6. Реализация объекта-функции
- •12.4. Еще раз об итераторах
- •12.4.1. Итераторы вставки
- •12.4.2. Обратные итераторы
- •12.4.3. Потоковые итераторы
- •12.4.4. Итератор istream_iterator
- •12.4.5. Итератор ostream_iterator
- •12.4.6. Пять категорий итераторов
- •12.5. Обобщенные алгоритмы
- •12.5.1. Алгоритмы поиска
- •12.5.2. Алгоритмы сортировки и упорядочения
- •12.5.3. Алгоритмы удаления и подстановки
- •12.5.4. Алгоритмы перестановки
- •12.5.5. Численные алгоритмы
- •12.5.6. Алгоритмы генерирования и модификации
- •12.5.7. Алгоритмы сравнения
- •12.5.8. Алгоритмы работы с множествами
- •12.5.9. Алгоритмы работы с хипом
- •12.6.1. Операция list_merge()
- •12.6.2. Операция list::remove()
- •12.6.3. Операция list::remove_if()
- •12.6.4. Операция list::reverse()
- •12.6.5. Операция list::sort()
- •12.6.6. Операция list::splice()
- •12.6.7. Операция list::unique()
- •Часть IV
- •13. Классы
- •13.1. Определение класса
- •13.1.1. Данные-члены
- •13.1.2. Функции-члены
- •13.1.3. Доступ к членам
- •13.1.4. Друзья
- •13.1.5. Объявление и определение класса
- •13.2. Объекты классов
- •13.3. Функции-члены класса
- •13.3.1. Когда использовать встроенные функции-члены
- •13.3.2. Доступ к членам класса
- •13.3.3. Закрытые и открытые функции-члены
- •13.3.4. Специальные функции-члены
- •13.3.5. Функции-члены со спецификаторами const и volatile
- •13.3.6. Объявление mutable
- •13.4. Неявный указатель this
- •13.4.1. Когда использовать указатель this
- •13.5. Статические члены класса
- •13.5.1. Статические функции-члены
- •13.6. Указатель на член класса
- •13.6.1. Тип члена класса
- •13.6.2. Работа с указателями на члены класса
- •13.6.3. Указатели на статические члены класса
- •13.7. Объединение – класс, экономящий память
- •13.8. Битовое поле – член, экономящий память
- •13.9. Область видимости класса A
- •13.9.1. Разрешение имен в области видимости класса
- •13.10. Вложенные классы A
- •13.11. Классы как члены пространства имен A
- •13.12. Локальные классы A
- •14.1. Инициализация класса
- •14.2. Конструктор класса
- •14.2.1. Конструктор по умолчанию
- •14.2.2. Ограничение прав на создание объекта
- •14.2.3. Копирующий конструктор
- •14.3. Деструктор класса
- •14.3.1. Явный вызов деструктора
- •14.3.2. Опасность увеличения размера программы
- •14.4. Массивы и векторы объектов
- •14.4.1. Инициализация массива, распределенного из хипа A
- •14.4.2. Вектор объектов
- •14.5. Список инициализации членов
- •14.6. Почленная инициализация A
- •14.6.1. Инициализация члена, являющегося объектом класса
- •14.7. Почленное присваивание A
- •14.8. Соображения эффективности A
- •15.1. Перегрузка операторов
- •15.1.1. Члены и не члены класса
- •15.1.2. Имена перегруженных операторов
- •15.1.3. Разработка перегруженных операторов
- •15.2. Друзья
- •15.3. Оператор =
- •15.4. Оператор взятия индекса
- •15.5. Оператор вызова функции
- •15.6. Оператор “стрелка”
- •15.7. Операторы инкремента и декремента
- •15.8. Операторы new и delete
- •15.8.1. Операторы new[ ] и delete [ ]
- •15.8.2. Оператор размещения new() и оператор delete()
- •15.9. Определенные пользователем преобразования
- •15.9.1. Конвертеры
- •15.9.2. Конструктор как конвертер
- •15.10. Выбор преобразования A
- •15.10.1. Еще раз о разрешении перегрузки функций
- •15.10.2. Функции-кандидаты
- •15.11. Разрешение перегрузки и функции-члены A
- •15.11.1. Объявления перегруженных функций-членов
- •15.11.2. Функции-кандидаты
- •15.11.3. Устоявшие функции
- •15.12. Разрешение перегрузки и операторы A
- •15.12.1. Операторные функции-кандидаты
- •15.12.2. Устоявшие функции
- •15.12.3. Неоднозначность
- •16. Шаблоны классов
- •16.1. Определение шаблона класса
- •16.1.1. Определения шаблонов классов Queue и QueueItem
- •16.2. Конкретизация шаблона класса
- •16.2.1. Аргументы шаблона для параметров-констант
- •16.3. Функции-члены шаблонов классов
- •16.3.1. Функции-члены шаблонов Queue и QueueItem
- •16.4. Объявления друзей в шаблонах классов
- •16.4.1. Объявления друзей в шаблонах Queue и QueueItem
- •16.5. Статические члены шаблонов класса
- •16.6. Вложенные типы шаблонов классов
- •16.7. Шаблоны-члены
- •16.8. Шаблоны классов и модель компиляции A
- •16.8.1. Модель компиляции с включением
- •16.8.2. Модель компиляции с разделением
- •16.8.3. Явные объявления конкретизации
- •16.9. Специализации шаблонов классов A
- •16.10. Частичные специализации шаблонов классов A
- •16.11. Разрешение имен в шаблонах классов A
- •16.12. Пространства имен и шаблоны классов
- •16.13. Шаблон класса Array
- •Часть V
- •17. Наследование и подтипизация классов
- •17.1. Определение иерархии классов
- •17.1.1. Объектно-ориентированное проектирование
- •17.2. Идентификация членов иерархии
- •17.2.1. Определение базового класса
- •17.2.2. Определение производных классов
- •17.2.3. Резюме
- •17.3. Доступ к членам базового класса
- •17.4. Конструирование базового и производного классов
- •17.4.1. Конструктор базового класса
- •17.4.2. Конструктор производного класса
- •17.4.3. Альтернативная иерархия классов
- •17.4.4. Отложенное обнаружение ошибок
- •17.4.5. Деструкторы
- •17.5.1. Виртуальный ввод/вывод
- •17.5.2. Чисто виртуальные функции
- •17.5.3. Статический вызов виртуальной функции
- •17.5.4. Виртуальные функции и аргументы по умолчанию
- •17.5.5. Виртуальные деструкторы
- •17.5.6. Виртуальная функция eval()
- •17.5.7. Почти виртуальный оператор new
- •17.5.8. Виртуальные функции, конструкторы и деструкторы
- •17.6. Почленная инициализация и присваивание A
- •17.7. Управляющий класс UserQuery
- •17.7.1. Определение класса UserQuery
- •17.8. Соберем все вместе
- •18.1. Готовим сцену
- •18.2. Множественное наследование
- •18.3. Открытое, закрытое и защищенное наследование
- •18.3.1. Наследование и композиция
- •18.3.2. Открытие отдельных членов
- •18.3.3. Защищенное наследование
- •18.3.4. Композиция объектов
- •18.4. Область видимости класса и наследование
- •18.5. Виртуальное наследование A
- •18.5.1. Объявление виртуального базового класса
- •18.5.2. Специальная семантика инициализации
- •18.5.3. Порядок вызова конструкторов и деструкторов
- •18.5.4. Видимость членов виртуального базового класса
- •18.6.2. Порождение класса отсортированного массива
- •18.6.3. Класс массива с множественным наследованием
- •19. Применение наследования в C++
- •19.1. Идентификация типов во время выполнения
- •19.1.1. Оператор dynamic_cast
- •19.1.2. Оператор typeid
- •19.1.3. Класс type_info
- •19.2. Исключения и наследование
- •19.2.1. Исключения, определенные как иерархии классов
- •19.2.2. Возбуждение исключения типа класса
- •19.2.3. Обработка исключения типа класса
- •19.2.4. Объекты-исключения и виртуальные функции
- •19.2.5. Раскрутка стека и вызов деструкторов
- •19.2.6. Спецификации исключений
- •19.2.7. Конструкторы и функциональные try-блоки
- •19.3. Разрешение перегрузки и наследование A
- •19.3.1. Функции-кандидаты
- •19.3.3. Наилучшая из устоявших функций
- •20. Библиотека iostream
- •20.1. Оператор вывода <<
- •20.2. Ввод
- •20.2.1. Строковый ввод
- •20.3. Дополнительные операторы ввода/вывода
- •20.4. Перегрузка оператора вывода
- •20.5. Перегрузка оператора ввода
- •20.6. Файловый ввод/вывод
- •20.7. Состояния потока
- •20.8. Строковые потоки
- •20.9. Состояние формата
- •20.10. Сильно типизированная библиотека
- •accumulate()
- •adjacent_difference()
- •adjacent_find()
- •binary_search()
- •copy()
- •copy_backward()
- •count_if()
- •equal()
- •equal_range()
- •fill()
- •find()
- •find_if()
- •find_end()
- •find_first_of()
- •generate()
- •generate_n()
- •includes()
- •inplace_merge()
- •iter_swap()
- •lexicographical_compare()
- •max_element()
- •merge()
- •next_permutation()
- •nth_element()
- •partial_sort()
- •partial_sort_copy()
- •partition()
- •prev_permutation()
- •random_shuffle()
- •remove()
- •remove_if()
- •remove_copy_if()
- •replace_copy()
- •replace_if()
- •replace_copy_if()
- •reverse_copy()
- •rotate()
- •search_n()
- •set_difference()
- •set_intersection()
- •set_union()
- •sort()
- •stable_partition()
- •swap()
- •swap_ranges()
- •transform()
- •unique_copy()
- •upper_bound()
- •Алгоритмы для работы с хипом
- •make_heap()
- •pop_heap()
- •push_heap()
- •sort_heap()
С++ для начинающих |
249 |
Упражнение 6.1
Что лучше выбрать в следующих примерах: вектор, список или двустороннюю очередь? Или ни один из контейнеров не является предпочтительным?
1.Неизвестное заранее количество слов считывается из файла для генерации случайных предложений.
2.Считывается известное количество слов, которые вставляются в контейнер в алфавитном порядке.
3.Считывается неизвестное количество слов. Слова добавляются в конец контейнера, а удаляются всегда из начала.
4.Считывается неизвестное количество целых чисел. Числа сортируются и печатаются.
6.3. Как растет вектор?
Вектор может расти динамически. Как это происходит? Он должен выделить область памяти, достаточную для хранения всех элементов, скопировать в эту область все старые элементы и освободить ту память, в которой они содержались раньше. Если при этом элементы вектора являются объектами класса, то для каждого из них при таком копировании вызываются конструктор и деструктор. Поскольку у списка нет необходимости в таких дополнительных действиях при добавлении новых элементов, кажется очевидным, что ему проще поддерживать динамический рост контейнера. Однако на практике это не так. Давайте посмотрим почему.
Вектор может запрашивать память не под каждый новый элемент. Вместо этого она запрашивается с некоторым запасом, так что после очередного выделения вектор может поместить в себя некоторое количество элементов, не обращаясь за ней снова. (Каков размер этого запаса, зависит от реализации.) На практике такое свойство вектора обеспечивает значительное увеличение его эффективности, особенно для небольших объектов. Давайте рассмотрим некоторые примеры из реализации стандартной библиотеки С++ от компании Rogue Wave. Однако сначала определим разницу между размером и емкостью контейнера.
Емкость – это максимальное количество элементов, которое может вместить контейнер без дополнительного выделения памяти. (Емкостью обладают только те контейнеры, в которых элементы хранятся в непрерывной области памяти, – vector, deque и string. Для контейнера list это понятие не определено.) Емкость может быть получена с помощью функции capacity(). Размер – это реальное количество элементов, хранящихся в данный момент в контейнере. Размер можно получить с помощью функции size(). Например:
С++ для начинающих |
250 |
||
|
|
#include <vector> |
|
|
|
|
|
|
|
#include <iostream> |
|
|
|
int main() |
|
|
|
{ |
|
|
|
vector< int > ivec; |
|
|
|
cout << "ivec: размер: " << ivec.size() |
|
|
|
<< " емкость: " << ivec.capacity() << endl; |
|
|
|
for ( int ix = 0; -ix < 24; ++ix ) { |
|
|
|
ivec.push_back( ix ); |
|
|
|
cout << "ivec: размер: " << ivec.size() |
|
|
|
<< " емкость: " << ivec.capacity() << endl; |
|
|
|
} |
|
|
|
} |
|
|
|
||
|
|
|
|
В реализации Rogue Wave и размер, и емкость ivec сразу после определения равны 0. |
|
||
После вставки первого элемента размер становится равным 1, а емкость – 256. Это |
|
||
значит, что до первого дополнительного выделения памяти в ivec можно вставить 256 |
|
||
элементов. При добавлении 256-го элемента вектор должен увеличиться: выделить |
|
||
память объемом в два раза больше текущей емкости, скопировать в нее старые элементы |
|
||
и освободить прежнюю память. Обратите внимание: чем больше и сложнее тип данных |
|
||
элементов, тем менее эффективен вектор в сравнении со списком. В таблице 6.1 показана |
|
||
зависимость начальной емкости вектора от используемого типа данных. |
|
Таблица 6.1. Размер и емкость для различных типов данных
Тип данных |
Размер |
Емкость после |
|
в байтах |
первой вставки |
|
|
|
int |
4 |
256 |
double |
8 |
128 |
простой класс #1 |
12 |
85 |
string |
12 |
85 |
большой простой класс |
8000 |
1 |
большой сложный класс |
8000 |
1 |
Итак, в реализации Rogue Wave при первой вставке выделяется точно или примерно 1024 байта. После каждого дополнительного выделения памяти емкость удваивается. Для типа данных, имеющего большой размер, емкость мала, и увеличение памяти с копированием старых элементов происходит часто, вызывая потерю эффективности. (Говоря о сложных классах, мы имеем в виду класс, обладающий копирующим конструктором и операцией присваивания.) В таблице 6.2 показано время в секундах, необходимое для вставки десяти миллионов элементов разного типа в список и в вектор. Таблица 6.3 показывает время, требуемое для вставки 10 000 элементов (вставка элементов большего размера оказалась слишком медленной).
Таблица 6.2. Время в секундах для вставки 10 000 000 элементов
Тип данных |
List |
Vector |
|
|
|
int |
10.38 |
3.76 |
С++ для начинающих |
|
|
|
|
251 |
||||||
|
|
double |
|
10.72 |
|
|
3.95 |
|
|
|
|
|
|
|
|
|
|||||||
|
|
простой класс |
|
12.31 |
|
|
5.89 |
|
|
|
|
|
|
string |
|
14.42 |
|
|
11.80 |
|
|
|
|
Таблица 6.3. Время в секундах для вставки 10 000 элементов |
|||||||||||
|
|
|
|
|
|
|
|
|
|||
|
Тип данных |
|
|
List |
|
|
Vector |
|
|||
|
|
|
|
|
|
|
|
|
|||
|
большой простой класс |
|
0.36 |
|
2.23 |
|
|
|
|||
|
большой сложный класс |
|
2.37 |
|
6.70 |
|
|
|
Отсюда следует, что вектор лучше подходит для типов данных малого размера, нежели список, и наоборот. Эта разница объясняется необходимостью выделения памяти и копирования в нее старых элементов. Однако размер данных – не единственный фактор, влияющий на эффективность. Сложность типа данных также ухудшает результат. Почему?
Вставка элемента как в список, так и в вектор, требует вызова копирующего конструктора, если он определен. (Копирующий конструктор инициализирует один объект значением другого. В разделе 2.2 приводится начальная информация, а в разделе 14.5 о таких конструкторах рассказывается подробно). Это и объясняет различие в поведении простых и сложных объектов при вставке в контейнер. Объекты простого класса вставляются побитовым копированием (биты одного объекта пересылаются в биты другого), а для строк и сложных классов это производится вызовом копирующего конструктора.
Вектор должен вызывать их для каждого элемента при перераспределении памяти. Более того, освобождение памяти требует работы деструкторов для всех элементов (понятие деструктора вводится в разделе 2.2). Чем чаще происходит перераспределение памяти,
тем больше времени тратится на эти дополнительные вызовы конструкторов и деструкторов.
Конечно, одним из решений может быть переход от вектора к списку, когда эффективность вектора становится слишком низкой. Другое, более предпочтительное решение состоит в том, чтобы хранить в векторе не объекты сложного класса, а указатели на них. Такая замена позволяет уменьшить затраты времени на 10 000 вставок с 6.70 секунд до 0.82 секунды. Почему? Емкость возросла с 1 до 256, что существенно снизило частоту перераспределения памяти. Кроме того, копирующий конструктор и деструктор
не вызываются больше для каждого элемента при копировании прежнего содержимого вектора.
Функция reserve() позволяет программисту явно задать емкость контейнера11.
int main() {
vector< string > svec;
svec.reserve( 32 ); // задает емкость равной 32 // ...
Например:
11 Отметим, что deque не поддерживает операцию reserve()
С++ для начинающих |
252 |
}
svec получает емкость 32 при размере 0. Однако эксперименты показали, что любое изменение начальной емкости для вектора, у которого она по умолчанию отлична от 1, ведет к снижению производительности. Так, для векторов типа string и double увеличение емкости с помощью reserve() дало худшие показатели. С другой стороны,
увеличение емкости для больших сложных типов дает значительный рост производительности, как показано в таблице 6.4.
Таблица 6.4. Время в секундах для вставки 10 000 элементов при различной емкости*
Емкость |
Время в секундах |
|
|
1 по умолчанию |
670 |
4,096 |
555 |
8,192 |
444 |
10,000 |
222 |
*Сложный класс размером 8000 байт с
конструктором копирования и деструктором
В нашей системе текстового поиска для хранения объектов типа string мы будем использовать вектор, не меняя его емкости по умолчанию. Наши измерения показали, что производительность вектора в данном случае лучше, чем у списка. Но прежде чем приступать к реализации, посмотрим, как определяется объект контейнерного типа.
Упражнение 6.2
Объясните разницу между размером и емкостью контейнера. Почему понятие емкости необходимо для контейнера, содержащего элементы в непрерывной области памяти, и не нужно для списка?
Упражнение 6.3
Почему большие сложные объекты удобнее хранить в контейнере в виде указателей на них, а для коллекции целых чисел применение указателей снижает эффективность?
Упражнение 6.4
Объясните, какой из типов контейнера – вектор или список – больше подходит для приведенных примеров (во всех случаях происходит вставка неизвестного заранее числа элементов):.
(a)Целые числа
(b)Указатели на большие сложные объекты
(c)Большие сложные объекты
6.4. Как определить последовательный контейнер?
Для того чтобы определить объект контейнерного типа, необходимо сначала включить соответствующий заголовочный файл:
С++ для начинающих |
253 |
#include <vector> #inclnde <list> #include <deque> #include <map>
#include <set>
Определение контейнера начинается именем его типа, за которым в угловых скобках
vector< string > svec;
следует тип данных его элементов12. Например:
list< int > |
ilist; |
Переменная svec определяется как вектор, способный содержать элементы типа string, а ilist – как список с элементами типа int. Оба контейнера при таком определении
if ( svec.empty() != true )
пусты. Чтобы убедиться в этом, можно вызвать функцию-член empty():
; // что-то не так
Простейший метод вставки элементов – использование функции-члена push_back(),
string text_word;
while ( cin >> text_word )
которая добавляет элементы в конец контейнера. Например: svec.push_back( text_word );
Здесь строки из стандартного ввода считываются в переменную text_word, и затем копия каждой строки добавляется в контейнер svec с помощью push_back().
Список имеет функцию-член push_front(), которая добавляет элемент в его начало. Пусть есть следующий массив:
int ia[ 4 ] = { 0, 1, 2, 3 };
12 Существующие на сегодняшний день реализации не поддерживают шаблоны с параметрами по умолчанию. Второй параметр – allocator – инкапсулирует способы выделения и освобождения памяти. В С++ он имеет значение по умолчанию, и его задавать не обязательно. Стандартная реализация использует операторы new и delete. Применение распределителя памяти преследует две цели: упростить реализацию контейнеров путем отделения всех деталей, касающихся работы с памятью, и позволить программисту при желании реализовать собственную стратегию выделения памяти. Определения объектов для компилятора, не поддерживающего значения по умолчанию параметров шаблонов, выглядят следующим образом:
vector< string, allocator > svec;
list< int, allocator > |
ilist; |
С++ для начинающих |
254 |
for ( int ix=0; ix<4; ++ix )
Использование push_back() ilist.push_back( ia[ ix ] );
for ( int ix=0; ix<4; ++ix )
создаст последовательность 0, 1, 2, 3, а push_front() ilist.push_front( ia[ ix ] );
создаст последовательность 3, 2, 1, 0. 13
Мы можем при создании явно указать размер массива – как константным, так и
#include <list> #include <vector> #include <string>
extern int get_word_count( string file_name ); const int list_size = 64;
list< int > ilist( list_size );
неконстантным выражением:
vector< string > svec(get_word_count(string("Chimera")));
Каждый элемент контейнера инициализируется значением по умолчанию, соответствующим типу данных. Для int это 0. Для строкового типа вызывается конструктор по умолчанию класса string.
list< int > ilist( list_size, -1 );
Мы можем указать начальное значение всех элементов: vector< string > svec( 24, "pooh" );
Разрешается не только задавать начальный размер контейнера, но и впоследствии изменять его с помощью функции-члена resize(). Например:
svec.resize( 2 * svec.size() );
Размер svec в этом примере удваивается. Каждый новый элемент получает значение по умолчанию. Если мы хотим инициализировать его каким-то другим значением, то оно указывается вторым параметром функции-члена resize():
13 Если функция-член push_front() используется часто, следует применять тип deque, а не vector: в deque эта операция реализована наиболее эффективно.
С++ для начинающих |
255 |
// каждый новый элемент получает значение "piglet"
svec.resize( 2 * svec.size(), "piglet" );
Кстати, какова наиболее вероятная емкость svec при определении, если его начальный размер равен 24? Правильно, 24! В общем случае минимальная емкость вектора равна его текущему размеру. При удвоении размера емкость, как правило, тоже удваивается
vector< string > svec2( svec );
Мы можем инициализировать новый контейнер с помощью существующего. Например: list< int > ilist2( ilist ) ;
Каждый контейнер поддерживает полный набор операций сравнения: равенство, неравенство, меньше, больше, меньше или равно, больше или равно. Сопоставляются попарно все элементы контейнера. Если они равны и размеры контейнеров одинаковы, то эти контейнеры равны; в противном случае – не равны. Результат операций “больше” или “меньше” определяется сравнением первых двух неравных элементов. Вот что печатает программа, сравнивающая пять векторов:
ivecl: 1 3 5 7 9 12 ivec2: 0 1 1 2 3 5 8 13 ivec3: 1 3 9
ivec4: 1 3 5 7 ivec5: 2 4
//первый неравный элемент: 1, О
//ivecl больше чем ivec2
ivecl < ivec2 //false ivec2 < ivecl //true
//первый неравный элемент: 5, 9 ivecl < ivec3 //true
//все элементы равны, но ivec4 содержит меньше элементов
//следовательно, ivec4 меньше, чем ivecl
ivecl < ivec4 //false
// первый неравный элемент: 1, 2 ivecl < ivec5 //true
ivecl == ivecl //true ivecl == ivec4 //false ivecl != ivec4 //true
ivecl > ivec2 //true ivec3 > ivecl //true ivec5 > ivec2 //true
Существуют три ограничения на тип элементов контейнера (практически это касается только пользовательских классов). Для должны быть определены:
∙операция “равно”;
∙операция “меньше” (все операции сравнения контейнеров, о которых говорилось выше, используют только эти две операции сравнения);
∙значение по умолчанию (для класса это означает наличие конструктора по умолчанию).
С++ для начинающих |
256 |
Все предопределенные типы данных, включая указатели и классы из стандартной библиотеки С++ удовлетворяют этим требованиям.
Упражнение 6.5
#include <string> #include <vector> #include <iostream>
#int main()
{
vector<string> svec; svec.reserve( 1024 );
string text_word;
while ( cin >> text_word ) svec.push_back( text_word );
svec.resize( svec.size()+svec.size()/2 );
// ...
Объясните, что делает данная программа:
}
Упражнение 6.6
Может ли емкость контейнера быть меньше его размера? Желательно ли, чтобы емкость была равна размеру: изначально или после вставки элемента? Почему?
Упражнение 6.7
Если программа из упражнения 6.5 прочитает 256 слов, то какова наиболее вероятная емкость контейнера после изменения размера? А если она считает 512 слов? 1000? 1048?
Упражнение 6.8
Какие из данных классов не могут храниться в векторе: