С помощью контейнера STL map (словарь) мы можем хранить все слова в сбалансированном двоичном дереве поиска (что делает поиск очень быстрой операцией), не программируя самостоятельно функциональность такого дерева. Каждый узел дерева содержит слово (используемое в качестве ключа) вместе с множеством номеров строк. В терминологии STL каждый элемент словаря является парой (first, second), где

first = слово; представляется типом string; second = множество номеров строк; представляется типом set<int>.

Имя входного файла также будет содержаться в переменной типа string; полностью программа приведена ниже:

concord.срр: Сводный указатель, использующий словари,

множества и строки.

iinclude <iostream>

iinclude <fstream>

iinclude <iomanip>

iinclude <ctype.h>

iinclude <string>

iinclude <set>

iinclude <map>

using namespace std;

typedef set<int, less<int> > settype;

typedef map<string, settype, less<string> > maptype;

bool wordreadiifstream sifstr, string Sword,

int slinenr) { char ch;

найдем первую букву:

for (;;)

{ ifstr.get(ch);

if (ifstr.failO) return false; if (isalpha(ch)) break; if (ch == \n) linenr++;

return true;

int mainO { maptype M;

maptype::iterator im;

settype::iterator,is, isbegin, isend;

string inpfilename, word;

ifstream ifstr;

int linenr = 1;

cout << Enter name of input file: ; cin inpfilename; ifstr.open(inpfilename.c str()); if (lifstr)

{ cout Cannot open input file.\n ; exit(l); }

while (wordread(ifstr, word, linenr)) { im = M.find(word); if (im == M.endO )

im = M.insert(maptype::value type(word, settype())).first; (*im).second.insert(linenr);

for (im = M.beginO; im != M.endO; im++) { cout setiosflags(ios::left) setw(15) (*im).first.c str(); isbegin = (*im).second.begin(); isend = (*im).second.end(); for (is=isbegin; is != isend; is++)

cout << << *is; cout << endl;

return 0;

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

word = ;

найдем первый небуквенный символ: do

{ word += tolower(ch);

ifstr.get(ch); } while (!ifstr.fail{) && isalpha(ch)); if (ifstr.failO ) return false; ifstr.putback(ch); ch может быть \n

Приведенный ниже фрагмент программы создает полный словарь, содержащий основные данные:

while {wordread{ifstr, word, linenr)) { im = M.find(word); if (im == M.endO )

im = M.insert(maptype::value type(word, settype{))).first; {*im).second.insert(linenr);

Вызов wordread(ifstr, word, linenr) читает, если это возможно, следующее слово из потока ifstr. Он возвращает true, если слово было прочитано успешно, и false, если встретился конец файла. После этого мы с помощью функции find проверим, присутствует ли прочитанное слово в словаре. Теперь мы различаем два случая: слово найдено или не найдено. Вспомним, что элемент словаря состоит из слова и множества номеров строк. Если слово найдено в словаре, текущий номер строки добавляется в множество номеров строк; каким именно образом, мы увидим ниже. Если слово не найдено, возвращенный функцией итератор im равен M.endQ, и сначала нам нужно добавить новый элемент словаря, состоящий из нового слова и пустого множества. Этого мы достигаем с помощью довольно сложного оператора, располагающегося на двух строках программы; он имеет следующий вид:

im = М.insert(ххх).first;

Рассматриваемый вызов возвращает пару (iterator, true), поскольку нам известно, что ключ пока отсутствует в словаре. Значение итератора из этой пары, указывающее на позицию только что добавленного элемента, присваивается переменной im. В приведенной выше записи ххх заменяет собой пару (k, d), где k является новым словом, ad - пустым множеством, которое записано в программе в виде выражения settypeQ. Напомним, что это выражение вызывает конструктор по умолчанию для типа settype, который является типом используемых нами множеств. Для пары (k, d) = ххх мы в действительности пишем

maptype::value type(word, settype{))

(тип value J.ype мы обсуждали в разделах 2.7, 2.10 и 3.1). Теперь в любом из двух упоминавшихся случаев im указывает на элемент словаря, который содержит рассматриваемое слово как (*im).first. В соответствующее множество (*im)second текущий номер строки добавляется с помощью оператора

(*im).second.insert(linenr);