Язык программирования C++. Вводный курс. С для начинающих

• Название: С для начинающих
• Дата: 24.08.2022
• Размер: 5.41 Mb.
• Имя файла: Язык программирования C++. Вводный курс.pdf
• Тип: Документы; #652350
• страница: 28 из 93

301
Контейнер set не допускает дублирования ключей. Поэтому можно гарантировать, что occurrence_lines не содержит повторений. Теперь нам достаточно перебрать данное множество, чтобы показать все номера строк, где встретилось данное слово:
}
(Полная реализация query_text() представлена в следующем разделе.)
Класс set поддерживает операции size(), empty() и erase() точно таким же образом, как и класс map, описанный выше. Кроме того, обобщенные алгоритмы предоставляют набор специфических функций для множеств, например set_union() (объединение) и set_difference()
(разность). (Они использованы при реализации языка запросов в главе 17.)
Упражнение 6.23
Добавьте в программу множество слов, в которых заключающее 's' не подчиняется общим правилам и не должно удаляться. Примерами таких слов могут быть Pythagoras,
Brahms и Burne_Jones. Включите в функцию suffix_s() из раздела 6.10 проверку этого набора.
Упражнение 6.24
Определите вектор, содержащий названия книг, которые вы собираетесь прочесть в ближайшие шесть виртуальных месяцев, и множество, включающее названия уже прочитанных произведений. Напишите программу, которая выбирает для вас книгу из вектора при условии, что вы ее еще не прочитали. Выбранное название программа должна заносить в множество прочитанных. Однако вы могли отложить книгу; следовательно, нужно обеспечить возможность удалять ее название из множества прочитанных. По окончании шести виртуальных месяцев распечатайте список прочитанного и непрочитанного.
6.14.
Окончательная программа
Ниже представлен полный текст программы, разработанной в этой главе, с двумя модификациями: мы инкапсулировали все структуры данных и функции в класс
TextQuery
(в последующих главах мы обсудим подобное использование классов), кроме того, текст был изменен, так как наш компилятор поддерживал стандарт С++ не полностью. register int size = occurrence_lines.size(); cout << "\n" << query_text
<< " встречается " << size
<< " раз(а):")
<< "\n\n"; set< short >::iterator it=occurrence_lines.begin(); for ( ; it != occurrence_lines.end(); ++it ) { int line = -it; cout << "\t( строка "
<< line + 1 << " ) "
<< (*text_file)[line] << endl;

С++ для начинающих
302
Например, библиотека iostream не соответствовала текущему стандарту. Шаблоны не поддерживали значения аргументов по умолчанию. Возможно, вам придется изменить кое-что в этой программе, чтобы она компилировалась в вашей системе.

С++ для начинающих
303
// стандартные заголовочные файлы С++
#include
#include
#include
#include
#include

С++ для начинающих
304
}
Упражнение 6.25
Объясните, почему нам потребовался специальный класс inserter для заполнения набора стоп-слов (это упоминается в разделе 6.13.1, а детально рассматривается в 12.4.1). inserter(exclusion_set, exclusion_set.begin() ));
Упражнение 6.26
Первоначальная реализация поисковой системы отражает процедурный подход: набор глобальных функций оперирует набором независимых структур данных. Окончательный вариант представляет собой альтернативный подход, когда мы инкапсулируем функции и данные в класс TextQuery. Сравните оба способа. Каковы недостатки и преимущества каждого?
Упражнение 6.27
В данной версии программы имя файла с текстом вводится по запросу. Более удобно было бы задавать его как параметр командной строки; в главе 7 мы покажем, как это делается. Какие еще параметры командной строки желательно реализовать?
6.15.
Контейнеры multimap и multiset
Контейнеры map и set не допускают повторяющихся значений ключей, а multimap
(мультиотображение) и multiset (мультимножество) позволяют сохранять ключи с дублирующимися значениями. Например, в телефонном справочнике может понадобиться отдельный список номеров для каждого абонента. В перечне книг одного автора может быть несколько названий, а в нашей программе с одним словом текста сопоставляется несколько позиций. Для использования multimap и multiset нужно включить соответствующий заголовочный файл – map или set: multiset< type > multisetName;
Для прохода по мультиотображению или мультимножеству можно воспользоваться комбинацией итератора, который возвращает find() (он указывает на первый найденный элемент), и значения, которое возвращает count(). (Это работает, поскольку в данных контейнерах элементы с одинаковыми ключами обязательно являются соседними). Например: set exclusion_set; ifstream infile( "exclusion_set" ); copy( default_excluded_words, default_excluded_words+25,
#include

С++ для начинающих
305
}
Более элегантный способ перебрать все значения с одинаковыми ключами использует специальную функцию-член equal_range(), которая возвращает пару итераторов. Один из них указывает на первое найденное значение, а второй – на следующее за последним найденным. Если последний из найденных элементов является последним в контейнере, второй итератор содержит величину, равную end():
#include

С++ для начинающих
306
}
Вставка и удаление элементов в multimap и multiset ничем не отличаются от аналогичных операций с контейнерами map и set. Функция equal_range() доставляет итераторную пару, задающую диапазон удаляемых элементов: authors.erase( pos.first, pos.second );
#include

С++ для начинающих
307
При каждом вызове функции-члена insert() добавляется новый элемент, даже если в контейнере уже был элемент с таким же ключом. Например: string( "Lost in the Funhouse" )));
Контейнер multimap не поддерживает операцию взятия индекса. Поэтому следующее выражение ошибочно: authors[ "Barth, John" ]; // ошибка: multimap
Упражнение 6.28
Перепишите программу текстового поиска из раздела 6.14 с использованием multimap для хранения позиций слов. Каковы производительность и дизайн в обоих случаях?
Какое решение вам больше нравится? Почему?
6.16.
Стек
В разделе 4.5 операции инкремента и декремента были проиллюстрированы на примере реализации абстракции стека. В общем случае стек является очень полезным механизмом для сохранения текущего состояния, если в разные моменты выполнения программы одновременно существует несколько состояний, вложенных друг в друга. Поскольку стек – это важная абстракция данных, в стандартной библиотеке С++ предусмотрен класс stack
, для использования которого нужно включить заголовочный файл:
#include
В стандартной библиотеке стек реализован несколько иначе, чем у нас. Разница состоит в том, что доступ к элементу с вершины стека и удаление его осуществляются двумя функциями – top() и pop(). Полный набор операций со стеком приведен в таблице 6.5.
Таблица 6.5. Операции со стеком
Операция
Действие
empty()
Возвращает true, если стек пуст, и false в противном случае size()
Возвращает количество элементов в стеке pop()
Удаляет элемент с вершины стека, но не возвращает его значения top()
Возвращает значение элемента с вершины typedef multimap::value_type valType; multimap authors;
// первый элемент с ключом Barth authors.insert( valType ( string( "Barth, John" ), string( "Sot-Weed Factor" )));
// второй элемент с ключом Barth authors.insert( va1Type( string( "Barth, John" ),

С++ для начинающих
308
стека, но не удаляет его push(item)
Помещает новый элемент в стек
В нашей программе приводятся примеры использования этих операций:
}
Объявление stack< int > intStack; определяет intStack как пустой стек, предназначенный для хранения элементов типа int
. Стек является надстройкой над некоторым контейнерным типом, поскольку реализуется с помощью того или иного контейнера. По умолчанию это deque, поскольку именно эта структура обеспечивает эффективную вставку и удаление первого элемента, а vector эти операции не поддерживает. Однако мы можем явно указать другой тип контейнера, задав его как второй параметр:
#include
#include int main()
{ const int ia_size = 10; int ia[ia_size ]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
// заполним стек int ix = 0; stack< int > intStack; for ( ; ix < ia_size; ++ix ) intStack.push( ia[ ix ] ); int error_cnt = 0; if ( intStack.size() != ia_size ) { cerr << "
Ошибка! неверный размер IntStack: "
<< intStack.size()
<< "\t ожидается: " << ia_size << endl,
++error_cnt;
} int value; while ( intStack.empty() == false )
{
// считаем элемент с вершины value = intStack.top(); if ( value != --ix ) { cerr << "
Ошибка! ожидается " << ix
<< " получено " << value << endl;
++error_cnt;
}
// удалим элемент intStack.pop();
} cout << "
В результате запуска программы получено "
<< error_cnt << " ошибок" << endl;

С++ для начинающих
309
stack< int, list > intStack;
Элементы, добавляемые в стек, копируются в реализующий его контейнер. Это может приводить к потере эффективности для больших или сложных объектов, особенно если мы только читаем элементы. В таком случае удобнее определить стек указателей на объекты. Например: stack< NurbSurface* > surf_Stack;
К двум стекам одного типа можно применять операции сравнения: равенство, неравенство, меньше, больше, меньше или равно, больше или равно, если они определены над элементами стека. Элементы сопоставляются попарно. Первая пара несовпадающих элементов определяет результат операции сравнения в целом.
Стек будет использован в нашей программе текстового поиска в разделе 17.7 для поддержки сложных запросов типа
Civil && ( War || Rights )
6.17.
Очередь и очередь с приоритетами
Абстракция очереди реализует метод доступа FIFO (first in, first out – “первым вошел, первым вышел”): объекты добавляются в конец очереди, а извлекаются из начала.
Стандартная библиотека предоставляет две разновидности этого метода: очередь FIFO, или простая очередь, и очередь с приоритетами, которая позволяет сопоставлять элементы с их приоритетами. Текущий элемент помещается не в конец такой очереди, а перед элементами с более низким приоритетом. Программист, определяющий такую структуру, задает способ вычисления приоритетов. В реальной жизни подобное можно увидеть, скажем, при регистрации багажа в аэропорту. Как правило, пассажиры, чей рейс через 15 минут, передвигаются в начало очереди, чтобы не опоздать на самолет.
Примером из практики программирования служит планировщик операционной системы, определяющий последовательность выполнения процессов.
Для использования queue и priority_queue необходимо включить заголовочный файл:
#include
Полный набор операций с контейнерами queue и priority_queue приведен в таблице
6.6.
Таблица 6.6. Операции с queue и priority_queue
Операция
Действие
empty()
Возвращает true, если очередь пуста, и false в противном случае
#include class NurbSurface { /* mumble */ };

С++ для начинающих
310
size()
Возвращает количество элементов в очереди pop()
Удаляет первый элемент очереди, но не возвращает его значения. Для очереди с приоритетом первым является элемент с наивысшим приоритетом front()
Возвращает значение первого элемента очереди, но не удаляет его. Применимо только к простой очереди back()
Возвращает значение последнего элемента очереди, но не удаляет его. Применимо только к простой очереди top()
Возвращает значение элемента с наивысшим приоритетом, но не удаляет его.
Применимо только к очереди с приоритетом push(item)
Помещает новый элемент в конец очереди.
Для очереди с приоритетом позиция элемента определяется его приоритетом.
Элементы priority_queue отсортированы в порядке убывания приоритетов. По умолчанию упорядочение основывается на операции “меньше”, определенной над парами элементов. Конечно, можно явно задать указатель на функцию или объект-функцию, которая будет использоваться для сортировки. (В разделе 12.3 можно найти более подробное объяснение и иллюстрации использования такой очереди.)
6.18.
Вернемся в классу iStack
У класса iStack, разработанного нами в разделе 4.15, два недостатка:
•
он поддерживает только тип int. Мы хотим обеспечить поддержку любых типов. Это можно сделать, преобразовав наш класс в шаблон класса Stack;
•
он имеет фиксированную длину. Это неудобно в двух отношениях: заполненный стек становится бесполезным, а в попытке избежать этого мы окажемся перед необходимостью отвести ему изначально слишком много памяти.
Разумным выходом будет разрешить динамический рост стека. Это можно сделать, пользуясь тем, что лежащий в основе стека вектор способен динамически расти.
Напомним определение нашего класса iStack:

С++ для начинающих
311
};
Сначала реализуем динамическое выделение памяти. Тогда вместо использования индекса при вставке и удалении элемента нам нужно будет применять соответствующие функции-члены. Член _top больше не нужен: функции push_back() и pop_back() автоматически работают в конце массива. Вот модифицированный текст функций pop() и push():
}
Функции-члены empty(), size() и full() также нуждаются в изменении: в этой версии они теснее связаны с лежащим в основе стека вектором. return _stack.max_size() == _stack.size(); }
Надо немного изменить функцию-член display(), чтобы _top больше не фигурировал в качестве граничного условия цикла.
#include class iStack { public: iStack( int capacity )
: _stack( capacity ), _top( 0 ) {}; bool pop( int &value ); bool push( int value ); bool full(); bool empty(); void display(); int size(); private: int _top; vector< int > _stack; bool iStack::pop( int &top_value )
{ if ( empty() ) return false; top_value = _stack.back(); _stack.pop_back(); return true;
} bool iStack::push( int value )
{ if ( full() ) return false;
_stack.push_back( value ); return true; inline bool iStack::empty(){ return _stack.empty(); } inline bool iStack::size() { return _stack.size(); } inline bool iStack::full() {

С++ для начинающих
312
}
Наиболее существенным изменениям подвергнется конструктор iStack. Никаких действий от него теперь не требуется. Можно было бы определить пустой конструктор: inline iStack::iStack() {}
Однако это не совсем приемлемо для пользователей нашего класса. До сих пор мы строго сохраняли интерфейс класса iStack, и если мы хотим сохранить его до конца, необходимо оставить для конструктора один необязательный параметр. Вот как будет выглядеть объявление конструктора с таким параметром типа int:
};
Что делать с аргументом, если он задан? Используем его для указания емкости вектора:
}
Превращение класса в шаблон еще проще, в частности потому, что лежащий в основе вектор сам является шаблоном. Вот модифицированное объявление: void iStack::display()
{ cout << "( " << size() << " )( bot: "; for ( int ix=0; ix < size(); ++ix ) cout << _stack[ ix ] << " "; cout << " stop )\n"; class iStack { public: iStack( int capacity = 0 );
// ... inline iStack::iStack( int capacity )
{ if ( capacity )
_stack.reserve( capacity );
#include template class Stack { public:
Stack( int capacity=0 ); bool pop( elemType &value ); bool push( elemType value ); bool full(); bool empty(); void display(); int size(); private: vector< elemType > _stack;

С++ для начинающих