Главная страница
Навигация по странице:

  • 6.12.1. Определение объекта map и заполнение его элементами

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


    Скачать 5.41 Mb.
    НазваниеС для начинающих
    Дата24.08.2022
    Размер5.41 Mb.
    Формат файлаpdf
    Имя файлаЯзык программирования C++. Вводный курс.pdf
    ТипДокументы
    #652350
    страница26 из 93
    1   ...   22   23   24   25   26   27   28   29   ...   93
    278
    Упражнение 6.15
    Напишите программу, которая удаляет все символы, кроме STL из строки:
    "/.+(STL).$1/" используя сначала erase(pos,count), а затем erase(iter,iter).
    Упражнение 6.16
    Напишите программу, которая с помощью разных функций вставки из строк string s2 ( "pixie" ) составит предложение "A whistling-dixie kind of walk"
    6.10.
    Приводим слова к стандартной форме
    Одной из проблем при разработке текстовых поисковых систем является необходимость распознавать слова в различных словоформах, такие, как cry, cries и cried, baby и babies
    , и, что гораздо проще, написанные заглавными и строчными буквами, например home и Home. Первая задача, распознавание словоформ, слишком сложна, поэтому мы приведем здесь ее заведомо неполное решение. Сначала заменим все прописные буквы строчными:
    }
    Функция to1ower( (*iter)[pos] ); string sentence( "kind of" ); string s1 ( "whistle" ) void strip_caps( vector *words )
    { vector::iterator iter=words->begin() ; vector::iterator iter_end=words->end() ; string caps( "ABCDEFGHIJKLMNOPQRSTUVWXYZ" ); 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;
    }

    С++ для начинающих
    279
    входит в стандартную библиотеку С. Она заменяет прописную букву соответствующей ей строчной. Для использования tolower() необходимо включить заголовочный файл:
    #include
    (В этом файле объявлены и другие функции, такие, как isalpha(), isdigit(), ispunct()
    , isspace(), toupper(). Полное описание этих функций см. [PLAUGER92].
    Стандартная библиотека С++ включает класс ctype, который инкапсулирует всю функциональность стандартной библиотеки Си, а также набор функций, не являющихся членами, например toupper(), tolower() и т.д. Для их использования нужно включить заголовочный файл
    #include
    Однако наша реализация компилятора еще не поддерживала класс ctype, и нам пришлось использовать стандартную библиотеку Си.)
    Проблема словоформ слишком сложна для того, чтобы пытаться решить ее в общем виде.
    Но даже самый примитивный вариант способен значительно улучшить работу нашей поисковой системы. Все, что мы сделаем в данном направлении, – удалим букву 's' на концах слов:
    }
    Слова из трех и менее букв мы пропускаем. Это позволяет оставить без изменения, например, has, its, is и т.д., однако слова tv и tvs мы не сможем распознать как одинаковые.
    Если слово кончается на "ies", как babies и cries, необходимо заменить "ies" на "y": void suffix_text( vector *words )
    { vector::iterator iter = words->begin(), iter_end = words->end(); while ( iter != iter_end ) {
    // оставим слова короче трех букв как есть if ( (*iter).size() <= 3 )
    { ++iter; continue; } if ( (*iter)[ (*iter).size()-1 ] == 's' ) suffix_s( *iter );
    // здесь мы могли бы обработать суффиксы
    // ed, ing, 1y
    ++iter;
    } string::size_type pos() = word.size()-3; string ies( "ies" ); if ( ! word.compare( pos3, 3, ies )) { word.replace( pos3, 3, 1, '
    у' ); return;

    С++ для начинающих
    280
    } compare()
    возвращает 0, если две строки равны. Первый аргумент, pos3, обозначает начальную позицию, второй – длину сравниваемой подстроки (в нашем случае 3). Третий аргумент, ies, – строка-эталон. (На самом деле существует шесть вариантов функции compare()
    . Остальные мы покажем в следующем разделе.) replace()
    заменяет подстроку набором символов. В данном случае мы заменяем подстроку "ies" длиной в 3 символа единичным символом 'y'. (Имеется десять перегруженных вариантов функции replace(). В следующем разделе мы коснемся остальных вариантов.)
    Если слово заканчивается на "ses", как promises или purposes, нужно удалить суффикс "es"
    16
    :
    }
    Если слово кончается на "ous", как oblivious, fulvous, cretaceous, или на "is", как genesis
    , mimesis, hepatitis, мы не будем изменять его. (Наша система несовершенна.
    Например, в слове kiwis надо убрать последнее 's'.) Пропустим и слова, оканчивающиеся на "ius" (genius) или на "ss" (hiss, lateness, less). Нам поможет вторая форма функции compare(): return;
    В противном случае удалим последнее 's': word.erase( pos3+2 );
    16 Конечно, в английском языке существуют исключения из правил. Наш эвристический алгоритм превратит crises (множ. число от crisisприм. перев.) в cris. Ошибочка!
    string ses( "ses" ); if ( ! word.compare( pos3, 3, ses )) { word.erase( pos3+l, 2 ); return; 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 ) || // ous
    ! word.compare( pos3, 3, suffixes, spos+6, 3 ) || // ius
    ! word.compare( pos3+l, 2, suffixes, spos+2, 2 ) || // ss
    ! word.compare( pos3+l, 2, suffixes, spos+4, 2 ) ) // is
    // удалим последнее 's'

    С++ для начинающих
    281
    Имена собственные, например Pythagoras, Brahms, Burne-Jones, не подпадают под общие правила. Этот случай мы оставим как упражнение для читателя, когда будем рассказывать об ассоциативных контейнерах.
    Но прежде чем перейти к ним, рассмотрим оставшиеся строковые операции.
    Упражнение 6.17
    Наша программа не умеет обрабатывать суффиксы ed (surprised), ly (surprisingly) и ing
    (surprisingly). Реализуйте одну из функций для этого случая:
    (a) suffix_ed() (b) suffix_ly()
    (c) suffix_ing()
    6.11.
    Дополнительные операции со строками
    Вторая форма функции-члена erase() принимает в качестве параметров два итератора, ограничивающих удаляемую подстроку. Например, превратим string name( "AnnaLiviaPlurabelle" ); в строку "Annabelle": name.begin()+endPos );
    Символ, на который указывает второй итератор, не входит в удаляемую подстроку.
    Для третьей формы параметром является только один итератор; эта форма удаляет все символы, начиная с указанной позиции до конца строки. Например: name.erase( name. begin()+4 ); оставляет строку "Anna".
    Функция-член insert() позволяет вставить в заданную позицию строки другую строку или символ. Общая форма выглядит так: string_object.insert( position, new_string ); position обозначает позицию, перед которой производится вставка. new_string может быть объектом класса string, C-строкой или символом: string_object.insert( pos+1, 's' ); typedef string::size_type size_type; size_type startPos = name.find( 'L' ) size_type endPos = name.find_1ast_of( 'b' ); name.erase( name.begin()+startPos, string string_object( "Missisippi" ); string::size_type pos = string_object.find( "isi" );

    С++ для начинающих
    282
    Можно выделить для вставки подстроку из new_string:
    ) string_object получает значение "Mississippi Belle". Если мы хотим вставить все символы new_string, начиная с pos, последний параметр нужно опустить.
    Пусть есть две строки: string s2( "Annabelle" );
    Как получить третью строку со значением "Miss Anna"?
    Можно использовать функции-члены assign() и append(): s3.assign ( s1, 4 ); s3
    теперь содержит значение "Miss". s3 += ' ';
    Теперь s3 содержит "Miss ". s3.append(s2,4); s3
    получила значение "Miss Anna". То же самое можно сделать короче: s3.assign(s1,4).append(' ').append(s2,4); string new_string ( "AnnaBelle Lee" ); string_object += ' '; // добавим пробел
    // найдем начальную и конечную позицию в new_string pos = new_string.find( 'B' ); string::size_type posEnd = new_string.find( ' ' ); string_object.insert( string_object.size(), // позиция вставки new_string, pos, // начало подстроки в new_string posEnd // конец подстроки new_string string sl( "Mississippi" ); string s3;
    // скопируем первые 4 символа s1
    // добавим пробел
    // добавим 4 первых символа s2

    С++ для начинающих
    283
    Другая форма функции-члена assign() имеет три параметра: второй обозначает позицию начала, а третий – длину. Позиции нумеруются с 0. Вот как, скажем, извлечь "belle"
    из "Annabelle": beauty.assign( s2, 4, 5 );
    Вместо этих параметров мы можем использовать пару итераторов: beauty.assign( s2, s2.begin()+4, s2.end() );
    В следующем примере две строки содержат названия текущего проекта и проекта, находящегося в отложенном состоянии. Они должны периодически обмениваться значениями, поскольку работа идет то над одним, то над другим. Например: string pending_project( "Fantasia 2000, Firebird segment" );
    Функция-член swap() позволяет обменять значения двух строк с помощью вызова current_project.swap( pending_project );
    Для строки string first_novel( "V" ); операция взятия индекса char ch = first_novel[ 1 ]; возвратит неопределенное значение: длина строки first_novel равна 1, и единственное правильное значение индекса – 0. Такая операция взятия индекса не обеспечивает проверку правильности параметра, но мы всегда можем сделать это сами с помощью функции-члена size(): string beauty;
    // присвоим beauty значение "belle"
    // присвоим beauty значение "belle" string current_project( "C++ Primer, 3rd Edition" );

    С++ для начинающих
    284
    }
    Там, где это невозможно или нежелательно, например:
    } следует воспользоваться функцией at(), которая делает то же, что и операция взятия индекса, но с проверкой. Если индекс выходит за границу, возбуждается исключение out_of_range
    :
    }
    Строки можно сравнивать лексикографически. Например: string cplus_program_crash( "abort" );
    Строка cobol_program_crash лексикографически меньше, чем cplus_program_crash: сопоставление производится по первому отличающемуся символу, а буква e в латинском алфавите идет раньше, чем o. Операция сравнения выполняется функцией-членом compare()
    . Вызов sl.compare( s2 ); int elem_count( const string &word, char elem )
    { int occurs = 0;
    // не надо больше проверять ix for ( int ix=0; ix < word.size(); ++-ix ) if ( word[ ix ] == elem )
    ++occurs; return occurs; void mumble( const string &st, int index )
    {
    // возможна ошибка char ch = st[ index ];
    // ... void mumble( const string &st, int index )
    { try { char ch = st.at( index );
    // ...
    } catch ( std::out_of_range ){...}
    // ... string cobol_program_crash( "abend" );

    С++ для начинающих
    285
    возвращает одно из трех значений:

    если s1 больше, чем s2, то положительное;

    если s1 меньше, чем s2, то отрицательное;

    если s1 равно s2, то 0.
    Например, cobol_program_crash.compare( cplus_program_crash ); вернет отрицательное значение, а cplus_program_crash.compare( cobol_program_crash ); положительное. Перегруженные операции сравнения (<, >, !=, ==, <=, >=) являются более компактной записью функции compare().
    Шесть вариантов функции-члена compare() позволяют выделить сравниваемые подстроки в одном или обоих операндах. (Примеры вызовов приводились в предыдущем разделе.)
    Функция-член replace() дает десять способов заменить одну подстроку на другую (их длины не обязаны совпадать). В двух основных формах replace() первые два аргумента задают заменяемую подстроку: в первом варианте в виде начальной позиции и длины, во втором – в виде пары итераторов на ее начало и конец. Вот пример первого варианта: sentence.repiace( position, length, "Abstract Data Type" ); position представляет собой начальную позицию, а length – длину заменяемой подстроки. Третий аргумент является подставляемой строкой. Его можно задать несколькими способами. Допустим, как объект string: sentence.replace( position, length, new_str );
    Следующий пример иллюстрирует выделение подстроки в new_str: string sentence(
    "An ADT provides both interface and implementation." ); string::size_type position = sentence.find_1ast_of( 'A' ); string::size_type length = 3;
    // заменяем ADT на Abstract Data Type string new_str( "Abstract Data Type" );

    С++ для начинающих
    286
    sentence.replace( position, 1, new_str, posA, 9 );
    Еще один вариант позволяет заменить подстроку на один символ, повторенный заданное количество раз: hmm.repiace( position, 4, 'x', 4 );
    В данном примере используется указатель на символьный массив и длина вставляемой подстроки: ahhem.replace(0, 3, lang+index[1], index[2]-index[1]);
    А здесь мы используем пару итераторов: sentence.repiace( start, start+3, "Abstract Data Type" );
    Оставшиеся четыре варианта допускают задание заменяющей строки как объекта типа string
    , символа, повторяющегося N раз, пары итераторов и C-строки.
    Вот и все, что мы хотели сказать об операциях со строками. Для более полной информации обращайтесь к определению стандарта С++ [ISO-C++97].
    #include typedef string::size_type size_type;
    // найдем позицию трех букв size_type posA = new_str.find( 'A' ); size_type posD = new_str.find( 'D' ); size_type posT = new_str.find( 'T' );
    // нашли: заменим T на "Type" sentence.replace( position+2, 1, new_str, posT, 4 );
    // нашли: заменим D на "Data " sentence.replace( position+1, 1, new_str, posD, 5 );
    // нашли: заменим A на "Abstract " string hmm( "Some celebrate Java as the successor to C++." ); string:: size_type position = hmm.find( 'J' );
    // заменим Java на xxxx const char *lang = "EiffelAda95JavaModula3"; int index[] = { 0, 6, 11, 15, 22 }; string ahhem(
    "C++ is the language for today's power programmers." ); string sentence(
    "An ADT provides both interface and implementation." );
    // указывает на 'A' в ADT string: iterator start = sentence. begin()+3;
    // заменяем ADT на Abstract Data Type

    С++ для начинающих
    287
    Упражнение 6.18
    Напишите программу, которая с помощью функций-членов assign() и append() из строк string quote2( "The child "is father of the man" ); составит предложение "The child is in the dooryard"
    Упражнение 6.19
    Напишите функцию: int length ); которая в строке string generic1( "Dear Ms Daisy:" ); заменяет Daisy и Ms (миссис). Вместо Daisy подставляется параметр lastname, а вместо
    Ms подстрока string generic2( "MrsMsMissPeople" ); длины length, начинающаяся с pos.
    Например, вызов generate_salutation( generici, lastName, generic2, 5, 4 ); вернет строку:
    Dear Miss AnnaP: string quote1( "When lilacs last in the dooryard bloom'd" ); string generate_salutation( string generic1, string lastname, string generic2, string::size_type pos, string lastName( "AnnaP" ); string greetings =

    С++ для начинающих
    288
    6.12.
    Строим отображение позиций слов
    В этом разделе мы построим отображение (map), позволяющее для каждого уникального слова текста сохранить номера строк и колонок, в которых оно встречается. (В следующем разделе мы изучим ассоциативный контейнер set.) В общем случае контейнер set полезен, если мы хотим знать, содержится ли определенный элемент в некотором множестве, а map позволяет связать с каждым из них какую-либо величину.
    В map хранятся пары ключ/значение. Ключ играет роль индекса для доступа к ассоциированному с ним значению. В нашей программе каждое уникальное слово текста будет служить ключом, а значением станет вектор, содержащий пары (номер строки, номер колонки). Для доступа применяется оператор взятия индекса. Например: locat = text_map[ query ];
    Ключом здесь является строка, а значение имеет тип location*.
    Для использования отображения необходимо включить соответствующий заголовочный файл:
    #include
    Какие основные действия производятся над ассоциативными контейнерами? Их заполняют элементами или проверяют на наличие определенного элемента. В следующем подразделе мы покажем, как определить пару ключ/значение и как поместить такие пары в контейнер. Далее мы расскажем, как сформулировать запрос на поиск элемента и извлечь значение, если элемент существует.
    6.12.1.
    Определение объекта map и заполнение его
    элементами
    Чтобы определить объект класса map, мы должны указать, как минимум, типы ключа и значения. Например: map word_count;
    Здесь задается объект word_count типа map, для которого ключом служит объект типа string
    , а ассоциированным с ним значением – объект типа int. Аналогично map> personnel; определяет personnel как отображение ключа типа int (уникальный номер служащего) на указатель, адресующий объект класса employee. string query( "pickle" ); vector< location > *locat;
    // возвращается location*, ассоциированный с "pickle" class employee;

    С++ для начинающих
    289
    Для нашей поисковой системы полезно такое отображение: map text_map;
    Поскольку имевшийся в нашем распоряжении компилятор не поддерживал аргументы по умолчанию для параметров шаблона, нам пришлось написать более развернутое определение: text_map;
    По умолчанию сортировка ассоциативных контейнеров производится с помощью операции “меньше”. Однако можно указать и другой оператор сравнения (см. раздел 12.3 об объектах-функциях).
    После того как отображение определено, необходимо заполнить его парами ключ/значение. Интуитивно хочется написать примерно так:
    // и так далее ...
    Когда мы пишем: word_count[ string("Anna") ] = 1; на самом деле происходит следующее:
    1. Безымянный временный объект типа string инициализируется значением "Anna" и передается оператору взятия индекса, определенному в классе map.
    2. Производится поиск элемента с ключом "Anna" в массиве word_count. Такого элемента нет.
    3. В word_count вставляется новая пара ключ/значение. Ключом является, естественно, строка "Anna". Значением – 0, а не 1.
    4. После этого значению присваивается величина 1. typedef pair location; typedef vector loc; map, // оператор сравнения allocator> // распределитель памяти по умолчанию
    #include
    #include map word_count; word_count[ string("Anna") ] = 1; word_count[ string("Danny") ] = 1; word_count[ string("Beth") ] = 1;

    С++ для начинающих
    1   ...   22   23   24   25   26   27   28   29   ...   93


    написать администратору сайта