| Меню сайта |
|
 |
| Категория |
|
|
| Развлечение |
|
|
| ON - LINE |
|
|
| Опрос |
|
|
| Оbserver Ward |
Онлайн всего: 1 Гостей: 1 Пользователей: 0
|
|
| Друзья сайта |
|
|
| Hаша кнопка |
Для обмена банерами , наша кнопка для размещения у вас на сайте
|
|
|
6. Абстрактные контейнерные типы (4)
6.14. Окончательная программа
Ниже представлен полный текст программы, разработанной в этой главе, с двумя модификациями: мы инкапсулировали все структуры данных и функции в класс TextQuery (в последующих главах мы обсудим подобное использование классов), кроме того, текст был изменен, так как наш компилятор поддерживал стандарт С++ не полностью.
Например, библиотека iostream не соответствовала текущему стандарту. Шаблоны не поддерживали значения аргументов по умолчанию. Возможно, вам придется изменить кое-что в этой программе, чтобы она компилировалась в вашей системе.
// стандартные заголовочные файлы С++
#include <algorithm>
#include <string>
#include <vector>
#include <utility>
#include <map>
#include <set>
// заголовочный файл iostream, не отвечающий стандарту
#include <fstream.h>
// заголовочные файлы С
#include <stddef.h>
#include <ctype.h>
// typedef для удобства чтения
typedef pair<short,short> location;
typedef vector<location,allocator> loc;
typedef vector<string,allocator> text;
typedef pair<text*,loc*> text_loc;
class TextQuery {
public:
TextQuery() { memset( this, 0, sizeof( TextQuery )); }
static void
filter_elements( string felems ) { filt_elems = felems; }
void query_text();
void display_map_text();
void display_text_locations();
void doit() {
retrieve_text();
separate_words();
filter_text();
suffix_text();
strip_caps();
build_word_map();
}
private:
void retrieve_text();
void separate_words():
void filter_text();
void strip_caps();
void suffix_textQ;
void suffix_s( string& );
void build_word_map();
private:
vector<string,allocator> *lines_of_text;
text_loc *text_locations;
map< string,loc*,
less<string>,allocator> *word_map;
static string filt_elems;
};
string TextQuery::filt_elems( "\", •;: !?)(\V" );
int main()
{
TextQuery tq;
tq.doit();
tq.query_text();
tq.display_map_text();
}
void
TextQuery::
retrieve_text()
{
string file_name;
cout << "please enter file name: ";
cin >> file_name;
ifstream infile( file_name.c_str(), ios::in );
if ( !infile ) {
cerr << "oops' unable to open file "
<< file_name << " -- bailing out!\n";
exit( -1 );
}
else cout << "\n";
lines_of_text = new vector<string,allocator>;
string textline;
while ( getline( infile, textline, '\n' ))
lines_of_text->push_back( textline );
}
void
TextQuery::
separate_words()
{
vector<string,allocator> *words =
new vector<string,allocator>;
vector<location,allocator> *locations =
new vector<location,allocator>;
for ( short line_pos = 0; line_pos < lines_of_text->size();
line_pos++ )
{
short word_pos = 0;
string textline = (*lines_of_text)[ line_pos ];
string::size_type eol = textline.1ength();
string::size_type pos = 0, prev_pos = 0;
while (( pos = textline.find_first_of( ' ', pos ))
!= string::npos )
{
words->push_back(
textline.substr( prev_pos, pos - prev_pos ));
locations->push_back(
make_pair( line_pos, word_pos ));
word_pos++; pos++; prev_pos = pos;
}
words->push_back(
textline.substr( prev_pos, pos - prev_pos ));
locations->push_back(make_pair(line_pos,word_pos));
}
text_locations = new text_loc( words, locations );
}
void
TextQuery::
filter_text()
{
if ( filt_elems.empty() )
return;
vector<string,allocator> *words = text_locations->first;
vector<string,allocator>::iterator iter = words->begin();
vector<string,allocator>::iterator iter_end = words->end();
while ( iter != iter_end )
{
string::size_type pos = 0;
while ((pos = (*iter).find_first_of(filt_elems, pos))
!= string::npos )
(*iter).erase(pos,l);
++iter;
}
}
void
TextQuery::
suffix_text()
{
vector<string,allocator> *words = text_locations->first;
vector<string,allocator>::iterator iter = words->begin();
vector<string,allocator>::iterator iter_end = words->end() ;
while ( iter != iter_end ) {
if ( (*iter).size() <= 3 )
{ iter++; continue; }
if ( (*iter)[ (*iter).size()-l ] == 's' )
suffix_s( *iter );
// дополнительная обработка суффиксов...
iter++;
}
}
void
TextQuery::
suffix_s( string &word )
{
string::size_type spos = 0;
string::size_type pos3 = word.size()-3;
// "ous", "ss", "is", "ius"
string suffixes( "oussisius" );
if ( ! word.compare( pos3, 3, suffixes, spos, 3 ) ||
! word.compare( pos3, 3, suffixes, spos+6, 3) ||
! word.compare( pos3+l, 2, suffixes, spos+2, 2 ) ||
! word.compare( pos3+l, 2, suffixes, spos+4, 2 ))
return;
string ies( "ies" );
if ( ! word.compare( pos3, 3, ies ))
{
word.replace( pos3, 3, 1, 'у' );
return;
}
string ses( "ses" );
if ( ! word.compare( pos3, 3, ses ))
{
word.erase( pos3+l, 2 );
return;
}
// удалим 's' в конце
word.erase( pos3+2 );
// удалим "'s"
if ( word[ pos3+l ] == '\'' )
word.erase( pos3+l );
}
void
TextQuery::
strip_caps()
{
vector<string,allocator> *words = text_locations->first;
vector<string,allocator>::iterator iter = words->begin();
vector<string,allocator>::iterator iter_end = words->end();
string caps( "ABCDEFGHI3KLMNOPQRSTUVWXYZ" );
while ( iter != iter_end ) {
string::size_type pos = 0;
while (( pos = (*iter).find_first_of( caps, pos ))
!= string::npos )
(*iter)[ pos ] = to1ower( (*iter)[pos] );
++iter;
}
}
void
TextQuery::
build_word_map()
{
word_map = new map<string,loc*,less<string>,allocator>;
typedef map<string,loc*,less<string>,allocator>::value_type
value_type;
typedef set<string,less<string>,allocator>::difference_type
diff_type;
set<string,less<string>,allocator> exclusion_set;
ifstream infile( "exclusion_set" );
if ( !infile )
{
static string default_excluded_words[25] = {
"the","and","but","that","then","are","been",
"can","can't","cannot","could","did","for",
"had","have","him","his","her","its"."into",
"were","which","when","with","would"
};
cerr << "warning! unable to open word exclusion file! -- "
<< "using default set\n";
copy( default_excluded_words,
default_excluded_words+25,
inserter(exclusion_set, exclusion_set.begin()));
}
else {
istream_iterator< string, diff_type >
input_set( infile ), eos;
copy( input_set, eos,
inserter( exclusion_set, exclusion_set.begin() ));
}
// пробежимся по всем словам, вставляя пары
vector<string,allocator> *text_words =
text_locations->first;
vector<location,allocator> *text.locs =
text_locations->second;
register int elem_cnt = text_words->size();
for ( int ix = 0; ix < elem_cnt; ++-ix )
{
string textword = ( *text_words )[ ix ];
if ( textword.size() < 3 ||
exclusion_set.count( textword ))
continue;
if ( ! word_map->count((*text_words)[ix] ))
{ // слово отсутствует, добавим:
loc *ploc = new vector<location,allocator>;
ploc->push_back( (*text_locs)[ix] );
word_map->insert( value_type( (*text_words)[ix],ploc ));
}
else (*word_map) [(*text_words) [ix]]->
push_back( (*text_locs) [ix] );
}
}
void
TextQuery::
query_text()
{
string query_text;
do {
cout
<< "enter a word against which to search the text.\n"
<< "to quit, enter a single character ==> ";
cin >> query_text;
if ( query_text.size() < 2 ) break;
string caps( "ABCDEFGHIJKLMNOPQRSTUVWXYZ" );
string::size_type pos = 0;
while (( pos = query_text.find_first_of( caps, pos ))
!= string::npos )
query_text[ pos ] = to1ower( query_text[pos] );
// query_text должно быть введено
if ( !word_map->count( query_text )) {
cout << "\nSorry. There are no entries for "
<< query_text << ".\n\n";
continue;
}
loc *ploc = (*word_map) [ query_text ];
set<short,less<short>,allocator> occurrence_1i nes;
loc::iterator liter = ploc->begin(),
liter_end = ploc->end();
while ( liter != liter_end ) {
occurrence_lines.1nsert(
occurrence_lines.end(), (*liter).first);
++liter;
}
register int size = occurrence_lines.size();
cout << "\n" << query_text
<< " occurs " << size
<< (size == 1 ? " time:" : " times:")
<< "\n\n";
set<short,less<short>,allocator>::iterator
it=occurrence_lines.begin();
for ( ; it != occurrence_"lines.end(); ++it ) {
int line = *it;
cout << "\t( line "
// будем нумеровать строки с 1,
// как это принято везде
<< line + 1 << " ) "
<< (*lines_of_text)[line] << endl;
}
cout << endl;
}
while ( ! query_text.empty() );
cout << "Ok, bye!\n";
}
void
TextQuery::
display_map_text()
{
typedef map<string,loc*, less<string>, allocator> map_text;
map_text::iterator iter = word_map->begin(),
iter_end = word_map->end();
while ( iter != iter_end ) {
cout << "word: " << (*iter).first << " (";
int loc_cnt = 0;
loc *text_locs = (*iter).second;
loc::iterator liter = text_locs->begin(),
liter_end = text_locs->end();
while ( liter != liter_end )
{
if ( loc_cnt )
cout << ",";
else ++loc_cnt;
cout << "(" << (*liter).first
<< "," << (*liter).second << ")";
++"liter;
}
cout << ")\n";
++iter;
}
cout << endl;
}
void
TextQuery::
disp1ay_text_locations()
{
vector<string,allocator> *text_words =
text_locations->first;
vector<location,allocator> *text_locs =
text_locations->second;
register int elem_cnt = text_words->size();
if ( elem_cnt != text_locs->size() )
{
cerr
<< "oops! internal error: word and position vectors "
<< "are of unequal size\n"
<< "words: " << elem_cnt << " "
<< "locs: " << text_locs->size()
<< " -- bailing out!\n";
exit( -2 );
}
for ( int ix=0; ix < elem_cnt; ix++ )
{
cout << "word: " << (*text_words)[ ix ] << "\t"
<< "location: ("
<< (*text_locs)[ix].first << ","
<< (*text.locs)[ix].second << ")"
<< "\n";
}
cout << endl;
}
Упражнение 6.25
Объясните, почему нам потребовался специальный класс inserter для заполнения набора стоп-слов (это упоминается в разделе 6.13.1, а детально рассматривается в 12.4.1).
set<string> exclusion_set;
ifstream infile( "exclusion_set" );
copy( default_excluded_words, default_excluded_words+25,
inserter(exclusion_set, exclusion_set.begin() ));
Упражнение 6.26
Первоначальная реализация поисковой системы отражает процедурный подход: набор глобальных функций оперирует набором независимых структур данных. Окончательный вариант представляет собой альтернативный подход, когда мы инкапсулируем функции и данные в класс TextQuery. Сравните оба способа. Каковы недостатки и преимущества каждого?
Упражнение 6.27
В данной версии программы имя файла с текстом вводится по запросу. Более удобно было бы задавать его как параметр командной строки; в главе 7 мы покажем, как это делается. Какие еще параметры командной строки желательно реализовать?
6.15. Контейнеры multimap и multiset
Контейнеры map и set не допускают повторяющихся значений ключей, а multimap (мультиотображение) и multiset (мультимножество) позволяют сохранять ключи с дублирующимися значениями. Например, в телефонном справочнике может понадобиться отдельный список номеров для каждого абонента. В перечне книг одного автора может быть несколько названий, а в нашей программе с одним словом текста сопоставляется несколько позиций. Для использования multimap и multiset нужно включить соответствующий заголовочный файл – map или set:
#include <map>
multimap< key_type, value_type > multimapName;
Для прохода по мультиотображению или мультимножеству можно воспользоваться комбинацией итератора, который возвращает find() (он указывает на первый найденный элемент), и значения, которое возвращает count(). (Это работает, поскольку в данных контейнерах элементы с одинаковыми ключами обязательно являются соседними). Например:
#include <map>
#include <string>
void code_fragment()
{
multimap< string, string > authors;
string search_item( "Alain de Botton" );
// ...
int number = authors.count( search_item );
mu1timap< string,string >::iterator iter;
iter = authors.find( search_item );
for ( int cnt = 0; cnt < number; ++cnt, ++-iter )
do_something( *iter );
// ...
}
Более элегантный способ перебрать все значения с одинаковыми ключами использует специальную функцию-член equal_range(), которая возвращает пару итераторов. Один из них указывает на первое найденное значение, а второй – на следующее за последним найденным. Если последний из найденных элементов является последним в контейнере, второй итератор содержит величину, равную end():
#include <map>
#include <string>
#include <utility>
void code_fragment()
{
multimap< string, string > authors;
// ...
string search_item( "Haruki Murakami" );
while ( cin && cin >> search_item )
switch ( authors.count( search_item ))
{
// не найдено
case 0:
break;
// найден 1, обычный find()
case 1: {
multimap< string, string >: iterator iter;
iter = authors.find( search_item );
// обработка элемента ...
break;
}
// найдено несколько ...
default:
{
typedef multimap<string,string>::iterator iterator;
pair< iterator, iterator > pos;
// pos.first - адрес 1-го найденного
// pos.second - адрес 1-го отличного
// от найденного
pos = authors.equa1_range( search_item );
for (; pos.first != pos.second; pos.first++ )
// обработка элемента ...
}
}
}
Вставка и удаление элементов в multimap и multiset ничем не отличаются от аналогичных операций с контейнерами map и set. Функция equal_range() доставляет итераторную пару, задающую диапазон удаляемых элементов:
#include <multimap>
#include <string>
typedef multimap< string, string >::iterator iterator;
pair< iterator, iterator > pos;
string search_item( "Kazuo Ishiguro" );
// authors - multimap<string, string>
// эквивалентно
// authors.erase( search_item );
pos = authors.equa1_range( search_item );
authors.erase( pos.first, pos.second );
При каждом вызове функции-члена insert() добавляется новый элемент, даже если в контейнере уже был элемент с таким же ключом. Например:
typedef multimap<string,string>::value_type valType;
multimap<string,string> authors;
// первый элемент с ключом Barth
authors.insert( valType (
string( "Barth, John" ),
string( "Sot-Weed Factor" )));
// второй элемент с ключом Barth
authors.insert( va1Type(
string( "Barth, John" ),
string( "Lost in the Funhouse" )));
Контейнер multimap не поддерживает операцию взятия индекса. Поэтому следующее выражение ошибочно:
authors[ "Barth, John" ]; // ошибка: multimap
Упражнение 6.28
Перепишите программу текстового поиска из раздела 6.14 с использованием multimap для хранения позиций слов. Каковы производительность и дизайн в обоих случаях? Какое решение вам больше нравится? Почему?
6.16. Стек
В разделе 4.5 операции инкремента и декремента были проиллюстрированы на примере реализации абстракции стека. В общем случае стек является очень полезным механизмом для сохранения текущего состояния, если в разные моменты выполнения программы одновременно существует несколько состояний, вложенных друг в друга. Поскольку стек – это важная абстракция данных, в стандартной библиотеке С++ предусмотрен класс stack, для использования которого нужно включить заголовочный файл:
#include <stack>
В стандартной библиотеке стек реализован несколько иначе, чем у нас. Разница состоит в том, что доступ к элементу с вершины стека и удаление его осуществляются двумя функциями – top() и pop(). Полный набор операций со стеком приведен в таблице 6.5.
Таблица 6.5. Операции со стеком
Операция Действие
empty() Возвращает true, если стек пуст, и false в противном случае
size() Возвращает количество элементов в стеке
pop() Удаляет элемент с вершины стека, но не возвращает его значения
top() Возвращает значение элемента с вершины стека, но не удаляет его
push(item) Помещает новый элемент в стек
В нашей программе приводятся примеры использования этих операций:
#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;
}
Объявление
stack< int > intStack;
определяет intStack как пустой стек, предназначенный для хранения элементов типа int. Стек является надстройкой над некоторым контейнерным типом, поскольку реализуется с помощью того или иного контейнера. По умолчанию это deque, поскольку именно эта структура обеспечивает эффективную вставку и удаление первого элемента, а vector эти операции не поддерживает. Однако мы можем явно указать другой тип контейнера, задав его как второй параметр:
stack< int, list<int> > intStack;
Элементы, добавляемые в стек, копируются в реализующий его контейнер. Это может приводить к потере эффективности для больших или сложных объектов, особенно если мы только читаем элементы. В таком случае удобнее определить стек указателей на объекты. Например:
#include <stack>
class NurbSurface { /* mumble */ };
stack< NurbSurface* > surf_Stack;
К двум стекам одного типа можно применять операции сравнения: равенство, неравенство, меньше, больше, меньше или равно, больше или равно, если они определены над элементами стека. Элементы сопоставляются попарно. Первая пара несовпадающих элементов определяет результат операции сравнения в целом.
Стек будет использован в нашей программе текстового поиска в разделе 17.7 для поддержки сложных запросов типа
Civil && ( War || Rights )
6.17. Очередь и очередь с приоритетами
Абстракция очереди реализует метод доступа FIFO (first in, first out – "первым вошел, первым вышел”): объекты добавляются в конец очереди, а извлекаются из начала. Стандартная библиотека предоставляет две разновидности этого метода: очередь FIFO, или простая очередь, и очередь с приоритетами, которая позволяет сопоставлять элементы с их приоритетами. Текущий элемент помещается не в конец такой очереди, а перед элементами с более низким приоритетом. Программист, определяющий такую структуру, задает способ вычисления приоритетов. В реальной жизни подобное можно увидеть, скажем, при регистрации багажа в аэропорту. Как правило, пассажиры, чей рейс через 15 минут, передвигаются в начало очереди, чтобы не опоздать на самолет. Примером из практики программирования служит планировщик операционной системы, определяющий последовательность выполнения процессов.
Для использования queue и priority_queue необходимо включить заголовочный файл:
#include <queue>
Полный набор операций с контейнерами queue и priority_queue приведен в таблице 6.6.
Таблица 6.6. Операции с queue и priority_queue
Операция Действие
empty()
Возвращает true, если очередь пуста, и false в противном случае
size()
Возвращает количество элементов в очереди
pop()
Удаляет первый элемент очереди, но не возвращает его значения. Для очереди с приоритетом первым является элемент с наивысшим приоритетом
front()
Возвращает значение первого элемента очереди, но не удаляет его. Применимо только к простой очереди
back()
Возвращает значение последнего элемента очереди, но не удаляет его. Применимо только к простой очереди
top()
Возвращает значение элемента с наивысшим приоритетом, но не удаляет его. Применимо только к очереди с приоритетом
push(item)
Помещает новый элемент в конец очереди. Для очереди с приоритетом позиция элемента определяется его приоритетом.
Элементы priority_queue отсортированы в порядке убывания приоритетов. По умолчанию упорядочение основывается на операции "меньше”, определенной над парами элементов. Конечно, можно явно задать указатель на функцию или объект-функцию, которая будет использоваться для сортировки. (В разделе 12.3 можно найти более подробное объяснение и иллюстрации использования такой очереди.)
6.18. Вернемся в классу iStack
У класса iStack, разработанного нами в разделе 4.15, два недостатка:
* он поддерживает только тип int. Мы хотим обеспечить поддержку любых типов. Это можно сделать, преобразовав наш класс в шаблон класса Stack;
* он имеет фиксированную длину. Это неудобно в двух отношениях: заполненный стек становится бесполезным, а в попытке избежать этого мы окажемся перед необходимостью отвести ему изначально слишком много памяти. Разумным выходом будет разрешить динамический рост стека. Это можно сделать, пользуясь тем, что лежащий в основе стека вектор способен динамически расти.
Напомним определение нашего класса iStack:
#include <vector>
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;
};
Сначала реализуем динамическое выделение памяти. Тогда вместо использования индекса при вставке и удалении элемента нам нужно будет применять соответствующие функции-члены. Член _top больше не нужен: функции push_back() и pop_back() автоматически работают в конце массива. Вот модифицированный текст функций pop() и push():
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;
}
Функции-члены empty(), size() и full() также нуждаются в изменении: в этой версии они теснее связаны с лежащим в основе стека вектором.
inline bool iStack::empty(){ return _stack.empty(); }
inline bool iStack::size() { return _stack.size(); }
inline bool iStack::full() {
return _stack.max_size() == _stack.size(); }
Надо немного изменить функцию-член display(), чтобы _top больше не фигурировал в качестве граничного условия цикла.
void iStack::display()
{
cout << "( " << size() << " )( bot: ";
for ( int ix=0; ix < size(); ++ix )
cout << _stack[ ix ] << " ";
cout << " stop )\n";
}
Наиболее существенным изменениям подвергнется конструктор iStack. Никаких действий от него теперь не требуется. Можно было бы определить пустой конструктор:
inline iStack::iStack() {}
Однако это не совсем приемлемо для пользователей нашего класса. До сих пор мы строго сохраняли интерфейс класса iStack, и если мы хотим сохранить его до конца, необходимо оставить для конструктора один необязательный параметр. Вот как будет выглядеть объявление конструктора с таким параметром типа int:
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;
};
Для обеспечения совместимости с программами, использующими наш прежний класс iStack, определим следующий typedef:
typedef Stack<int> iStack;
Модификацию операторов класса мы оставим читателю для упражнения.
Упражнение 6.29
Модифицируйте функцию peek() (упражнение 4.23 из раздела 4.15) для шаблона класса Stack.
Упражнение 6.30
Модифицируйте операторы для шаблона класса Stack. Запустите тестовую программу из раздела 4.15 для новой реализации
Упражнение 6.31
По аналогии с классом List из раздела 5.11.1 инкапсулируйте наш шаблон класса Stack в пространство имен Primer_Third_Edition
|
| Категория: С++ | Добавил: r2d2 (29.09.2011)
|
| Просмотров: 686
| Рейтинг: 0.0/0 |
Добавлять комментарии могут только зарегистрированные пользователи. [ Регистрация | Вход ] |
|
| Born in Ussr |
|
|
| Залогиниться |
|
|
|
| Турниры |
|
|
|
