<< Пред. стр. 25 (из 121) След. >>
Список литературы по разделу
svec_two.insert( svec_two.begin() + svec_two.size()/2,
svec.begin(), svec.end() );
или любого контейнера, содержащего строки:
list< string > slist;
// ...
// вставляем элементы svec
// перед элементом, содержащим stringVal
list< string >::iterator iter =
find( slist.begin(), slist.end(), stringVal );
slist.insert( iter, svec.begin(), svec.end() );
6.6.1. Удаление
В общем случае удаление осуществляется двумя формами функции-члена erase(). Первая форма удаляет единственный элемент, вторая – диапазон, отмеченный парой итераторов. Для последнего элемента можно воспользоваться функцией-членом pop_back().
При вызове erase() параметром является итератор, указывающий на нужный элемент. В следующем фрагменте кода мы воспользуемся обобщенным алгоритмом find() для нахождения элемента и, если он найден, передадим его адрес функции-члену erase().
string searchValue( "Quasimodo" );
list< string >::iterator iter =
find( slist.begin(), slist.end(), searchValue );
if ( iter != slist.end() )
slist.erase( iter );
Для удаления всех элементов контейнера или некоторого диапазона можно написать следующее:
// удаляем все элементы контейнера
slist.erase( slist.begin(), slist.end() );
// удаляем элементы, помеченные итераторами
list< string >::iterator first, last;
first = find( slist. begin(), slist.end(), vail );
last = find( slist.begin(), slist.end(), va12 );
// ... проверка first и last
slist.erase( first, last );
Парной по отношению к push_back() является функция-член pop_back(), удаляющая из контейнера последний элемент, не возвращая его значения:
vector< string >::iterator iter = buffer.begin();
for ( ; iter != buffer.end(), iter++ )
{
slist.push_back( *iter );
if ( ! do_something( slist ))
slist.pop_back();
}
6.6.2. Присваивание и обмен
Что происходит, если мы присваиваем один контейнер другому? Оператор присваивания копирует элементы из контейнера, стоящего справа, в контейнер, стоящий слева от знака равенства. А если эти контейнеры имеют разный размер? Например:
// svecl содержит 10 элементов
// svec2 содержит 24 элемента
// после присваивания оба содержат по 24 элемента
svecl = svec2;
Контейнер-адресат (svec1) теперь содержит столько же элементов, сколько контейнер-источник (svec2). 10 элементов, изначально содержавшихся в svec1, удаляются (для каждого из них вызывается деструктор класса string).
Функция обмена swap() может рассматриваться как дополнение к операции присваивания. Когда мы пишем:
svecl.swap( svec2 );
svec1 после вызова функции содержит 24 элемента, которые он получил бы в результате присваивания:
svecl = svec2;
но зато теперь svec2 получает 10 элементов, ранее находившихся в svec1. Контейнеры “обмениваются” своим содержимым.
6.6.3. Обобщенные алгоритмы
Операции, описанные в предыдущих разделах, составляют набор, поддерживаемый непосредственно контейнерами vector и deque. Согласитесь, что это весьма небогатый интерфейс и ему явно не хватает базовых операций find(), sort(), merge() и т.д. Планировалось вынести общие для всех контейнеров операции в набор обобщенных алгоритмов, которые могут применяться ко всем контейнерным типам, а также к массивам встроенных типов. (Обобщенные алгоритмы описываются в главе 12 и в Приложении.) Эти алгоритмы связываются с определенным типом контейнера с помощью передачи им в качестве параметров пары соответствующих итераторов. Вот как выглядят вызовы алгоритма find() для списка, вектора и массива разных типов:
#include
#include
int ia[ 6 ] = { 0, 1, 2, 3, 4, 5 };
vector svec;
list dtist;
// соответствующий заголовочный файл
#include
vector::iterator viter;
list::iterator liter;
#int *pia;
// find() возвращает итератор на найденный элемент
// для массива возвращается указатель ...
pia = find( &ia[0], &ia[6], some_int_value );
liter = find( dlist.begin(), dlist.end(), some_double_value );
viter = find( svec.begin(), svec.end(), some_string_value );
Контейнер list поддерживает дополнительные операции, такие, как sort() и merge(), поскольку в нем не реализован произвольный доступ к элементам. (Эти операции описаны в разделе 12.6.)
Теперь вернемся к нашей поисковой системе.
Упражнение 6.11
Напишите программу, в которой определены следующие объекты:
int ia[] = { 1, 5, 34 };
int ia2[] = { 1, 2, 3 };
int ia3[] = { 6, 13, 21, 29, 38, 55, 67, 89 };
vector ivec;
Используя различные операции вставки и подходящие значения ia, ia2 и ia3, модифицируйте вектор ivec так, чтобы он содержал последовательность:
{ 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 }
Упражнение 6.12
Напишите программу, определяющую данные объекты:
int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };
list ilist( ia, ia+11 );
Используя функцию-член erase() с одним параметром, удалите из ilist все нечетные элементы.
6.7. Читаем текстовый файл
Первая наша задача – прочитать текстовый файл, в котором будет производиться поиск. Нам нужно сохранить следующую информацию: само слово, номер строки и позицию в строке, где слово встречается.
Как получить одну строку текста? Стандартная библиотека предоставляет для этого функцию getline():
istream&
getline( istream &is, string str, char delimiter );
getline()берет из входного потока все символы, включая пробелы, и помещает их в объект типа string, до тех пор пока не встретится символ delimiter, не будет достигнут конец файла или количество полученных символов не станет равным величине, возвращаемой функцией-членом max_size()класса string.
Мы будем помещать каждую такую строку в вектор.
Мы вынесли код, читающий файл, в функцию, названную retrieve_text(). В объекте типа pair дополнительно сохраняется размер и номер самой длинной строки. (Полный текст программы приводится в разделе 6.14.)
Вот реализация функции ввода файла:
// возвращаемое значение - указатель на строковый вектор
vector*
retrieve_text()
{
string file_name;
cout << "please enter file name: ";
cin >> file_name;
// откроем файл для ввода ...
ifstream 1nfile( file_name.c_str(), ios::in );
if ( ! infile ) {
cerr << "oops! unable to open file "
<< file_name << " -- bailing out!\n";
exit( -1 );
}
else cout << '\n';
vector *1ines_of_text =
new vector;
string textime;
typedef pair stats;
stats maxline;
int linenum = 0;
while ( getline( infile, textline, '\n' )) {
cout << "line read: " << textline << '\n';
if ( maxline.first < textline.size() ) {
maxline.first = textline.size() ;
maxline.second = linenum;
}
1ines_of_text->push_back( textline );
linenum++;
}
return lines_of_text;
}
Вот как выглядит вывод программы (размер страницы книги недостаточен, чтобы расположить напечатанные строки во всю длину, поэтому мы сделали в тексте отступы, показывающие, где реально заканчивалась строка):
please enter file name: a1ice_emma
line read: Alice Emma has long flowing red hair. Her Daddy says
line read: when the wind blows through her hair, it looks
almost alive,
line read: like a fiery bird in flight. A beautiful fiery bird,
he tells her,
line read: magical but untamed. "Daddy, shush, there is no such
thing, "
line read: she tells him, at the same time wanting him to tell
her more.
line read: Shyly, she asks, "I mean. Daddy, is there?"
number of lines: 6
maximum length: 66
longest line: like a fiery bird in flight. A beautiful fiery
bird, he tells her,
После того как все строки текста сохранены, нужно разбить их на слова. Сначала мы отбросим знаки препинания. Например, возьмем строку из части “Anna Livia Plurrabelle” романа “Finnegans Wake”.
"For every tale there's a telling,
and that's the he and she of it."
В приведенном фрагменте есть следующие знаки препинания:
"For
there's
telling,
that's
it."
А хотелось бы получить:
For
there
telling
that
it
Можно возразить, что
there's
должно превратиться в
there is
но мы-то движемся в другом направлении: следующий шаг – это отбрасывание семантически нейтральных слов, таких, как is, that, and, it и т.д. Так что для данной строчки из “Finnegans Wake” только два слова являются значимыми: tale и telling, и только по этим словам будет выполняться поиск. (Мы реализуем набор стоп-слов с помощью контейнерного типа set, который подробно рассматривается в следующем разделе.)
После удаления знаков препинания нам необходимо превратить все прописные буквы в строчные, чтобы избежать проблем с поиском в таких, например, строках:
Home is where the heart is.
A home is where they have to let you in.
Несомненно, запрос слова home должен найти обе строки.
Мы должны также обеспечить минимальную поддержку учета словоформ: отбрасывать окончания слов, чтобы слова dog и dogs, love, loving и loved рассматривались системой как одинаковые.
В следующем разделе мы вернемся к описанию стандартного класса string и рассмотрим многочисленные операции над строками, которые он поддерживает, в контексте дальнейшей разработки нашей поисковой системы.
6.8. Выделяем слова в строке
Нашей первой задачей является разбиение строки на слова. Мы будем вычленять слова, находя разделяющие их пробелы с помощью функции find(). Например, в строке
Alice Emma has long flowing red hair.
насчитывается шесть пробелов, следовательно, эта строка содержит семь слов.
Класс string имеет несколько функций поиска. find() – наиболее простая из них. Она ищет образец, заданный как параметр, и возвращает позицию его первого символа в строке, если он найден, или специальное значение string::npos в противном случае. Например:
#include
#include
int main() {
string name( "AnnaBelle" );
int pos = name.find( "Anna" );
if ( pos == string::npos )
cout << "Anna не найдено!\n";
else cout << "Anna найдено в позиции: " << pos << endl;
}
Хотя позиция подстроки почти всегда имеет тип int, более правильное и переносимое объявление типа результата, возвращаемого find(), таково:
string::size_type
Например:
string::size_type pos = name.find( "Anna" );
Функция find() делает не совсем то, что нам надо. Требуемая функциональность обеспечивается функцией find_first_of(), которая возвращает позицию первого символа, соответствующего одному из заданных в строке-параметре. Вот как найти первый символ, являющийся цифрой:
#include
#include
int main() {
string numerics( "0123456789" );
string name( "r2d2" );
string:: size_type pos = name.find_first_of( numerics );
cout << "найдена цифра в позиции: "
<< pos << "\tэлемент равен "
<< name[pos] << endl;
}
В этом примере pos получает значение 1 (напоминаем, что символы строки нумеруются с 0).
Но нам нужно найти все вхождения символа, а не только первое. Такая возможность реализуется передачей функции find_first_of() второго параметра, указывающего позицию, с которой начать поиск. Изменим предыдущий пример. Можете ли вы сказать, что в нем все еще не вполне удовлетворительно?
#include
#include
int main() {
string numerics( "0123456789" );
string name( "r2d2" );
string::size_type pos = 0;
// где-то здесь ошибка!
while (( pos = name.find_first_of( numerics, pos ))
!= string::npos )
cout << "найдена цифра в позиции: "
<< pos << "\tэлемент равен "
<< name[pos] << endl;
}
В начале цикла pos равно 0, поэтому поиск идет с начала строки. Первое вхождение обнаружено в позиции 1. Поскольку найденное значение не совпадает с string::npos, выполнение цикла продолжается. Для второго вызова find_first_of()значение pos равно 1. Поиск начнется с 1-й позиции. Вот ошибка! Функция find_first_of() снова найдет цифру в первой позиции, и снова, и снова... Получился бесконечный цикл. Нам необходимо увеличивать pos на 1 в конце каждой итерации:
// исправленная версия цикла
while (( pos = name.find_first_of( numerics, pos ))
!= string::npos )
{
cout << "найдена цифра в позиции: "
<< pos << "\tэлемент равен "
<< name[pos] << endl;
// сдвинуться на 1 символ
++pos;
}
Чтобы найти все пустые символы (к которым, помимо пробела, относятся символы табуляции и перевода строки), нужно заменить строку numerics в этом примере строкой, содержащей все эти символы. Если же мы уверены, что используется только символ пробела и никаких других, то можем явно задать его в качестве параметра функции:
// фрагмент программы
while (( pos = textline.find_first_of( ' ', pos ))
!= string::npos )
// ...
Чтобы узнать длину слова, введем еще одну переменную:
// фрагмент программы
// pos: позиция на 1 большая конца слова
// prev_pos: позиция начала слова
string::size_type pos = 0, prev_pos = 0;
while (( pos = textline.find_first_of( ' ', pos ))
!= string::npos )
{
// ...
// запомнить позицию начала слова
prev_pos = ++pos;
}
На каждой итерации prev_pos указывает позицию начала слова, а pos – позицию следующего символа после его конца. Соответственно, длина слова равна:
pos - prev_pos; // длина слова
После того как мы выделили слово, необходимо поместить его в строковый вектор. Это можно сделать, копируя в цикле символы из textline с позиции prev_pos до pos -1. Функция substr() сделает это за нас:
// фрагмент программы
vector words;
while (( pos = textline.find_first_of( ' ', pos ))
!= string::npos )
{
words.push_back( textline.substr(
prev_pos, pos-prev_pos));
prev_pos = ++pos;
}
Функция substr() возвращает копию подстроки. Первый ее аргумент обозначает первую позицию, второй – длину подстроки. (Второй аргумент можно опустить, тогда подстрока включит в себя остаток исходной строки, начиная с указанной позиции.)
В нашей реализации допущена ошибка: последнее слово не будет помещено в контейнер. Почему? Возьмем строку:
seaspawn and seawrack
После каждого из первых двух слов поставлен пробел. Два вызова функции find_first_of() вернут позиции этих пробелов. Третий же вызов вернет string::npos, и цикл закончится. Таким образом, последнее слово останется необработанным.
Вот полный текст функции, названной нами separate_words(). Помимо сохранения слов в векторе строк, она вычисляет координаты каждого слова – номер строки и колонки (нам эта информация потребуется впоследствии).
typedef pair location;
typedef vector loc;
typedef vector text;
<< Пред. стр. 25 (из 121) След. >>
Список литературы по разделу