| Меню сайта |
|
 |
| Категория |
|
|
| Развлечение |
|
|
| ON - LINE |
|
|
| Опрос |
|
|
| Оbserver Ward |
Онлайн всего: 1 Гостей: 1 Пользователей: 0
|
|
| Друзья сайта |
|
|
| Hаша кнопка |
Для обмена банерами , наша кнопка для размещения у вас на сайте
|
|
|
6. Абстрактные контейнерные типы (1)
6. Абстрактные контейнерные типы
В этой главе мы продолжим рассмотрение типов данных, начатое в главе 3, представим дополнительную информацию о классах vector и string и познакомимся с другими контейнерными типами, входящими в состав стандартной библиотеки С++. Мы также расскажем об операторах и выражениях, упомянутых в главе 4, сосредоточив внимание на тех операциях, которые поддерживаются объектами контейнерных типов.
Последовательный контейнер содержит упорядоченный набор элементов одного типа. Можно выделить два основных типа контейнеров – вектор (vector) и список (list). (Третий последовательный контейнер – двусторонняя очередь (deque) – обеспечивает ту же функциональность, что и vector, но особенно эффективно реализует операции вставки и удаления первого элемента. deque следует применять, например, при реализации очереди, из которой извлекается только первый элемент. Все сказанное ниже относительно вектора применимо также и к deque.)
Ассоциативный контейнер эффективно реализует операции проверки существования и извлечения элемента. Два основных ассоциативных контейнера – это отображение (map) и множество (set). map состоит из пар ключ/значение, причем ключ используется для поиска элемента, а значение содержит хранимую информацию. Телефонный справочник хорошо иллюстрирует понятие отображения: ключом является фамилия и имя абонента, а значением – его телефонный номер.
Элемент контейнера set содержит только ключ, поэтому set эффективно реализует операцию проверки его существования. Этот контейнер можно применить, например, при реализации системы текстового поиска для хранения списка так называемых стоп-слов – слов, не используемых при поиске, таких, как и, или, не, так и тому подобных. Программа обработки текста считывает каждое слово и проверяет, есть ли оно в указанном списке. Если нет, то слово добавляется в базу данных.
В контейнерах map и set не может быть дубликатов – повторяющихся ключей. Для поддержки дубликатов существуют контейнеры multimap и multiset. Например, multimap можно использовать при реализации такого телефонного справочника, в котором содержится несколько номеров одного абонента.
В последующих разделах мы детально рассмотрим контейнерные типы и разработаем небольшую программу текстового поиска.
6.1. Система текстового поиска
В систему текстового поиска входят текстовый файл, указанный пользователем, и средство для задания запроса, состоящего из слов и, возможно, логических операторов.
Если одно или несколько слов запроса найдены, печатается количество их вхождений. По желанию пользователя печатаются предложения, содержащие найденные слова. Например, если нужно найти все вхождения словосочетаний Civil War и Civil Rights, запрос может выглядеть таким образом :
Civil && ( War || Rights )
Результат запроса:
Civil: 12 вхождений
War: 48 вхождений
Rights: 1 вхождение
Civil && War: 1 вхождение
Civil && Rights: 1 вхождение
(8) Civility, of course, is not to be confused with
Civil Rights, nor should it lead to Civil War
Здесь (8) представляет собой номер предложения в тексте. Наша система должна печатать фразы, содержащие найденные слова, в порядке возрастания их номеров (т.е. предложение номер 7 будет напечатано раньше предложения номер 9), не повторяя одну и ту же несколько раз.
Наша программа должна уметь:
* запросить имя текстового файла, а затем открыть и прочитать этот файл;
* организовать внутреннее представление этого файла так, чтобы впоследствии соотнести
найденное слово с предложением, в котором оно встретилось, и определить порядковый номер этого слова;
* понимать определенный язык запросов. В нашем случае он включает следующие операторы:
&& два слова непосредственно следуют одно за другим в строке
|| одно или оба слова встречаются в строке
! слово не встречается в строке
() группировка слов в запросе
Используя этот язык, можно написать:
Lincoln
чтобы найти все предложения, включающие слово Lincoln, или
! Lincoln
для поиска фраз, не содержащих такого слова, или же
( Abe || Abraham ) && Lincoln
для поиска тех предложений, где есть словосочетания Abe Lincoln или Abraham Lincoln.
Представим две версии нашей системы. В этой главе мы решим проблему чтения и хранения текстового файла в отображении, где ключом является слово, а значением – номер строки и позиции в строке. Мы обеспечим поиск по одному слову. (В главе 17 мы реализуем полную систему поиска, поддерживающую все указанные выше операторы языка запросов с помощью класса Query.) .
Возьмем шесть строчек из неопубликованного детского рассказа Стена Липпмана (Stan Lippman) :
Рис. 2.
Alice Emma has long flowing red hair. Her Daddy says when the wind blows through her hair, it looks almost alive, like a fiery bird in flight. A beautiful fiery bird, he tells her, magical but untamed. "Daddy, shush, there is no such thing," she tells him, at the same time wanting him to tell her more. Shyly, she asks, "I mean. Daddy, is there?"
После считывания текста его внутреннее представление выглядит так (процесс считывания включает ввод очередной строки, разбиение ее на слова, исключение знаков препинания, замену прописных букв строчными, минимальная поддержка работы с суффиксами и исключение таких слов, как and, a, the):
alice ((0,0))
alive ((1,10))
almost ((1,9))
ask ((5,2))
beautiful ((2,7))
bird ((2,3),(2,9))
blow ((1,3))
daddy ((0,8),(3,3),(5,5))
emma ((0,1))
fiery ((2,2),(2,8))
flight ((2,5))
flowing ((0,4))
hair ((0,6),(1,6))
has ((0,2))
like ((2,0))
long ((0,3))
look ((1,8))
magical ((3,0))
mean ((5,4))
more ((4,12))
red ((0,5))
same ((4,5))
say ((0,9))
she ((4,0),(5,1))
shush ((3,4))
shyly ((5,0))
such ((3,8))
tell ((2,11),(4,1),(4,10))
there ((3,5),(5,7))
thing ((3,9))
through ((1,4))
time ((4,6))
untamed ((3,2))
wanting ((4,7))
wind ((1,2))
Ниже приводится пример работы программы, которая будет реализована в данном разделе (то, что задает пользователь, выделено курсивом):
please enter file name: alice_emma
enter a word against which to search the text.
to quit, enter a single character ==> alice
alice occurs 1 time:
( line 1 ) Alice Emma has long flowing red hair. Her Daddy says
enter a word against which to search the text.
to quit, enter a single character ==> daddy
daddy occurs 3 times:
( line 1 ) Alice Emma has long flow-ing red hair. Her Daddy says
( line 4 ) magical but untamed. "Daddy, shush, there is no such thing,"
( line 6 ) Shyly, she asks, "I mean, Daddy, is there?"
enter a word against which to search the text.
to quit, enter a single character ==> phoenix
Sorry. There are no entries for phoenix.
enter a word against which to search the text.
to quit, enter a single character ==> .
Ok, bye!
Для того чтобы реализация была достаточно простой, необходимо детально рассмотреть стандартные контейнерные типы и тип string, представленный в главе 3.
6.2. Вектор или список?
Первая задача, которую должна решить наша программа, – это считывание из файла заранее неизвестного количества слов. Слова хранятся в объектах типа string. Возникает вопрос: в каком контейнере мы будем хранить слова – в последовательном или ассоциативном?
С одной стороны, мы должны обеспечить возможность поиска слова и, в случае успеха, извлечь относящуюся к нему информацию. Отображение map является самым удобным для этого классом.
Но сначала нам нужно просто сохранить слова для предварительной обработки – исключения знаков препинания, суффиксов и т.п. Для этой цели последовательный контейнер подходит гораздо больше. Что же нам использовать: вектор или список?
Если вы уже писали программы на С или на С++ прежних версий, для вас, скорее всего, решающим фактором является возможность заранее узнать количество элементов. Если это количество известно на этапе компиляции, вы используете массив, в противном случае – список, выделяя память под очередной его элемент.
Однако это правило неприменимо к стандартным контейнерам: и vector, и deque допускают динамическое изменение размера. Выбор одного из этих трех классов должен зависеть от способов, с помощью которых элементы добавляются в контейнер и извлекаются из него.
Вектор представляет собой область памяти, где элементы хранятся друг за другом. Для этого типа произвольный доступ (возможность извлечь, например, элемент 5, затем 15, затем 7 и т.д.) можно реализовать очень эффективно, поскольку каждый из них находится на некотором фиксированном расстоянии от начала. Однако вставка, кроме случая добавления в конец, крайне неэффективна: операция вставки в середину вектора потребует перемещения всего, что следует за вставляемым. Особенно это сказывается на больших векторах. (Класс deque устроен аналогично, однако операции вставки и удаления самого первого элемента работают в нем быстрее; это достигается двухуровневым представлением контейнера, при котором один уровень представляет собой реальное размещение элементов, а второй уровень адресует первый и последний из них.)
Список располагается в памяти произвольным образом. Каждый элемент содержит указатели на предыдущий и следующий, что позволяет перемещаться по списку вперед и назад. Вставка и удаление реализованы эффективно: изменяются только указатели. С другой стороны, произвольный доступ поддерживается плохо: чтобы прийти к определенному элементу, придется посетить все предшествующие. Кроме того, в отличие от вектора, дополнительно расходуется память под два указателя на каждый элемент списка.
Вот некоторые критерии для выбора одного из последовательных контейнеров:
* если требуется произвольный доступ к элементам, вектор предпочтительнее;
* если количество элементов известно заранее, также предпочтительнее вектор;
* если мы должны иметь возможность вставлять и удалять элементы в середину, предпочтительнее список;
* если нам не нужна возможность вставлять и удалять элементы в начало контейнера, вектор предпочтительнее, чем deque.
Как быть, если нам нужна возможность и произвольного доступа, и произвольного добавления/удаления элементов? Приходится выбирать: тратить время на поиск элемента или на его перемещение в случае вставки/удаления. В общем случае мы должны исходить из того, какую основную задачу решает приложение: поиск или добавление элементов? (Для выбора подхода может потребоваться измерение производительности для обоих типов контейнеров.) Если ни один из стандартных контейнеров не удовлетворяет нас, может быть, стоит разработать свою собственную, более сложную, структуру данных.
Какой из контейнеров выбрать, если мы не знаем количества его элементов (он будет динамически расти) и у нас нет необходимости ни в произвольном доступе, ни в добавлении элементов в середину? Что в таком случае более эффективно: список или вектор? (Мы отложим ответ на этот вопрос до следующего раздела.)
Список растет очень просто: добавление каждого нового элемента приводит к тому, что указатели на предыдущий и следующий для тех элементов, между которыми вставляется новый, меняют свои значения. В новом элементе таким указателям присваиваются значения адресов соседних элементов. Список использует только тот объем памяти, который нужен для имеющегося количества элементов. Накладными расходами являются два указателя в каждом элементе и необходимость использования указателя для получения значения элемента.
Внутреннее представление вектора и управление занимаемой им памятью более сложны. Мы рассмотрим это в следующем разделе.
Упражнение 6.1
Что лучше выбрать в следующих примерах: вектор, список или двустороннюю очередь? Или ни один из контейнеров не является предпочтительным?
1. Неизвестное заранее количество слов считывается из файла для генерации случайных предложений.
2. Считывается известное количество слов, которые вставляются в контейнер в алфавитном порядке.
3. Считывается неизвестное количество слов. Слова добавляются в конец контейнера, а удаляются всегда из начала.
4. Считывается неизвестное количество целых чисел. Числа сортируются и печатаются.
6.3. Как растет вектор?
Вектор может расти динамически. Как это происходит? Он должен выделить область памяти, достаточную для хранения всех элементов, скопировать в эту область все старые элементы и освободить ту память, в которой они содержались раньше. Если при этом элементы вектора являются объектами класса, то для каждого из них при таком копировании вызываются конструктор и деструктор. Поскольку у списка нет необходимости в таких дополнительных действиях при добавлении новых элементов, кажется очевидным, что ему проще поддерживать динамический рост контейнера. Однако на практике это не так. Давайте посмотрим почему.
Вектор может запрашивать память не под каждый новый элемент. Вместо этого она запрашивается с некоторым запасом, так что после очередного выделения вектор может поместить в себя некоторое количество элементов, не обращаясь за ней снова. (Каков размер этого запаса, зависит от реализации.) На практике такое свойство вектора обеспечивает значительное увеличение его эффективности, особенно для небольших объектов. Давайте рассмотрим некоторые примеры из реализации стандартной библиотеки С++ от компании Rogue Wave. Однако сначала определим разницу между размером и емкостью контейнера.
Емкость – это максимальное количество элементов, которое может вместить контейнер без дополнительного выделения памяти. (Емкостью обладают только те контейнеры, в которых элементы хранятся в непрерывной области памяти, – vector, deque и string. Для контейнера list это понятие не определено.) Емкость может быть получена с помощью функции capacity(). Размер – это реальное количество элементов, хранящихся в данный момент в контейнере. Размер можно получить с помощью функции size(). Например:
#include <vector>
#include <iostream>
int main()
{
vector< int > ivec;
cout << "ivec: размер: " << ivec.size()
<< " емкость: " << ivec.capacity() << endl;
for ( int ix = 0; -ix < 24; ++ix ) {
ivec.push_back( ix );
cout << "ivec: размер: " << ivec.size()
<< " емкость: " << ivec.capacity() << endl;
}
}
В реализации Rogue Wave и размер, и емкость ivec сразу после определения равны 0. После вставки первого элемента размер становится равным 1, а емкость – 256. Это значит, что до первого дополнительного выделения памяти в ivec можно вставить 256 элементов. При добавлении 256-го элемента вектор должен увеличиться: выделить память объемом в два раза больше текущей емкости, скопировать в нее старые элементы и освободить прежнюю память. Обратите внимание: чем больше и сложнее тип данных элементов, тем менее эффективен вектор в сравнении со списком. В таблице 6.1 показана зависимость начальной емкости вектора от используемого типа данных.
Таблица 6.1. Размер и емкость для различных типов данных
Тип данных Размер в байтах Емкость после первой вставки
int 5 256
double 8 128
простой класс #1 12 85
string 12 85
большой простой класс 8000 1
большой сложный класс 8000 1
Итак, в реализации Rogue Wave при первой вставке выделяется точно или примерно 1024 байта. После каждого дополнительного выделения памяти емкость удваивается. Для типа данных, имеющего большой размер, емкость мала, и увеличение памяти с копированием старых элементов происходит часто, вызывая потерю эффективности. (Говоря о сложных классах, мы имеем в виду класс, обладающий копирующим конструктором и операцией присваивания.) В таблице 6.2 показано время в секундах, необходимое для вставки десяти миллионов элементов разного типа в список и в вектор. Таблица 6.3 показывает время, требуемое для вставки 10 000 элементов (вставка элементов большего размера оказалась слишком медленной).
Таблица 6.2. Время в секундах для вставки 10 000 000 элементов
Тип данных List Vector
int 10.38 3.76
double 10.72 3.95
простой класс 12.31 5.89
string 14.42 11.8
Таблица 6.3. Время в секундах для вставки 10 000 элементов
Тип данных List Vector
большой простой класс 0.36 2.23
большой сложный класс 2.37 6.70
Отсюда следует, что вектор лучше подходит для типов данных малого размера, нежели список, и наоборот. Эта разница объясняется необходимостью выделения памяти и копирования в нее старых элементов. Однако размер данных – не единственный фактор, влияющий на эффективность. Сложность типа данных также ухудшает результат. Почему?
Вставка элемента как в список, так и в вектор, требует вызова копирующего конструктора, если он определен. (Копирующий конструктор инициализирует один объект значением другого. В разделе 2.2 приводится начальная информация, а в разделе 14.5 о таких конструкторах рассказывается подробно). Это и объясняет различие в поведении простых и сложных объектов при вставке в контейнер. Объекты простого класса вставляются побитовым копированием (биты одного объекта пересылаются в биты другого), а для строк и сложных классов это производится вызовом копирующего конструктора.
Вектор должен вызывать их для каждого элемента при перераспределении памяти. Более того, освобождение памяти требует работы деструкторов для всех элементов (понятие деструктора вводится в разделе 2.2). Чем чаще происходит перераспределение памяти, тем больше времени тратится на эти дополнительные вызовы конструкторов и деструкторов.
Конечно, одним из решений может быть переход от вектора к списку, когда эффективность вектора становится слишком низкой. Другое, более предпочтительное решение состоит в том, чтобы хранить в векторе не объекты сложного класса, а указатели на них. Такая замена позволяет уменьшить затраты времени на 10 000 вставок с 6.70 секунд до 0.82 секунды. Почему? Емкость возросла с 1 до 256, что существенно снизило частоту перераспределения памяти. Кроме того, копирующий конструктор и деструктор не вызываются больше для каждого элемента при копировании прежнего содержимого вектора.
Функция reserve() позволяет программисту явно задать емкость контейнера . Например:
int main() {
vector< string > svec;
svec.reserve( 32 ); // задает емкость равной 32
// ...
}
svec получает емкость 32 при размере 0. Однако эксперименты показали, что любое изменение начальной емкости для вектора, у которого она по умолчанию отлична от 1, ведет к снижению производительности. Так, для векторов типа string и double увеличение емкости с помощью reserve() дало худшие показатели. С другой стороны, увеличение емкости для больших сложных типов дает значительный рост производительности, как показано в таблице 6.4.
Таблица 6.4. Время в секундах для вставки 10 000 элементов при различной емкости*
Емкость Время в секундах
1 по умолчанию 670
4,096 555
8,192 444
10,000 222
*Сложный класс размером 8000 байт с конструктором копирования и деструктором
В нашей системе текстового поиска для хранения объектов типа string мы будем использовать вектор, не меняя его емкости по умолчанию. Наши измерения показали, что производительность вектора в данном случае лучше, чем у списка. Но прежде чем приступать к реализации, посмотрим, как определяется объект контейнерного типа.
Упражнение 6.2
Объясните разницу между размером и емкостью контейнера. Почему понятие емкости необходимо для контейнера, содержащего элементы в непрерывной области памяти, и не нужно для списка?
Упражнение 6.3
Почему большие сложные объекты удобнее хранить в контейнере в виде указателей на них, а для коллекции целых чисел применение указателей снижает эффективность?
Упражнение 6.4
Объясните, какой из типов контейнера – вектор или список – больше подходит для приведенных примеров (во всех случаях происходит вставка неизвестного заранее числа элементов):.
(a) Целые числа
(b) Указатели на большие сложные объекты
(c) Большие сложные объекты
6.4. Как определить последовательный контейнер?
Для того чтобы определить объект контейнерного типа, необходимо сначала включить соответствующий заголовочный файл:
#include <vector>
#inclnde <list>
#include <deque>
#include <map>
#include <set>
Определение контейнера начинается именем его типа, за которым в угловых скобках следует тип данных его элементов . Например:
vector< string > svec;
list< int > ilist;
Переменная svec определяется как вектор, способный содержать элементы типа string, а ilist – как список с элементами типа int. Оба контейнера при таком определении пусты. Чтобы убедиться в этом, можно вызвать функцию-член empty():
if ( svec.empty() != true )
; // что-то не так
Простейший метод вставки элементов – использование функции-члена push_back(), которая добавляет элементы в конец контейнера. Например:
string text_word;
while ( cin >> text_word )
svec.push_back( text_word );
Здесь строки из стандартного ввода считываются в переменную text_word, и затем копия каждой строки добавляется в контейнер svec с помощью push_back().
Список имеет функцию-член push_front(), которая добавляет элемент в его начало. Пусть есть следующий массив:
int ia[ 4 ] = { 0, 1, 2, 3 };
Использование push_back()
for ( int ix=0; ix<4; ++ix )
ilist.push_back( ia[ ix ] );
создаст последовательность 0, 1, 2, 3, а push_front()
for ( int ix=0; ix<4; ++ix )
ilist.push_front( ia[ ix ] );
создаст последовательность 3, 2, 1, 0.
Мы можем при создании явно указать размер массива – как константным, так и неконстантным выражением:
#include <list>
#include <vector>
#include <string>
extern int get_word_count( string file_name );
const int list_size = 64;
list< int > ilist( list_size );
vector< string > svec(get_word_count(string("Chimera")));
Каждый элемент контейнера инициализируется значением по умолчанию, соответствующим типу данных. Для int это 0. Для строкового типа вызывается конструктор по умолчанию класса string.
Мы можем указать начальное значение всех элементов:
list< int > ilist( list_size, -1 );
vector< string > svec( 24, "pooh" );
Разрешается не только задавать начальный размер контейнера, но и впоследствии изменять его с помощью функции-члена resize(). Например:
svec.resize( 2 * svec.size() );
Размер svec в этом примере удваивается. Каждый новый элемент получает значение по умолчанию. Если мы хотим инициализировать его каким-то другим значением, то оно указывается вторым параметром функции-члена resize():
// каждый новый элемент получает значение "piglet"
svec.resize( 2 * svec.size(), "piglet" );
Кстати, какова наиболее вероятная емкость svec при определении, если его начальный размер равен 24? Правильно, 24! В общем случае минимальная емкость вектора равна его текущему размеру. При удвоении размера емкость, как правило, тоже удваивается
Мы можем инициализировать новый контейнер с помощью существующего. Например:
vector< string > svec2( svec );
list< int > ilist2( ilist ) ;
Каждый контейнер поддерживает полный набор операций сравнения: равенство, неравенство, меньше, больше, меньше или равно, больше или равно. Сопоставляются попарно все элементы контейнера. Если они равны и размеры контейнеров одинаковы, то эти контейнеры равны; в противном случае – не равны. Результат операций "больше” или "меньше” определяется сравнением первых двух неравных элементов. Вот что печатает программа, сравнивающая пять векторов:
ivecl: 1 3 5 7 9 12
ivec2: 0 1 1 2 3 5 8 13
ivec3: 1 3 9
ivec4: 1 3 5 7
ivec5: 2 4
// первый неравный элемент: 1, О
// ivecl больше чем ivec2
ivecl < ivec2 //false
ivec2 < ivecl //true
// первый неравный элемент: 5, 9
ivecl < ivec3 //true
// все элементы равны, но ivec4 содержит меньше элементов
// следовательно, ivec4 меньше, чем ivecl
ivecl < ivec4 //false
// первый неравный элемент: 1, 2
ivecl < ivec5 //true
ivecl == ivecl //true
ivecl == ivec4 //false
ivecl != ivec4 //true
ivecl > ivec2 //true
ivec3 > ivecl //true
ivec5 > ivec2 //true
Существуют три ограничения на тип элементов контейнера (практически это касается только пользовательских классов). Для должны быть определены:
* операция "равно”;
* операция "меньше” (все операции сравнения контейнеров, о которых говорилось выше, используют только эти две операции сравнения);
* значение по умолчанию (для класса это означает наличие конструктора по умолчанию).
Все предопределенные типы данных, включая указатели и классы из стандартной библиотеки С++ удовлетворяют этим требованиям.
Упражнение 6.5
Объясните, что делает данная программа:
#include <string>
#include <vector>
#include <iostream>
#int main()
{
vector<string> svec;
svec.reserve( 1024 );
string text_word;
while ( cin >> text_word )
svec.push_back( text_word );
svec.resize( svec.size()+svec.size()/2 );
// ...
}
Упражнение 6.6
Может ли емкость контейнера быть меньше его размера? Желательно ли, чтобы емкость была равна размеру: изначально или после вставки элемента? Почему?
Упражнение 6.7
Если программа из упражнения 6.5 прочитает 256 слов, то какова наиболее вероятная емкость контейнера после изменения размера? А если она считает 512 слов? 1000? 1048?
Упражнение 6.8
Какие из данных классов не могут храниться в векторе:
(a)
class cl1 {
public:
c11( int=0 );
bool operator==();
bool operator!=();
bool operator<=();
bool operator<();
// ...
};
(b)
class c12 {
public:
c12( int=0 );
bool operator!=();
bool operator<=();
// ...
};
(с)
class c13 {
public:
int ival;
};
(d)
class c14 {
public:
c14( int, int=0 );
bool operator==();
bool operator!=();
// ...
}
6.5. Итераторы
Итератор предоставляет обобщенный способ перебора элементов любого контейнера – как последовательного, так и ассоциативного. Пусть iter является итератором для какого-либо контейнера. Тогда
++iter;
перемещает итератор так, что он указывает на следующий элемент контейнера, а
*iter;
разыменовывает итератор, возвращая элемент, на который он указывает.
Все контейнеры имеют функции-члены begin() и end().
* begin() возвращает итератор, указывающий на первый элемент контейнера.
* end() возвращает итератор, указывающий на элемент, следующий за последним в контейнере.
Чтобы перебрать все элементы контейнера, нужно написать:
for ( iter = container. begin();
iter != container.end(); ++iter )
do_something_with_element( *iter );
Объявление итератора выглядит слишком сложным. Вот определение пары итераторов вектора типа string:
// vector<string> vec;
vector<string>::iterator iter = vec.begin();
vector<string>::iterator iter_end = vec.end();
В классе vector для определения iterator используется typedef. Синтаксис
vector<string>::iterator
ссылается на iterator, определенный с помощью typedef внутри класса vector, содержащего элементы типа string.
Для того чтобы напечатать все элементы вектора, нужно написать:
for( ; iter != iter_end; ++iter )
cout << *iter << '\n';
Здесь значением *iter выражения является, конечно, элемент вектора.
В дополнение к типу iterator в каждом контейнере определен тип const_iterator, который необходим для навигации по контейнеру, объявленному как const. const_iterator позволяет только читать элементы контейнера:
#include <vector>
void even_odd( const vector<int> *pvec,
vector<int> *pvec_even,
vector<int> *pvec_odd )
{
// const_iterator необходим для навигации по pvec
vector<int>::const_iterator c_iter = pvec->begin();
vector<int>::const_1terator c_iter_end = pvec->end();
for ( ; c_iter != c_iter_end; ++c_iter )
if ( *c_iter % 2 )
pvec_even->push_back( *c_iter );
else pvec_odd->push_back( *c_iter );
}
Что делать, если мы хотим просмотреть некоторое подмножество элементов, например взять каждый второй или третий элемент, или хотим начать с середины? Итераторы поддерживают адресную арифметику, а значит, мы можем прибавить некоторое число к итератору:
vector<int>::iterator iter = vec->begin()+vec.size()/2;
iter получает значение адреса элемента из середины вектора, а выражение
iter += 2;
сдвигает iter на два элемента.
Арифметические действия с итераторами возможны только для контейнеров vector и deque. list не поддерживает адресную арифметику, поскольку его элементы не располагаются в непрерывной области памяти. Следующее выражение к списку неприменимо:
ilist.begin() + 2;
так как для перемещения на два элемента необходимо два раза перейти по адресу, содержащемуся в закрытом члене next. У классов vector и deque перемещение на два элемента означает прибавление 2 к указателю на текущий элемент. (Адресная арифметика рассматривается в разделе 3.3.)
Объект контейнерного типа может быть инициализирован парой итераторов, обозначающих начало и конец последовательности копируемых в новый объект элементов. (Второй итератор должен указывать на элемент, следующий за последним копируемым.) Допустим, есть вектор:
#include <vector>
#include <string>
#include <iostream>
int main()
{
vector<string> svec;
string intext;
while ( cin >> intext )
svec.push_back( intext );
// обработать svec ...
}
Вот как можно определить новые векторы, инициализируя их элементами первого вектора:
int main() {
vector<string> svec;
// ...
// инициализация svec2 всеми элементами svec
vector<string> svec2( svec.begin(), svec.end() );
// инициализация svec3 первой половиной svec
vector<string>::iterator it =
svec.begin() + svec.size()/2;
vector<string> svec3 ( svec.begin(), it );
// ...
}
Использование специального типа istream_iterator (о нем рассказывается в разделе 12.4.3) упрощает чтение элементов из входного потока в svec:
#include <vector>
#include <string>
#include <iterator>
int mainQ
{
// привязка istream_iterator к стандартному вводу
istream_iterator<string> infile( cin );
// istream_iterator, отмечающий конец потока
istream_iterator<string> eos;
// инициализация svec элементами, считываемыми из cin;
vector<string> svec( infile, eos );
// ...
}
Кроме итераторов, для задания диапазона значений, инициализирующих контейнер, можно использовать два указателя на массив встроенного типа. Пусть есть следующий массив строк:
#include <string>
string words[4] = {
"stately", "plump", "buck", "mulligan"
};
Мы можем инициализировать вектор с помощью указателей на первый элемент массива и на элемент, следующий за последним:
vector< string > vwords( words, words+4 );
Второй указатель служит "стражем”: элемент, на который он указывает, не копируется.
Аналогичным образом можно инициализировать список целых элементов:
int ia[6] = { 0, 1, 2, 3, 4, 5 };
list< int > ilist( ia, ia+6 );
В разделе 12.4 мы снова обратимся к итераторам и опишем их более детально. Сейчас информации достаточно для того, чтобы использовать итераторы в нашей системе текстового поиска. Но прежде чем вернуться к ней, рассмотрим некоторые дополнительные операции, поддерживаемые контейнерами.
Упражнение 6.9
Какие ошибки допущены при использовании итераторов:
const vector< int > ivec;
vector< string > svec;
list< int > ilist;
(a) vector<int>::iterator it = ivec.begin();
(b) list<int>::iterator it = ilist.begin()+2;
(c) vector<string>::iterator it = &svec[0];
(d) for ( vector<string>::iterator
it = svec.begin(); it != 0; ++it )
// ...
Упражнение 6.10
Найдите ошибки в использовании итераторов:
int ia[7] = { 0, 1, 1, 2, 3, 5, 8 };
string sa[6] = {
"Fort Sumter", "Manassas", "Perryville", "Vicksburg",
"Meridian", "Chancellorsvine" };
(a) vector<string> svec( sa, &sa[6] );
(b) list<int> ilist( ia+4, ia+6 );
(c) list<int> ilist2( ilist.begin(), ilist.begin()+2 );
(d) vector<int> ivec( &ia[0], ia+8 );
(e) list<string> slist( sa+6, sa );
(f) vector<string> svec2( sa, sa+6 );
6.6. Операции с последовательными контейнерами
Функция-член 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() );
или любого контейнера, содержащего строки:
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 <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 все нечетные элементы.
6.7. Читаем текстовый файл
Первая наша задача – прочитать текстовый файл, в котором будет производиться поиск. Нам нужно сохранить следующую информацию: само слово, номер строки и позицию в строке, где слово встречается.
Как получить одну строку текста? Стандартная библиотека предоставляет для этого функцию getline():
istream&
getline( istream &is, string str, char delimiter );
getline()берет из входного потока все символы, включая пробелы, и помещает их в объект типа string, до тех пор пока не встретится символ delimiter, не будет достигнут конец файла или количество полученных символов не станет равным величине, возвращаемой функцией-членом max_size()класса string.
Мы будем помещать каждую такую строку в вектор.
Мы вынесли код, читающий файл, в функцию, названную retrieve_text(). В объекте типа pair дополнительно сохраняется размер и номер самой длинной строки. (Полный текст программы приводится в разделе 6.14.)
Вот реализация функции ввода файла:
// возвращаемое значение - указатель на строковый вектор
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;
}
lines_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 и рассмотрим многочисленные операции над строками, которые он поддерживает, в контексте дальнейшей разработки нашей поисковой системы.
|
| Категория: С++ | Добавил: r2d2 (29.09.2011)
|
| Просмотров: 1376
| Рейтинг: 0.0/0 |
Добавлять комментарии могут только зарегистрированные пользователи. [ Регистрация | Вход ] |
|
| Born in Ussr |
|
|
| Залогиниться |
|
|
|
| Турниры |
|
|
|
