Язык программирования C++. Пятое издание - Стенли Липпман

uninitialized_fill_n(q, vi.size(), 42);

Подобно алгоритму copy() (см. раздел 10.2.2), алгоритм uninitialized_copy() получает три итератора. Первые два обозначают исходную последовательность, а третий обозначает получателя, в который будут скопированы эти элементы. Итератор назначения, переданный алгоритму uninitialized_copy(), должен обозначить незаполненную память. В отличие от алгоритма copy(), алгоритм uninitialized_copy() создает элементы в своем получателе.

Подобно алгоритму copy(), алгоритм uninitialized_copy() возвращает (приращенный) итератор назначения. Таким образом, вызов функции uninitialized_copy() возвращает указатель на следующий элемент после последнего заполненного. В данном примере этот указатель сохраняется в переменной q, передаваемой функции uninitialized_fill_n(). Эта функция, как и функция fill_n() (см. раздел 10.2.2), получает указатель на получателя, количество и значение. Она создает заданное количество объектов из заданного значения в позиции, начиная с заданной получателем.

Упражнения раздела 12.2.2

Упражнение 12.26. Перепишите программу из начала раздела, используя класс allocator.

12.3. Использование библиотеки: программа запроса текста

Для завершения обсуждения библиотеки реализуем простую программу текстового запроса. Она позволит пользователю искать в заданном файле слова, которые могли встречаться в нем. Результатом запроса будет количество экземпляров слова и список строк, в которых оно присутствует. Если слово встречается несколько раз в той же строке, то она отображается только однажды. Строки отображаются в порядке возрастания, т.е. строка номер 7 отображается перед строкой номер 9 и т.д.

Например, прочитав файл, содержащий начало этой главы и запустив поиск слова element, программа должна создать следующий вывод:

element occurs 112 times

 (line 36) A set element contains only a key;

 (line 158) operator creates a new element

 (line 160) Regardless of whether the element

 (line 168) When we fetch an element from a map, we

 (line 214) If the element is not found, find returns

Далее следует примерно 100 строк, также содержащих слово element.

12.3.1. Проект программы

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

• Читая ввод, программа должна запоминать строку (строки), в которой присутствует искомое слово. Следовательно, программа должна читать ввод построчно и разделять прочитанные строки на отдельные слова

• При создании вывода программа должна:

  • получать номера строк, содержащих искомое слово;

  • нумеровать строки в порядке возрастания без дубликатов;

  • отображать текст исходного файла по заданному номеру строки.

Эти требования можно выполнить с помощью библиотечных средств.

• Для хранения копии всего входного файла используем вектор vector<string>. Каждая строка входного файла станет элементом этого вектора. При необходимости вывода строку можно будет выбрать, используя ее номер как индекс.

• Для разделения строки на слова используем строковый поток istringstream (см. раздел 8.3).

• Для хранения номеров строк, в которых присутствует искомое слово, используем контейнер set. Это гарантирует, что каждая строка будет присутствовать только однажды, а номера строки будут храниться в порядке возрастания.

• Для связи каждого слова с набором номеров строк, в которых присутствует искомое слово, используем контейнер map. Это позволит выбрать соответствующий набор для каждого заданного слова.

По рассматриваемым вскоре причинам в решении будет также использован указатель shared_ptr.

Структуры данных

Несмотря на то что программу можно было бы написать, используя контейнеры vector, set и map непосредственно, полезней определить более абстрактное решение. Для начала разработаем класс для содержания входного файла, чтобы упростить запрос. Этот класс, TextQuery, будет содержать вектор и карту. Вектор будет содержать текст входного файла, а карта ассоциировать каждое слово в этом файле с набором номеров строк, в которых присутствует искомое слово. У этого класса будет конструктор, читающий заданный входной файл, и функция, обрабатывающая запросы.

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

Проще всего вернуть все эти данные, определив второй класс, назовем его QueryResult, который и будет содержать результаты запроса. У этого класса будет функция print(), выводящая результаты, хранимые в объекте класса QueryResult.

Совместное использование данных классами

Класс QueryResult предназначен для представления результатов запроса. Эти результаты включают набор номеров строк, связанных с искомым словом, и текст соответствующих строк из входного файла. Эти данные хранятся в объектах типа TextQuery.

Поскольку данные, необходимые объекту класса QueryResult, хранятся в объекте класса TextQuery, необходимо решить, как получить к ним доступ. Можно было бы скопировать набор номеров строк, но это может оказаться слишком дорого. Кроме того, копировать вектор не хотелось бы потому, что это повлечет за собой копирование всего файла для вывода лишь его части (как обычно и бывает).

Избежать копирования можно, возвратив итераторы (или указатели) на содержимое объекта TextQuery. Но с этим подходом связана проблема: что если объект класса TextQuery будет удален до объекта класса QueryResult? В этом случае объект класса QueryResult ссылался бы на данные в больше не существующем объекте.

Это требует синхронизации продолжительности существования объекта класса QueryResult с объектом класса TextQuery, результаты которого он представляет. Таким образом, эти два класса концептуально "совместно используют" данные. Для отражения совместного использования этих структур данных используем указатели shared_ptr (см. раздел 12.1.1).

Применение класса TextQuery

При разработке класса может быть полезно написать использующие его программы, прежде чем фактически реализовать его члены. Таким образом можно выяснить, какие функции ему необходимы. Например, следующая программа использует проектируемые классы TextQuery и QueryResult. Эта функция получает поток класса ifstream для подлежащего обработке файла и взаимодействует с пользователем, выводя результаты по заданному слову:

void runQueries(ifstream &infile) {

 // infile - поток ifstream для входного файла

 TextQuery tq(infile); // хранит файл и строит карту запроса

 // цикл взаимодействия с пользователем: приглашение ввода искомого

 // слова и вывод результатов

 while (true) {

  cout << "enter word to look for, or q to quit: ";

  string s;

  // остановиться по достижении конца файла или при встрече

  // символа 'q' во вводе

  if (!(cin >> s) || s == "q") break;

  // выполнить запрос и вывести результат

  print(cout, tq.query(s)) << endl;

 }

}

Начнем с инициализации объекта tq класса TextQuery данными из переданного потока ifstream. Конструктор TextQuery() читает файл в свой вектор и создает карту, связывающую слова из ввода с номерами строк, в которых они присутствуют.

Цикл while (непрерывно) запрашивает у пользователя искомое слово и выводит полученные результаты. Условие цикла проверяет литерал true (см. раздел 2.1.3), поэтому оно всегда истинно. Для выхода из цикла используется оператор break (см. раздел 5.5.1) в операторе if. Он проверяет успешность чтения. Если оно успешно, проверяется также, не ввел ли пользователь символ "q", желая завершить работу. Получив искомое слово, запрашиваем его поиск у объекта tq, а затем вызываем функцию print() для вывода результата поиска.

Упражнения раздела 12.3.1

Упражнение 12.27. Классы TextQuery и QueryResult используют только те возможности, которые уже были описаны ранее. Не заглядывая вперед, напишите собственные версии этих классов.