ChatGPT解决这个技术问题 Extra ChatGPT

Initial capacity of vector in C++

What is the capacity() of an std::vector which is created using the default constuctor? I know that the size() is zero. Can we state that a default constructed vector does not call heap memory allocation?

This way it would be possible to create an array with an arbitrary reserve using a single allocation, like std::vector<int> iv; iv.reserve(2345);. Let's say that for some reason, I do not want to start the size() on 2345.

For example, on Linux (g++ 4.4.5, kernel 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. Is it a rule, or is it STL vendor dependent?

Standard doesn't specifies anything about initial capacity of vector but most implementations use 0 .
There's no guarantee, but I would seriously question the quality of any implementation that allocated memory without me requesting any.
@MikeSeymour Disagree. A really high performance implementation might contain a small inline buffer, in which case setting the initial capacity() to that would make sense.
@alastair When using swap all iterators and references remain valid (except end()s). That means that an inline buffer is not possible.

M
Mark Ransom

The standard doesn't specify what the initial capacity of a container should be, so you're relying on the implementation. A common implementation will start the capacity at zero, but there's no guarantee. On the other hand there's no way to better your strategy of std::vector<int> iv; iv.reserve(2345); so stick with it.


I don't buy your last statement. If you cannot rely on the capacity to be 0 initially, you might restructure your program to allow your vector to have an initial size. This would half the number of heap-memory requests (from 2 to 1).
@bitmask: Being practical: do you know of any implementation where a vector allocating memory in the default constructor? It is not guaranteed by the standard, but as Mike Seymour points out triggering an allocation without the need would be a bad smell regarding the quality of implementation.
@DavidRodríguez-dribeas: That's not the point. The premise was "you cannot do better than your current strategy, so do not bother wondering if there might be stupid implementations". If the premise was "there are no such implementations, so don't bother" I would buy it. The conclusion happens to be true, but the implication doesn't work. Sorry, maybe I'm nit picking.
@bitmask If there exists an implementation that allocates memory on default construction, doing what you said would halve the number of allocations. But vector::reserve is not the same as specifying an initial size. The vector constructors that take an initial size value/copy initialize n objects, and thus have linear complexity. OTOH, calling reserve only means copying / moving of size() elements if a reallocation is triggered. On an empty vector there is nothing to copy. So the latter might be desirable even if the implementation allocates memory for a default constructed vector.
@bitmask, if you're concerned about the allocations to this degree then you should look at your particular standard library's implementation and not rely on speculation.
Z
Zitrax

Storage implementations of std::vector vary significantly, but all the ones I've come across start from 0.

The following code:

#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;
}

Gives the following output:

0
1
2
4
4
8
8
8
8
16
16

under GCC 5.1, 11.2 - Clang 12.0.1 and:

0
1
2
3
4
6
6
9
9
9
13

under MSVC 2013.


This is so underrated @Andrew
Well you find virtually everywhere that the recommendation for speed purposes is almost always to just use a vector, so if you're doing anything that involves sparse data...
@Andrew what should they have started it at? allocating anything would just be wasting time allocating and deallocating that memory if the programmer wants to reserve more than the default. if you're assuming they should begin with 1, it'll allocate that as soon as somebody is allocating 1 anyway.
@Puddle You're reading in between the lines instead of taking it at face value. The clue that it's not sarcasm is the word "smart", as well as my second comment mentioning sparse data.
@Andrew Oh good, you were relieved enough they started it at 0. Why even comment about it in a joking way?
D
Don Pedro

As far as I understood the standard (though I could actually not name a reference), container instanciation and memory allocation have intentionally been decoupled for good reason. Therefor you have distinct, separate calls for

constructor to create the container itself

reserve() to pre allocate a suitably large memory block to accomodate at least(!) a given number of objects

And this makes a lot of sense. The only right to exist for reserve() is to give you the opportunity to code around possibly expensive reallocations when growing the vector. In order to be useful you have to know the number of objects to store or at least need to be able to make an educated guess. If this is not given you better stay away from reserve() as you will just change reallocation for wasted memory.

So putting it all together:

The standard intentionally does not specify a constructor that allows you to pre allocate a memory block for a specific number of objects (which would be at least more desirable than allocating an implementation specific, fixed "something" under the hood).

Allocation shouldn't be implicit. So, to preallocate a block you need to make a separate call to reserve() and this need not be at the same place of construction (could/should of course be later, after you became aware of the required size to accomodate)

Thus if a vector would always preallocate a memory block of implementation defined size this would foil the intended job of reserve(), wouldn't it?

What would be the advantage of preallocating a block if the STL naturally cannot know the intended purpose and expected size of a vector? It'll be rather nonsensical, if not counter-productive.

The proper solution instead is to allocate and implementation specific block with the first push_back() - if not already explicitely allocated before by reserve().

In case of a necessary reallocation the increase in block size is implementation specific as well. The vector implementations I know of start with an exponential increase in size but will cap the increment rate at a certain maximum to avoid wasting huge amounts of memory or even blowing it.

All this comes to full operation and advantage only if not disturbed by an allocating constructor. You have reasonable defaults for common scenarios that can be overriden on demand by reserve() (and shrink_to_fit()). So, even if the standard does not explicitely state so, I'm quite sure assuming that a newly constructed vector does not preallocate is a pretty safe bet for all current implementations.


D
David Woo

As a slight addition to the other answers, I found that when running under debug conditions with Visual Studio a default constructed vector will still allocate on the heap even though the capacity starts at zero.

Specifically if _ITERATOR_DEBUG_LEVEL != 0 then vector will allocate some space to help with iterator checking.

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

I just found this slightly annoying since I was using a custom allocator at the time and was not expecting the extra allocation.


Interesting, they break the noexcept-guarantees (at least for C+17, earlier?): en.cppreference.com/w/cpp/container/vector/vector
W
WhiZTiM

This is an old question, and all answers here have rightly explained the standard's point of view and the way you can get an initial capacity in a portable manner by using std::vector::reserve;

However, I'll explain why it doesn't make sense for any STL implementation to allocate memory upon construction of an std::vector<T> object;

std::vector of incomplete types; Prior to C++17, it was undefined behavior to construct a std::vector if the definition of T is still unknown at point of instantiation. However, that constraint was relaxed in C++17. In order to efficiently allocate memory for an object, you need to know its size. From C++17 and beyond, your clients may have cases where your std::vector class does not know the size of T. Does it makes sense to have memory allocation characteristics dependent on type completeness? Unwanted Memory allocations There are many, many, many times you'll need model a graph in software. (A tree is a graph); You are most likely going to model it like: class Node { .... std::vector children; //or std::vector< *some pointer type* > children; .... }; Now think for a moment and imagine if you had lots of terminal nodes. You would be very pissed if your STL implementation allocates extra memory simply in anticipation of having objects in children. This is just one example, feel free to think of more...


A
Archie Yalakki

Standard doesnt specify initial value for capacity but the STL container automatically grows to accomodate as much data as you put in, provided you don't exceed the maximum size(use max_size member function to know). For vector and string, growth is handled by realloc whenever more space is needed. Suppose you'd like to create a vector holding value 1-1000. Without using reserve, the code will typically result in between 2 and 18 reallocations during following loop:

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

Modifying the code to use reserve might result in 0 allocations during the loop:

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

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

Roughly to say, vector and string capacities grow by a factor of between 1.5 and 2 each time.