6.2. Вектор или список?

6.2. Вектор или список?

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

С одной стороны, мы должны обеспечить возможность поиска слова и, в случае успеха, извлечь относящуюся к нему информацию. Отображение map является самым удобным для этого классом.

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

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

Однако это правило неприменимо к стандартным контейнерам: и vector, и deque допускают динамическое изменение размера. Выбор одного из этих трех классов должен зависеть от способов, с помощью которых элементы добавляются в контейнер и извлекаются из него.

Вектор представляет собой область памяти, где элементы хранятся друг за другом. Для этого типа произвольный доступ (возможность извлечь, например, элемент 5, затем 15, затем 7 и т.д.) можно реализовать очень эффективно, поскольку каждый из них находится на некотором фиксированном расстоянии от начала. Однако вставка, кроме случая добавления в конец, крайне неэффективна: операция вставки в середину вектора потребует перемещения всего, что следует за вставляемым. Особенно это сказывается на больших векторах. (Класс deque устроен аналогично, однако операции вставки и удаления самого первого элемента работают в нем быстрее; это достигается двухуровневым представлением контейнера, при котором один уровень представляет собой реальное размещение элементов, а второй уровень адресует первый и последний из них.)

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

Вот некоторые критерии для выбора одного из последовательных контейнеров:

* если требуется произвольный доступ к элементам, вектор предпочтительнее;

* если количество элементов известно заранее, также предпочтительнее вектор;

* если мы должны иметь возможность вставлять и удалять элементы в середину, предпочтительнее список;

* если нам не нужна возможность вставлять и удалять элементы в начало контейнера, вектор предпочтительнее, чем deque.

Как быть, если нам нужна возможность и произвольного доступа, и произвольного добавления/удаления элементов? Приходится выбирать: тратить время на поиск элемента или на его перемещение в случае вставки/удаления. В общем случае мы должны исходить из того, какую основную задачу решает приложение: поиск или добавление элементов? (Для выбора подхода может потребоваться измерение производительности для обоих типов контейнеров.) Если ни один из стандартных контейнеров не удовлетворяет нас, может быть, стоит разработать свою собственную, более сложную, структуру данных.

Какой из контейнеров выбрать, если мы не знаем количества его элементов (он будет динамически расти) и у нас нет необходимости ни в произвольном доступе, ни в добавлении элементов в середину? Что в таком случае более эффективно: список или вектор? (Мы отложим ответ на этот вопрос до следующего раздела.)

Список растет очень просто: добавление каждого нового элемента приводит к тому, что указатели на предыдущий и следующий для тех элементов, между которыми вставляется новый, меняют свои значения. В новом элементе таким указателям присваиваются значения адресов соседних элементов. Список использует только тот объем памяти, который нужен для имеющегося количества элементов. Накладными расходами являются два указателя в каждом элементе и необходимость использования указателя для получения значения элемента.

Внутреннее представление вектора и управление занимаемой им памятью более сложны. Мы рассмотрим это в следующем разделе.

Упражнение 6.1

Что лучше выбрать в следующих примерах: вектор, список или двустороннюю очередь? Или ни один из контейнеров не является предпочтительным?

* Неизвестное заранее количество слов считывается из файла для генерации случайных предложений.

* Считывается известное количество слов, которые вставляются в контейнер в алфавитном порядке.

* Считывается неизвестное количество слов. Слова добавляются в конец контейнера, а удаляются всегда из начала.

* Считывается неизвестное количество целых чисел. Числа сортируются и печатаются.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг

КОСМОС: Красный вектор: Что нового мы узнали о Марсе за последние десят лет?

Из книги Журнал «Компьютерра» N 10 от 13 марта 2007 года автора Журнал «Компьютерра»

КОСМОС: Красный вектор: Что нового мы узнали о Марсе за последние десят лет? Автор: Александр БумагинС тех пор как переводчики переврали смысл работы Скиапарелли, разместив на Марсе рукотворные каналы, разговоры об этой планете не утихают. Голубая мечта о братьях по


Вектор (Vector)

Из книги Руководство по стандартной библиотеке шаблонов (STL) автора Ли Менг

Вектор (Vector) vector - вид последовательности, которая поддерживает итераторы произвольного доступа. Кроме того, он поддерживает операции вставки и удаления в конце с постоянным (амортизированным) временем; вставка и удаление в середине занимают линейное время. Управление


СПИСОК ЛІТЕРАТУРИ

Из книги Вступ до інженерії програмного забезпечення автора Сидоров М. О.

СПИСОК ЛІТЕРАТУРИ 1. Basilli V.R. Viewing Maintenance as Reuse-Oriented Software Development/V.R. Basilli //IEEE Software. 1990. - June. -P. 19-25.2. Boehm B.W. Improving Software Productivity / B.W. Boehm // Computer. - 1987. - Vol. 20, n.9. - P. 43 - 57.3. Boehm B.W. Software Engineering Economics / B.W. Boehm - Englewood Cliffs, Ш.: Prentice-Hall, 1981. - 257 p.4. Boehm B.W. Spiral Model of software Development and Enhancement / B.W. Boehm // Computer. - 1988, - May. - P.


23.4.4. Список

Из книги Linux: Полное руководство автора Колисниченко Денис Николаевич

23.4.4. Список Виджит CList представляет собой список, состоящий из нескольких колонок. Ячейки такого списка могут содержать текстовые значения. Мы можем обратиться отдельно к каждой ячейке списка. Создать список можно одной из функций:GtkWidget *gtk_clist_new(gint columns);GtkWidget


Список литературы

Из книги Фундаментальные алгоритмы и структуры данных в Delphi автора Бакнелл Джулиан М.

Список литературы Ниже приведен список литературы, которая использовалась при написании этой книги. Некоторые из указанных работ имеют исключительно большое значение - без них я не смог бы разобраться в некоторых алгоритмах и пояснить их читателям применительно к Delphi.


1.10. Список литературы

Из книги Видеосамоучитель создания реферата, курсовой, диплома на компьютере автора Баловсяк Надежда Васильевна

1.10. Список литературы Составление списка литературы – важный этап в написании работы. Этот небольшой раздел сразу привлекает внимание проверяющих. Поэтому рекомендуется отнестись к созданию и оформлению перечня использованных источников особо тщательно.Список


Список Web-сайтов

Из книги Firebird РУКОВОДСТВО РАЗРАБОТЧИКА БАЗ ДАННЫХ автора Борри Хелен

Список Web-сайтов Сайты проекта Firebird http://sourceforge.net/projects/firebird является сайтом разработчиков, где вы можете получить доступ к дереву CVS, к исходным и двоичным кодам комплекта поставки и просмотреть список выявленных ошибок.http://www.firebirdsql.org, алиас http://firebird.sourceforge.net. Здесь вы


Контрольный список

Из книги IT-безопасность: стоит ли рисковать корпорацией? автора Маккарти Линда

Контрольный список Используйте этот список, чтобы определить, позволяет ли организационное строение вашей компании и имеющиеся в ней уровни руководства надлежащим образом решать вопросы безопасности. Можете ли вы поставить «Да» напротив каждого пункта?— Регулярно ли


3. Список

Из книги Инфобизнес за один день автора Ушанов Азамат

3. Список «10 способов, как сделать то-то», «17 секретов, как добиться успеха», «Пять способов, как избежать неудачи» – статья, видеоурок или скрин-каст. Это делается легко, потому что любой вопрос можно разбить на несколько частей, секретов, фишек и технологий, и описать их в


7 февраля 2014 года — день истины, определивший вектор самосовершенствования Сергей Голубицкий

Из книги Цифровой журнал «Компьютерра» № 211 автора Журнал «Компьютерра»

7 февраля 2014 года — день истины, определивший вектор самосовершенствования Сергей Голубицкий Опубликовано 07 февраля 2014 На сегодня у меня была запланирована бомба, потенциал которой я попытался вложить в название — «Окончательный вердикт по


БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Из книги Основы программирования на Java автора Сухов С. А.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК 1. Стефен Р. Дэвис. Программирование на Microsoft Visual Java++: пер. с англ. - М.: Издательский отдел «Русская редакция», 1997.2. Ленди М., Сиддикви С., Свишер Д., Borland JBuilder. Руководство разработчика.: пер. с англ. - М.: Издательский дом «Вильямс», 2004.3. Нотон П. Java.


2.8. Стандартный массив - это вектор

Из книги C++ для начинающих автора Липпман Стенли

2.8. Стандартный массив - это вектор Хотя встроенный массив формально и обеспечивает механизм контейнера, он, как мы видели выше, не поддерживает семантику абстракции контейнера. До принятия стандарта C++ для программирования на таком уровне мы должны были либо


5.11.1. Обобщенный список

Из книги Программист-фанатик автора Фаулер Чед

5.11.1. Обобщенный список Наш класс ilist имеет серьезный недостаток: он может хранить элементы только целого типа. Если бы он мог содержать элементы любого типа – как встроенного, так и определенного пользователем, – то его область применения была бы гораздо шире.


6.3. Как растет вектор?

Из книги автора

6.3. Как растет вектор? Вектор может расти динамически. Как это происходит? Он должен выделить область памяти, достаточную для хранения всех элементов, скопировать в эту область все старые элементы и освободить ту память, в которой они содержались раньше. Если при этом


14.4.2. Вектор объектов

Из книги автора

14.4.2. Вектор объектов Когда определяется вектор из пяти объектов класса, например:vector Point vec( 5 );* то инициализация элементов производится в следующем порядке5: С помощью конструктора по умолчанию создается временный объект типа класса, хранящегося в векторе.* К каждому