C++ для начинающих

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))

Ниже приводится пример работы программы, которая будет реализована в данном разделе (то, что задает пользователь, выделено курсивом):

( line 1 ) Alice Emma has long flowing red hair. Her Daddy says

enter a word against which to search the text.

( 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.

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.