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

Question

I've got a two vectors in class A that contain other class objects B and C. I know exactly how many elements these vectors are supposed to hold at maximum. In the initializer list of class A's constructor, I initialize these vectors to their max sizes (constants).

If I understand this correctly, I now have a vector of objects of class B that have been initialized using their default constructor. Right? When I wrote this code, I thought this was the only way to deal with things. However, I've since learned about std::vector.reserve() and I'd like to achieve something different.

I'd like to allocate memory for these vectors to grow as large as possible because adding to them is controlled by user-input, so I don't want frequent resizings. However, I iterate through this vector many, many times per second and I only currently work on objects I've flagged as "active". To have to check a boolean member of class B/C on every iteration is silly. I don't want these objects to even BE there for my iterators to see when I run through this list.

Is reserving the max space ahead of time and using push_back to add a new object to the vector a solution to this?

Answer 1

Yes, reserve(n) will allocate space without actually putting elements there - increasing capacity() without increasing size().

BTW, if "adding to them is controlled by user-input" means that the user hits "insert X" and you insert X into the vector, you need not worry about the overhead of resizing. Waiting for user input is many times slower than the amortized constant resizing performance.

Answer 2

Your question is a little confusing, so let me try to answer what I think you asked.

Let's say you have a vector<B> which you default-construct. You then call vec.reserve(100). Now, vec contains 0 elements. It's empty. vec.empty() returns true and vec.size() returns 0. Every time you call push_back, you will insert one element, and unless vec conatins 100 elements, there will be no reallocation.

Answer 3

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.