<< Пред.           стр. 29 (из 121)           След. >>

Список литературы по разделу

  exclusion_set.begin() ));
 }
 В этом фрагменте кода встречаются два элемента, которые мы до сих пор не рассматривали: тип difference_type и класс inserter. difference_type – это тип результата вычитания двух итераторов для нашего множества строк. Он передается в качестве одного из параметров шаблона istream_iterator.
 copy() –один из обобщенных алгоритмов. (Мы рассмотрим их в главе 12 и в Приложении.) Первые два параметра – пара итераторов или указателей – задают диапазон. Третий параметр является либо итератором, либо указателем на начало контейнера, в который элементы копируются.
 Проблема с этой функцией вызвана ограничением, вытекающим из ее реализации: количество копируемых элементов не может превосходить числа элементов в контейнере-адресате. Дело в том, что copy() не вставляет элементы, она только присваивает каждому элементу новое значение. Однако ассоциативные контейнеры не позволяют явно задать размер. Чтобы скопировать элементы в наше множество, мы должны заставить copy() вставлять элементы. Именно для этого служит класс inserter (детально он рассматривается в разделе 12.4).
 6.13.2. Поиск элемента
 Две операции, позволяющие отыскать в наборе определенное значение, – это find() и count(). find() возвращает итератор, указывающий на найденный элемент, или значение, равное end(), если он отсутствует. count() возвращает 1 при наличии элемента и 0 в противном случае. Добавим проверку на существование в функцию build_word_map():
 if ( exclusion_set.count( textword ))
  continue;
 // добавим отсутствующее слово
 6.13.3. Навигация по множеству
 Для проверки наших кодов реализуем небольшую функцию, выполняющую поиск по одному слову (поддержка языка запросов будет добавлена в главе 17). Если слово найдено, мы будем показывать каждую строку, в которой оно содержится. Слово может повторяться в строке, например:
 
 tomorrow and tomorrow and tomorrow
 
 однако такая строка будет представлена только один раз.
 Одним из способов не учитывать повторное вхождение слова в строку является использование множества, как показано в следующем фрагменте кода:
 // получим указатель на вектор позиций
 loc ploc = (*text_map)[ query_text ];
 
 // переберем все позиции
 // вставим все номера строк в множество
 set< short > occurrence_lines;
 loc::iterator liter = ploc->begin(),
  liter_end = ploc->end();
 
 while ( liter != liter_end ) {
  occurrence_lines.insert( occurrence_lines.end(),
  (*liter).first );
  ++liter;
 }
 Контейнер set не допускает дублирования ключей. Поэтому можно гарантировать, что occurrence_lines не содержит повторений. Теперь нам достаточно перебрать данное множество, чтобы показать все номера строк, где встретилось данное слово:
 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;
 }
 (Полная реализация 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 (в последующих главах мы обсудим подобное использование классов), кроме того, текст был изменен, так как наш компилятор поддерживал стандарт С++ не полностью.
 Например, библиотека iostream не соответствовала текущему стандарту. Шаблоны не поддерживали значения аргументов по умолчанию. Возможно, вам придется изменить кое-что в этой программе, чтобы она компилировалась в вашей системе.
 // стандартные заголовочные файлы С++
 #include
 #include
 #include
 #include
 #include
 #include
 
 // заголовочный файл iostream, не отвечающий стандарту
 #include
 
 // заголовочные файлы С
 #include
 #include
 
 // typedef для удобства чтения
 typedef pair location;
 typedef vector loc;
 typedef vector text;
 typedef pair 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 *lines_of_text;
  text_loc *text_locations;
  map< string,loc*,
  less,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 textline;
 
  while ( getline( infile, textline, '\n' ))
  lines_of_text->push_back( textline );
 }
 
 void
 TextQuery::
 separate_words()
 {
  vector *words =
  new vector;
  vector *locations =
  new vector;
 
  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 *words = text_locations->first;
  vector::iterator iter = words->begin();
  vector::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 *words = text_locations->first;
 
  vector::iterator iter = words->begin();
  vector::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 *words = text_locations->first;
 
  vector::iterator iter = words->begin();
  vector::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,allocator>;
 
  typedef map,allocator>::value_type
  value_type;
  typedef set,allocator>::difference_type
  diff_type;
 
  set,allocator> exclusion_set;
 
  ifstream infile( "exclusion_set" );
  if ( !infile )
  {
  static string default_excluded_words[25] = {

<< Пред.           стр. 29 (из 121)           След. >>

Список литературы по разделу