Стенли Липпман - Язык программирования 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

---

А.2. Краткий обзор алгоритмов

В библиотеке определено более 100 алгоритмов. Чтобы научиться их использовать, следует понять структуру, а не запоминать подробности применения каждого из них. Лежащая в их основе архитектура описана в главе 10, а в этом разделе описан каждый из алгоритмов.

• beg и end — итераторы, обозначающие диапазон элементов (см. раздел 9.2.1). Почти все алгоритмы работают с последовательностями, обозначенными итераторами beg и end.

• beg2 — итератор, обозначающий начало второй исходной последовательности. Если итератор end2 присутствует, он обозначает конец второй последовательности. Если итератора end2 нет, подразумевается, что обозначенная итератором beg2 последовательность такого же размера, что и исходная, обозначенная итераторами beg и end. Типы итераторов beg и beg2 не обязаны совпадать. Но должна существовать возможность применить указанную операцию или заданный вызываемый объект к элементам этих двух последовательностей.

• dest — итератор, обозначающий назначение. Последовательность назначения должна быть способна содержать столько элементов, сколько необходимо для исходной последовательности.

• unaryPred и binaryPred — унарные и бинарные предикаты (см. раздел 10.3.1), возвращающие применимый в условии тип и получающие соответственно один и два аргумента, являющиеся элементами исходного диапазона.

• comp — бинарный предикат, отвечающий требованиям упорядочивания по ключу в ассоциативном контейнере (см. раздел 11.2.2).

• unaryOp и binaryOp — вызываемые объекты (см. раздел 10.3.2), которые могут быть вызваны с одним и двумя аргументами из исходного диапазона соответственно.

А.2.1. Алгоритмы поиска объекта

Эти алгоритмы осуществляют поиск в исходной последовательности заданного значения или последовательности значений.

Каждый алгоритм предоставляет две перегруженных версии. Первая версия для сравнения элементов использует оператор равенства (==) базового типа, а вторая использует предоставленные пользователем предикаты unaryPred или binaryPred.

Простой алгоритм поиска

Для поиска этим алгоритмам требуются итераторы ввода.

find(beg, end, val)

find_if(beg, end, unaryPred)

find_if_not(beg, end, unaryPred)

count(beg, end, val)

count_if(beg, end, unaryPred)

Функция find() возвращает итератор на первый элемент в исходном диапазоне, равный значению val. Функция find_if() возвращает итератор на первый элемент, для которого выполняется предикат unaryPred. Функция find_if_not() возвращает итератор на первый элемент, для которого предикат unaryPred возвращает значение false. Все три функции возвращают итератор end, если искомый элемент не существует.

Функция count() возвращает количество вхождений значения val. Функция count_if() подсчитает количество элементов, для которых предикат unaryPred возвращает значение true.

all_of(beg, end, unaryPred)

any_of(beg, end, unaryPred)

none_of(beg, end, unaryPred)

Возвращают логическое значение, указывающее, выполняется ли предикат unaryPred для всех элементов, какого-нибудь элемента или ни одного элемента соответственно. Если последовательность пуста, функция any_of() возвращает значение false, а функции all_of() и none_of() — true.

Алгоритм поиска одного из нескольких значений

Этим алгоритмам требуются прямые итераторы. Они ищут в исходной последовательности повторяющиеся элементы.

adjacent_find(beg, end)

adjacent_find(beg, end, binaryPred)

Возвращает итератор на первую пару смежных совпадающих элементов. Возвращает итератор end, если смежных совпадающих элементов нет.

search_n(beg, end, count, val)

search_n(beg, end, count, val, binaryPred)

Возвращает итератор на начало внутренней последовательности из count равных элементов. Возвращает итератор end, если такой внутренней последовательности не существует.

Алгоритм поиска последовательности

За исключением алгоритма find_first_of() этим алгоритмам требуются две пары прямых итераторов. Для обозначения первой своей последовательности алгоритм find_first_of() использует итераторы ввода и прямые итераторы для второй. Эти алгоритмы ищут последовательность, а не одиночный элемент.

search(beg1, end1, beg2, end2)

search(beg1, end1, beg2, end2, binaryPred)

Возвращает итератор на первую позицию исходного диапазона, с которой начинается искомая последовательность. Возвращает итератор end1, если искомая последовательность не найдена.

find_first_of(beg1, end1, beg2, end2)

find_first_of(beg1, end1, beg2, end2, binaryPred)

Возвращает итератор на первое вхождение в первом диапазоне любого элемента из второго диапазона. Возвращает итератор endl, если искомое соответствие отсутствует.

find_end(beg1, end1, beg2, end2)

find_end(beg1, end1, beg2, end2, binaryPred)

Подобен алгоритму search(), но возвращает итератор на последнюю позицию в исходном диапазоне, в которой второй диапазон встречается как внутренняя последовательность. Возвращает итератор end1, если вторая последовательность пуста или не найдена.

А.2.2. Другие алгоритмы, осуществляющие только чтение

Для первых двух аргументов этим алгоритмам требуются итераторы ввода.

Алгоритмы equal() и mismatch() получают также дополнительный итератор ввода, обозначающий начало второго диапазона. Они также предоставляют две перегруженных версии. Первая версия для сравнения элементов использует оператор равенства (==) базового типа, а вторая сравнивает элементы используя предоставленный пользователем предикат unaryPred или binaryPred.

for_each(beg, end, unaryOp)

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

mismatch(beg1, end1, beg2)

mismatch(beg1, end1, beg2, binaryPred)

Сравнивает элементы в двух последовательностях. Возвращает пару (см. раздел 11.2.3) итераторов, обозначающих первые элементы в каждой не совпадающей последовательности. Если все элементы соответствуют друг другу, первый итератор возвращенной пары окажется равным end1, а итератор beg2 — смещению, равному размеру первой последовательности.

equal(beg1, end1, beg2)

equal(beg1, end1, beg2, binaryPred)

Выявляет равенство двух последовательностей. Возвращает значение true, если каждый элемент в исходном диапазоне равен соответствующему элементу последовательности, начинающейся с позиции beg2.

А.2.3. Алгоритмы бинарного поиска

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

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

Эти алгоритмы требуют, чтобы элементы в исходной последовательности уже были упорядочены. Эти алгоритмы ведут себя подобно одноименным функциям-членам ассоциативных контейнеров (см. раздел 11.3.5).

Алгоритмы equal_range(), lower_bound() и upper_bound() возвращают итераторы на позиции последовательности, куда мог бы быть вставлен заданный элемент при сохранении существующего порядка в последовательности. Если элемент больше всех остальных в последовательности, то возвращаемый итератор будет итератором после конца.

Каждый алгоритм предоставлен в двух версиях: первая использует для проверки элементов оператор меньше (<) типа элемента, а вторая использует заданную функцию сравнения. В следующих алгоритмах "x меньше, чем y" означает, что выражения x<y и comp(x, y) истинны:

lower_bound(beg, end, val)

lower_bound(beg, end, val, comp)

Возвращает итератор, обозначающий первый элемент, значение которого больше или равно значению val, или итератор end, если такого элемента нет.