Пространственная сложность std :: vector после вызова Reserve ()

Question

Я пытаюсь понять, как пространственная сложность std :: vector развивается после вызова функции Reserve ().

Вот код:

vector<SparseData<T_Indices, T_Values>> v1 = vector<SparseData<T_Indices, T_Values>>();
v1.reserve(341);
vector<SparseData<T_Indices, T_Values>> v2 = vector<SparseData<T_Indices, T_Values>>();
v2.reserve(342);

С SparseDataсодержит 3 целых числа (4 байта каждое).

v1 стоимость - теоретическая стоимость O(v1) = 341*3*4 = 4092 Bytes.Отлично.

Моя проблема - стоимость v2.Я ожидал O(v2) = 342*3*4 = 4104 Bytes, но фактическая стоимость 4151 Bytes.Существует дельта 47 Bytes, которую я не могу понять.

Я измеряю пространство с помощью средств диагностики сообщества Visual Studio 2017 (куча моментальных снимков), которые, я считаю, являются надежными.

Чтосмысл этих 47 Bytes?Что они, возможно, представляют?

Заранее спасибо.

Редактировать: Я отредактировал первоначальный пост, чтобы имена классов соответствовали скриншотам.Ниже приведены измеренные значения для v1 (соответственно v2) после вызова резерва (341) (соответственно резерва (342)).Обратите внимание, что два элемента не имеют одинаковые «значения», чем другие.Кроме того, v2 содержит 345 SparseData элементов, давая объяснение для первого 4140 Bytes: отлично, это или больше часть из документации :

Если n больше текущей векторной емкости, функция заставляет контейнер перераспределять свое хранилище, увеличивая его емкость до n (или больше).

По-прежнему ищем 11 Bytes delta tho.

Answer 1

На основании вашего последующего эксперимента

v2.reserve(342) = 4151 
v2.reserve(343) = 4163

4163 - 4151 = 12, что = 4 * 3, что является ожидаемым увеличением без дополнительных затрат.

Разница между использованием двух памятиуровни 12 байт.Следовательно, 47 байтов могут быть просто служебными данными, которые компилятор использует для отслеживания других деталей, связанных с вектором.

Может быть, что Reserve () выделяет определенный объем памяти и что фактическое добавление элементов создастшаг-функция увеличения использования памяти.

В любом случае, резерв () должен быть установлен на уровне, который вы не должны превышать.Поскольку вектор увеличивается в размере, среда выполнения должна перераспределить память и скопировать старый вектор в новое пространство памяти.Следовательно, как я уверен, вы уже знаете, резерв () не должен вызываться постепенно.

Было бы интересно увидеть график вызовов резерва (n) от 1 до 1000 с использованием памяти по сравнению сдобавление 1000 элементов с количеством использованной памяти после каждого добавления.

Answer 2

Есть несколько вещей, которые могут происходить

1. std::vector::reserve разрешено перераспределять пространство.Это потому, что распределителю разрешено перераспределять пространство.Так что вы можете видеть только то, что выделяет распределитель MSVC, когда вы запрашиваете 4014 байта.

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

3. комбинация 1 и 2.