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

Что из capacity()того, std::vectorчто создается с использованием конструктора по умолчанию? Я знаю, что 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?

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

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

  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.

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

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

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

Итак, сложим все вместе:

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

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

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

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

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

Меня это просто немного раздражало, поскольку в то время я использовал специальный распределитель и не ожидал дополнительного выделения.

Это старый вопрос, и все ответы здесь правильно объясняют точку зрения стандарта и способ получения начальной емкости переносимым способом, используя std::vector::reserve;

Однако я объясню, почему для какой-либо реализации STL не имеет смысла выделять память при создании std::vector<T>объекта ;

1. std::vector<T> неполных типов;

   До C ++ 17 было неопределенным поведением конструировать, std::vector<T>если определение Tвсе еще неизвестно в точке создания. Однако в C ++ 17 это ограничение было ослаблено .

   Чтобы эффективно выделить память для объекта, вам нужно знать его размер. Начиная с C ++ 17 и выше, у ваших клиентов могут быть случаи, когда ваш std::vector<T>класс не знает размер T. Имеет ли смысл иметь характеристики распределения памяти в зависимости от полноты типа?

2. Unwanted Memory allocations

   Много, много, много раз вам понадобится смоделировать график в программном обеспечении. (Дерево - это граф); Скорее всего, вы собираетесь моделировать это так:

   class Node {
       ....
       std::vector<Node> children; //or std::vector< *some pointer type* > children;
       ....
    };
   

   Теперь подумайте на мгновение и представьте, если бы у вас было много терминальных узлов. Вы были бы очень разозлены, если бы ваша реализация STL выделяла дополнительную память просто в ожидании наличия объектов children.

   Это всего лишь один пример, не стесняйтесь думать о большем ...

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