Начальная емкость вектора в 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;

}


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

807   5  

5 ответов:

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

48  
2012-09-04 23:44:55

реализации хранения 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.

17  
2016-04-02 11:34:46

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

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

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

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

2  
2018-03-01 12:44:05

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

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

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

Итак, собирая все это вместе:

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

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

2  
2018-04-19 11:34:59

стандарт не указывает начальное значение для емкости, но контейнер STL автоматически растет, чтобы вместить столько данных, сколько вы вставляете, при условии, что вы не превышаете максимальный размер(используйте функцию-член max_size, чтобы знать). Для вектора и строки рост обрабатывается realloc всякий раз, когда требуется больше места. Предположим, вы хотите создать вектор, содержащий значение 1-1000. Без использования reserve код обычно приводит к промежуточным результатам 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 раза каждый раз.

0  
2018-03-01 13:20:55

Comments

    Ничего не найдено.
Click here to cancel reply.