What Is the Overhead Cost of an Empty Vector

std::vectorstd::vectorT vs std::vectorT*

It's actually 4, you missed the allocator. See What is the overhead cost of an empty vector?

Depends on your application.
Do you never append to the internal vectors?
Do they all have the same number of elements?
Is the average size of the data stored in the internal vectors small?

If you answered yes to all the questions above than maybe T* is an acceptable solution.
If not think about how would you handle that issue without the support of vector. It might be easier to just take the hit on memory.

What is a truly empty std::vector in C++?

A vector has capacity and it has size. The capacity is the number of elements for which memory has been allocated. Size is the number of elements which are actually in the vector. A vector is empty when its size is 0. So, size() returns 0 and empty() returns true. That says nothing about the capacity of the vector at that point (that would depend on things like the number of insertions and erasures that have been done to the vector since it was created). capacity() will tell you the current capacity - that is the number of elements that the vector can hold before it will have to reallocate its internal storage in order to hold more.

So, when you construct a vector, it has a certain size and a certain capacity. A default-constructed vector will have a size of zero and an implementation-defined capacity. You can insert elements into the vector freely without worrying about whether the vector is large enough - up to max_size() - max_size() being the maximum capacity/size that a vector can have on that system (typically large enough not to worry about). Each time that you insert an item into the vector, if it has sufficient capacity, then no memory-allocation is going to be allocated to the vector. However, if inserting that element would exceed the capacity of the vector, then the vector's memory is internally re-allocated so that it has enough capacity to hold the new element as well as an implementation-defined number of new elements (typically, the vector will probably double in capacity) and that element is inserted into the vector. This happens without you having to worry about increasing the vector's capacity. And it happens in constant amortized time, so you don't generally need to worry about it being a performance problem.

If you do find that you're adding to a vector often enough that many reallocations occur, and it's a performance problem, then you can call reserve() which will set the capacity to at least the given value. Typically, you'd do this when you have a very good idea of how many elements your vector is likely to hold. However, unless you know that it's going to a performance issue, then it's probably a bad idea. It's just going to complicate your code. And constant amortized time will generally be good enough to avoid performance issues.

You can also construct a vector with a given number of default-constructed elements as you mentioned, but unless you really want those elements, then that would be a bad idea. vector is supposed to make it so that you don't have to worry about reallocating the container when you insert elements into it (like you would have to with an array), and default-constructing elements in it for the purposes of allocating memory is defeating that. If you really want to do that, use reserve(). But again, don't bother with reserve() unless you're certain that it's going to improve performance. And as was pointed out in another answer, if you're inserting elements into the vector based on user input, then odds are that the time cost of the I/O will far exceed the time cost in reallocating memory for the vector on those relatively rare occasions when it runs out of capacity.

Capacity-related functions:

capacity()  // Returns the number of elements that the vector can hold
reserve()   // Sets the minimum capacity of the vector.

Size-related functions:

clear()  // Removes all elements from the vector.
empty()  // Returns true if the vector has no elements.
resize() // Changes the size of the vector.
size()  // Returns the number of items in the vector.

Overhead of std::optionalT?

-> and * ought to have zero overhead.

value and value_or ought to have the overhead of one branch: if(active)
Also, copy/move constructor, copy/move assignment, swap, emplace, operator==, operator<, and the destructor ought to also have the overhead of one branch.

However, one banch of overhead is so small it probably can't even be measured. Seriously, write pretty code, and don't worry about the performance here. Odds are making the code pretty will result in it running faster than if you tried to make it fast. Counter-intuitive, but do it anyway.

There are definitely cases where the overhead becomes noticible, for instance sorting a large number of optionals. In these cases, there's four situations,

(A) all the optionals known to be empty ahead of time, in which case, why sort?

(B) Some optionals may or may not be active, in which case the overhead is required and there is no better way.

(C) All optionals are known to have values ahead of time and you don't need the sorted-data in place, in which case, use the zero overhead operators to make a copy of the data where the copy is using the raw type instead of optional, and sort that.

(D) All optionals are known to have values ahead of time, but you need the sorted data in-place. In this case, optional is adding unnecessary overhead, and the easiest way to work around it is to do step C, and then use the no-overhead operators to move the data back.

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.

vector::clear() cost so much time?

It depends on what is in your vector, if your nested vectors contain classes then you will be invoking the d'tor for each instance in the nested vectors. I'm quite sure it will also be deallocating memory.

It sounds like you are writing a game? If so a few books (PDFs) I've read on game writing suggest that vector is good for general use but you will be better off NOT using it for games. Just use native arrays and manage the memory yourself or roll your own container class.

Is 640 the upper-bound of your vector? Would you be better of perhaps using something like this?

sometype Values[20][640];
int size[20];

Then your reset call could just be

for(int i=0; i<20; i++) size[0] = 0;

You will still even be able to use any stl functions like this:

std::sort(Values[i], Values[i] + size[i]);

That's about as much help as I can provide without any more information

Is std::vector so much slower than plain arrays?

Using the following:

g++ -O3 Time.cpp -I <MyBoost>

./a.out

UseArray completed in 2.196 seconds

UseVector completed in 4.412 seconds

UseVectorPushBack completed in 8.017 seconds

The whole thing completed in 14.626 seconds

So array is twice as quick as vector.

But after looking at the code in more detail this is expected; as you run across the vector twice and the array only once. Note: when you resize() the vector you are not only allocating the memory but also running through the vector and calling the constructor on each member.

Re-Arranging the code slightly so that the vector only initializes each object once:

 std::vector<Pixel>  pixels(dimensions * dimensions, Pixel(255,0,0));

Now doing the same timing again:

g++ -O3 Time.cpp -I <MyBoost>

./a.out

UseVector completed in 2.216 seconds

The vector now performance only slightly worse than the array. IMO this difference is insignificant and could be caused by a whole bunch of things not associated with the test.

I would also take into account that you are not correctly initializing/Destroying the Pixel object in the UseArrray() method as neither constructor/destructor is not called (this may not be an issue for this simple class but anything slightly more complex (ie with pointers or members with pointers) will cause problems.