Стенли Липпман - Язык программирования C++. Пятое издание

• Название: Язык программирования C++. Пятое издание
• Автор: Стенли Липпман
• Издательство: Издательский дом "Вильямс"
• Жанр: Программирование
• Год: 2014
• ISBN: 978-5-8459-1839-0

Лучшее руководство по программированию и справочник по языку, полностью пересмотренное и обновленное под стандарт С++11!

Вы держите в руках новое издание популярного и исчерпывающего бестселлера по языку программирования С++, которое было полностью пересмотрено и обновлено под стандарт С++11. Оно поможет вам быстро изучить язык и использовать его весьма эффективными и передовыми способами. В соответствии с самыми передовыми и современными методиками изложения материала авторы демонстрируют использование базового языка и его стандартной библиотеки для разработки эффективного, читабельного и мощного кода.

С самого начала этой книги читатель знакомится со стандартной библиотекой С++, ее самыми популярными функциями и средствами, что позволяет сразу же приступить к написанию полезных программ, еще не овладев всеми нюансами языка. Большинство примеров из книги было пересмотрено так, чтобы использовать новые средства языка и продемонстрировать их наилучшие способы применения. Эта книга — не только проверенное руководство для новичков в С++, она содержит также авторитетное обсуждение базовых концепций и методик языка С++ и является ценным ресурсом для опытных программистов, особенно желающих побыстрей узнать об усовершенствованиях С++11.

Стенли Б. Липпман работал старшим консультантом в Jet Propulsion Laboratory, архитектором группы Visual С++ корпорации Microsoft, техническим сотрудником Bell Laboratories и главным инженером- программистом по анимации в кинокомпаниях Disney, DreamWorks, Pixar и PDI.

Жози Лажойе, работающий ныне в кинокомпании Pixar, был членом канадской группы разработчиков компилятора C/C++ корпорации IBM, а также возглавлял рабочую группу базового языка С++ в составе международной организации по стандартизации ANSI/ISO.

Барбара Э. Му имеет почти тридцатилетний опыт программирования. На протяжении пятнадцати лет она работала в компании AT&T, сотрудничая с Бьярне Страуструпом, автором языка С++, и несколько лет руководила группой разработчиков С++.

• Узнайте, как использовать новые средства языка С++11 и стандартной библиотеки для быстрого создания надежных программ, а также ознакомьтесь с высокоуровневым программированием

• Учитесь на примерах, в которых показаны передовые стили программирования и методики проектирования

• Изучите принципы и узнайте почему язык С++11 работает именно так

• Воспользуйтесь множеством перекрестных ссылок, способных помочь вам объединить взаимосвязанные концепции и проникнуть в суть

• Ознакомьтесь с современными методиками обучения и извлеките пользу из упражнений, в которых подчеркиваются ключевые моменты, позволяющие избежать проблем

• Освойте лучшие методики программирования и закрепите на практике изученный материал

Исходный код примеров можно загрузить с веб-страницы книги на сайте издательства по адресу: http://www.williamspublishing.com

---

Таблица 11.1. Типы ассоциативных контейнеров

Элементы упорядочиваются по ключу map Ассоциативный массив, хранящий пары ключ-значение set Контейнер, в котором ключ является значением multimap Карта, допускающая совпадение ключей multiset Набор, допускающий совпадение ключей Неупорядоченные коллекции unordered_map Карта, организованная по хеш-функции unordered_set Набор, организованный по хеш-функции unordered_multimap Хешированная карта; ключи могут повторяться unordered multiset Хешированный набор; ключи могут повторяться

Типы map и multimap определены в заголовке map; классы set и multiset — в заголовке set; неупорядоченные версии контейнеров определены в заголовках unordered_map и unordered_set соответственно.

11.1. Использование ассоциативных контейнеров

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

Карта (тип map) — это коллекция пар ключ-значение. Например, каждая пара может содержать имя человека как ключ и номер его телефона как значение. О такой структуре данных говорят, что она "сопоставляет имена с номерами телефонов". Тип map зачастую называют ассоциативным массивом (associative array). Ассоциативный массив похож на обычный массив, но его индексы не обязаны быть целыми числами. Значения в карте находят по ключу, а не по их позиции. В карте имен и номеров телефонов имя человека использовалось бы как индекс для поиска номера телефона этого человека.

В отличие от карты, набор — это просто коллекция ключей. Набор полезен тогда, когда необходимо знать, имеется ли в нем значение. Например, банк мог бы определить набор bad_checks для хранения имен личностей, которые выписывали фальшивые чеки. Прежде чем принять чек, этот банк запросил бы набор bad_checks и убедился, есть ли в нем имя клиента.

Использование контейнера map

Классическим примером применения ассоциативного массива является программа подсчета слов:

// подсчитать, сколько раз каждое слово встречается во вводе

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;

Эта программа читает ввод и сообщает, сколько раз встречается каждое слово.

Подобно последовательным контейнерам, ассоциативные контейнеры являются шаблонами (см. раздел 3.3). Чтобы определить карту, следует указать типы ключа и значения. В этой программе карта хранит элементы, ключи которых имеют тип string, а значения — тип size_t (см. раздел 3.5.2). При индексации карты word_count строка используется как индекс, а возвращаемый счетчик типа size_t связан с этой строкой.

Цикл while читает слова со стандартного устройства ввода по одному за раз. Он использует каждое слово для индексирования карты word_count. Если слова еще нет в карте, оператор индексирования создает новый элемент, ключом которого будет слово, а значением 0. Независимо от того, должен ли быть создан элемент, его значение увеличивается.

Как только весь ввод прочитан, серийный оператор for (см. раздел 3.2.3) перебирает карту выводя каждое слово и соответствующий счетчик.

При получении элемента из карты возвращается объект типа pair (пара), рассматриваемого в разделе 11.2.3 (стр. 545). Если не вдаваться в подробности, то pair — это шаблон типа, который содержит две открытые переменные-члена по имени first (первый) и second (второй). У используемых картой пар член first является ключом, a second — соответствующим значением. Таким образом, оператор вывода должен отобразить каждое слово и связанный с ним счетчик.

Если бы эта программа была запущена для текста первого параграфа данного раздела, то вывод был бы таким:

Although occurs 1 time

Before occurs 1 time

an occurs 1 time

and occurs 1 time

...

Использование контейнера set

Логичным усовершенствованием создаваемой программы будет игнорирование таких распространенных слов, как "the", "and", "or" и т.д. Для хранения игнорируемых слов будет использован набор, а подсчитываться будут только те слова, которые отсутствуют в этом наборе:

// подсчитать, сколько раз каждое слово встречается во вводе

map<string, size_t> word_count; // пустая карта строк и чисел

set<string> exclude = {"The", "But", "And", "Or", "An", "A",

                       "the", "but", "and", "or", "an", "a"};

string word;

while (cin >> word)

 // подсчитать только не исключенные слова

 if (exclude.find(word) == exclude.end())

  ++word_count[word]; // получить и прирастить счетчик слов

Подобно другим контейнерам, set является шаблоном. Чтобы определить набор, следует указать тип его элементов, которым в данном случае будет string. Подобно последовательным контейнерам, для элементов ассоциативного контейнера применима списочная инициализация (см. раздел 3.3.6). Набор exclude будет содержать 12 слов, которые следует игнорировать.

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

// подсчитать только не исключенные слова

if (exclude.find(word) == exclude.end())

Вызов функции find() возвращает итератор. Если заданный ключ находится в наборе, итератор указывает на него. Если элемент не найден, функция find() возвращает итератор на элемент после конца. В этой версии счетчик слов изменяется, только если слово не находится в наборе exclude.

Если запустить эту версию для того же ввода, что и прежде, вывод будет таким:

Although occurs 1 time

Before occurs 1 time

are occurs 1 time

as occurs 1 time

...

Упражнения раздела 11.1

Упражнение 11.1. Опишите различия между картой и вектором.

Упражнение 11.2. Приведите пример того, когда наиболее полезен контейнер list, vector, deque, map и set.

Упражнение 11.3. Напишите собственную версию программы подсчета слов.

Упражнение 11.4. Усовершенствуйте свою программу так, чтобы игнорировать регистр и пунктуацию. Т.е. слова "example" и "Example", например, должны увеличить тот же счетчик.

11.2. Обзор ассоциативных контейнеров

Ассоциативные контейнеры (и упорядоченные, и неупорядоченные) поддерживают общие функции контейнеров, описанные в разделе 9.2 и перечисленные в табл. 9.2. Ассоциативные контейнеры не поддерживают функции, специфические для последовательных контейнеров, такие как push_front() или back(). Поскольку элементы хранятся на основании их ключа, эти операции были бы бессмысленны для ассоциативных контейнеров. Кроме того, ассоциативные контейнеры не поддерживают конструкторы и функции вставки, получающие значение элемента и его позицию.

Кроме функций, общих для всех контейнеров, ассоциативные контейнеры предоставляют некоторые функции (табл. 11.7) и псевдонимы типов (табл. 11.3), которых нет у последовательных контейнеров. Помимо этого, неупорядоченные контейнеры предоставляют функции настройки производительности их хеша, которые рассматриваются в разделе 11.4.

Итераторы ассоциативных контейнеров двунаправлены (см. раздел 10.5.1).

11.2.1. Определение ассоциативного контейнера