С.Б. Липпман, Ж. Лажойе - Язык программирования С++ Вводный курс (1114944), страница 42
Текст из файла (страница 42)
Дляэтого типа произвольный доступ (возможность извлечь, например, элемент 5, затем 15,затем 7 и т.д.) можно реализовать очень эффективно, поскольку каждый из нихнаходится на некотором фиксированном расстоянии от начала. Однако вставка, кромеслучая добавления в конец, крайне неэффективна: операция вставки в середину векторапотребует перемещения всего, что следует за вставляемым. Особенно это сказывается набольших векторах. (Класс deque устроен аналогично, однако операции вставки иудаления самого первого элемента работают в нем быстрее; это достигаетсядвухуровневым представлением контейнера, при котором один уровень представляетсобой реальное размещение элементов, а второй уровень адресует первый и последний изних.)Список располагается в памяти произвольным образом. Каждый элемент содержитуказатели на предыдущий и следующий, что позволяет перемещаться по списку вперед иназад. Вставка и удаление реализованы эффективно: изменяются только указатели.
Сдругой стороны, произвольный доступ поддерживается плохо: чтобы прийти копределенному элементу, придется посетить все предшествующие. Кроме того, в отличиеот вектора, дополнительно расходуется память под два указателя на каждый элементсписка.Вот некоторые критерии для выбора одного из последовательных контейнеров:•если требуется произвольный доступ к элементам, вектор предпочтительнее;•если количество элементов известно заранее, также предпочтительнее вектор;•если мы должны иметь возможность вставлять и удалять элементы в середину,предпочтительнее список;•если нам не нужна возможность вставлять и удалять элементы в началоконтейнера, вектор предпочтительнее, чем deque.Как быть, если нам нужна возможность и произвольного доступа, и произвольногодобавления/удаления элементов? Приходится выбирать: тратить время на поиск элементаили на его перемещение в случае вставки/удаления.
В общем случае мы должны исходитьиз того, какую основную задачу решает приложение: поиск или добавление элементов?(Для выбора подхода может потребоваться измерение производительности для обоихтипов контейнеров.) Если ни один из стандартных контейнеров не удовлетворяет нас,может быть, стоит разработать свою собственную, более сложную, структуру данных.Какой из контейнеров выбрать, если мы не знаем количества его элементов (он будетдинамически расти) и у нас нет необходимости ни в произвольном доступе, ни вдобавлении элементов в середину? Что в таком случае более эффективно: список иливектор? (Мы отложим ответ на этот вопрос до следующего раздела.)Список растет очень просто: добавление каждого нового элемента приводит к тому, чтоуказатели на предыдущий и следующий для тех элементов, между которыми вставляетсяновый, меняют свои значения.
В новом элементе таким указателям присваиваютсязначения адресов соседних элементов. Список использует только тот объем памяти,который нужен для имеющегося количества элементов. Накладными расходами являютсядва указателя в каждом элементе и необходимость использования указателя дляполучения значения элемента.Внутреннее представление вектора и управление занимаемой им памятью более сложны.Мы рассмотрим это в следующем разделе.248С++ для начинающихУпражнение 6.1Что лучше выбрать в следующих примерах: вектор, список или двустороннюю очередь?Или ни один из контейнеров не является предпочтительным?1.
Неизвестное заранее количество слов считывается из файла для генерации случайныхпредложений.2. Считывается известное количество слов, которые вставляются в контейнер валфавитном порядке.3. Считывается неизвестное количество слов. Слова добавляются в конец контейнера, аудаляются всегда из начала.4. Считывается неизвестное количество целых чисел. Числа сортируются и печатаются.6.3. Как растет вектор?Вектор может расти динамически. Как это происходит? Он должен выделить областьпамяти, достаточную для хранения всех элементов, скопировать в эту область все старыеэлементы и освободить ту память, в которой они содержались раньше.
Если при этомэлементы вектора являются объектами класса, то для каждого из них при такомкопировании вызываются конструктор и деструктор. Поскольку у списка нетнеобходимости в таких дополнительных действиях при добавлении новых элементов,кажется очевидным, что ему проще поддерживать динамический рост контейнера.Однако на практике это не так. Давайте посмотрим почему.Вектор может запрашивать память не под каждый новый элемент. Вместо этого оназапрашивается с некоторым запасом, так что после очередного выделения вектор можетпоместить в себя некоторое количество элементов, не обращаясь за ней снова. (Каковразмер этого запаса, зависит от реализации.) На практике такое свойство вектораобеспечивает значительное увеличение его эффективности, особенно для небольшихобъектов.
Давайте рассмотрим некоторые примеры из реализации стандартнойбиблиотеки С++ от компании Rogue Wave. Однако сначала определим разницу междуразмером и емкостью контейнера.Емкость – это максимальное количество элементов, которое может вместить контейнербез дополнительного выделения памяти. (Емкостью обладают только те контейнеры, вкоторых элементы хранятся в непрерывной области памяти, – vector, deque и string.Для контейнера list это понятие не определено.) Емкость может быть получена спомощью функции capacity(). Размер – это реальное количество элементов,хранящихся в данный момент в контейнере.
Размер можно получить с помощью функцииsize(). Например:249С++ для начинающих250#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Размер Емкость послев байтах первой вставки4256double8128простой класс #1128512858000800011stringбольшой простой классбольшой сложный классИтак, в реализации Rogue Wave при первой вставке выделяется точно или примерно 1024байта. После каждого дополнительного выделения памяти емкость удваивается.
Для типаданных, имеющего большой размер, емкость мала, и увеличение памяти с копированиемстарых элементов происходит часто, вызывая потерю эффективности. (Говоря о сложныхклассах, мы имеем в виду класс, обладающий копирующим конструктором и операциейприсваивания.) В таблице 6.2 показано время в секундах, необходимое для вставкидесяти миллионов элементов разного типа в список и в вектор.
Таблица 6.3 показываетвремя, требуемое для вставки 10 000 элементов (вставка элементов большего размераоказалась слишком медленной).Таблица 6.2. Время в секундах для вставки 10 000 000 элементовТип данныхintListVector10.383.76С++ для начинающих251double10.723.95простой класс12.315.89string14.4211.80Таблица 6.3. Время в секундах для вставки 10 000 элементовТип данныхListVectorбольшой простой класс0.362.23большой сложный класс2.376.70Отсюда следует, что вектор лучше подходит для типов данных малого размера, нежелисписок, и наоборот.
Эта разница объясняется необходимостью выделения памяти икопирования в нее старых элементов. Однако размер данных – не единственный фактор,влияющий на эффективность. Сложность типа данных также ухудшает результат.Почему?Вставка элемента как в список, так и в вектор, требует вызова копирующегоконструктора, если он определен. (Копирующий конструктор инициализирует одинобъект значением другого. В разделе 2.2 приводится начальная информация, а в разделе14.5 о таких конструкторах рассказывается подробно). Это и объясняет различие вповедении простых и сложных объектов при вставке в контейнер. Объекты простогокласса вставляются побитовым копированием (биты одного объекта пересылаются вбиты другого), а для строк и сложных классов это производится вызовом копирующегоконструктора.Вектор должен вызывать их для каждого элемента при перераспределении памяти.
Болеетого, освобождение памяти требует работы деструкторов для всех элементов (понятиедеструктора вводится в разделе 2.2). Чем чаще происходит перераспределение памяти,тем больше времени тратится на эти дополнительные вызовы конструкторов идеструкторов.Конечно, одним из решений может быть переход от вектора к списку, когдаэффективность вектора становится слишком низкой. Другое, более предпочтительноерешение состоит в том, чтобы хранить в векторе не объекты сложного класса, а указателина них. Такая замена позволяет уменьшить затраты времени на 10 000 вставок с 6.70секунд до 0.82 секунды. Почему? Емкость возросла с 1 до 256, что существенно снизилочастоту перераспределения памяти.
Кроме того, копирующий конструктор и деструкторне вызываются больше для каждого элемента при копировании прежнего содержимоговектора.Функция reserve() позволяет программисту явно задать емкость контейнера11.int main() {vector< string > svec;svec.reserve( 32 ); // задает емкость равной 32// ...Например:11 Отметим, что deque не поддерживает операцию reserve()С++ для начинающих252}svec получает емкость 32 при размере 0. Однако эксперименты показали, что любоеизменение начальной емкости для вектора, у которого она по умолчанию отлична от 1,ведет к снижению производительности.
Так, для векторов типа string и doubleувеличение емкости с помощью reserve() дало худшие показатели. С другой стороны,увеличение емкости для больших сложных типов дает значительный ростпроизводительности, как показано в таблице 6.4.Таблица 6.4. Время в секундах для вставки 10 000 элементов при различнойемкости*ЕмкостьВремя в секундах1 по умолчанию6704,0965558,19244410,000222*Сложный класс размером 8000 байт сконструктором копирования и деструкторомВ нашей системе текстового поиска для хранения объектов типа string мы будемиспользовать вектор, не меняя его емкости по умолчанию. Наши измерения показали, чтопроизводительность вектора в данном случае лучше, чем у списка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
