ным false, и цикл прекратится. Далее программа дважды переводит строку, чтобы результат вычислений не наезжал на введенные числа, и затем вызывается стандартная функция accuniulateO, которая складывает все числа в контейнере и отправляет результат на экран. Используя два итератора, t.beginC) и t .endC), функция accutnulateO вычисляет сумму всех объектов, начиная с того, на который указывает итератор t.beginC), и кончая объектом, стоящим непосредственно перед тем, на который указывает итератор t.endC). Третий аргумент функции accumul ate() - начальное значение суммы - равен нулю. Это значит, что сумма целых чисел, входяП1ИХ в контейнер, тоже будет целым числом, что опасно, ведь при большом количестве слагаемых может наступить переполнение. Поэтому лучше, когда для суммы предусмотрен больший диапазон значений, чем для отдельных с/гагаемых. Чтобы, например, сумма оказалась типа doubl е, нужно сделать третий аргумент фун-кции равным 0.0.

Только что мы суммировали целые числа, но функция accumulateO, как и многие другие функции, работающие с контейнерами, может суммировать любые объекты, лишь бы для них был определен оператор +, например строки. Программа, показанная в листинге 4.9, складывает строки, введенные с клавиатуры. А поскольку сложение для строк - это их объединение, то на выходе появится одна строка, состоящая из всех поочередно введенных строк. Если, скажем, с клавиатуры были введены буквы а , Ь , г , а , с , а , d , а , Ь , г , а , то в сумме получится abracadabra*.

Листинг 4.9

#include <iostream> #include <vector> #1nclude <string>

Файлы

Ввод с клавиатуры - важный источгшк питания программ, но далеко не единственный. Вспомним о файлах, в изобилии встречающихся на жестких дисках наших компьютеров. Файлы хранят тексты программ, данные, которые должен обрабатывать компьютер, статьи, книги и многое другое. За десятилетия существования компьютеров человечество успело создать миллиарды файлов, которые, конечно же, должны быть доступны программам.

С точки зрения С++, файл - это особый объект, управляемый собственными функциями и операторами. Программа, показанная в листинге 4.10, открывает файл rhyme, читает его строка за строкой, а затем сортирует прочитанные строки и выводит их на экран.

finclude <numer1c> using namespace std: int main(){ string buf; vector<string> t; whileCcin buf)

t.push back(buf): cout endl endl; cout accumulateCt.beginO.t.endO.

static cast<string>( )) endl:

Эта программа мало отличается от предыдущей. Правда, в ней иначе задается начальное значение суммы: static cast<stri ng>( )

Казалось бы, достаточно просто записать , но компилятор поймет это как массив из одного завершающего нулевого символа (см. об этом раздел Массивы ). Чтобы превратить его в пустую строку, приходится использовать оператор static casto().

Листинг 4.10

#include <iostream> #include <fstreani> #include <string> finclude <vector> #include <algorithm> using namespace std; int main(){ char buff[80]; vector<string> s; ifstream infile; infile.openCrhyme );

while (1) {

infile.getlineCbuff. sizeof(buff)); IfCinfile.eofO) break; s.push backCbuff);

sortCs.beginO .s.endO); forCint i=0;i < s.sizeC);i++)

cout S[i] endl; infile.closeC): }

Файл inf i le, объявляемый в профамме, - .это объект типа ifstream, описанный во в1слючаемом файле <:fstream>. Далее в программе инструкция infile.openCrhyme ) открывает файл под названием rhyme, который должен быть в той же папке, что и сама программа. Файл rhyme находится среди исходных текстов программ, размещенных на сайте www.piter.com, и содержит строки детской счита-чочки царь, царевич, король, королевич, сапожник, портной... .

После открытия файла начинается самое важное: чтение строк и заполнение пмн контейнера s. Все это делается в цикле whi led) {}. Единица в круглых скобках означает, что условие всегда выполняется, поэтому причину выхода из цикла ггужно искать у него внутри.

Файлы 71

Но прежде посмотрим, как происходит чтение строк. Делает это следующая функция:

infile.getlineCbuff. sizeofCbuff)):

У функции два аргумента: имя массива, где оказывается только что прочпта1Н1ая строка, и его размер - sizeofCbuf), равный в нашем случае восьмидесяти. До сих пор мы-не встречались с оператором sizeofC), который определяет размер объекта С++. Нам была бы привычней собстг1енпая функция buff .sizeC), ffo массив buff, как мы уже говорили, нельзя считать нолноце1Н1ЫМ объектом С++, поскольку у массивов не бывает собственных функций, вот и приходится исгюльзоватьоператор sizeof (). Впрочем, оператор sizeof С) очень удобен и часто используется. С его помощью можно узнать размер переменных int или double в байтах и количество памяти (в байтах), занимаемое любым другим объектом.

Итак, мы поняли, как считать из файла отдельггую строку. Но теперь перед нами неумолимо встает вопрос: а до каких пор продолжать чтегше, как узнать о том, что файл кончился? К сожалению, сделать это можно, когда уже поздно и неприятность произошла . О заверп1ении файла можно узнать, лишь когда не удастся очередная попытка чтения. Вот почему инструкция ifdnfileeofO) break стоит раньше инструкций передачи очередной прочитанной строки в кон-TeHFiep. Если очередное чтение не удалось, значит, достигнут конец файла, функция infile.eofO возвращает истину , выполняется инструкция break, которая прерывает выполнения цикла, и программа переходит к следующей за whileOd инструкции sortC). Заметим, что break можно иримегшть и в цикле forC). при этом действие будет таким же: break мгновенно

Приходится испо.пыювать массивы, потому что более соверпюн-ные объекты (строки) функция gctlinc() не воспринимает.

Анаграммы

Лучшее описание этого алгоритма из тех, что я слышал, - размахивание руками Т. Каргилла: Отсортируйте это так (горизонтальное движение рукой), а затем так (вертикальный взмах) .

Д Бентли,

Жемчужигш программирования

Анаграммы - это наборы слов, состоящих из одних и тех же букв, например сон и нос для русского или excitation (волнение) и intoxicate (отравиться) для английского. Чтобы искать анаграммы на компьютере (вручную это вряд ли возможно), необходим словарь соответствующего языка. Предположим, он у нас есть. Но что делать дальше? Проще всего получить перестановки всех букв в слове (для слова нос это нос , нсо , сон , сно , онс , осн ) и затем искать каждую перестановку в словаре. Все, что найдено, и будет набором анаграмм.

Этот план вполне реален, хотя компьютеру придется здорово потрудиться, чтобы его выполнить. Ведь число перестановок уже десяти букв равно 10!, то есть более трех миллионов, а при дальнейшем увеличении числа букв количество возможных перестановок становится астрономическим. Ну и что же - скажете вы - на то и компьютер, чтобы выполнять нудную однообразную работу. Напишем программу и подождем. Но очень часто желание заставить компьютер работать вместо себя приводит к тому, что он работает вечно.

Чтобы успешно вычислять на компьютере, нужны алгоритмы - способы быстро и эффективно справить-

ся с определенной задачей. Конечно, алгоритмом получения анаграмм можно считать и тупой перебор комбинаций всех букв с последующей проверкой и отбором в словаре. Но гораздо уместнее назвать алгоритмом следующую идею: раз анаграммы состоят из одних и тех же букв, то отсортированная последовательность букв окажется для анаграмм одинаковой. Отсортировав буквы в словах excitation и intoxicate , получим одно и то же: aceiinottx .

Итак, идея: возьмем словарь, составим пары одинаковых слов и отсортируем буквы в одном из слов, составляющих пару, например левом. Тогда слева от каждого слова появляется отпечаток , а слова с одинаковыми отпечатками - и есть анаграммы. Чтобы легче было искать одинаковые отпечатки, достаточно отсортировать пары слов по возрастанию их отпечатков. А дальше - читать одинаковые отпечатки и выводить па экран соответствующие им слова.

Итак, задача поиска анаграмм сводится к двуй сортировкам. Сначала сортируются буквы в словах, затем - сами слова. Эта задача все-таки остается трудной, но стандартная библиотека С++ имеет специальный контейнер multimap, идеально приспособленный для отыскания анаграмм.

В ког1тейнере multimap объекты хранятся парами <ключ> <объект>, по ключу их можно сортировать. Поэтому план нахождения анаграмм обретаеттакие чер- ты: открыть файл словаря, прочитать слово, скопировать его в строку, отсортировать буквы в строке и заслать пару из отсортированного и нетронутого слова в контейнер, причем поступить так со всеми словами в словаре. Затем остается отсортировать контейнер по ключу и вывести на экран анаграммы. Эту задачу решает программа, показанная в листинге 4.11.

ВЫВОДИТ программу за пределы цикла к первой следующей за ним инструкции.