циями isalpha() и isspace() стандартной библиотеки С, заменив все ненужные символы пробелами. После замены мы сможем легко извлечь слова из каждой прочитанной строки:

: C07:WordLlst.cpp

Вывод списка слов, встречающихся в документе

#include <algorithm>

linclude <cctype>

linclude <cstring>

linclude <fstream>

linclude <iostream>

linclude <iterator>

linclude <set>

linclude <sstream>

linclude <string>

linclude ../require.h

using namespace std:

char replaceJunk(char c) {

В тексте остаются только алфавитные символы, пробелы (в качестве разделителей) и символы return (isalpha(c) с == \ ) ? с : :

int main(int argc, char* argv[]) { char* fname = WordList.cpp : if(argc > 1) fname = argv[l]: ifstream in(fname): assureCin, fname): set<string> wordlist: string line:

while(getline(in, line)) { transformCline.beginO. line.endO. line.beginO. replaceJunk): istringstream is(line): string word: while (is word) wordlist.insert(word):

Вывод результатов:

copy(wordl 1 st. beginО. wordl 1 st.endO.

ostream iterator<stnng>(cout, \n )):

} /:-

Вызов transformO заменяет все посторонние символы пробелами. Множество не только игнорирует повторяющиеся слова, но и сравнивает свои элементы объектом функции less<string> (второй аргумент по умолчанию шаблона set). В свою очередь, этот объект функции использует операторную функцию string::operator<(), поэтому слова следуют в алфавитном порядке.

Если вы всего лишь хотите получить отсортированную последовательность, не обязательно использовать множество. То же самое можно сделать при помощи алгоритма sort() (и множества других алгоритмов STL) с другими контейнерами STL. И все же вполне вероятно, что множество позволит решить эту задачу быстрее. Множество особенно хорошо приспособлено для поиска, поскольку его функция find О работает с логарифмической сложностью и заметно превосходит по скорости обобщенный алгоритм find(). Как вы помните, обобщенный алгоритм find() перебирает весь интервал до тех пор, пока не найдет искомый элемент, по-

этому в худшем случае он работает со сложностью М,ав среднем - со сложностью N/2. Впрочем, для заранее отсортированных последовательных контейнеров поиск может выполняться функцией equaLrange() с логарифмической сложностью.

В следующем примере список слов строится при помощи итератора istreambufjterator. Программа перемещает из входного потока в объект string те символы, для которых функция isalphaO стандартной библиотеки С возвращает true:

: C07:WordList2.cpp

1streambuf 1terator и итераторы вставки

#include <cstr1ng>

linclude <fstreani>

linclude <iostreani>

linclude <iterator>

linclude <set>

linclude <string>

linclude ../require.h

using namespace std;

int mainCint argc. char* argv[]) ( char* fname = WordList2.cpp ; if(argc > 1) fname = argv[l]; ifstream in(fname); assure(in. fname);

istreambuf iterator<char> p(in). end; set<string> wordlist; while (p != end) { string word; i nsert i terator<stri ng>

ii(word. word.beginO); Поиск первого алфавитного символа: while (р != end && lisalpha (*p)) ++p:

Копирование до первого неалфавитного символа: while (р != end && lisalpha (*р))

++*ii = *р++: if (word.sizeO != 0)

wordlist.insert(word):

Вывод результатов: copy(wordliSt.beginO, wordlist.endO. ostream iterator<string>(cout, \n )): } /:-

Данный пример был предложен Натаном Майерсом (Nathan Myers), разработчиком итератора istreambufjterator и его родственников . Итератор посимвольно читает информацию из потока. Хотя аргумент шаблона istreambufjterator наводит на мысль, что вместо char можно было бы извлечь, допустим, int, на самом деле это не так. Аргумент должен относиться к символьному типу - обычному (char) или расширенному.

После открытия файла итератор istreambufjterator с именем р присоединяется к потоку для чтения символов. Полученные слова сохраняются в множестве set<string> с именем wordhst.

Цикл while читает слова до тех пор, пока не обнаружит конец входного потока. Для проверки используется конструктор по умолчанию istreambufjterator, возвра-

Этот пример также был предложен Натаном Майерсом (Nathan Myers).

щающий конечный итератор end. Следовательно, если вы хотите проверить, не достиг ли итератор конца потока, можно воспользоваться простым условием р != end.

Вторая разновидность итераторов, встречающихся в программе, - итератор вставки insertjterator, с которым мы уже знакомы. Этот итератор вставляет новые объекты в контейнер. В данном случае контейнером является объект string с именем word, который с точки зрения insertjterator вполне подходит на роль контейнера. Конструктор insertjterator получает контейнер и итератор, установленный в начальную позицию вставки. Также можно было воспользоваться итератором backjnsertjterator, требующим, чтобы контейнер поддерживал функцию push back() (объект string ее поддерживает).

После завершения подготовки программа начинает поиск первого алфавитного символа и увеличивает start до тех пор, пока такой символ не будет найден. Далее символы копируются из одного итератора в другой до тех пор, пока не встретится неалфавитный символ. Каждое непустое значение word включается в wordlist.

Выделение лексем из потока

в рассмотренных примерах используются разные способы выделения слов (в более общем виде - лексем) из потока, ни один из которых не обладает достаточной гибкостью. Поскольку итераторы занимают центральное место в работе контейнеров и алгоритмов STL, наиболее гибкое решение также должно использовать итератор. Класс Tokenlterator представляет собой итератор-оболочку для любого другого итератора, выдающего символьные данные. Поскольку Tokenlterator несомненно принадлежит к числу итераторов ввода (самой примитивной категории итераторов), он может поставлять входные данные любому алгоритму STL. Такой итератор не только полезен сам по себе, но и является хорошим примером, на котором можно учиться разрабатывать собственные итераторы.

Класс Tokenlterator обладает двумя степенями свободы . Во-первых, он позволяет выбрать тип итератора, поставляющего символьные входные данные. Во-вторых, вместо простого определения символов-ограничителей Tokenlterator использует предикат - объект функции, оператор () которого получает char и решает, принадлежит ли он текущей лексеме. Хотя в двух приводимых примерах принадлежность символов к лексемам определяется статическим критерием, вы можете легко написать собственный объект функции, изменяющий свое состояние в процессе чтения символов.

Следующий заголовочный файл содержит два базовых предиката Isalpha и Delimiters, а также шаблон Tokenlterator:

: С07:Tokenlterator.h #ifndef TOKENITERATOR H Idefine TOKENITERATOR H linclude <algorithm> linclude <cctype> linclude <functional> linclude <iterator> linclude <string>

struct Isalpha : std::unary function<char. bool> {