Начальная емкость вектора в С++

Что такое capacity() для std::vector, который создается с помощью стандартного constuctor? Я знаю, что size() равно нулю. Можем ли мы заявить, что построенный по умолчанию вектор не вызывает выделение памяти кучи?

Таким образом, можно создать массив с произвольным резервом, используя одно выделение, например std::vector<int> iv; iv.reserve(2345);. Скажем, что по какой-то причине я не хочу запускать size() на 2345.

Например, в Linux (g++ 4.4.5, ядро 2.6.32 amd64)

#include <iostream>
#include <vector>

int main()
{
  using namespace std;
  cout << vector<int>().capacity() << "," << vector<int>(10).capacity() << endl;
  return 0;
}

напечатан 0,10. Это правило, или это зависит от поставщика STL?

Ответ 1

В стандарте не указывается, какой должен быть начальный capacity контейнера, поэтому вы полагаетесь на реализацию. Общая реализация начнет пропускную способность на ноль, но нет никакой гарантии. С другой стороны, нет способа улучшить вашу стратегию std::vector<int> iv; iv.reserve(2345);, поэтому придерживайтесь ее.

Ответ 2

Реализации хранилища 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;
}

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

под GCC 5.1 и:

в MSVC 2013.

Ответ 3

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

В частности, если _ITERATOR_DEBUG_LEVEL! = 0, тогда вектор выделит некоторое пространство для помощи при проверке итератора.

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

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

Ответ 4

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

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

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

Так что все вместе:

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

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

Ответ 5

Стандарт не определяет начальное значение емкости, но контейнер 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 раз.