быстрее, чем это делает функция dict find{)? Что может быть быстрее линейного перебора элементов?

Ответ таков: если элементы расположены хаотично, то ничего другого не остается. Но если они отсортированы, можно применить замечательный aлгopггм, которым восхищались еще древние греки, - бинарный поиск.

Представим себе, что слова расставлены в алфавитном порядке, и есть слово, которое нужно отыскать в словаре. Начнем поиск с того, что поделим словарь па две примерно равные части и сравним наше слово с первым словом второй части. Если оно окажется болыпе, значит, искать его надо во второй половине, если меньше - в первой. Выбранную половину опять делим на две части и так повторяем до тех пор, пока слово не найдется И.Т1И выяснится, что его нет в словаре.

Задача 6.1. Целые числа расположены в массиве в порядке возрастания. Напишите программу бинарного поиска заданного числа.

Бинарный поиск позволяет во много раз сократить число сравнений элементов, поэтому он гораздо быстрее. В принципе, можно было бы сортировать контейнер vector и написать для него функцию бинарного поиска. Но гораздо проще использовать уже готовое ренление - контейнер пар, который отличается от контейнера multimap, использованного нами при поиске анаграмм, тем, что ключ (первый объект пары) должен бьпъ уникальным. Для словаря это хорошо, потому что все слова в нем - разные.

Конечно, контейнер тар не похож на отсортированный контейнер vector. Но прелесть стандартных контейнеров в том и состоит, что нам не нужно знать, как они устроены, достаточно знать о том, что собственная функция i nsertc) контейнера map работает быстро (на манер 1;воичного поиска), и после каждой вставки нового элемента контейнер оказывается отсортированным. Операция поиска в контейнере тар так же быстра, как и

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

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

di ct. i nsert (pai r<str i ng. str i ng>( b . )):

A слово zzzzzzzzz , включаемое в словарь, помечается буквой п :

dict.insertCpair<string.string>Cw. п )):

Нашу задачу можно считать наполовину решенной. Работоспособная версия программы (см. листинг 6.1) способна быстро искать .заданные слова в созданном ею контейнере (словаре). Теперь остается научиться добывать слова из текстового файла и включать в контейнер каждое полученное слово, если его там еще нет.

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

Например, для получения слов можно считывать целую строку с помощью функции getl ine{), а затем выделять из нее последовательности идущих подряд букв. Такой подход относительно быстр (читается целая строка), но очень зависит от структуры текста. Слишком длинная строка не уместится в буфере, и некоторые слова могут потеряться или оказаться обрезанными.

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

Добавление функций

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

Теперь нужно рсшить, как будет выглядеть функщ\я, каковы ее имя, параметры и возврап1асмое значение. Чтобы лучше понимать программу, нужно отразить в названии функции то, что она делает, поэтому хорошо назвать ее GetWord (в переводе с английского - получить слово ). Функция будет возвращать значение тина bool (true - при удачном чтснгн!, false - при достижении конца файла). А параметро.м функции обязательно должна быть ссылка на строку, где окгшется очередное слово. Если бы у нас была такая функция, то цикл, в котором новые слова включаются в словарь, выглядел бы очень просто:

while (1) {

if (GetWord(nw)==false) break:

else

diet.insert{pair<string.String>(nw. n )); }

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

Ьоо1 GetWordCstring bw )

Однако первый вариант програм.мы с участием новой функции компилятор отверг на том основании, что внуфи функции GetWord обнаружился неизвестный объект infile- файл, из которого считываются буквы. Здесь меня подвело знание языка С, где файлы глобальны, то есть доступны всем функциям. Но в С++ это не так, и приходится вводить в функцию enie один параметр. То есть ее прототип должен выглядеть так:

bool GetWordCstring 8iw. ifstream Infile):

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

Поставив оператор & перед словом infile, я получил наконец функцию (листинг 6.2), к которой компилятор отнесся благосклонно.

Листинг 6.2

bool GetWordCstring &w. ifstream &infile){

char ch:

w.eraseC):

whileCl){

infile.get(ch):

ifCinfile.eofO)

проАопжение

ла, в котором может пе быть строк и даже самих букв. В этом случае программа тоже будет работать, по не найдет ни одного слова. Недостаток такого подхода - низкая скорость, ведь чтение из файла - медленная операция, а здесь приходится читать каж;и>1Й символ.

Но все же, немного подумав, я выбрал второй вариант. Во-первых, он проще, во-вторых, он универсален, и, наконец, в-третьих, он пе должен сильно замедлит[> работу программы, так как основное время будет, скорее всего, потрачено на поиск слова в контейнере, а нг на извлечение его из файла.

Листинг 6.2 (проАОлжвниё)

ifCw!= ) return true; else return false: if{is1etter(ch))

w+=ch: else if{w != ) return true:

Функция GetWordO оказалась довольно сложной из-за того, что при чтении каждого символа приходится проверять, не достигнут ли конец файла.

Все начинается с очистки строки, где окажется только что вьщеленное слово. Это делает собственная функция w.eraseO. Далее из файла читается симвал и запоминается в переменной ch. После этого нужно npoBcptrrb, не достигнут ли конец фа11ла. Если чтение неудачно, то вызов infile.eofO возвран1ает true. Но просто выйти в этот момент из функции нельзя, ведь в строке w может храниться последнее слово файла. Поэтому проверка выглядит так:

ifCinfile.eofO)

if{w!= ) return true: else return false:

Если достигнут конец файла, но строка не пустая (W != ), возвращается true и делается попыгка включить последнее слово в словарь. Если же строка пуста, возвращается false - файл кончился, слов больше нет!

Теперь нужно проверить, буква ли прочитанный символ, и если да - присоединить его к строке. Если же симвал - не буква, значит, слово найдено, и его нужно возвратить во внешний мир и попытаться включить в словарь. Проверка выглядит так:

ifCisletter(ch))

w+-ch: else if(w != )

return true:

Обратите внимание, значение true возвращается, лишь когда строка не пуста. Если же в строке ничего нет.

функция читает следующий символ, и так до тех пор, пока не найдется буква или пока не кончится файл.

Вы, наверное, уже обратили внимание на функцию isletterCch), возвращающую true, когда ch - буква, И false - в противном случае. Эту функцию я придумал, когда писал функцию GetWord(), чтобы не отвлекаться и думать только над одной задачей. Проверять ошибки компиляции это не меншет, нужно только в начале программы поместить прототип функции is1etter().

Но когда фугпция GetWordO готова (или мы просто думаем так, потому что не проверяли ее в деле ), приходит черед и функции islettero. А чтобы ее написать, нужно знать, какие латинские символы - буквы, а какие - нет. Можно, конечно, найти какую-нибудь справочную книгу, где есть различные кодировки. Но можно понять, как кодируиэтся буквы, и экспериментально с по-моии>ю простой программы, показанной в листинге 6.3. Листинг 6.3

#include <iostream> using namespace std; int mainC) { char ch:

forCint i=l; i<127:i++) { ch=i:

cout 1 ch endl:

В этой программе перебираются числа сгг 1 до 126, каждое число записывается в переменную ch, а затем дважды вьшодится на экран: как переменная 1 nt (cout i) и как символ (cout ch). Запустив программу, мы увидим, что прописные латинские буквы щут плотно, без просветов и кодируются числами от 65 (буква А) до 90 (Z). Строчные латинские буквы расположены также

Вывод программы лучше перенаправить в файл командой I63.exe > Z. Об этом уже говорилось в начале главы.