управление памятью — начальная емкость вектора в переполнении стека

Реализации хранилища std :: vector значительно различаются, но все, с которыми я сталкивался, начинаются с 0.

Следующий код:

#include <iostream>
#include <vector>

int main()
{
using namespace std;

vector<int> normal;
cout << normal.capacity() << endl;

for (unsigned int loop = 0; loop != 10; ++loop)
{
normal.push_back(1);
cout << normal.capacity() << endl;
}

std::cin.get();
return 0;
}

Дает следующий вывод:

0
1
2
4
4
8
8
8
8
16
16

в соответствии с GCC 5.1 и:

0
1
2
3
4
6
6
9
9
9
13

под MSVC 2013.

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

В частности, если _ITERATOR_DEBUG_LEVEL! = 0, то вектор выделит некоторое пространство, чтобы помочь с проверкой итератора.

https://docs.microsoft.com/en-gb/cpp/standard-library/iterator-debug-level

Я только нашел это немного раздражающим, так как я использовал пользовательский распределитель в то время и не ожидал дополнительного выделения.

Насколько я понял стандарт (хотя на самом деле я не мог назвать ссылку), инстанцирование контейнера и выделение памяти были преднамеренно разделены по уважительной причине. Для этого у вас есть отдельные, отдельные призывы к

• constructor создать сам контейнер
• reserve() предварительно выделить достаточно большой блок памяти для размещения хотя бы (!) заданного количества объектов

И это имеет большой смысл. Единственное право на существование для reserve() чтобы дать вам возможность кодировать возможные дорогостоящие перераспределения при увеличении вектора. Для того, чтобы быть полезным, вы должны знать количество объектов для хранения или, по крайней мере, должны уметь делать обоснованные предположения. Если это не дано, вам лучше держаться подальше от reserve() как вы просто измените перераспределение для потраченной памяти.

Итак, все вместе:

• Стандарт намеренно делает не указать конструктор, который позволяет предварительно выделить блок памяти для определенного количества объектов (что было бы по меньшей мере более желательно, чем выделение определенной реализации, фиксированной «что-то» под капотом).
• Распределение не должно быть неявным. Итак, чтобы предварительно выделить блок, вам нужно сделать отдельный вызов reserve() и это не обязательно должно быть в том же месте строительства (может / должно быть, конечно, позже, после того, как вы узнали о необходимом размере для размещения)
• Таким образом, если вектор всегда будет предварительно выделять блок памяти определенного размера реализации, это помешает намеченной работе reserve()не так ли?
• Каким будет преимущество предварительного выделения блока, если STL, естественно, не может знать предназначение и ожидаемый размер вектора? Это будет довольно бессмысленным, если не контрпродуктивным.
• Вместо этого правильным решением является выделение и реализация конкретного блока с первым push_back() — если это еще не было reserve(),
• В случае необходимости перераспределения увеличение размера блока также зависит от конкретной реализации. Знаменитости векторных реализаций, которые я знаю, начинаются с экспоненциального увеличения размера, но будут ограничивать скорость приращения на определенном максимуме, чтобы не тратить огромные объемы памяти и даже не уносить ее.

Все это доходит до полной работы и преимущества только в том случае, если не мешает конструктор выделения. У вас есть разумные значения по умолчанию для распространенных сценариев, которые могут быть изменены по требованию reserve() (а также shrink_to_fit()). Таким образом, даже если в стандарте прямо не указано иное, я вполне уверен, что вновь созданный вектор не выделяется заранее — это довольно надежная ставка для всех текущих реализаций.

Стандарт не определяет начальное значение для емкости, но контейнер STL автоматически увеличивается, чтобы вместить столько данных, сколько вы вводите, при условии, что вы не превышаете максимальный размер (используйте функцию-член max_size, чтобы узнать).
Для вектора и строки, рост обрабатывается realloc всякий раз, когда требуется больше места. Предположим, вы хотите создать вектор, содержащий значение 1-1000. Без использования резерва код обычно приводит к
2 и 18 перераспределения во время следующего цикла:

vector<int> v;
for ( int i = 1; i <= 1000; i++) v.push_back(i);

Изменение кода для использования резерва может привести к 0 выделениям во время цикла:

vector<int> v;
v.reserve(1000);

for ( int i = 1; i <= 1000; i++) v.push_back(i);

Грубо говоря, пропускная способность векторов и струн увеличивается каждый раз в 1,5-2 раза.