Операции с последовательными контейнерами

Предыдущая 5 6 7 8 9 10 111213 14 15 16 17 18 19 20 Следующая

Функция-член push_back() позволяет добавить единственный элемент в конец контейнера. Но как вставить элемент в произвольную позицию? А целую последовательность элементов? Для этих случаев существуют более общие операции.

Например, для вставки элемента в начало контейнера можно использовать:

vector< string > svec; list< string > slist; string spouse( "Beth" ); slist.insert( slist.begin(), spouse );

svec.insert( svec.begin(), spouse );

Первый параметр функции-члена insert() (итератор, адресующий некоторый элемент контейнера) задает позицию, а второй – вставляемое перед этой позицией значение. В примере выше элемент добавляется в начало контейнера. А так можно реализовать вставку в произвольную позицию:

string son( "Danny" ); list<string>::iterator iter; iter = find( slist.begin(), slist.end(), son );

slist.insert( iter, spouse );

Здесь find() возвращает позицию элемента в контейнере, если элемент найден, либо итератор end(), если ничего не найдено. (Мы вернемся к функции find() в конце следующего раздела.) Как можно догадаться, push_back() эквивалентен следующей записи:

// эквивалентный вызов: slist.push_back( value );

slist.insert( slist.end(), value );

Вторая форма функции-члена insert() позволяет вставить указанное количество одинаковых элементов, начиная с определенной позиции. Например, если мы хотим добавить десять элементов Anna в начало вектора, то должны написать:

vector<string> svec; string anna( "Anna" );

svec.insert( svec.begin(), 10, anna );

insert() имеет и третью форму, помогающую вставить в контейнер несколько элементов. Допустим, имеется следующий массив:

string sarray[4] = { "quasi", "simba", "frollo", "scar" };

Мы можем добавить все его элементы или только некоторый диапазон в наш вектор строк:

svec.insert( svec.begin(), sarray, sarray+4 ); svec.insert( svec.begin() + svec.size()/2,

sarray+2, sarray+4 );

Такой диапазон отмечается и с помощью пары итераторов

// вставляем элементы svec // в середину svec_two svec_two.insert( svec_two.begin() + svec_two.size()/2,

svec.begin(), svec.end() );

или любого контейнера, содержащего строки:[14]

list< string > slist; // ... // вставляем элементы svec // перед элементом, содержащим stringVal list< string >::iterator iter = find( slist.begin(), slist.end(), stringVal );

slist.insert( iter, svec.begin(), svec.end() );

Удаление

В общем случае удаление осуществляется двумя формами функции-члена 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();

}

Присваивание и обмен

Что происходит, если мы присваиваем один контейнер другому? Оператор присваивания копирует элементы из контейнера, стоящего справа, в контейнер, стоящий слева от знака равенства. А если эти контейнеры имеют разный размер? Например:

// svecl содержит 10 элементов // svec2 содержит 24 элемента // после присваивания оба содержат по 24 элемента

svecl = svec2;

Контейнер-адресат (svec1) теперь содержит столько же элементов, сколько контейнер-источник (svec2). 10 элементов, изначально содержавшихся в svec1, удаляются (для каждого из них вызывается деструктор класса string).

Функция обмена swap() может рассматриваться как дополнение к операции присваивания. Когда мы пишем:

svecl.swap( svec2 );

svec1 после вызова функции содержит 24 элемента, которые он получил бы в результате присваивания:

svecl = svec2;

но зато теперь svec2 получает 10 элементов, ранее находившихся в svec1. Контейнеры “обмениваются” своим содержимым.

Обобщенные алгоритмы

Операции, описанные в предыдущих разделах, составляют набор, поддерживаемый непосредственно контейнерами vector и deque. Согласитесь, что это весьма небогатый интерфейс и ему явно не хватает базовых операций find(), sort(), merge() и т.д. Планировалось вынести общие для всех контейнеров операции в набор обобщенных алгоритмов, которые могут применяться ко всем контейнерным типам, а также к массивам встроенных типов. (Обобщенные алгоритмы описываются в главе 12 и в Приложении.) Эти алгоритмы связываются с определенным типом контейнера с помощью передачи им в качестве параметров пары соответствующих итераторов. Вот как выглядят вызовы алгоритма find() для списка, вектора и массива разных типов:

#include <list> #include <vector> int ia[ 6 ] = { 0, 1, 2, 3, 4, 5 }; vector<string> svec; list<double> dtist; // соответствующий заголовочный файл #include <algorithm> vector<string>::iterator viter; list<double>::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<int> 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<int> ilist( ia, ia+11 );

Используя функцию-член erase() с одним параметром, удалите из ilist все нечетные элементы.

Читаем текстовый файл

Первая наша задача – прочитать текстовый файл, в котором будет производиться поиск. Нам нужно сохранить следующую информацию: само слово, номер строки и позицию в строке, где слово встречается.

Как получить одну строку текста? Стандартная библиотека предоставляет для этого функцию getline():

istream&

getline( istream &is, string str, char delimiter );

getline()берет из входного потока все символы, включая пробелы, и помещает их в объект типа string, до тех пор пока не встретится символ delimiter, не будет достигнут конец файла или количество полученных символов не станет равным величине, возвращаемой функцией-членом max_size()класса string.

Мы будем помещать каждую такую строку в вектор.

Мы вынесли код, читающий файл, в функцию, названную retrieve_text(). В объекте типа pair дополнительно сохраняется размер и номер самой длинной строки. (Полный текст программы приводится в разделе 6.14.)

Вот реализация функции ввода файла:[15]

// возвращаемое значение - указатель на строковый вектор vector<string,allocator>* 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<string, allocator> *1ines_of_text = new vector<string, allocator>; string textime; typedef pair<string::size_type, int> 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

Можно возразить, что

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 и рассмотрим многочисленные операции над строками, которые он поддерживает, в контексте дальнейшей разработки нашей поисковой системы.

Выделяем слова в строке

Нашей первой задачей является разбиение строки на слова. Мы будем вычленять слова, находя разделяющие их пробелы с помощью функции find(). Например, в строке

Alice Emma has long flowing red hair.

насчитывается шесть пробелов, следовательно, эта строка содержит семь слов.

Класс string имеет несколько функций поиска. find() – наиболее простая из них. Она ищет образец, заданный как параметр, и возвращает позицию его первого символа в строке, если он найден, или специальное значение string::npos в противном случае. Например:

#include <string> #include <iostream> 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 <string> #include <iostream> 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 <string> #include <iostream> 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<string> 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<short,short> location; typedef vector<location> loc; typedef vector<string> text; typedef pair<text* ,loc*> text_loc; text_loc* separate_words( const vector<string> *text_file ) { // words: содержит набор слов // locations: содержит информацию о строке и позиции // каждого слова vector<string> *words = new vector<string>; vector<location> * locations = new vector<location>; short line_pos = 0; // текущий номер строки // iterate through each line of text for ( ; line_pos < text_file->size(); ++line_pos ) // textline: обрабатываемая строка // word_pos: позиция в строке short word_pos = 0; string textline = (*text_file) [ line_pos ]; 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; prev_pos = ++pos; } // обработаем последнее слово words->push_back( textline.substr( prev_pos, pos - prev_pos )); locations->push_back( make_pair( line_pos, word_pos )); } return new text_loc( words, locations );

}

Теперь функция main()выглядит следующим образом:

int main() { vector<string> *text_file = retrieve_text(); text_loc *text_locations = separate_words( text_file ); // ...

}

Вот часть распечатки, выданной тестовой версией separate_words():

textline: Alice Emma has long flowing red hair. Her Daddy

says

eol: 52 pos: 5 line: 0 word: 0 substring: Alice

eol: 52 pos: 10 line: 0 word: 1 substring: Emma

eol: 52 pos: 14 line: 0 word: 2 substring: has

eol: 52 pos: 19 line: 0 word: 3 substring: long

eol: 52 pos: 27 line: 0 word: 4 substring: flowing

eol: 52 pos: 31 line: 0 word: 5 substring: red

eol: 52 pos: 37 line: 0 word: 6 substring: hair.

eol: 52 pos: 41 line: 0 word: 7 substring: Her

eol: 52 pos: 47 line: 0 word: 8 substring: Daddy

last word on line substring: says

...

textline: magical but untamed. "Daddy, shush, there is no

such thing,"

eol: 60 pos: 7 line: 3 word: 0 substring: magical

eol: 60 pos: 11 line: 3 word: 1 substring: but

eol: 60 pos: 20 line: 3 word: 2 substring: untamed

eol: 60 pos: 28 line: 3 word: 3 substring: "Daddy,

eol: 60 pos: 35 line: 3 word: 4 substring: shush,

eol: 60 pos: 41 line: 3 word: 5 substring: there

eol: 60 pos: 44 line: 3 word: 6 substring: is

eol: 60 pos: 47 line: 3 word: 7 substring: no

eol: 60 pos: 52 line: 3 word: 8 substring: such

last word on line substring: thing,":

...

textline: Shy1y, she asks, "I mean, Daddy: is there?"

eol: 43 pos: 6 line: 5 word: 0 substring: Shyly,

eol: 43 pos: 10 line: 5 word: 1 substring: she

eol: 43 pos: 16 line: 5 word: 2 substring: asks,

eol: 43 pos: 19 line: 5 word: 3 substring: "I

eol: 43 pos: 25 line: 5 word: 4 substring: mean,

eol: 43 pos: 32 line: 5 word: 5 substring: Daddy,

eol: 43 pos: 35 line: 5 word: 6 substring: is

last word on line substring: there?":

Прежде чем продолжить реализацию поисковой системы, вкратце рассмотрим оставшиеся функции-члены класса string, предназначенные для поиска. Функция rfind() ищет последнее, т.е. самое правое, вхождение указанной подстроки:

string river( "Mississippi" ); string::size_type first_pos = river.find( "is" );

string::size_type 1ast_pos = river.rfind( "is" );

find() вернет 1, указывая позицию первого вхождения подстроки "is", а rfind() – 4 (позиция последнего вхождения "is").

find_first_not_of() ищет первый символ, не содержащийся в строке, переданной как параметр. Например, чтобы найти первый символ, не являющийся цифрой, можно написать:

string elems( "0123456789" ); string dept_code( "03714p3" ); // возвращается позиция символа 'p'

string::size_type pos = dept_code.find_first_not_of(elems) ;

find_last_of() ищет последнее вхождение одного из указанных символов. find_last_not_of() – последний символ, не совпадающий ни с одним из заданных. Все эти функции имеют второй необязательный параметр – позицию в исходной строке, с которой начинается поиск.

Упражнение 6.13

Напишите программу, которая ищет в строке

"ab2c3d7R4E6"

цифры, а затем буквы, используя сначала find_first_of(), а потом find_first_not_of().

Упражнение 6.14

Напишите программу, которая подсчитывает все слова и определяет самое длинное и самое короткое из них в строке sentence:

string linel = "We were her pride of 10 she named us --"; string line2 = "Benjamin, Phoenix, the Prodigal" string line3 = "and perspicacious pacific Suzanne";

string sentence = linel + line2 + line3;

Если несколько слов имеют длину, равную максимальной или минимальной, учтите их все.

Предыдущая 5 6 7 8 9 10 111213 14 15 16 17 18 19 20 Следующая

Не нашли, что искали? Воспользуйтесь поиском по сайту: