Initial Capacity of Vector in C++

Initial capacity of vector in C++

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.

C++ Vector initial capacity

The capacity of a vector cannot be controlled by the constructors - there is no applicable overload.

The C++ standard doesn't give any guarantee about the capacity of a default-constructed vector vector<Foo> bar;. However all well-known implementations use 0 as the default capacity. This is something you can rely on, as allocating memory at that point just doesn't make sense.

So I believe the answer to your question is: just use

vector<Foo> bar;
bar.reserve(4);

How to set initial size of std::vector?

std::vector<CustomClass *> whatever(20000);

or:

std::vector<CustomClass *> whatever;
whatever.reserve(20000);

The former sets the actual size of the array -- i.e., makes it a vector of 20000 pointers. The latter leaves the vector empty, but reserves space for 20000 pointers, so you can insert (up to) that many without it having to reallocate.

At least in my experience, it's fairly unusual for either of these to make a huge difference in performance--but either can affect correctness under some circumstances. In particular, as long as no reallocation takes place, iterators into the vector are guaranteed to remain valid, and once you've set the size/reserved space, you're guaranteed there won't be any reallocations as long as you don't increase the size beyond that.

Set both elements and initial capacity of std::vector

It's not clear how you want all the elements constructed. Let's say you want the vector to have n elements and capacity desired_capacity, which may be equal to n.

If you want n elements identical, try this:

std::vector<T> v(n, t);  // creates n copies of the value t.
v.reserve(desired_capacity);

If you don't want to specify an initial value, you can omit that:

std::vector<T> v(n);     // creates n copies of T, default constructed.
v.reserve(desired_capacity);

If you have a certain number of elements you want to specify individually, try an initializer list.

std::vector({t1, t2, ..., tn});  // initializer list
v.reserve(desired_capacity);

The list of possibilities goes on; for more, see the vector::vector reference. Using "in-place" construction means you can populate a vector with types that are not copy-constructible.

Another option, to fill a vector with non-copyable types, is to use emplace_back repeatedly:

std::vector<T> v;
v.reserve(n); 
for (int i = 0; i < n; ++i)
{
   v.emplace_back(x, y, z);  // Construct T(x, y, z) in-place
}

One note about your original question: your for loop contains an error:

for(T t : v) t = T();    
// almost certainly want for (T& t : v) ...
// in order to get references to modify vector elements.

Initializing the size of a C++ vector

There are a few ways of creating a vector with n elements and I will even show some ways of populating a vector when you don't know the number of elements in advance.

But first

what NOT to do

std::vector<Entry> phone_book;
for (std::size_t i = 0; i < n; ++i)
{
    phone_book[i] = entry; // <-- !! Undefined Behaviour !!
}

The default constructed vector, as in the example above creates an empty vector. Accessing elements outside of the range of the vector is Undefined Behavior. And don't expect to get a nice exception. Undefined behavior means anything can happen: the program might crash or might seem to work or might work in a wonky way. Please note that using reserve doesn't change the actual size of the vector, i.e. you can't access elements outside of the size of the vector, even if you reserved for them.

And now some options analyzed

default ctor + `push_back` (suboptimal)

std::vector<Entry> phone_book;
for (std::size_t i = 0; i < n; ++i)
{
    phone_book.push_back(entry);
}

This has the disadvantage that reallocations will occur as you push back elements. This means memory allocation, elements move (or copy if they are non-movable, or for pre c++11) and memory deallocation (with object destruction). This will most likely happen more than once for an n decently big. It is worth noting that it is guaranteed "amortized constant" for push_back which means that it won't do reallocations after each push_back. Each reallocation will increase the size geometrically. Further read: std::vector and std::string reallocation strategy

Use this when you don't know the size in advance and you don't even have an estimate for the size.

"count default-inserted instances of T" ctor with later assignments (not recommended)

std::vector<Entry> phone_book(n);
for (auto& elem : phone_book)
{
    elem = entry;
}

This does not incur any reallocation, but all n elements will be initially default constructed, and then copied for each push. This is a big disadvantage and the effect on the performance will most likely be measurable. (this is less noticeable for basic types).

Don't use this as there are better alternatives for pretty much every scenario.

"count copies of elements" ctor (recommended)

std::vector<Entry> phone_book(n, entry);

This is the best method to use. As you provide all the information needed in the constructor, it will make the most efficient allocation + assignment. This has the potential to result in branchless code, with vectorized instructions for assignments if Entry has a trivial copy constructor.

default ctor + `reserve` + `push_back` (situational recommended)

vector<Entry> phone_book;
phone_book.reserve(m);

while (some_condition)
{
     phone_book.push_back(entry);
}

// optional
phone_book.shrink_to_fit();

No reallocation will occur and the objects will be constructed only once until you exceed the reserved capacity. A better choice for push_back can be emplace_back.

Use this If you have a rough approximation of the size.

There is no magical formula for the reserve value. Test with different values for your particular scenarios to get the best performance for your application. At the end you can use shrink_to_fit.

default ctor + `std::fill_n` and `std::back_inserter` (situational recommended)

#include <algorithm>
#include <iterator>

std::vector<Entry> phone_book;

// at a later time
// phone_book could be non-empty at this time
std::fill_n(std::back_inserter(phone_book), n, entry);

Use this if you need to fill or add elements to the vector after its creation.

default ctor + `std::generate_n` and `std::back_inserter` (for different `entry` objects)

Entry entry_generator();

std::vector<Entry> phone_book;
std::generate_n(std::back_inserter(phone_book), n, [] { return entry_generator(); });

You can use this if every entry is different and obtained from a generator

Intializer list (Bonus)

Since this has become such a big answer, beyond of what the question asked, I will be remised if I didn't mention the initializer list constructor:

std::vector<Entry> phone_book{entry0, entry1, entry2, entry3};

In most scenarios this should be the default go-to constructor when you have a small list of initial values for populating the vector.

Some resources:

std::vector::vector (constructor)

std::vector::insert

standard algorithm library (with std::generate std::generate_n std::fill std::fill_n etc.)

std::back_inserter

Does declaring a vector with size offer any improvements over using push_back in C++

With

vector<int> Array(n);

you create a vector that contains n elements, all memory needed for those elements is allocated immediately.

When you use e.g.

Array.push_back(value);

then the vector needs to be resized, which could mean the memory have to be reallocated and all the contents have to be copied to the new memory.

Instead of creating an array with a set size, you could instead preallocate (or reserve) memory:

vector<int> Array;  // An empty vector
Array.reserve(n);   // Reserve memory, but keep the size as zero (it's still empty)
Array.push_back(value);  // No reallocation needed, size is now one

This is useful when you have a vector of objects that can't be default-constructed.

Important concepts to learn: The vector size and its capacity and what the difference between them is.

The capacity is the number of elements the vector have allocated memory for.

The size is the current number of elements in the vector.

It's quite common for the capacity to be different from the size. And it must always be true that capacity >= size.

Vector: initialization or reserve?

Both variants have different semantics, i.e. you are comparing apples and oranges.

The first gives you a vector of n default-initialized values, the second variant reserves the memory, but does not initialize them.

Choose what better fits your needs, i.e. what is "better" in a certain situation.

Is std::vector X(0) guaranteed not to allocate?

That constructor calls explicit vector( size_type count ) which does:

Constructs the container with count default-inserted instances of T.
No copies are made.

The only guarantee you get is that the vector will be empty, its size() will be 0. Implementations are allowed to allocate whatever they want for book keeping or whatever on initialization.

So if your question is if you can count on X taking up 0 bytes of free store space then the answer is no.

Initial Capacity of Vector in C++