Язык программирования C++. Вводный курс


Как растет вектор? - часть 2


/p>

}

В реализации Rogue Wave и размер, и емкость ivec сразу после определения равны 0. После вставки первого элемента размер становится равным 1, а емкость – 256. Это значит, что до первого дополнительного выделения памяти в ivec

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

Таблица 6.1. Размер и емкость для различных типов данных

Тип данных

Размер в байтах

Емкость после первой вставки

int

4

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

 

Таблица 6.3. Время в секундах для вставки 10 000 элементов

Тип данных

List

Vector

большой простой класс

0.36

2.23

большой сложный класс

2.37

6.70

<


Начало  Назад  Вперед



Книжный магазин